Quantum key search for ternary LWE. (English) Zbl 1489.81023
Cheon, Jung Hee (ed.) et al., Post-quantum cryptography. 12th international workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12841, 117-132 (2021).
Summary: Ternary LWE, i.e., LWE with coefficients of the secret and the error vectors taken from \(\{-1, 0, 1\}\), is a popular choice among NTRU-type cryptosystems and some signatures schemes like BLISS and GLP.
In this work we consider quantum combinatorial attacks on ternary LWE. Our algorithms are based on the quantum walk framework of Magniez-Nayak-Roland-Santha. At the heart of our algorithms is a combinatorial tool called the representation technique that appears in algorithms for the subset sum problem. This technique can also be applied to ternary LWE resulting in faster attacks. The focus of this work is quantum speed-ups for such representation-based attacks on LWE.
When expressed in terms of the search space \(\mathcal{S}\) for LWE keys, the asymptotic complexity of the representation attack drops from \(\mathcal{S}^{0.24} \) (classical) down to \(\mathcal{S}^{0.19} \) (quantum). This translates into noticeable attack’s speed-ups for concrete NTRU instantiations like NTRU-HRSS [CHES’17] and NTRU Prime [SAC’17].
Our algorithms do not undermine current security claims for NTRU or other ternary LWE based schemes, yet they can lay ground for improvements of the combinatorial subroutines inside hybrid attacks on LWE.
For the entire collection see [Zbl 1482.94004].
In this work we consider quantum combinatorial attacks on ternary LWE. Our algorithms are based on the quantum walk framework of Magniez-Nayak-Roland-Santha. At the heart of our algorithms is a combinatorial tool called the representation technique that appears in algorithms for the subset sum problem. This technique can also be applied to ternary LWE resulting in faster attacks. The focus of this work is quantum speed-ups for such representation-based attacks on LWE.
When expressed in terms of the search space \(\mathcal{S}\) for LWE keys, the asymptotic complexity of the representation attack drops from \(\mathcal{S}^{0.24} \) (classical) down to \(\mathcal{S}^{0.19} \) (quantum). This translates into noticeable attack’s speed-ups for concrete NTRU instantiations like NTRU-HRSS [CHES’17] and NTRU Prime [SAC’17].
Our algorithms do not undermine current security claims for NTRU or other ternary LWE based schemes, yet they can lay ground for improvements of the combinatorial subroutines inside hybrid attacks on LWE.
For the entire collection see [Zbl 1482.94004].
MSC:
| 81P94 | Quantum cryptography (quantum-theoretic aspects) |
| 94A60 | Cryptography |
| 94A62 | Authentication, digital signatures and secret sharing |
References:
| [1] | Albrecht, MR; Curtis, BR; Deo, A.; Davidson, A.; Player, R.; Postlethwaite, EW; Virdia, F.; Wunderer, T.; Catalano, D.; De Prisco, R., Estimate All the LWE, NTRU Schemes!, Security and Cryptography for Networks, 351-367 (2018), Cham: Springer, Cham · Zbl 1517.94049 · doi:10.1007/978-3-319-98113-0_19 |
| [2] | Ambainis, A., Quantum walk algorithm for element distinctness, SIAM J. Comput., 37, 1, 210-239 (2007) · Zbl 1134.81010 · doi:10.1137/S0097539705447311 |
| [3] | Bonnetain, X.; Bricout, R.; Schrottenloher, A.; Shen, Y.; Moriai, S.; Wang, H., improved classical and quantum algorithms for subset-sum, Advances in Cryptology - ASIACRYPT 2020, 633-666 (2020), Cham: Springer, Cham · Zbl 1521.81056 · doi:10.1007/978-3-030-64834-3_22 |
| [4] | Becker, A.; Coron, J-S; Joux, A.; Paterson, KG, Improved generic algorithms for hard knapsacks, Advances in Cryptology - EUROCRYPT 2011, 364-385 (2011), Heidelberg: Springer, Heidelberg · Zbl 1281.94014 · doi:10.1007/978-3-642-20465-4_21 |
| [5] | Bernstein, DJ; Chuengsatiansup, C.; Lange, T.; van Vredendaal, C.; Adams, C.; Camenisch, J., NTRU prime: reducing attack surface at low cost, Selected Areas in Cryptography, 235-260 (2018), Cham: Springer, Cham · Zbl 1384.94034 · doi:10.1007/978-3-319-72565-9_12 |
| [6] | Buhrman, H., Quantum algorithms for element distinctness, SIAM J. Comput., 34, 6, 1324-1330 (2005) · Zbl 1081.68029 · doi:10.1137/S0097539702402780 |
| [7] | Bos, W.J., et al.: Crystals - kyber: a CCA-secure module-lattice-based kem. In: EuroS&P, pp. 353-367 (2018) |
| [8] | Bai, S.; Galbraith, SD; Susilo, W.; Mu, Y., Lattice decoding attacks on binary LWE, Information Security and Privacy, 322-337 (2014), Cham: Springer, Cham · Zbl 1337.94020 · doi:10.1007/978-3-319-08344-5_21 |
| [9] | Brassard, G.; Høyer, P.; Mosca, M.; Tapp, A., Quantum amplitude amplification and estimation, Quantum Comput. Inf., 305, 53-74 (2002) · Zbl 1063.81024 · doi:10.1090/conm/305 |
| [10] | Bernstein, DJ; Jeffery, S.; Lange, T.; Meurer, A.; Gaborit, P., Quantum algorithms for the subset-sum problem, PQCrypto 2013, 16-33 (2013), Heidelberg: Springer, Heidelberg · Zbl 1295.68127 · doi:10.1007/978-3-642-38616-9_2 |
| [11] | Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC. ACM Press, pp. 575-584 (2013) · Zbl 1293.68159 |
| [12] | Ducas, L.; Durmus, A.; Lepoint, T.; Lyubashevsky, V.; Canetti, R.; Garay, JA, Lattice Signatures and Bimodal Gaussians, Advances in Cryptology - CRYPTO 2013, 40-56 (2013), Heidelberg: Springer, Heidelberg · Zbl 1310.94141 · doi:10.1007/978-3-642-40041-4_3 |
| [13] | Guo, Q.; Johansson, T.; Stankovski, P.; Gennaro, R.; Robshaw, M., Coded-BKW: solving LWE using lattice codes, Advances in Cryptology - CRYPTO 2015, 23-42 (2015), Heidelberg: Springer, Heidelberg · Zbl 1336.94051 · doi:10.1007/978-3-662-47989-6_2 |
| [14] | Güneysu, T.; Lyubashevsky, V.; Pöppelmann, T.; Prouff, E.; Schaumont, P., Practical lattice-based cryptography: a signature scheme for embedded systems, Cryptographic Hardware and Embedded Systems - CHES 2012, 530-547 (2012), Heidelberg: Springer, Heidelberg · Zbl 1294.94050 · doi:10.1007/978-3-642-33027-8_31 |
| [15] | Grover, L.K.: A fast quantum mechanical algorithm for database search. In: 28th ACM STOC, pp. 212-219. ACM Press (1996) · Zbl 0922.68044 |
| [16] | Howgrave-Graham, N., Silverman, J.H., Whyte, W.: A meet-in-the-middle attack on an NTRU private key, Technical report, NTRU Cryptosystems, June 2003. Report (2003) |
| [17] | Howgrave-Graham, N.; Joux, A.; Gilbert, H., New generic algorithms for hard knapsacks, Advances in Cryptology - EUROCRYPT 2010, 235-256 (2010), Heidelberg: Springer, Heidelberg · Zbl 1280.94069 · doi:10.1007/978-3-642-13190-5_12 |
| [18] | Helm, A., May, A.: Subset sum quantumly in \(1.17^n\) .In: 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 111, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp. 5:1-5:15 (2018) |
| [19] | Howgrave-Graham, N.; Menezes, A., A hybrid lattice-reduction and meet-in-the-middle attack against NTRU, Advances in Cryptology - CRYPTO 2007, 150-169 (2007), Heidelberg: Springer, Heidelberg · Zbl 1215.94053 · doi:10.1007/978-3-540-74143-5_9 |
| [20] | Hoffstein, J.; Pipher, J.; Silverman, JH; Buhler, JP, NTRU: a ring-based public key cryptosystem, International Algorithmic Number Theory Symposium, Springer, 267-288 (1998), Berlin, Heidelberg: Springer, Berlin, Heidelberg · Zbl 1067.94538 · doi:10.1007/BFb0054868 |
| [21] | Hülsing, A.; Rijneveld, J.; Schanck, J.; Schwabe, P.; Fischer, W.; Homma, N., High-speed key encapsulation from NTRU, Cryptographic Hardware and Embedded Systems - CHES 2017, 232-252 (2017), Cham: Springer, Cham · Zbl 1440.94058 · doi:10.1007/978-3-319-66787-4_12 |
| [22] | Kirchner, P.; Fouque, P-A; Gennaro, R.; Robshaw, M., An improved BKW algorithm for LWE with applications to cryptography and lattices, Advances in Cryptology - CRYPTO 2015, 43-62 (2015), Heidelberg: Springer, Heidelberg · Zbl 1336.94058 · doi:10.1007/978-3-662-47989-6_3 |
| [23] | Kachigar, G.; Tillich, J-P; Lange, T.; Takagi, T., Quantum information set decoding algorithms, Post-Quantum Cryptography, 69-89 (2017), Cham: Springer, Cham · Zbl 1429.94060 · doi:10.1007/978-3-319-59879-6_5 |
| [24] | Lyubashevsky, V.; Peikert, C.; Regev, O.; Gilbert, H., On ideal lattices and learning with errors over rings, Advances in Cryptology - EUROCRYPT 2010, 1-23 (2010), Heidelberg: Springer, Heidelberg · Zbl 1279.94099 · doi:10.1007/978-3-642-13190-5_1 |
| [25] | Lyubashevsky, V.; Pointcheval, D.; Johansson, T., Lattice signatures without trapdoors, Advances in Cryptology - EUROCRYPT 2012, 738-755 (2012), Heidelberg: Springer, Heidelberg · Zbl 1295.94111 · doi:10.1007/978-3-642-29011-4_43 |
| [26] | May, A.: How to meet ternary lwe keys, Cryptology ePrint Archive, Report 2021/216 (2021). https://eprint.iacr.org/2021/216 |
| [27] | Magniez, F.; Nayak, A.; Roland, J.; Santha, M., Search via quantum walk, SIAM J. Comput., 40, 1, 142-164 (2011) · Zbl 1223.05289 · doi:10.1137/090745854 |
| [28] | Nivasch, G., Cycle detection using a stack, Inf. Process. Lett., 90, 135-140 (2004) · Zbl 1178.68648 · doi:10.1016/j.ipl.2004.01.016 |
| [29] | Prest, T., et al.: Falcon, Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions |
| [30] | Pollard, JM, A Monte Carlo method for factorization, BIT Numer. Math., 15, 331-334 (1975) · Zbl 0312.10006 · doi:10.1007/BF01933667 |
| [31] | Regev, O.: New lattice based cryptographic constructions. In: 35th ACM STOC, pp. 407-416. ACM Press (2003) · Zbl 1192.94105 |
| [32] | Stehlé, D.; Steinfeld, R.; Tanaka, K.; Xagawa, K.; Matsui, M., Efficient public key encryption based on ideal lattices, Advances in Cryptology - ASIACRYPT 2009, 617-635 (2009), Heidelberg: Springer, Heidelberg · Zbl 1267.94132 · doi:10.1007/978-3-642-10366-7_36 |
| [33] | Tani, S., In improved claw finding algorithm using quantum walk, Math. Found. Comput. Sci., 2007, 536-547 (2007) · Zbl 1147.81302 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
