SCIENCE CHINA Information Sciences, Volume 63 , Issue 9 : 192101(2020) https://doi.org/10.1007/s11432-018-9788-1

Rényi divergence on learning with errors

More info
  • ReceivedAug 7, 2018
  • AcceptedFeb 14, 2019
  • PublishedAug 10, 2020


Many lattice-based schemes are built from the hardness of the learning with errors problem, which naturally comes in two flavors: the decision LWE and search LWE. In this paper, we investigate the decision LWE and search LWE by Rényi divergence respectively and obtain the following results: For decision LWE, we apply RD on LWE variants with different error distributions (i.e., center binomial distribution and uniform distribution, which are frequently used in the NIST PQC submissions) and prove the pseudorandomness in theory. As a by-product, we extend the so-called public sampleability property and present an adaptively public sampling property to the application of Rényi divergence on more decision problems. As for search LWE, we improve the classical reduction proof from GapSVP to LWE. Besides, as an independent interest, we also explore the intrinsic relation between the decision problem and search problem.


This work was supported in part by National Natural Science Foundation of China (Nos. 61772520, 61632020, 61472416, 61802392), Key Research Project of Zhejiang Province (Grant No. 2017C01062), and National Key Research and Development Program of China (Grant No. 2017yfb0802200).


Appendixes A–C.


[1] Regev O. On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, 2005. 84--93. Google Scholar

[2] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco, 2010. Google Scholar

[3] Langlois A, Stehlé D. Worst-case to average-case reductions for module lattices. Des Codes Cryptogr, 2015, 75: 565-599 CrossRef Google Scholar

[4] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, 2008. 197--206. Google Scholar

[5] Lindner R, Peikert C. Better key sizes (and attacks) for LWE-based encryption. In: Proceedings of Cryptographers' Track at the RSA Conference, San Francisco, 2011. 319--339. Google Scholar

[6] Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, 2011. 97--106. Google Scholar

[7] Gentry C, Sahai A, Water B. Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Proceedings of Annual Cryptology Conference, Santa Barbara, 2013. 75--92. Google Scholar

[8] Alkim E, Ducas L, Pöppelmann T, et al. Post-quantum key exchange -- a new hope. In: Proceedings of the 25th USENIX Security Symposium, Austin, 2016. 327--343. Google Scholar

[9] Bos J W, Costello C, Ducas L, et al. Frodo: take off the ring practical, quantum-secure key exchange from LWE. In: Proceedings of the Conference on Computer and Communications Security, Vienna, 2016. 1006--1018. Google Scholar

[10] Bos J W, Ducas L, Kiltz E, et al. CRYSTALS-Kyber: a CCA-secure module-lattice-based KEM. In: Proceedings of European Symposium on Security and Privacy, London, 2018. 353--367. Google Scholar

[11] Alkim E, Avanzi R, Bos J, et al. NewHope: alogrithm specifcations and supporting documentation. http://newhopecrypto.org/. Google Scholar

[12] Lu X H, Liu Y M, Zhang Z F, et al. LAC: practical ring-LWE based public-key encryption with byte-level modulus. 2018. https://eprint.iacr.org/2018/1009.pdf. Google Scholar

[13] Smart N P, Albrecht M R, Lindell Y, et al. LIMA: a PQC encryption scheme. https://lima-pq.github.io/. Google Scholar

[14] Bansarkhani R E. KINDI: 20171130 submission. http://kindi-kem.de/. Google Scholar

[15] Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, et al. CRYSTALS-Dilithium: a lattice-based digital signature scheme. IACR Trans Cryptogr Hardw Embed Syst, 2018, 2018: 238--268. Google Scholar

[16] Bai S, Lepoint T, Roux-Langlois A. Improved Security Proofs in Lattice-Based Cryptography: Using the Rényi Divergence Rather than the Statistical Distance. J Cryptol, 2018, 31: 610-640 CrossRef Google Scholar

[17] Bogdanov A, Guo S Y, Masny D, et al. On the hardness of learning with rounding over small modulus. In: Proceedings of Theory of Cryptography, Israel, 2016. 209-224. Google Scholar

[18] Peikert C. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Bethesda, 2009. 333--342. Google Scholar

[19] Takashima K, Takayasu A. Tighter security for efficient lattice cryptography via the rényi divergence of optimized orders. In: Proceedings of International Conference on Provable Security, Kanazawa, 2015. 412--431. Google Scholar

[20] Prest T. Sharper bounds in lattice-based cryptography using the rényi divergence. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, 2017. 347--374. Google Scholar

[21] Ducas L, Durmus A, Lepoint T, et al. Lattice signatures and bimodal gaussians. In: Proceedings of Annual Cryptology Conference, Santa Barbara, 2013. 40+-56. Google Scholar

[22] Micciancio D, Regev O. Worst-case to average-case reductions based on gaussian measures. In: Proceedings of the 45th Symposium on Foundations of Computer Science, Rome, 2004. 372--381. Google Scholar

[23] Micciancio D, Mol P. Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions. In: Proceedings of Annual Cryptology Conference, Santa Barbara, 2011. 465--484. Google Scholar

[24] Micciancio D, Peikert C. Trapdoors for lattices: simpler, tighter, faster, smaller. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, 2012. 700--718. Google Scholar

[25] van Erven T, Harremoes P. Rényi Divergence and Kullback-Leibler Divergence. IEEE Trans Inform Theor, 2014, 60: 3797-3820 CrossRef Google Scholar

[26] Brakerski Z, Langlois A, Peikert C, et al. Classical hardness of learning with errors. In: Proceedings of Symposium on Theory of Computing Conference, Palo Alto, 2013. 575--584. Google Scholar

  • Table 1  

    Table 1List of NIST submissions based on LWE with different error distributions

    Scheme Functionality Hard problem Error distribution
    Kyber [10] KEM/PKE MLWE Center binomial distribution
    NewHope [11] KEM/PKE RLWE Center binomial distribution
    LAC [12] KEM/PKE RLWE Center binomial distribution
    LIMA [13]KEM/PKE RLWE Center binomial distribution
    KINDI [14] KEM/PKE MLWE Uniform distribution
    Dilithium [15] Signature MLWE Uniform distribution

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号