May  2021, 15(2): 257-266. doi: 10.3934/amc.2020057

Verifying solutions to LWE with implications for concrete security

Indian Statistical Institute, 203, BT Rd, Baranagar, Kolkata, West Bengal 700108, India

* Corresponding author: Palash Sarkar

Received  July 2019 Revised  August 2019 Published  January 2020

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.

Citation: Palash Sarkar, Subhadip Singha. Verifying solutions to LWE with implications for concrete security. Advances in Mathematics of Communications, 2021, 15 (2) : 257-266. doi: 10.3934/amc.2020057
References:
[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[6]

W. BosmaJ. Cannon and C. Playoust, The Magma algebra system. Ⅰ. The user language, J. Symbolic Comput., 24 (1997), 235-265.  doi: 10.1006/jsco.1996.0125.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

The Sage Developers, SageMath, the Sage Mathematics Software System (Version 7.5.1), 2019, https://www.sagemath.org. Google Scholar

show all references

References:
[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[6]

W. BosmaJ. Cannon and C. Playoust, The Magma algebra system. Ⅰ. The user language, J. Symbolic Comput., 24 (1997), 235-265.  doi: 10.1006/jsco.1996.0125.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

The Sage Developers, SageMath, the Sage Mathematics Software System (Version 7.5.1), 2019, https://www.sagemath.org. Google Scholar

[1]

Alvaro Sandroni, Eran Shmaya. A prequential test for exchangeable theories. Journal of Dynamics & Games, 2014, 1 (3) : 497-505. doi: 10.3934/jdg.2014.1.497

[2]

Dmitry Treschev. Travelling waves in FPU lattices. Discrete & Continuous Dynamical Systems - A, 2004, 11 (4) : 867-880. doi: 10.3934/dcds.2004.11.867

[3]

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907

[4]

Mikhail Gilman, Semyon Tsynkov. Statistical characterization of scattering delay in synthetic aperture radar imaging. Inverse Problems & Imaging, 2020, 14 (3) : 511-533. doi: 10.3934/ipi.2020024

[5]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[6]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225

[7]

Chin-Chin Wu. Existence of traveling wavefront for discrete bistable competition model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 973-984. doi: 10.3934/dcdsb.2011.16.973

[8]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355

[9]

M. R. S. Kulenović, J. Marcotte, O. Merino. Properties of basins of attraction for planar discrete cooperative maps. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2721-2737. doi: 10.3934/dcdsb.2020202

[10]

Sohana Jahan. Discriminant analysis of regularized multidimensional scaling. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 255-267. doi: 10.3934/naco.2020024

[11]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

[12]

Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623

[13]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[14]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446

[15]

Alexey Yulin, Alan Champneys. Snake-to-isola transition and moving solitons via symmetry-breaking in discrete optical cavities. Discrete & Continuous Dynamical Systems - S, 2011, 4 (5) : 1341-1357. doi: 10.3934/dcdss.2011.4.1341

[16]

Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195

[17]

Elena K. Kostousova. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021015

[18]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1

[19]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367

[20]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034

2019 Impact Factor: 0.734

Article outline

Figures and Tables

[Back to Top]