The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors
(2019) 2019 IEEE International Symposium on Information Theory p.2579-2583- Abstract
- The Learning with Errors problem (LWE) is one of the main candidates for post-quantum cryptography. At Asiacrypt 2017, coded-BKW with sieving, an algorithm combining the Blum-Kalai-Wasserman algorithm (BKW) with lattice sieving techniques, was proposed. In this paper, we improve that algorithm by using different reduction factors in different steps of the sieving part of the algorithm. In the Regev setting, where $q = n^2$ and $\sigma = n^{1.5}/(\sqrt{2\pi}\log_2^2 n)$, the asymptotic complexity is $2^{0.8917n}$, improving the previously best complexity of $2^{{0.8927n}}$. When a quantum computer is assumed or the number of samples is limited, we get a similar level of improvement.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/16992295-5f9a-4627-85bc-ee256fa7c415
- author
- Mårtensson, Erik LU
- organization
- publishing date
- 2019
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- IEEE International Symposium on Information Theory (ISIT)
- article number
- 8849218
- pages
- 2579 - 2583
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 2019 IEEE International Symposium on Information Theory
- conference location
- Paris, France
- conference dates
- 2019-07-07 - 2019-07-12
- external identifiers
-
- scopus:85073142754
- ISBN
- 978-153869291-2
- DOI
- 10.1109/ISIT.2019.8849218
- language
- English
- LU publication?
- yes
- id
- 16992295-5f9a-4627-85bc-ee256fa7c415
- date added to LUP
- 2019-08-13 11:10:56
- date last changed
- 2024-01-31 04:12:31
@inproceedings{16992295-5f9a-4627-85bc-ee256fa7c415, abstract = {{The Learning with Errors problem (LWE) is one of the main candidates for post-quantum cryptography. At Asiacrypt 2017, coded-BKW with sieving, an algorithm combining the Blum-Kalai-Wasserman algorithm (BKW) with lattice sieving techniques, was proposed. In this paper, we improve that algorithm by using different reduction factors in different steps of the sieving part of the algorithm. In the Regev setting, where $q = n^2$ and $\sigma = n^{1.5}/(\sqrt{2\pi}\log_2^2 n)$, the asymptotic complexity is $2^{0.8917n}$, improving the previously best complexity of $2^{{0.8927n}}$. When a quantum computer is assumed or the number of samples is limited, we get a similar level of improvement.}}, author = {{Mårtensson, Erik}}, booktitle = {{IEEE International Symposium on Information Theory (ISIT)}}, isbn = {{978-153869291-2}}, language = {{eng}}, pages = {{2579--2583}}, publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}}, title = {{The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors}}, url = {{http://dx.doi.org/10.1109/ISIT.2019.8849218}}, doi = {{10.1109/ISIT.2019.8849218}}, year = {{2019}}, }