Coded-BKW with Sieving

Guo, Qian;Johansson, Thomas;Mårtensson, Erik;Stankovski, Paul
(2017) Annual international conference on theory and application of cryptology and information security, ASIACRYPT — Location: Hong Kong (3.December.2017)

Files

document.pdf
  • Restricted Access
  • Adobe PDF
  • 580.39 KB
No access

Details

Authors
  • Guo, QianLund University
    Author
  • Johansson, ThomasLund University
    Author
  • Mårtensson, ErikLund University
    Author
  • Stankovski, PaulUCLouvain
    Author
Abstract
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Guo, Q., Johansson, T., Mårtensson, E., & Stankovski, P. (2017). Coded-BKW with Sieving. Lecture Notes in Computer Science, 10624 LNCS, 323-346. https://doi.org/10.1007/978-3-319-70694-8_12 (Original work published 2017)