Advanced

Coded-BKW with Sieving: An Improved Algorithm for Solving the LWE Problem

Guo, Qian LU ; Johansson, Thomas LU ; Mårtensson, Erik LU and Stankovski, Paul LU (2017) 23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017 In Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
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 = n^2 and noise level \sigma = n^1.5/(\sqrt{2\pi} \log_2^2 n), the asymptotic complexity is 2^{0.895n} in the standard setting, improving on the previously best known complexity of roughly 2^{0.930n}. Also for concrete parameter instances, improved performance is indicated.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
in press
subject
keywords
LWE, BKW, Coded-BKW, Lattice codes, Lattice sieving
in
Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
publisher
Springer Verlag
conference name
23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017
language
English
LU publication?
yes
id
83815ef3-610c-4764-a308-17871218ea81
date added to LUP
2017-08-16 14:48:47
date last changed
2017-08-16 15:46:56
@inproceedings{83815ef3-610c-4764-a308-17871218ea81,
  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 = n^2 and noise level \sigma = n^1.5/(\sqrt{2\pi} \log_2^2 n), the asymptotic complexity is 2^{0.895n} in the standard setting, improving on the previously best known complexity of roughly 2^{0.930n}. Also for concrete parameter instances, improved performance is indicated.},
  author       = {Guo, Qian and Johansson, Thomas and Mårtensson, Erik and Stankovski, Paul},
  booktitle    = {Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings},
  keyword      = {LWE,BKW,Coded-BKW,Lattice codes,Lattice sieving},
  language     = {eng},
  month        = {08},
  publisher    = {Springer Verlag},
  title        = {Coded-BKW with Sieving: An Improved Algorithm for Solving the LWE Problem},
  year         = {2017},
}