Zero-knowledge Identification based on Lattices with Low Communication Costs

• Rosemberg Silva UNICAMP
• Pierre-Louis Cayrel Université de Saint-Etienne
• Richard Lindner Technische Universität Darmstadt

DOI: https://doi.org/10.5753/sbseg.2011.20566

Resumo

In this paper we propose a new 5-pass zero-knowledge identification scheme with soundness error close to 1/2. We use the hardness of the Inhomogeneous Small Integer Solution problem as security basis. Our protocol achieves lower communication costs compared with previous lattice-based zeroknowledge identification schemes. Besides, our construction allows smaller public and secret keys by applying the use of ideal lattices. We allow the prover to possess several pairs of secret and public keys, and choose randomly which pair is to be used in a given round of execution. We also dealt with nonces in zero-knowledge schemes in a new way, lowering the number of values exchanged between the prover and the verifier. Hence, our scheme has the good features of having a zero-knowledge security proof based on a well known hard problem of lattice theory, with worst to average-case reduction, and small size of secret and public keys.

Referências

Aguilar, C., Gaborit, P., and Shreck, J. (2011). A new zero-knowledge code-based identification and signature scheme with reduced communications. preprint.

Ajtai, M. (1996). Generating hard instances of lattice problems. Electronic Colloquium on Computational Complexity (ECCC), 3(7).

Ajtai, M. and Dwork, C. (1996). A public-key cryptosystem with worst-case/average-case equivalence. Electronic Colloquium on Computational Complexity (ECCC), 3(65).

Cayrel, P.-L., Lindner, R., Rückert, M., and Silva, R. (2010). Improved zero-knowledge identification with lattices. In Provable Security, volume 6402 of Lecture Notes in Computer Science, pages 1–17. Springer.

Fiat, A. and Shamir, A. (1986). How to prove yourself: Practical solutions to identification and signature problems. In Odlyzko, A. M., editor, CRYPTO, volume 263 of Lecture Notes in Computer Science, pages 186–194. Springer.

Gaborit, P. and Girault, M. (2007). Lightweight code-based identification and signature. IEEE Transactions on Information Theory (ISIT), pages 186–194.

Girault, M. (1990). A (non-practical) three-pass identification protocol using coding theory. In Seberry, J. and Pieprzyk, J., editors, AUSCRYPT, volume 453 of Lecture Notes in Computer Science, pages 265–272. Springer.

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, page 304. ACM.

Harari, S. (1988). A new authentication algorithm. In Cohen, G. D. and Wolfmann, J., editors, Coding Theory and Applications, volume 388 of Lecture Notes in Computer Science, pages 91–105. Springer.

Kawachi, A., Tanaka, K., and Xagawa, K. (2008). Concurrently secure identification schemes based on the worst-case hardness of lattice problems. In ASIACRYPT ’08: Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security, pages 372–389, Berlin, Heidelberg. SpringerVerlag.

Lyubashevsky, V. (2008). Lattice-based identification schemes secure under active attacks. In Cramer, R., editor, Public Key Cryptography, volume 4939 of Lecture Notes in Computer Science, pages 162–179. Springer.

Lyubashevsky, V. and Micciancio, D. (2006). Generalized compact knapsacks are collision resistant. In Bugliesi, M., Preneel, B., Sassone, V., and Wegener, I., editors, ICALP (2), volume 4052 of Lecture Notes in Computer Science, pages 144–155. Springer.

Lyubashevsky, V., Micciancio, D., Peikert, C., and Rosen, A. (2008). Swifft: A modest proposal for fft hashing. In Nyberg, K., editor, FSE, volume 5086 of Lecture Notes in Computer Science, pages 54–72. Springer.

Micciancio, D. (2007). Generalized compact knapsacks, cyclic lattices, and efficient oneway functions. In Computational Complexity. Springer.

Micciancio, D. and Goldwasser, S. (2002). Complexity of Lattice Problems: a cryptographic perspective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, Massachusetts.

Shor, P. W. (1994). Polynominal time algorithms for discrete logarithms and factoring on a quantum computer. In Adleman, L. M. and Huang, M.-D. A., editors, ANTS, volume 877 of Lecture Notes in Computer Science, page 289. Springer.

Stern, J. (1993). A new identification scheme based on syndrome decoding. In Stinson, D. R., editor, CRYPTO, volume 773 of Lecture Notes in Computer Science, pages 13– 21. Springer.

Véron, P. (1995). Cryptanalysis of harari’s identification scheme. In Boyd, C., editor, IMA Conf., volume 1025 of Lecture Notes in Computer Science, pages 264–269. Springer.

Véron, P. (1996). Improved identification schemes based on error-correcting codes. Appl. Algebra Eng. Commun. Comput., 8(1):57–69.

Wagner, D. (2002). A generalized birthday problem. In Yung, M., editor, CRYPTO, volume 2442 of Lecture Notes in Computer Science, pages 288–303. Springer.