Improved Zero-Knowledge Identification with Lattices

Cayrel, Pierre-Louis; Lindner, Richard; Rückert, Markus; Silva, Rosemberg

doi:10.2478/v10127-012-0038-4

Abstract

Zero-knowledge identification schemes solve the problem of authenticating one party to another via an insecure channel without disclosing any additional information that might be used by an impersonator. In this paper we propose a scheme whose security relies on the existence of a commitment scheme and on the hardness of worst-case lattice problems. We adapt a code- -based identification scheme devised by Cayrel, V´eron and El Yousfi, which constitutes an improvement of Stern’s construction. Our solution sports analogous improvements over the lattice adaption of Stern’s scheme which Kawachi et al. presented at ASIACRYPT ’08. Specifically, due to a smaller cheating probability close to 1/2 and a similar communication cost, any desired level of security will be achieved in fewer rounds. Compared to Lyubashevsky’s scheme presented at ASIACRYPT ’09, our proposal, like Kawachi’s, offers a much milder security assumption: namely, the hardness of SIS for trinary solutions. The same assumption was used for the SWIFFT hash function, which is secure for much smaller parameters than those proposed by Lyubashevsky.

References

[1] ABDALLA, M.-AN, J. H.-BELLARE, M.-NAMPREMPRE, CH.: From identification to signatures via the Fiat-Shamir transform: Minimizing assumptions for security and forward-security, in: Advances in Cryptology-EUROCRYPT ’02, 21st Internat. Conf. on the Theory and Appl. of Cryptographic Techniques (L. Knudsen, ed.), Amsterdam, 2002, Lecture Notes in Comput. Sci., Vol. 2332, Springer, Berlin, 2002, pp. 418-433.
Search in Google Scholar
[2] MELCHOR, C. A.-CAYREL, P.-L.-GABORIT, P.: A new efficient threshold ring signature scheme based on coding theory, in: Post-Quantum Cryptography, 2nd Internat. Workshop-PQCrypto ’08, Cincinnati, OH, USA, 2008 (J. Buchmann et al., eds.), Lecture Notes in Comput. Sci., Vol. 5299, Springer, Berlin, 2008, pp. 1-16.
Search in Google Scholar
[3] AJTAI, M.: Generating hard instances of lattice problems, Electronic Colloquium on Computational Complexity (ECCC) 3 (1996).10.1145/237814.237838
Search in Google Scholar
[4] AJTAI, M.-DWORK, C.: A public-key cryptosystem with worst-case/average-case equivalence, Electronic Colloquium on Computational Complexity (ECCC) 3 (1996).10.1145/258533.258604
Search in Google Scholar
[5] BELLARE, M.-PALACIO, A.: GQ and Schnorr identification schemes: proofs of security against impersonation under active and concurrent attacks, in: Advances in Cryptology-CRYPTO ’02, 22nd Annual Internat. Cryptology Conf., Santa Barbara, CA, USA, 2002 (M. Yung, ed.), Lecture Notes in Comput. Sci., Vol. 2442, Springer, Berlin, 2002, pp. 162-177.
Search in Google Scholar
[6] BERNSTEIN, D. J.-BUCHMANN, J.-DAHMEN, E.: Post Quantum Cryptography. Springer Publishing Company, Incorporated, 2008.10.1007/978-3-540-88702-7
Search in Google Scholar
[7] BERNSTEIN, D. J.-LANGE, T.-PETERS, CH.: Attacking and defending the McEliece cryptosystem, in: Post-Quantum Cryptography-PQCrypto ’08 (J. Buchmann and J. Ding, eds.), Lecture Notes in Comput. Sci., Vol. 5299, Springer, Berlin, 2008, pp. 31-46.
Search in Google Scholar
[8] BUCHMANN, J.-DING, J., EDS.: Post-Quantum Cryptography, in: 2nd Internat. Workshop-PQCrypto ’08, Cincinnati, OH, USA, 2008, Lecture Notes in Comput. Sci., Vol. 5299, Springer, Berlin, 2008.
Search in Google Scholar
[9] CAYREL, P.-L.-LINDNER, R.-RÜCKERT, M.-SILVA, R.: Improved zero-knowledgeidentification with lattices, in: Provable Security, 4th Internat. Conf.-ProvSec ’10, Malacca, Malaysia, 2010 (S. H. Heng et al., eds.), Lecture Notes in Comput. Sci., Vol. 6402, Springer, Berlin, 2010, pp. 1-17.
Search in Google Scholar
[10] CAYREL, P.-L.-LINDNER, R.-RÜCKERT, M.-SILVA, R.: A lattice-based thresholdring signature scheme, in: Progress in Cryptology-LATINCRYPT ’10, 1st Internat. Conf. on Cryptology and Information Security (M. Abdalla et al., eds.) Puebla, Mexico, 2010, Lecture Notes in Comput. Sci., Vol. 6212, Springer, Berlin, 2010, pp. 255-272.
Search in Google Scholar
[11] CAYREL, P.-L.-VÉRON, P.-SILVA, R.: Improved code-based identification scheme, in: Provable Security, 4th Internat. Conf.-ProvSec ’10, Malacca, Malaysia, 2010 (S.-H. Heng, et al., eds.), Lecture Notes in Comput. Sci., Vol. 6402, Springer, Berlin, 2010, pp. 1-17.
Search in Google Scholar
[12] FEIGE, U.-FIAT, A.-SHAMIR, A.: Zero Knowledge Proofs of Identity, in: Proc. of the 19th Annual ACM Symposium on Theory of Computing-STOC ’87, (A. V. Aho), New York, USA, ACM, New York, 1987, pp. 210-217.10.1145/28395.28419
Search in Google Scholar
[13] FEIGE, U.-FIAT, A.-SHAMIR, A.: Witness indistinguishable and witness hiding protocols, in: Proc. of the 22nd Annual ACM Symposium on Theory of Computing-STOC ’90, ACM, New York, 1990, pp. 416-426.10.1145/100216.100272
Search in Google Scholar
[14] FIAT, A.-SHAMIR, A.: How to prove yourself: practical solutions to identification and signature problems, in: Advances in Cryptology-CRYPTO ’86 (A. M. Odlyzko, ed.), Santa Barbara, Calif., 1986, Lecture Notes in Comput. Sci., Vol. 263, Springer, Berlin, 1986, pp. 186-194.10.1007/3-540-47721-7_12
Search in Google Scholar
[15] GABORIT, P.-GIRAULT, M.: Lightweight code-based identification and signature, in: IEEE Transactions on Information Theory-ISIT ’07, Nice, France, 2007, IEEE, pp. 186-194.10.1109/ISIT.2007.4557225
Search in Google Scholar
[16] GAMA, N.-NGUYEN, P. Q.: Predicting lattice reduction, in: Advances in Cryptology- -EUROCRYPT ’08, 27th Annual Internat. Conf. on the Theory and Appl. of Cryptographic Techniques (N. Smart, ed.), Istanbul, Turkey, 2008, Lecture Notes in Comput. Sci., Vol. 4965, Springer, Berlin, pp. 31-51.
Search in Google Scholar
[17] GOLDWASSER, S.-MICALI, S.-RACKOFF, C.: The know ledge complexity of interactive proof-systems, in: Proc. of the 17th Annual ACM Symposium on Theory of Computing, ACM, New York, 1985, pp. 291-304.10.1145/22145.22178
Search in Google Scholar
[18] HALEVI, S.-MICALI, S.: Practical and provably-secure commitment schemes from collision-free hashing, in: Advances in Cryptology-CRYPTO ’96 (N. Koblitz, ed.), Santa Barbara, California, 1996 Lecture Notes in Comput. Sci., Vol. 1109, Springer, Berlin, pp. 201-215.
Search in Google Scholar
[19] KAWACHI, A.-TANAKA, K.-XAGAWA, K.: Concurrently Secure identification Schemes based on the worst-case hardness of lattice problems, in: Advances in Cryptology-ASIACRYPT ’08, 14th Internat. Conf. on the Theory and Appl. of Cryp-tology and Information Security (J. Pieprzyk, ed.), Melbourne, Australia, 2008. Lecture Notes in Comput. Sci., Vol. 5350, Springer, Berlin, 2008, pp. 372-389.
Search in Google Scholar
[20] KILIAN, J.-PETRANK, E.: Concurrent and resettable zero-knowledge in poly-loalgorithm rounds, in: Proc. of the 33rd Annual ACM Symposium on Theory of Computing (J. S. Vitter et al., eds.), Hersonissos, Greece, 2001, ACM, New York, NY, USA, pp. 560-569.10.1145/380752.380851
Search in Google Scholar
[21] LYUBASHEVSKY, V.: Lattice-based identification schemes secure under active attacks, in: Public key cryptography-PKC ’08, 11th Internat. Workshop on Practice and Theory in Public-Key Cryptography (R. Cramer, ed.), Barcelona, Spain, 2008, Lecture Notes in Comput. Sci., Vol. 4939, Springer, Berlin, 2008, pp. 162-179.
Search in Google Scholar
[22] LYUBASHEVSKY, V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures, in: Advances in Cryptology-ASIACRYPT ’09, 15th Internat. Conf. on the Theory and Application of Cryptology and Information Security (M. Matsui, ed.), Tokyo, Japan, 2009, Lecture Notes in Comput. Sci., Vol. 5912, Springer, Berlin, 2009, pp. 598-616.
Search in Google Scholar
[23] LYUBASHEVSKY, V.-MICCIANCIO, D.: Generalized compact knapsacks are collision resistant, in: Automata, Languages and Programming, 33rd Internat. Colloquium- -ICALP ’06 (M. Bugliesi et al. ed.), Venice, Italy, 2006, Lecture Notes in Comput. Sci., Vol. 4052, Springer, Berlin, 2006, pp. 144-155.
Search in Google Scholar
[24] LYUBASHEVSKY, V.-MICCIANCIO, D.: Asymptotically efficient lattice-based digital signatures, in: Theory of Cryptography Conference-TCC ’08 (R. Canetti, ed.), New York, USA, 2008, Lecture Notes in Comput. Sci., Vol. 4948, Springer, Berlin, 2008, pp. 37-54.
Search in Google Scholar
[25] LYUBASHEVSKY, V.-MICCIANCIO, D.-PEIKERT, CH.-ROSEN, A.: SWIFFT: A modest proposal for FFT hashing, in: Fast Software Encryption, 15th Internat. Workshop-FSE ’08 (K. Nyberg, ed.), Lausanne, Switzerland, 2008, Lecture Notes in Comput. Sci., Vol. 5086, Springer, Berlin, 2008, pp. 54-72.
Search in Google Scholar
[26] MICCIANCIO, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions, Comput. Complexity 16 (2007), 365-411.10.1007/s00037-007-0234-9
Search in Google Scholar
[27] MICCIANCIO, D.-GOLDWASSER, SH.: Complexity of Lattice Problems: A Cryptographic Perspective, in: Kluwer Academic Publishers, The Kluwer International Series in Engineering and Computer Science, Vol. 671, Kluwer Academic Publishers, Boston, 2002.
Search in Google Scholar
[28] MICCIANCIO, D.-REGEV, O.: Worst-case to average-case reductions based on Gaussian measures, SIAM J. Comput. 37 (2007), 267-302.10.1137/S0097539705447360
Search in Google Scholar
[29] Micciancio, D.-Vadhan, S. P. Statistical zero-knowledge proofs with efficient povers: lat-¯ tice problems and more, in: Proc. of the 23rd Internat. Conf. on Cryptology-CRYPTO ’03 (D. Boneh, ed.), Santa Barbara, 2003, Lecture Notes in Comput. Sci., Vol. 2729, Springer, Berlin, 2003, pp. 282-298.
Search in Google Scholar
[30] OHTA, K.-OKAMOTO, T.: On concrete security treatment of signatures derived from identification, in: Advances in Cryptology-CRYPTO ’98, 18th Annual Internat. Cryptol-ogy Conf. (H. Krawczyk, ed.), Santa Barbara, CA, USA, 1998, Lecture Notes in Comput. Sci., Vol. 1462, Springer, Berlin, pp. 354-369.
Search in Google Scholar
[31] POINTCHEVAL, D.-STERN, J.: Security proofs for signature schemes, in: Proc. of the 15th Annual Internat. Conf. on Theory and Appl. of Cryptographic Techniques- -EUROCRYPT ’96 (U. Maurer, ed.), Zaragoza, Spain, 1996, Lecture Notes in Comput. Sci., Vol. 1070, Springer, Berlin, pp. 387-398.
Search in Google Scholar
[32] SCHNORR, C. P.: Efficient identification and signatures for smart cards, in: Advances in Cryptology-CRYPTO ’89, Santa Barbara, CA, 1989, Lecture Notes in Comput. Sci., Vol. 435, Springer, Berlin, 1990, pp. 239-252.10.1007/0-387-34805-0_22
Search in Google Scholar
[33] SHOR, P. W.: Polynominal time algorithms for discrete logarithms and factoring on a quantum computer, in: Algorithmic Number Theory, 1st Internat. Symposium-ANTS-I (L. M. Adleman and M.-D. A. Huang, eds.), Ithaca, NY, USA, 1994, Lecture Notes in Comput. Sci., Vol. 877, Springer, Berlin, 1994, p. 289.10.1007/3-540-58691-1_68
Search in Google Scholar
[34] STERN, J.: A new identification scheme based on syndrome decoding, in: Advances in Cryptology-CRYPTO ’93, 13th Annual Internat. Cryptology Conf. (D. R. Stinson, ed.), Santa Barbara, CA, USA, 1993, Lecture Notes in Comput. Sci., Vol. 773, Springer, Berlin, 1994, pp. 13-21.10.1007/3-540-48329-2_2
Search in Google Scholar
[35] VÉRON, P.: Improved identification schemes based on error-correcting codes, Appl. Algebra Engrg. Comm. Comput. 8 (1996), 57-69.10.1007/s002000050053
Search in Google Scholar
[36] WAGNER, D.: A generalized birthday problem, in: Advances in Cryptology-CRYPTO ’02, 22nd Annual Internat. Cryptology Conf. (M. Yung, ed.), Santa Barbara, CA, USA, 2002, Lecture Notes in Comput. Sci., Vol. 2442, Springer, Berlin, 2002, pp. 288-303.
Search in Google Scholar
[37] YUNG, M., ED.: Advances in Cryptology, in: Proc of the 22nd Annual Internat. Cryp-tology Conference, Santa Barbara, California, USA, 2002, Lecture Notes in Comput. Sci., Vol. 2442, Springer, Berlin, 2002.
Search in Google Scholar

Improved Zero-Knowledge Identification with Lattices

Abstract

Paradigm

My account