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:
https://lup.lub.lu.se/record/83815ef3-610c-4764-a308-17871218ea81
- author
- Guo, Qian
LU
; Johansson, Thomas
LU
; Mårtensson, Erik
LU
and Stankovski, Paul
LU
- organization
- publishing date
- 2017-08-13
- 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-70693-1
- 978-3-319-70694-8
- 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
- 2025-01-07 18:47:06
@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-70693-1}},
issn = {{0302-9743}},
keywords = {{LWE; BKW; Coded-BKW; Lattice codes; Lattice sieving}},
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}},
}