An efficient statistical zero-knowledge authentication protocol for smart cards

References

• M. Ajtai, Generating hard instances of lattice problems, Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC ’96), ACM, Dallas, Texas, USA, 1996, pp. 99–108.
   Google Scholar
• M. Bellare and P. Rogaway, The exact security of digital signatures – how to sign with RSA and Rabin, in Advances in Cryptology – EUROCRYPT '96, Saragossa, Spain, U.M. Maurer, eds., Springer, Berlin, 1996, pp. 399–416.
   Google Scholar
• D.J. Bernstein, T. Lange, and C. Peters, Attacking and defending the McEliece cryptosystem, Proceedings of the 2nd International Workshop on Post-Quantum Cryptography (PQCrypto 2008), Springer, Cincinnati, OH, USA, 2008, pp. 31–46.
   Google Scholar
• A. Boorghany, S. Bayat Sarmadi, and R. Jalili, On constrained implementation of lattice-based cryptographic primitives and schemes on smart cards (2014), accepted for publication in “ACM Transactions on Embedded Computing Systems.” Available at http://eprint.iacr.org /2014/514http://eprint.iacr.org /2014/514.
   Google Scholar
• A. Boorghany and R. Jalili, Implementation and comparison of lattice-based identification protocols on smart cards and microcontrollers, Cryptology ePrint Archive (2014). Available at http://eprint.iacr.org/2014/078http://eprint.iacr.org/2014/078.
   Google Scholar
• P.L. Cayrel and P. Véron, Improved code-based identification scheme (2010), unpublished manuscript. Available at http://arxiv.org/abs/1001.3017v1http://arxiv.org/abs/1001.3017v1.
   Google Scholar
• P.L. Cayrel, R. Lindner, M. Rückert, and R. Silva, Improved zero-knowledge identification with lattices, in Proceedings of the 4th International Conference on Provable Security – ProvSec 2010, Malacca, Malaysia, S.-H. Heng and K. Kurosawa, eds., Springer, Berlin, 2010, pp. 1–17.
   Google Scholar
• Y. Chen and P.Q. Nguyen, BKZ 2.0: Better lattice security estimates, in Advances in Cryptology – ASIACRYPT 2011, Seoul, South Korea, D.H. Lee and X. Wang, eds., Springer, Berlin, 2011, pp. 1–20.
   Google Scholar
• M.S. Dousti and R. Jalili, Efficient statistical zero-knowledge authentication protocols for smart cards secure against active & concurrent attacks, Cryptology ePrint Archive (2013). Available at http://eprint.iacr.org/2013/709http://eprint.iacr.org/2013/709.
   Google Scholar
• L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky, Lattice signatures and bimodal Gaussians, in Advances in Cryptology – CRYPTO 2013, R. Canetti and J.A. Garay, eds., Springer, Santa Barbara, CA, 2013, pp. 40–56.
   Google Scholar
• U. Feige, A. Fiat, and A. Shamir, Zero-knowledge proofs of identity, J. Cryptol. 1 (1988), pp. 77–94. doi: 10.1007/BF02351717
   Google Scholar
• A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Advances in Cryptology – CRYPTO '86, Springer, Santa Barbara, CA, 1987, pp. 186–194.
   Google Scholar
• D.M. Freeman, O. Goldreich, E. Kiltz, A. Rosen, and G. Segev, More constructions of lossy and correlation-secure trapdoor functions, in Public Key Cryptography (PKC 2010), Nara, Japan, K. Kurosawa and G. Hanaoka, eds., Springer, Berlin, 2010, pp. 279–295.
   Google Scholar
• O. Goldreich and H. Krawczyk, On the composition of zero-knowledge proof systems, SIAM J. Comput.25 (1996), pp. 169–192. doi: 10.1137/S0097539791220688
   Web of Science ®Google Scholar
• N. Göttert, T. Feller, M. Schneider, J. Buchmann, and S. Huss, On the design of hardware building blocks for modern lattice-based encryption schemes, in Proceedings of the 14th International Workshop Cryptographic Hardware and Embedded Systems (CHES 2012), Leuven, Belgium, E. Prouff and P. Schaumont, eds., Springer, Berlin, 2012, pp. 512–529.
   Google Scholar
• T. Güneysu, V. Lyubashevsky, and T. Pöppelmann, Practical lattice-based cryptography: A signature scheme for embedded systems, in Cryptographic Hardware and Embedded Systems – CHES 2012, Leuven, Belgium, E. Prouff and P. Schaumont, eds., Springer, Berlin, 2012, pp. 530–547.
   Google Scholar
• J. Hoffstein, J. Pipher, and J.H. Silverman, NTRU: A ring-based public key cryptosystem, in Proceedings of the 3rd International Symposium on Algorithmic Number Theory (ANTS-III), Portland, OR, USA, J. Buhler, ed., Springer, Berlin, 1998, pp. 267–288.
   Google Scholar
• A. Kawachi, K. Tanaka, and K. Xagawa, Concurrently secure identification schemes based on the worstcase hardness of lattice problems, in Advances in Cryptology – ASIACRYPT 2008, Melbourne, Australia, J. Pieprzyk, ed., Springer, Berlin, 2008, pp. 372–389.
   Google Scholar
