Concrete analysis of approximate ideal-SIVP to decision ring-LWE reduction

Neal Koblitz; Subhabrata Samajder; Palash Sarkar; Subhadip Singha

doi:10.3934/amc.2022082

Article Contents

2024, Volume 18, Issue 5: 1216-1258. Doi: 10.3934/amc.2022082

This issue Previous Article $ \mathbb{Z}_{p^r}\mathbb{Z}_{p^s}\mathbb{Z}_{p^t} $-additive cyclic codes Next Article Improved lower bounds for self-dual codes over $ \mathbb{F}_{11} $, $ \mathbb{F}_{13} $, $ \mathbb{F}_{17} $, $ \mathbb{F}_{19} $ and $ \mathbb{F}_{23} $

Concrete analysis of approximate ideal-SIVP to decision ring-LWE reduction

1.
University of Washington, USA
2.
Indraprastha Institute of Information Technology, India
3.
Indian Statistical Institute, India

^*Corresponding author: Palash Sarkar
^*Corresponding author: Palash Sarkar

Received: June 2022

Early access: October 2022

Published: October 2024

Abstract / Introduction Full Text(HTML) Figure(2) / Table(2) Related Papers Cited by

Abstract

A seminal 2013 paper by Lyubashevsky, Peikert, and Regev proposed basing post-quantum cryptography on ideal lattices and supported this proposal by giving a polynomial-time security reduction from the approximate Shortest Independent Vectors Problem (SIVP) to the Decision Learning With Errors (DLWE) problem in ideal lattices. We give a concrete analysis of this multi-step reduction. We find that the tightness gap in the reduction is so great as to vitiate any meaningful security guarantee, and we find reasons to doubt the feasibility in the foreseeable future of the quantum part of the reduction. In addition, when we make the reduction concrete it appears that the approximation factor in the SIVP problem is far larger than expected, a circumstance that causes the corresponding approximate-SIVP problem most likely not to be hard for proposed cryptosystem parameters. We also discuss implications for systems such as Kyber and SABER that are based on module-DLWE.

Keywords:

Mathematics Subject Classification: Primary: 94A60.

Citation:

Full Text(HTML)

Figure 1. Inputs and outputs of algorithms $ \mathcal{A}_1 $ to $ \mathcal{A}_5 $

Download: Full-size image PowerPoint slide

Figure 2. Inputs and outputs of algorithms $ \mathcal{A}_5 $ to $ \mathcal{A}_7 $ and distinguishers $ \mathcal{D}_1 $ and $ \mathcal{D}_2 $

Download: Full-size image PowerPoint slide

Table 1. For $ n = 2^{10} $ the lower bounds on $ \gamma $ and upper bounds on $ 2^{n/k} $ along with lower bounds on $ q $

$ \delta_2 $	$ 2^{-128} $	$ 2^{-50} $	$ 2^{-25} $
$ \gamma=2^k $	$ 2^{81.5} $	$ 2^{42.5} $	$ 2^{30} $
$ 2^{n/k} $	$ 2^{12} $	$ 2^{24} $	$ 2^{34} $
$ q $	$ 2^{76} $	$ 2^{37} $	$ 2^{34} $

| Show Table

DownLoad: CSV

