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]

Jintai Ding, Joshua Deaton, Kurt Schmidt. Giophantus distinguishing attack is a low dimensional learning with errors problem. Advances in Mathematics of Communications, 2020, 14 (1) : 171-175. doi: 10.3934/amc.2020014

[2]

Jintai Ding, Joshua Deaton, Kurt Schmidt. Giophantus distinguishing attack is a low dimensional learning with errors problem. Advances in Mathematics of Communications, 2020, 14 (4) : 573-577. doi: 10.3934/amc.2020030

[3]

Valery Y. Glizer, Vladimir Turetsky, Emil Bashkansky. Statistical process control optimization with variable sampling interval and nonlinear expected loss. Journal of Industrial & Management Optimization, 2015, 11 (1) : 105-133. doi: 10.3934/jimo.2015.11.105

[4]

Chuandong Li, Fali Ma, Tingwen Huang. 2-D analysis based iterative learning control for linear discrete-time systems with time delay. Journal of Industrial & Management Optimization, 2011, 7 (1) : 175-181. doi: 10.3934/jimo.2011.7.175

[5]

Marco Cicalese, Matthias Ruf. Discrete spin systems on random lattices at the bulk scaling. Discrete & Continuous Dynamical Systems - S, 2017, 10 (1) : 101-117. doi: 10.3934/dcdss.2017006

[6]

Sari Lasanen. Non-Gaussian statistical inverse problems. Part II: Posterior convergence for approximated unknowns. Inverse Problems & Imaging, 2012, 6 (2) : 267-287. doi: 10.3934/ipi.2012.6.267

[7]

Sari Lasanen. Non-Gaussian statistical inverse problems. Part I: Posterior distributions. Inverse Problems & Imaging, 2012, 6 (2) : 215-266. doi: 10.3934/ipi.2012.6.215

[8]

Costică Moroşanu. Stability and errors analysis of two iterative schemes of fractional steps type associated to a nonlinear reaction-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2020, 13 (5) : 1567-1587. doi: 10.3934/dcdss.2020089

[9]

Roberto C. Alamino, Nestor Caticha. Bayesian online algorithms for learning in discrete hidden Markov models. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 1-10. doi: 10.3934/dcdsb.2008.9.1

[10]

Jiang Xie, Junfu Xu, Celine Nie, Qing Nie. Machine learning of swimming data via wisdom of crowd and regression analysis. Mathematical Biosciences & Engineering, 2017, 14 (2) : 511-527. doi: 10.3934/mbe.2017031

[11]

Andreas Chirstmann, Qiang Wu, Ding-Xuan Zhou. Preface to the special issue on analysis in machine learning and data science. Communications on Pure & Applied Analysis, 2020, 19 (8) : i-iii. doi: 10.3934/cpaa.2020171

[12]

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

[13]

Li Li, Xinzhen Zhang, Zheng-Hai Huang, Liqun Qi. Test of copositive tensors. Journal of Industrial & Management Optimization, 2019, 15 (2) : 881-891. doi: 10.3934/jimo.2018075

[14]

Adrian Muntean, Toyohiko Aiki. Preface to ``The Mathematics of Concrete". Networks & Heterogeneous Media, 2014, 9 (4) : i-ii. doi: 10.3934/nhm.2014.9.4i

[15]

Onur Teymur, Sarah Filippi. A Bayesian nonparametric test for conditional independence. Foundations of Data Science, 2020, 2 (2) : 155-172. doi: 10.3934/fods.2020009

[16]

Fumio Ishizaki. Analysis of the statistical time-access fairness index of one-bit feedback fair scheduler. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 675-689. doi: 10.3934/naco.2011.1.675

[17]

Ikuo Arizono, Yasuhiko Takemoto. Statistical mechanics approach for steady-state analysis in M/M/s queueing system with balking. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020141

[18]

Janne M.J. Huttunen, J. P. Kaipio. Approximation errors in nonstationary inverse problems. Inverse Problems & Imaging, 2007, 1 (1) : 77-93. doi: 10.3934/ipi.2007.1.77

[19]

Jingang Zhao, Chi Zhang. Finite-horizon optimal control of discrete-time linear systems with completely unknown dynamics using Q-learning. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020030

[20]

Keaton Hamm, Longxiu Huang. Stability of sampling for CUR decompositions. Foundations of Data Science, 2020, 2 (2) : 83-99. doi: 10.3934/fods.2020006

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (91)
  • HTML views (328)
  • Cited by (0)

Other articles
by authors

[Back to Top]