Abstract
The Learning with Errors (LWE) problem is one of the most important computational problems in modern lattice-based cryptography. It can be viewed as a Bounded Distance Decoding (BDD) problem, which can be reduced to the unique Shortest Vector Problem (uSVP). The standard way to reduce BDD to uSVP is via Kannan’s embedding. At ICALP 2016, Bai, Stehlé, and Wen presented an improved theoretical reduction from BDD to uSVP which uses sparsification techniques. So far, the implications of this improved reduction and the use of sparsification to the hardness of LWE have not been studied. In this work, we consider a sparsified embedding attack on LWE which is deduced from the Bai–Stehlé–Wen reduction. In particular, we analyze its performance under the so-called 2016 estimate introduced at USENIX 2016 by Alkim, Ducas, Pöppelmann, and Schwabe and analyzed at ASIACRYPT 2017 by Albrecht, Göpfert, Virdia, and Wunderer. Our results suggest that in general the sparsified embedding attack does not yield a better attack on LWE in practice than Kannan’s embedding. However, for certain parameter sets and scenarios with a reasonable amount of computing clusters, the use of sparsification may be beneficial.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: Holz, T., Savage, S. (eds.) 25th USENIX Security Symposium, USENIX Security 16, pp. 327–343. USENIX Association (2016)
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
Albrecht, M.R., Göpfert, F., Virdia, F., Wunderer, T.: Revisiting the expected cost of solving uSVP and applications to LWE. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 297–322. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_11
Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of Learning with Errors. J. Math. Cryptol. 9(3), 169–203 (2015)
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
Bai, S., Galbraith, S.D.: An improved compression technique for signatures based on learning with errors. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 28–47. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-04852-9_2
Bai, S., Stehlé, D., Wen, W.: Improved reduction from the bounded distance decoding problem to the unique shortest vector problem in lattices. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) ICALP 2016, Volume 55 of LIPIcs, pp. 76:1–76:12. Schloss Dagstuhl, July 2016
Chen, Y.: Réduction de réseau et sécurité concrete du chiffrement completement homomorphe. Ph.D. thesis, ENS-Lyon, France (2013)
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
Dadush, D., Kun, G.: Lattice sparsification and the approximate closest vector problem. In: Khanna, S. (ed.) 24th SODA, pp. 1088–1102. ACM-SIAM, January 2013
Dadush, D., Regev, O., Stephens-Davidowitz, N.: On the closest vector problem with a distance guarantee. In: IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11–13, 2014, pp. 98–109. IEEE Computer Society (2014)
Gentry, C., Sahai, A., Waters, B.: homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_5
Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987)
Khot, S.: Hardness of approximating the shortest vector problem in high Lp norms. In: 44th FOCS, pp. 290–297. IEEE Computer Society Press, October 2003
Khot, S.: Hardness of approximating the shortest vector problem in lattices. In: 45th FOCS, pp. 126–135. IEEE Computer Society Press, October 2004
Liu, Y.-K., Lyubashevsky, V., Micciancio, D.: On bounded distance decoding for general lattices. In: Díaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX/RANDOM-2006. LNCS, vol. 4110, pp. 450–461. Springer, Heidelberg (2006). https://doi.org/10.1007/11830924_41
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
Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. Cryptology ePrint Archive, Report 2010/613 (2010). http://eprint.iacr.org/2010/613
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
Liu, M., Wang, X., Guangwu, X., Zheng, X.: A note on BDD problems with \(\lambda \)\({}_{\text{2 }}\)-gap. Inf. Process. Lett. 114(1–2), 9–12 (2014)
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 140 (2009)
Stephens-Davidowitz, N.: Discrete Gaussian sampling reduces to CVP and SVP. In: Krauthgamer, R. (ed.) 27th SODA, pp. 1748–1764. ACM-SIAM, January 2016
Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199 (1994)
Vardy, A.: Algorithmic complexity in coding theory and the minimum distance problem (invited session). In: 29th ACM STOC, pp. 92–109. ACM Press, May 1997
Wang, Y., Aono, Y., Takagi, T.: An experimental study of kannan’s embedding technique for the search LWE problem. In: Qing, S., Mitchell, C., Chen, L., Liu, D. (eds.) ICICS 2017. LNCS, vol. 10631, pp. 541–553. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89500-0_47
Acknowledgments
This work has been supported by JSPS KAKENHI Grant Number JP17J01987 and by the DFG as part of project P1 within the CRC 1119 CROSSING.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Wang, Y., Wunderer, T. (2018). Revisiting the Sparsification Technique in Kannan’s Embedding Attack on LWE. In: Su, C., Kikuchi, H. (eds) Information Security Practice and Experience. ISPEC 2018. Lecture Notes in Computer Science(), vol 11125. Springer, Cham. https://doi.org/10.1007/978-3-319-99807-7_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-99807-7_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99806-0
Online ISBN: 978-3-319-99807-7
eBook Packages: Computer ScienceComputer Science (R0)