• T. Laarhoven, M. Mosca, and J.H. van de Pol, Solving the shortest vector problem in lattices faster using quantum search, Proceedings of the 5th International Workshop on Post-Quantum Cryptography (PQCrypto 2013), Springer, Limoges, 2013, pp. 83–101.
   Google Scholar
• R. Lindner and C. Peikert, Better key sizes (and attacks) for LWE-based encryption, Proceedings of the 11th International Conference on Topics in Cryptology (CT-RSA 2011), Springer, San Francisco, CA, 2011, pp. 319–339. Available at http://eprint.iacr.org/2010/613.
   Google Scholar
• V. Lyubashevsky, Lattice-based identification schemes secure under active attacks, in Public Key Cryptography (PKC 2008), Barcelona, Spain, R. Cramer, ed., Springer, Berlin, 2008, pp. 162–179.
   Google Scholar
• V. Lyubashevsky, Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures, in Advances in Cryptology – ASIACRYPT 2009, Tokyo, Japan, M. Matsui, ed., Springer, Berlin, 2009, pp. 598–616.
   Google Scholar
• V. Lyubashevsky and D. Micciancio, Generalized compact knapsacks are collision resistant, in Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), Venice, Italy, M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, eds., Springer, Berlin, 2006, pp. 144–155.
   Google Scholar
• V. Lyubashevsky, C. Peikert, and O. Regev, On ideal lattices and learning with errors over rings, in Advances in Cryptology – EUROCRYPT 2010, Nice, French Riviera, H. Gilbert, ed., Springer, Berlin, 2010, pp. 1–23.
   Google Scholar
• V. Lyubashevsky, D. Micciancio, C. Peikert, and A. Rosen, SWIFFT: A modest proposal for FFT hashing, in Fast Software Encryption – FSE '08, Lausanne, Switzerland, K. Nyberg, ed., Springer, Berlin, 2008, pp. 54–72.
   Google Scholar
• D. Micciancio, Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions, Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS '02), IEEE Computer Society, Vancouver, BC, Canada, 2002, pp. 356–365
   Google Scholar
• D. Micciancio and C. Peikert, Trapdoors for lattices: Simpler, tighter, faster, smaller, in Advances in Cryptology – EUROCRYPT 2012, Springer, 2012, pp. 700–718. Available at http://eprint.iacr.org/2011/501.
   Google Scholar
• D. Micciancio and C. Peikert, Hardness of SIS and LWE with small parameters, in Advances in Cryptology – CRYPTO 2013, Springer, Santa Barbara, CA, 2013, pp. 21–39. Available at http://eprint.iacr.org/2013/069.
   Google Scholar
• D. Micciancio and O. Regev, Lattice-based cryptography, D.J. Bernstein, J. Buchmann, and E. Dahme, eds., in Post-Quantum Cryptography, Springer, Berlin, 2009, pp. 147–191.
   Google Scholar
• D. Micciancio and S.P. Vadhan, Statistical zero-knowledge proofs with efficient provers: Lattice problems and more, in Advances in Cryptology – CRYPTO 2003, Santa Barbara, CA, USA, D. Boneh, ed., Springer, Berlin, 2003, pp. 282–298.
   Google Scholar
• T. Okamoto, D. Chaum, and K. Ohta, Direct zero knowledge proofs of computational power in five rounds, in Advances in Cryptology – EUROCRYPT '91, Brighton, UK, Lecture Notes in Computer Science, Vol. 547, D.W. Davies, ed., Springer, Berlin, 1991, pp. 96–105.
   Google Scholar
• C. Peikert and A. Rosen, Efficient collision-resistant Hashing from worst-case assumptions on cyclic lattices, Proceedings of the Third conference on Theory of Cryptography, Theory of Cryptography – TCC '06, Springer, New York, 2006, pp. 145–166.
   Google Scholar
• P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26 (1997), pp. 1484–1509. doi: 10.1137/S0097539795293172
   Web of Science ®Google Scholar
• R. Silva, A.C.d.A. Campello, and R. Dahab, LWE-based identification schemes, Proceedings of the 11th IEEE Information Theory Workshop (ITW 2011), IEEE Computer Society, Paraty, Brazil, 2011, pp. 292–296.
   Google Scholar
• R. Silva, P.L. Cayrel, and R. Lindner, Zero-knowledge identification based on lattices with low communication costs, Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais (SBSEG), Available from http://www.cayrel.net/PublicationsCayrel/2011%20-%20ZK%20Id%20based%20on%20Lattices%20with%20Low%20Com%20Cost.pdf, Brazilian Computer Society (SBC), 2011.
   Google Scholar
• J. Stern, A new paradigm for public key identification, IEEE Trans Inf. Theory 42 (1996), pp. 1757–1768. doi: 10.1109/18.556672
   Web of Science ®Google Scholar
• K. Xagawa, Cryptography with lattices, Ph.D. thesis, Department of Mathematical and Computing Sciences (2010). Available at http://xagawa.net/pdf/2010Thesis.pdf.
   Google Scholar
• K. Xagawa and K. Tanaka, Zero-knowledge protocols for NTRU: Application to identification and proof of plain text knowledge, in Proceedings of the 3rd International Conference on Provable Security – ProvSec 2009, Guangzhou, China, J. Pieprzyk and F. Zhang, eds., Springer, Berlin, 2009, pp. 198–213.
   Google Scholar