Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors

Mårtensson, Erik LU orcid (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:
author
organization
publishing date
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}},
}