User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Coded-BKW with Sieving

Primary tabs

Guo, Qian [Lund University] Johansson, Thomas [Lund University] Mårtensson, Erik [Lund University] Stankovski, Paul [UCL]

The Learning with Errors problem (LWE) has become a central topic in recent cryptographic research. In this paper, we present a new solving algorithm combining important ideas from previous work on improving the BKW algorithm and ideas from sieving in lattices. The new algorithm is analyzed and demonstrates an improved asymptotic performance. For Regev parameters q = n2 and noise level (Forumula presented), the asymptotic complexity is 2 0.895 n in the standard setting, improving on the previously best known complexity of roughly 2 0.930 n. Also for concrete parameter instances, improved performance is indicated.

Document type Communication à un colloque (Conference Paper) – Présentation orale sans comité de sélection
Access type Accès restreint
Publication date 2017
Language Anglais
Conference "Annual international conference on theory and application of cryptology and information security, ASIACRYPT", Hong Kong (du 03/12/2017 au 07/12/2017)
Journal information "Lecture Notes in Computer Science" - Vol. 10624 LNCS, p. 323-346 (2017)
Peer reviewed yes
issn 03029743
Publisher Springer Verlag
Publication status Publié
Affiliation UCL - SST/ICTM/ELEN - Pôle en ingénierie électrique
Links
  1. Ajtai Miklós, Kumar Ravi, Sivakumar D., A sieve algorithm for the shortest lattice vector problem, 10.1145/380752.380857
  2. Albrecht, M., Cid, C., Faugere, J.C., Robert, F., Perret, L.: Algebraic algorithms for LWE problems. Cryptology ePrint Archive, report 2014/1018 (2014)
  3. Albrecht Martin R., Cid Carlos, Faugère Jean-Charles, Fitzpatrick Robert, Perret Ludovic, On the complexity of the BKW algorithm on LWE, 10.1007/s10623-013-9864-x
  4. Albrecht Martin R., Faugère Jean-Charles, Fitzpatrick Robert, Perret Ludovic, Lazy Modulus Switching for the BKW Algorithm on LWE, Public-Key Cryptography – PKC 2014 (2014) ISBN:9783642546303 p.429-445, 10.1007/978-3-642-54631-0_25
  5. Albrecht Martin R., Fitzpatrick Robert, Göpfert Florian, On the Efficacy of Solving LWE by Reduction to Unique-SVP, Information Security and Cryptology -- ICISC 2013 (2014) ISBN:9783319121598 p.293-310, 10.1007/978-3-319-12160-4_18
  6. Albrecht Martin R., Player Rachel, Scott Sam, On the concrete hardness of Learning with Errors, 10.1515/jmc-2015-0016
  7. Applebaum Benny, Cash David, Peikert Chris, Sahai Amit, Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems, Advances in Cryptology - CRYPTO 2009 (2009) ISBN:9783642033551 p.595-618, 10.1007/978-3-642-03356-8_35
  8. Arora Sanjeev, Ge Rong, New Algorithms for Learning in Presence of Errors, Automata, Languages and Programming (2011) ISBN:9783642220050 p.403-415, 10.1007/978-3-642-22006-7_34
  9. Becker Anja, Ducas Léo, Gama Nicolas, Laarhoven Thijs, New directions in nearest neighbor searching with applications to lattice sieving, 10.1137/1.9781611974331.ch2
  10. Becker Anja, Gama Nicolas, Joux Antoine, A sieve algorithm based on overlattices, 10.1112/s1461157014000229
  11. Bernstein Daniel J., Lange Tanja, Never Trust a Bunny, Radio Frequency Identification. Security and Privacy Issues (2013) ISBN:9783642361395 p.137-148, 10.1007/978-3-642-36140-1_10
  12. Blum Avrim, Kalai Adam, Wasserman Hal, Noise-tolerant learning, the parity problem, and the statistical query model, 10.1145/792538.792543
  13. Bogos Sonia, Vaudenay Serge, Optimization of $$\mathsf {LPN}$$ Solving Algorithms, Advances in Cryptology – ASIACRYPT 2016 (2016) ISBN:9783662538869 p.703-728, 10.1007/978-3-662-53887-6_26
  14. Brakerski Zvika, Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP, Lecture Notes in Computer Science (2012) ISBN:9783642320088 p.868-886, 10.1007/978-3-642-32009-5_50
  15. Brakerski Zvika, Vaikuntanathan Vinod, Efficient Fully Homomorphic Encryption from (Standard) LWE, 10.1109/focs.2011.12
  16. Brakerski Zvika, Vaikuntanathan Vinod, Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages, Advances in Cryptology – CRYPTO 2011 (2011) ISBN:9783642227912 p.505-524, 10.1007/978-3-642-22792-9_29
  17. Chen Yuanmi, Nguyen Phong Q., BKZ 2.0: Better Lattice Security Estimates, Lecture Notes in Computer Science (2011) ISBN:9783642253843 p.1-20, 10.1007/978-3-642-25385-0_1
  18. Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups, vol. 290. Springer, Heidelberg (2013)
  19. Dubiner Moshe, Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem, 10.1109/tit.2010.2050814
  20. Duc Alexandre, Tramèr Florian, Vaudenay Serge, Better Algorithms for LWE and LWR, Advances in Cryptology -- EUROCRYPT 2015 (2015) ISBN:9783662467992 p.173-202, 10.1007/978-3-662-46800-5_8
  21. Gentry Craig, Sahai Amit, Waters Brent, Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based, Advances in Cryptology – CRYPTO 2013 (2013) ISBN:9783642400407 p.75-92, 10.1007/978-3-642-40041-4_5
  22. Guo Qian, Johansson Thomas, Löndahl Carl, Solving LPN Using Covering Codes, Lecture Notes in Computer Science (2014) ISBN:9783662456101 p.1-20, 10.1007/978-3-662-45611-8_1
  23. Guo Qian, Johansson Thomas, Stankovski Paul, Coded-BKW: Solving LWE Using Lattice Codes, Lecture Notes in Computer Science (2015) ISBN:9783662479889 p.23-42, 10.1007/978-3-662-47989-6_2
  24. Hanrot Guillaume, Pujol Xavier, Stehlé Damien, Algorithms for the Shortest and Closest Lattice Vector Problems, Lecture Notes in Computer Science (2011) ISBN:9783642209000 p.159-190, 10.1007/978-3-642-20901-7_10
  25. Herold, G., Kirshanova, E., May, A.: On the asymptotic complexity of solving LWE. IACR Cryptology ePrint Archive 2015, 1222 (2015). http://eprint.iacr.org/2015/1222
  26. Herold Gottfried, Kirshanova Elena, May Alexander, On the asymptotic complexity of solving LWE, 10.1007/s10623-016-0326-0
  27. Indyk Piotr, Motwani Rajeev, Approximate nearest neighbors : towards removing the curse of dimensionality, 10.1145/276698.276876
  28. Kirchner, P.: Improved generalized birthday attack. Cryptology ePrint Archive, report 2011/377 (2011). http://eprint.iacr.org/
  29. Kirchner Paul, Fouque Pierre-Alain, An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices, Lecture Notes in Computer Science (2015) ISBN:9783662479889 p.43-62, 10.1007/978-3-662-47989-6_3
  30. Laarhoven Thijs, Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing, Lecture Notes in Computer Science (2015) ISBN:9783662479889 p.3-22, 10.1007/978-3-662-47989-6_1
  31. Laarhoven Thijs, Mosca Michele, van de Pol Joop, Finding shortest lattice vectors faster using quantum search, 10.1007/s10623-015-0067-5
  32. Laarhoven Thijs, de Weger Benne, Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing, Progress in Cryptology -- LATINCRYPT 2015 (2015) ISBN:9783319221731 p.101-118, 10.1007/978-3-319-22174-8_6
  33. Levieil Éric, Fouque Pierre-Alain, An Improved LPN Algorithm, Lecture Notes in Computer Science (2006) ISBN:9783540380801 p.348-359, 10.1007/11832072_24
  34. Lindner Richard, Peikert Chris, Better Key Sizes (and Attacks) for LWE-Based Encryption, Topics in Cryptology – CT-RSA 2011 (2011) ISBN:9783642190735 p.319-339, 10.1007/978-3-642-19074-2_21
  35. Liu Mingjie, Nguyen Phong Q., Solving BDD by Enumeration: An Update, Topics in Cryptology – CT-RSA 2013 (2013) ISBN:9783642360947 p.293-309, 10.1007/978-3-642-36095-4_19
  36. May Alexander, Ozerov Ilya, On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes, Advances in Cryptology -- EUROCRYPT 2015 (2015) ISBN:9783662467992 p.203-228, 10.1007/978-3-662-46800-5_9
  37. Micciancio Daniele, Regev Oded, Lattice-based Cryptography, Post-Quantum Cryptography ISBN:9783540887010 p.147-191, 10.1007/978-3-540-88702-7_5
  38. Micciancio Daniele, Voulgaris Panagiotis, Faster exponential time algorithms for the shortest vector problem, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (2010) ISBN:9780898717013 p.1468-1480, 10.1137/1.9781611973075.119
  39. De Mulder Elke, Hutter Michael, Marson Mark E., Pearson Peter, Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA: extended version, 10.1007/s13389-014-0072-z
  40. Nguyen Phong Q., Vidick Thomas, Sieve algorithms for the shortest vector problem are practical, 10.1515/jmc.2008.009
  41. Pujol, X., Stehlé, D.: Solving the shortest lattice vector problem in time 2 $${}^{\text{2.465n}}$$ 2.465n . IACR Cryptology ePrint Archive 2009, 605 (2009). http://eprint.iacr.org/2009/605
  42. Regev Oded, On lattices, learning with errors, random linear codes, and cryptography, 10.1145/1568318.1568324
  43. Schnorr C. P., Euchner M., Lattice basis reduction: Improved practical algorithms and solving subset sum problems, 10.1007/bf01581144
  44. Wagner David, A Generalized Birthday Problem, Advances in Cryptology — CRYPTO 2002 (2002) ISBN:9783540440505 p.288-304, 10.1007/3-540-45708-9_19
  45. Wang Xiaoyun, Liu Mingjie, Tian Chengliang, Bi Jingguo, Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem, 10.1145/1966913.1966915
  46. Zhang Bin, Jiao Lin, Wang Mingsheng, Faster Algorithms for Solving LPN, Advances in Cryptology – EUROCRYPT 2016 (2016) ISBN:9783662498897 p.168-195, 10.1007/978-3-662-49890-3_7
  47. Zhang Feng, Pan Yanbin, Hu Gengran, A Three-Level Sieve Algorithm for the Shortest Vector Problem, Selected Areas in Cryptography -- SAC 2013 (2014) ISBN:9783662434130 p.29-47, 10.1007/978-3-662-43414-7_2
Bibliographic reference Guo, Qian ; Johansson, Thomas ; Mårtensson, Erik ; Stankovski, Paul. Coded-BKW with Sieving.Annual international conference on theory and application of cryptology and information security, ASIACRYPT (Hong Kong, du 03/12/2017 au 07/12/2017). In: Lecture Notes in Computer Science, Vol. 10624 LNCS, p. 323-346 (2017)
Permanent URL http://hdl.handle.net/2078.1/198095