Advanced

Coded-BKW with Sieving

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 Lecture Notes in Computer Science 10624. p.323-346
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
; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
LWE, BKW, Coded-BKW, Lattice codes, Lattice sieving
host publication
Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
series title
Lecture Notes in Computer Science
volume
10624
pages
323 - 346
publisher
Springer
conference name
23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017
conference location
Hong Kong, China
conference dates
2017-12-03 - 2017-12-07
external identifiers
  • scopus:85037824547
ISSN
0302-9743
ISBN
978-3-319-70694-8
978-3-319-70693-1
DOI
10.1007/978-3-319-70694-8_12
language
English
LU publication?
yes
id
83815ef3-610c-4764-a308-17871218ea81
date added to LUP
2017-08-16 14:48:47
date last changed
2020-10-27 02:35:32
@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},
  isbn         = {978-3-319-70694-8},
  issn         = {0302-9743},
  language     = {eng},
  month        = {08},
  pages        = {323--346},
  publisher    = {Springer},
  series       = {Lecture Notes in Computer Science},
  title        = {Coded-BKW with Sieving},
  url          = {http://dx.doi.org/10.1007/978-3-319-70694-8_12},
  doi          = {10.1007/978-3-319-70694-8_12},
  volume       = {10624},
  year         = {2017},
}