
Previous Article
On the existence of PDsets: Algorithms arising from automorphism groups of codes
 AMC Home
 This Issue

Next Article
Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations
Verifying solutions to LWE with implications for concrete security
Indian Statistical Institute, 203, BT Rd, Baranagar, Kolkata, West Bengal 700108, India 
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 suboptimal. 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.
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/postquantumcryptography/round2submissions. 
[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/postquantumcryptography/round2submissions. 
[3] 
R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler and D. Stehlé, CRYSTALSKyber: Algorithm specifications and supporting documentation, (2009), https://csrc.nist.gov/projects/postquantumcryptography/round2submissions. 
[4] 
H. Baan, S. Bhattacharya, S. Fluhrer, O. GarciaMorchon, T. Laarhoven, R. Player, R. Rietman, M.J. O. Saarinen, L. Tolhuizen, J.L. TorreArce and Z. F. Zhang, Round5: KEM and PKE based on (Ring) learning With rounding, (2019), https://csrc.nist.gov/projects/postquantumcryptography/round2submissions. 
[5] 
D. J. Bernstein, Comparing proofs of security for latticebased 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), 235265. 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 CryptologyMycrypt 2016, Malicious and Exploratory Cryptology, (2016), 21–55. doi: 10.1007/9783319612737_3. 
[9] 
J.P. D'Anvers, A. Karmakar, S. S. Roy and F. Vercauteren, SABER: ModLWR based KEM (round 2 submission), (2019), https://csrc.nist.gov/projects/postquantumcryptography/round2submissions. 
[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: Latticebased Cryptosystems, (2019), https://csrc.nist.gov/projects/postquantumcryptography/round2submissions. 
[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, Publickey cryptosystems from the worstcase 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. 
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/postquantumcryptography/round2submissions. 
[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/postquantumcryptography/round2submissions. 
[3] 
R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler and D. Stehlé, CRYSTALSKyber: Algorithm specifications and supporting documentation, (2009), https://csrc.nist.gov/projects/postquantumcryptography/round2submissions. 
[4] 
H. Baan, S. Bhattacharya, S. Fluhrer, O. GarciaMorchon, T. Laarhoven, R. Player, R. Rietman, M.J. O. Saarinen, L. Tolhuizen, J.L. TorreArce and Z. F. Zhang, Round5: KEM and PKE based on (Ring) learning With rounding, (2019), https://csrc.nist.gov/projects/postquantumcryptography/round2submissions. 
[5] 
D. J. Bernstein, Comparing proofs of security for latticebased 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), 235265. 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 CryptologyMycrypt 2016, Malicious and Exploratory Cryptology, (2016), 21–55. doi: 10.1007/9783319612737_3. 
[9] 
J.P. D'Anvers, A. Karmakar, S. S. Roy and F. Vercauteren, SABER: ModLWR based KEM (round 2 submission), (2019), https://csrc.nist.gov/projects/postquantumcryptography/round2submissions. 
[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: Latticebased Cryptosystems, (2019), https://csrc.nist.gov/projects/postquantumcryptography/round2submissions. 
[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, Publickey cryptosystems from the worstcase 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. 
[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 (4) : 573577. doi: 10.3934/amc.2020030 
[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 (1) : 171175. doi: 10.3934/amc.2020014 
[3] 
Valery Y. Glizer, Vladimir Turetsky, Emil Bashkansky. Statistical process control optimization with variable sampling interval and nonlinear expected loss. Journal of Industrial and Management Optimization, 2015, 11 (1) : 105133. doi: 10.3934/jimo.2015.11.105 
[4] 
Chuandong Li, Fali Ma, Tingwen Huang. 2D analysis based iterative learning control for linear discretetime systems with time delay. Journal of Industrial and Management Optimization, 2011, 7 (1) : 175181. doi: 10.3934/jimo.2011.7.175 
[5] 
Marco Cicalese, Matthias Ruf. Discrete spin systems on random lattices at the bulk scaling. Discrete and Continuous Dynamical Systems  S, 2017, 10 (1) : 101117. doi: 10.3934/dcdss.2017006 
[6] 
YuChi Chen. Security analysis of public key encryption with filtered equality test. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021053 
[7] 
Palash Sarkar, Subhadip Singha. Classical reduction of gap SVP to LWE: A concrete security analysis. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021004 
[8] 
Jiaxin Zhang, Hoang Tran, Guannan Zhang. Accelerating reinforcement learning with a DirectionalGaussianSmoothing evolution strategy. Electronic Research Archive, 2021, 29 (6) : 41194135. doi: 10.3934/era.2021075 
[9] 
Congcong Li, Chunqiu Li, Jintao Wang. Statistical solution and Liouville type theorem for coupled SchrödingerBoussinesq equations on infinite lattices. Discrete and Continuous Dynamical Systems  B, 2022 doi: 10.3934/dcdsb.2021311 
[10] 
Carlo Bardaro, Ilaria Mantellini. Boundedness properties of semidiscrete sampling operators in Mellin–Lebesgue spaces. Mathematical Foundations of Computing, 2022, 5 (3) : 219229. doi: 10.3934/mfc.2021031 
[11] 
Sari Lasanen. NonGaussian statistical inverse problems. Part II: Posterior convergence for approximated unknowns. Inverse Problems and Imaging, 2012, 6 (2) : 267287. doi: 10.3934/ipi.2012.6.267 
[12] 
Sari Lasanen. NonGaussian statistical inverse problems. Part I: Posterior distributions. Inverse Problems and Imaging, 2012, 6 (2) : 215266. doi: 10.3934/ipi.2012.6.215 
[13] 
Costică Moroşanu. Stability and errors analysis of two iterative schemes of fractional steps type associated to a nonlinear reactiondiffusion equation. Discrete and Continuous Dynamical Systems  S, 2020, 13 (5) : 15671587. doi: 10.3934/dcdss.2020089 
[14] 
Mourad Nachaoui, Lekbir Afraites, Aissam Hadri, Amine Laghrib. A nonconvex nonsmooth bilevel parameter learning for impulse and Gaussian noise mixture removing. Communications on Pure and Applied Analysis, 2022, 21 (4) : 12491291. doi: 10.3934/cpaa.2022018 
[15] 
Wenming Li, Yongge Tian, Ruixia Yuan. Statistical analysis of a linear regression model with restrictions and superfluous variables. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022079 
[16] 
Roberto C. Alamino, Nestor Caticha. Bayesian online algorithms for learning in discrete hidden Markov models. Discrete and Continuous Dynamical Systems  B, 2008, 9 (1) : 110. doi: 10.3934/dcdsb.2008.9.1 
[17] 
Alvaro Sandroni, Eran Shmaya. A prequential test for exchangeable theories. Journal of Dynamics and Games, 2014, 1 (3) : 497505. doi: 10.3934/jdg.2014.1.497 
[18] 
Li Li, Xinzhen Zhang, ZhengHai Huang, Liqun Qi. Test of copositive tensors. Journal of Industrial and Management Optimization, 2019, 15 (2) : 881891. doi: 10.3934/jimo.2018075 
[19] 
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) : 511527. doi: 10.3934/mbe.2017031 
[20] 
Andreas Chirstmann, Qiang Wu, DingXuan Zhou. Preface to the special issue on analysis in machine learning and data science. Communications on Pure and Applied Analysis, 2020, 19 (8) : iiii. doi: 10.3934/cpaa.2020171 
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]