A Zero-Knowledge Proof for the Hidden Subset Sum Problem
Abstract
In this paper, we propose a zero-knowledge proof for a special case of the hidden subset sum problem. This problem was presented by [Boyko et al. 1998] as the underlying problem of methods for generating random pairs of the form (x, gx (mod p)) using precomputations. The proof we propose is an adaptation of a zero-knowledge protocol for the subset sum problem presented by [Blocki 2009].
References
Blocki, J. (2009). Direct zero-knowledge proofs. Senior Research Thesis, B.S. in Computer Science, Carnegie Mellon University.
Boyko, V., Peinado, M., and Venkatesan, R. (1998). Speeding up discrete log and factoring based schemes via precomputations. In Advances in Cryptology - Eurocrypt ’98, volume 1403 of Lecture Notes in Computer Science, pages 221–235.
Chor, B. and Rivest, R. L. (1988). A knapsack-type public key cryptosystem based on arithmetic in finite fields. IEEE Transactions on Information Theory, 34(5):901–909.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2001). Introduction to Algorithms. MIT Press and McGraw-Hill, 2nd edition.
Coster, M. J., Joux, A., LaMacchia, B. A., Odlyzko, A. M., Schnorr, C.-P., and Stern, J. (1992). Improved low-density subset sum algorithms. Computational Complexity, 2(2):111–128.
El Gamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. In Proceedings of CRYPTO 84 on Advances in Cryptology, pages 10–18, New York, NY, USA. Springer-Verlag New York, Inc.
Goldwasser, S., Micali, S., and Rackoff, C. (1985). The knowledge complexity of interactive proof-systems. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC ’85, pages 291–304, New York, NY, USA. ACM.
Lagarias, J. C. and Odlyzko, A. M. (1985). Solving low-density subset sum problems. J. Assoc. Comp. Mach., 32(1):229–246.
Lenstra, A. K., Lenstra Jr, H. W., and Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534.
Merkle, R. C. and Hellman, M. E. (1978). Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 24:525–534.
Nguyen, P. and Stern, J. (1999). The Hardness of the Hidden Subset Sum Problem and Its Cryptographic Implications, pages 31–46. Springer Berlin Heidelberg, Berlin, Heidelberg. NIST (1994). FIPS publication 186: Digital signature standard.
Quisquater, Jean-Jacques, G. L. C. and Berson, T. A. (1990). How to explain zeroknowledge protocols to your children. In Advances in Cryptology, CRYPTO ’89: Proceedings, pages 628–631. ACM.
Schnorr, C. P. (1994). Block reduced lattice bases and successive minima. Combinatorics, Probability and Computing, 3:507–522.
T. Okamoto, K. T. and Uchiyama, S. (2000). Quantum public-key cryptosystems. In Advances in Cryptology: Proceedings of CRYPTO 2000 (M. Bellare, ed.), Lecture Notes in Computer Science, pages 147–165, New York. Springer-Verlag.
Boyko, V., Peinado, M., and Venkatesan, R. (1998). Speeding up discrete log and factoring based schemes via precomputations. In Advances in Cryptology - Eurocrypt ’98, volume 1403 of Lecture Notes in Computer Science, pages 221–235.
Chor, B. and Rivest, R. L. (1988). A knapsack-type public key cryptosystem based on arithmetic in finite fields. IEEE Transactions on Information Theory, 34(5):901–909.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2001). Introduction to Algorithms. MIT Press and McGraw-Hill, 2nd edition.
Coster, M. J., Joux, A., LaMacchia, B. A., Odlyzko, A. M., Schnorr, C.-P., and Stern, J. (1992). Improved low-density subset sum algorithms. Computational Complexity, 2(2):111–128.
El Gamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. In Proceedings of CRYPTO 84 on Advances in Cryptology, pages 10–18, New York, NY, USA. Springer-Verlag New York, Inc.
Goldwasser, S., Micali, S., and Rackoff, C. (1985). The knowledge complexity of interactive proof-systems. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC ’85, pages 291–304, New York, NY, USA. ACM.
Lagarias, J. C. and Odlyzko, A. M. (1985). Solving low-density subset sum problems. J. Assoc. Comp. Mach., 32(1):229–246.
Lenstra, A. K., Lenstra Jr, H. W., and Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534.
Merkle, R. C. and Hellman, M. E. (1978). Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 24:525–534.
Nguyen, P. and Stern, J. (1999). The Hardness of the Hidden Subset Sum Problem and Its Cryptographic Implications, pages 31–46. Springer Berlin Heidelberg, Berlin, Heidelberg. NIST (1994). FIPS publication 186: Digital signature standard.
Quisquater, Jean-Jacques, G. L. C. and Berson, T. A. (1990). How to explain zeroknowledge protocols to your children. In Advances in Cryptology, CRYPTO ’89: Proceedings, pages 628–631. ACM.
Schnorr, C. P. (1994). Block reduced lattice bases and successive minima. Combinatorics, Probability and Computing, 3:507–522.
T. Okamoto, K. T. and Uchiyama, S. (2000). Quantum public-key cryptosystems. In Advances in Cryptology: Proceedings of CRYPTO 2000 (M. Bellare, ed.), Lecture Notes in Computer Science, pages 147–165, New York. Springer-Verlag.
Published
2017-11-06
How to Cite
BARROS, Charles F. de.
A Zero-Knowledge Proof for the Hidden Subset Sum Problem. In: BRAZILIAN SYMPOSIUM ON INFORMATION AND COMPUTATIONAL SYSTEMS SECURITY (SBSEG), 17. , 2017, Brasília.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 16-27.
DOI: https://doi.org/10.5753/sbseg.2017.19487.
