An experimental study of Kannan’s embedding technique for the search LWE problem. (English) Zbl 1452.94089

Qing, Sihan (ed.) et al., Information and communications security. 19th international conference, ICICS 2017, Beijing, China, December 6–8, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10631, 541-553 (2018).
Summary: The learning with errors (LWE) problem is considered as one of the most compelling candidates as the security base for the post-quantum cryptosystems. For the application of LWE based cryptographic schemes, the concrete parameters are necessary: the length \(n\) of secret vector, the moduli \(q\) and the deviation \(\sigma \). In the middle of 2016, Germany TU Darmstadt group initiated the LWE Challenge in order to assess the hardness of LWE problems. There are several approaches to solve the LWE problem via reducing LWE to other lattice problems. Xu et al.’s group solved some LWE Challenge instances using Liu and Nguyen’s adapted enumeration technique (reducing LWE to BDD problem) [14] and they published this result at ACNS 2017 [23]. In this paper, we study Kannan’s embedding technique (reducing LWE to unique SVP problem) to solve the LWE problem in the aspect of practice. The lattice reduction algorithm we use is the progressive BKZ [2, 3]. At first, from our experimental results we can intuitively observe that the embedding technique is more efficient with the embedding factor \(M\) closer to 1. Then especially for the cases of \(\sigma /q = 0.005\), we will give an preliminary analysis for the runtime and give an estimation for the proper size of parameters. Moreover, our experimental results show that for \(n\ge 55\) and the fixed \(\sigma /q = 0.005\), the embedding technique with progressive BKZ is more efficient than Xu et al.’s implementation of the enumeration algorithm in [21, 23]. Finally, by our parameter setting, we succeeded in solving the LWE Challenge over \((n,\sigma /q)=(70,0.005)\) using \(2^{16.8}\) s (32.73 single core hours).
(The numbers in brackets refer to the bibliography.)
For the entire collection see [Zbl 1435.68039].


94A60 Cryptography


Full Text: DOI


[1] Albrecht, M.R., Fitzpatrick, R., Göpfert, F.: On the efficacy of solving LWE by reduction to unique-SVP. In: Lee, H.-S., Han, D.-G. (eds.) ICISC 2013. LNCS, vol. 8565, pp. 293-310. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-12160-4_18 · Zbl 1368.94082
[2] Aono, Y., Wang, Y., Hayashi, T., Takagi, T.: Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 789-819. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_30 · Zbl 1385.94007
[3] The progressive BKZ code. http://www2.nict.go.jp/security/pbkzcode/
[4] Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. In: Mehlhorn, K. (ed.) STACS 1985. LNCS, vol. 182, pp. 13-20. Springer, Heidelberg (1985). https://doi.org/10.1007/BFb0023990 · Zbl 0593.68030
[5] Buchmann, J., Büscher, N., Göpfert, F., Katzenbeisser, S., Krämer, J., Micciancio, D., Siim, S., Vredendaal, C., Walter, M.: Creating cryptographic challenges using multi-party computation: the LWE challenge. In: AsiaPKC 2016, pp. 11-20 (2016)
[6] Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1-20. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_1 · Zbl 1227.94037
[7] Domich, P., Kannan, R., Trotter, L.: Hermite normal form computation using modulo determinant arithmetic. Math. Oper. Res. 12, 50-59 (1987) · Zbl 0624.65036
[8] Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31-51. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_3 · Zbl 1149.94314
[9] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC 2008, pp. 197-206 (2008) · Zbl 1231.68124
[10] Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415-440 (1987) · Zbl 0639.90069
[11] Kirchner, P., Fouque, P.-A.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 43-62. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_3 · Zbl 1336.94058
[12] Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515-534 (1982) · Zbl 0488.12001
[13] Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 577-594. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_34 · Zbl 1252.94084
[14] Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: an update. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 293-309. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36095-4_19 · Zbl 1312.94070
[15] Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319-339. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19074-2_21. Decoding Radius and DMT Optimality, ISIT2011, pp. 1106-1110 (2011) · Zbl 1284.94088
[16] Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography 2009, pp. 147-191. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-88702-7_5 · Zbl 1161.81324
[17] Victor Shoup’s NTL library. http://www.shoup.net/ntl/
[18] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005, pp. 84-93 (2005) · Zbl 1192.94106
[19] Schnorr, C.P.: Lattice reduction by random sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 145-156. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36494-3_14 · Zbl 1035.68113
[20] Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181-199 (1994) · Zbl 0829.90099
[21] TU Darmstadt Learning With Errors Challenge. https://www.latticechallenge.org/lwe_challenge/challenge.php
[22] Xu, R.: Private communication (2017)
[23] Xu, R.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.