Table 2. Pseudocode for algorithm $\mathcal{A}_7$ using distinguisher $\mathcal{D}_1$ as an oracle, as described in Section 4.4

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	E. Alkim, J. W. Bos, et al., $ {\sf FrodoKEM}$ : Learning With Errors Key Encapsulation Algorithm Specifications and Supporting Documentation, https://frodokem.org/files/FrodoKEM-specification-20210604.pdf, 2021, Accessed on April 28, 2022.
[2]	E. Alkim, L. Ducas, T. Pöppelmann and P. Schwabe, Post-quantum key exchange – a new hope, Cryptology ePrint Archive, (2015), https://ia.cr/2015/1092.
[3]	R. Avanzi, J. Bos, L. Ducas, et al., CRYSTALS-Kyber (version 3.02) – submission to round 3 of the NIST post-quantum project, specification document (update from august 2021), 2021-08-04, https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/Kyber-Round3.zip, accessed on September 19, 2022.
[4]	W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Math. Ann., 296 (1993), 625-635. doi: 10.1007/BF01445125.
[5]	M. Bellare, Practice-oriented provable-security, International Workshop on Information Security, 1396 (1997), 221-231.
[6]	D. J. Bernstein, Comparing proofs of security for lattice-based encryption, Cryptology ePrint Archive, (2019), 691, https://eprint.iacr.org/2019/691.
[7]	D. J. Bernstein and T. Lange, Non-randomness of S-unit lattices, Cryptology ePrint Archive, (2021), 1428, https://eprint.iacr.org/2021/1428.
[8]	J. W. Bos, C. Costello, M. Naehrig and D. Stebila, Post-quantum key exchange for the TLS protocol from the ring learning with errors problem, In IEEE Symposium on Security and Privacy, IEEE Computer Society, (2015), 553-570.
[9]	J. W. Bos, L. Ducas, E. Kiltz, et al., In IEEE European Symposium on Security and Privacy, EuroS & P, (2018), 353-367.
[10]	Z. Brakerski, A. Langlois, C. Peikert, O. Regev and Damien Stehlé, Classical hardness of learning with errors, STOC'13—Proceedings of the 2013 ACM Symposium on Theory of Computing, (2013), 575-584. doi: 10.1145/2488608.2488680.
[11]	G. Casella and R. L. Berger, Statistical Inference, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1990.
[12]	S. Chatterjee, N. Koblitz, A. Menezes and P. Sarkar, Another look at tightness II: Practical issues in cryptography, Paradigms in Cryptology - Mycrypt 2016, 10311 (2016), 21-55.
[13]	R. Cramer, L. Ducas and B. Wesolowski, Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time, J. ACM, 68 (2021), Art. 8, 26 pp. doi: 10.1145/3431725.
[14]	J.-P. D'Anvers, A. Karmakar, S. S. Roy and F. Vercauteren, Saber:Module-lwr based key exchange, cpa-secure encryption and cca-secure KEM, Progress in Cryptology—AFRICACRYPT 2018, 10831 (2018), 282-305. doi: 10.1007/978-3-319-89339-6_16.
[15]	L. Ducas and A. Durmus, Ring-LWE in polynomial rings, In Public Key Cryptography—PKC 2012, 7293, (2012), 34-51. doi: 10.1007/978-3-642-30057-8_3.
[16]	L. Ducas, E. Kiltz, et al., CRYSTALS-Dilithium–algorithm specifications and supporting documentation (version 3.1), specification document (update from february 2021), 2021-02-08., Accessed on September 19, 2022. https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/Dilithium-Round3.zip
[17]	F. Gates, Reduction-respecting parameters for lattice-based cryptosystems, Masters Thesis, McMaster University, 2018, https://macsphere.mcmaster.ca/bitstream/11375/24466/2/gates_fletcher_m_finalsubmission2018october_msc.pdf.
[18]	O. Goldreich and S. Goldwasser, On the limits of nonapproximability of lattice problems, J. Comput. Syst. Sci., 60 (2000), 540-563. doi: 10.1006/jcss.1999.1686.
[19]	T. Häner, M. Roetteler and K. M. Svore, Factoring using $2n+2$ qubits with Toffoli based modular multiplication, Quantum Inf. Comput., 17 (2017), 673-684, https://arXiv.org/abs/1611.07995. doi: 10.26421/QIC17.7-8-7.
[20]	W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58 (1963), 13-30. doi: 10.1080/01621459.1963.10500830.
[21]	J. Hoffstein, J. Pipher and J. H. Silverman, NTRU:A ring-based public key cryptosystem, Algorithmic Number Theory, 1423 (1998), 267-288. doi: 10.1007/BFb0054868.
[22]	T. Laarhoven, M. Mosca and J. van de Pol, Finding shortest lattice vectors faster using quantum search, Des. Codes Cryptogr., 77 (2015), 375-400. doi: 10.1007/s10623-015-0067-5.
[23]	A. Langlois and D. Stehlé, Worst-case to average-case reductions for module lattices, Des. Codes Cryptogr., 75 (2015), 565-599. doi: 10.1007/s10623-014-9938-4.
[24]	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.
[25]	D. Micciancio, Lattice algorithms and applications: Basis reduction, 2014, Accessed on February 8, 2022, https://cseweb.ucsd.edu/classes/sp14/cse206A-a/lec5.pdf
[26]	D. Micciancio and S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective, The Kluwer International Series in Engineering and Computer Science, 671. Kluwer Academic Publishers, Boston, MA, 2002. doi: 10.1007/978-1-4615-0897-7.
[27]	M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2010.
[28]	C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract, STOC'09—Proceedings of the 2009 ACM, (2009), 333-342.
[29]	C. Peikert, A decade of lattice cryptography, Found. Trends Theor. Comput. Sci., 10 (2016), 283-424. doi: 10.1561/0400000074.
[30]	C. Peikert and Z. Pepin, Algebraically structured LWE, revisited, Theory of Cryptography, 11891 (2019), 1-23. doi: 10.1007/978-3-030-36030-6_1.
[31]	C. Peikert, O. Regev and N. Stephens-Davidowitz, Pseudorandomness of ring-LWE for any ring and modulus, In STOC'17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, (2017), 461-473. doi: 10.1145/3055399.3055489.
[32]	C. Peikert, O. Regev and N. Stephens-Davidowitz, Pseudorandomness of ring-LWE for any ring and modulus, IACR Cryptol. ePrint Arch., 2017, version dated 6 June, 2020, https://eprint.iacr.org/2017/258.
[33]	O. Regev, Lattices in computer science: Average-case hardness, Accessed on February 8, 2022, 2004, https://cims.nyu.edu/ regev/teaching/lattices_fall_2004/ln/averagecase.pdf.
[34]	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.
[35]	O. Regev, The learning with errors problem (invited survey), In Computational Complexity Conference, IEEE Computer Society, (2010), 191-204.
[36]	M. Roetteler, M. Naehrig, K. M. Svore and K. E. Lauter, Quantum resource estimates for computing elliptic curve discrete logarithms, Advances in Cryptology—ASIACRYPT 2017, 10625 (2017), 241-270. doi: 10.1007/978-3-319-70697-9_9.
[37]	P. Sarkar and S. Singha, Classical reduction of gap SVP to LWE: A concrete security analysis, Advances in Mathematics of Communications, 2021. doi: 10.3934/amc.2021004.
[38]	P. Sarkar and S. Singha, Verifying solutions to LWE with implications for concrete security, Adv. Math. Commun., 15 (2021), 257-266. doi: 10.3934/amc.2020057.
[39]	D. Stehlé and R. Steinfeld, Making NTRU as secure as worst-case problems over ideal lattices, Advances in cryptology—EUROCRYPT 2011, 6632 (2011), 27-47. doi: 10.1007/978-3-642-20465-4_4.
[40]	D. Stehlé, R. Steinfeld, K. Tanaka and K. Xagawa, Efficient public key encryption based on ideal lattices, Advances in Cryptology—ASIACRYPT 2009, 5912 (2009), 617-635. doi: 10.1007/978-3-642-10366-7_36.
[41]	NTRU Prime Risk-Management Team, Risks of lattice KEMs, 2021. https://ntruprime.cr.yp.to/latticerisks-20211031.pdf, accessed on February 18, 2022.
[42]	Y. Yu, G. Xu and X. Wang, Provably secure NTRU instances over prime cyclotomic rings, Public-key Cryptography—PKC 2017, 10174 (2017), 409-434. doi: 10.1007/978-3-662-54365-8_17.