Article Contents
Article Contents

# Verifying solutions to LWE with implications for concrete security

• * Corresponding author: Palash Sarkar
• A key step in Regev's (2009) reduction of the Discrete Gaussian Sampling (DGS) problem to that of solving the Learning With Errors (LWE) problem is a statistical test required for verifying possible solutions to the LWE problem. We derive a lower bound on the success probability leading to an upper bound on the tightness gap of the reduction. The success probability depends on the rejection threshold $t$ of the statistical test. Using a particular value of $t$, Regev showed that asymptotically, the success probability of the test is exponentially close to one for all values of the LWE error $\alpha\in(0,1)$. From the concrete analysis point of view, the value of the rejection threshold used by Regev is sub-optimal. It leads to considering the lattice dimension to be as high as 400000 to obtain somewhat meaningful tightness gap. We show that by using a different value of the rejection threshold and considering $\alpha$ to be at most $1/\sqrt{n}$ results in the success probability going to 1 for small values of the lattice dimension. Consequently, our work shows that it may be required to modify values of parameters used in an asymptotic analysis to obtain much improved and meaningful concrete security.

Mathematics Subject Classification: Primary: 94A60.

 Citation:

•  [1] E. Alkim, R. Avanzi, J. Bos, L. Ducas, A. de la Piedra, T. Poppelmann, P. Schwabe, D. Stebila, M. R. Albrecht, E. Orsini, V. Osheter, K. G. Paterson, G. Peer and N. P. Smart, NewHope: Algorithm specifications and supporting documentation, (2019), https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions. [2] E. Alkim, J. Bos, L. Ducas, P. Longa, I. Mironov, M. Naehrig, V. Nikolaenko, C. Peikert, A. Raghunathan and D. Stebila, FrodoKEM: Learning With Errors key encapsulation, (2019), https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions. [3] R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler and D. Stehlé, CRYSTALS-Kyber: Algorithm specifications and supporting documentation, (2009), https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions. [4] H. Baan, S. Bhattacharya, S. Fluhrer, O. Garcia-Morchon, T. Laarhoven, R. Player, R. Rietman, M.-J. O. Saarinen, L. Tolhuizen, J.-L. Torre-Arce and Z. F. Zhang, Round5: KEM and PKE based on (Ring) learning With rounding, (2019), https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions. [5] D. J. Bernstein, Comparing proofs of security for lattice-based encryption, Cryptology ePrint Archive, Report 2019/691, 2019, https://eprint.iacr.org/2019/691. [6] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. Ⅰ. The user language, J. Symbolic Comput., 24 (1997), 235-265.  doi: 10.1006/jsco.1996.0125. [7] Z. Brakerski, A. Langlois, C. Peikert, O. Regev and D. Stehlé, Classical hardness of learning with errors (extended abstract), STOC'13—Proceedings of the 2013 ACM Symposium on Theory of Computing, ACM, New York, (2013), 575–584. doi: 10.1145/2488608.2488680. [8] S. Chatterjee, N. Koblitz, A. Menezes and P. Sarkar, Another look at tightness Ⅱ: Practical issues in cryptography, Mycrypt 2016: Paradigms in Cryptology-Mycrypt 2016, Malicious and Exploratory Cryptology, (2016), 21–55. doi: 10.1007/978-3-319-61273-7_3. [9] J.-P. D'Anvers, A. Karmakar, S. S. Roy and F. Vercauteren, SABER: Mod-LWR based KEM (round 2 submission), (2019), https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions. [10] X. H. Lu, Y. M. Liu, D. D. Jia, H. Y. Xue, J. G. He, Z. F. Zhang, Z. Liu, H. Yang, B. Li and K. P. Wang, LAC: Lattice-based Cryptosystems, (2019), https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions. [11] V. Lyubashevsky, C. Peikert and O. Regev, On ideal lattices and learning with errors over rings, J. ACM, 60 (2013), Art. 43, 35 pp. doi: 10.1145/2535925. [12] C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract, STOC'09—Proceedings of the 2009 ACM International Symposium on Theory of Computing, ACM, New York, (2009), 333–342. [13] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. ACM, 56 (2009), Art. 34, 40 pp. doi: 10.1145/1568318.1568324. [14] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 7.5.1), 2019, https://www.sagemath.org.