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, 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]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[2]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003

[3]

Javier Fernández, Cora Tori, Marcela Zuccalli. Lagrangian reduction of nonholonomic discrete mechanical systems by stages. Journal of Geometric Mechanics, 2020, 12 (4) : 607-639. doi: 10.3934/jgm.2020029

[4]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[5]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[6]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339

[7]

Veena Goswami, Gopinath Panda. Optimal customer behavior in observable and unobservable discrete-time queues. Journal of Industrial & Management Optimization, 2021, 17 (1) : 299-316. doi: 10.3934/jimo.2019112

[8]

Qianqian Han, Xiao-Song Yang. Qualitative analysis of a generalized Nosé-Hoover oscillator. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020346

[9]

Laurence Cherfils, Stefania Gatti, Alain Miranville, Rémy Guillevin. Analysis of a model for tumor growth and lactate exchanges in a glioma. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020457

[10]

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

[11]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[12]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375

[13]

Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166

[14]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, 2021, 20 (1) : 339-358. doi: 10.3934/cpaa.2020269

[15]

Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219

[16]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026

[17]

Martin Kalousek, Joshua Kortum, Anja Schlömerkemper. Mathematical analysis of weak and strong solutions to an evolutionary model for magnetoviscoelasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 17-39. doi: 10.3934/dcdss.2020331

[18]

Feifei Cheng, Ji Li. Geometric singular perturbation analysis of Degasperis-Procesi equation with distributed delay. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 967-985. doi: 10.3934/dcds.2020305

[19]

Illés Horváth, Kristóf Attila Horváth, Péter Kovács, Miklós Telek. Mean-field analysis of a scaling MAC radio protocol. Journal of Industrial & Management Optimization, 2021, 17 (1) : 279-297. doi: 10.3934/jimo.2019111

[20]

Wen Li, Wei-Hui Liu, Seak Weng Vong. Perron vector analysis for irreducible nonnegative tensors and its applications. Journal of Industrial & Management Optimization, 2021, 17 (1) : 29-50. doi: 10.3934/jimo.2019097

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (106)
  • HTML views (408)
  • Cited by (0)

Other articles
by authors

[Back to Top]