A new method of generating hard random lattices with short bases
Tóm tắt
This paper first gives a regularity theorem and its corollary. Then, a new construction of generating hard random lattices with short bases is obtained by using this corollary. This construction is from a new perspective and uses a random matrix whose entries obeyed Gaussian sampling which ensures that the corresponding schemes have a wider application future in cryptography area. Moreover, this construction is more specific than the previous constructions, which makes it can be implemented easier in practical applications.
Tài liệu tham khảo
C. Peikert, in Annual Cryptology Conference. An efficient and parallel Gaussian sampler for lattices (Springer, Berlin, 2010), pp. 80–97
Z. Brakerski, V. Vaikuntanathan, in Adannces in Cryptology -CRYPTO 2011. Fully homomorphic encryption from ring-LWE and security for key dependent message (2011), pp. 505–524
S. Dov Gordon, J. Katz, V. Vaikuntanathan, in Advances in cryptology -ASIACRYPT 2010, Lecture Notes in Computer Science. A group signature scheme from lattice assumptions, vol 6477 (2010), pp. 395–412
V. Lyubashevsky, C. Peikert, O. Regev, in Advances in Cryptology C EUROCRYPT 2010. On ideal lattices and learning with errors over rings (2010), pp. 1–23
V. Lyubashevsky, C. Peikert, O. Regev, in Advances in Cryptology C EUROCRYPT 2013. A Toolkit for Ring-LWE Cryptography (2013), pp. 35–54
S. Ling, K. Nguyen, D. Stehl, et al., in Public-Key CryptographyCPKC 2013. Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications (Springer, Berlin, 2013), pp. 107–124
D. Micciancio, C. Peikert, in Advances in Cryptology C EUROCRYPT 2012. Trapdoor for lattices: simpler, tighter, faster, smaller (2012), pp. 700–718
O. Regev, Lattice-based cryptography[C]. Annual International Cryptology Conference. (Springer, Berlin, Heidelberg, 2006), pp. 131–141
C. Peikert, B. Waters, Lossy trapdoor functions and their applications[J]. SIAM J. Comput. 40(6), 1803–1844 (2011)
T. Poppelmann, Efficient implementation of ideal lattice-based cryptography. Inf. Technol. 59(6), 305–309 (2017)
M. Ajtai, in International Colloquium on Automata, Languages, and Programming. Generating hard instances of the short basis problem (1999), pp. 1–9
J. Alwen, C. Peikert, Generating shorter bases for hard random lattices. Theory Comput. Syst. 48(3), 535–553 (2011)
V. Lyubashevsky, D. Micciancio, in Advances in Cryptology-CRYPTO 2009. On bounded distance decoding, unique shortest vectors, and the minimum distance problem (2009), pp. 577–594
T. Laarhoven, M. Mosca, J. Van De Pol, Finding shortest lattice vectors faster using quantum search. Des. Codes Crypt. 77(2–3), 375400 (2015)
M. Ajtai, in ACM Symposium on Theory of Computing -STOC. Generating hard instances of lattice problem-s (1996), pp. 99–108
C. Gentry, C. Peikert, V. Vaikuntanathan, in Proceedings of the fortieth annual ACM symposium on Theory of computing. Trapdoors for hard lattices and new cryptographic constructions (2008), pp. 197–206
D. Micciancio, O. Regev, Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007)