Improved Zero-Knowledge Identification with Lattices

[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.237838Search 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.258604Search 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-7Search 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.28419Search 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.100272Search 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_12Search 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.4557225Search 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.22178Search 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.380851Search 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-9Search 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/S0097539705447360Search 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_22Search 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_68Search 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_2Search 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/s002000050053Search 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