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

Erik Mårtensson

doi:10.1109/ISIT.2019.8849218

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

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

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.

Original language	English
Title of host publication	IEEE International Symposium on Information Theory (ISIT)
Publisher	IEEE - Institute of Electrical and Electronics Engineers Inc.
Pages	2579-2583
ISBN (Print)	978-153869291-2
DOIs	https://doi.org/10.1109/ISIT.2019.8849218
Publication status	Published - 2019
Event	2019 IEEE International Symposium on Information Theory - Paris, France Duration: 2019 Jul 7 → 2019 Jul 12 https://2019.ieee-isit.org/

Conference

Conference	2019 IEEE International Symposium on Information Theory
Abbreviated title	ISIT
Country/Territory	France
City	Paris
Period	2019/07/07 → 2019/07/12
Internet address	https://2019.ieee-isit.org/

Subject classification (UKÄ)

Other Electrical Engineering, Electronic Engineering, Information Engineering

Access to Document

10.1109/ISIT.2019.8849218

1 Doctoral Thesis (compilation)

Some Notes on Post-Quantum Cryptanalysis
Mårtensson, E., 2020, Lund: Department of Electroscience, Lund University. 290 p.
Research output: Thesis › Doctoral Thesis (compilation)

Open Access
File

Cite this

@inproceedings{169922955f9a462785bcee256fa7c415,

title = "The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors",

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 = "Erik M{\aa}rtensson",

year = "2019",

doi = "10.1109/ISIT.2019.8849218",

language = "English",

isbn = "978-153869291-2",

pages = "2579--2583",

booktitle = "IEEE International Symposium on Information Theory (ISIT)",

publisher = "IEEE - Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

note = "2019 IEEE International Symposium on Information Theory, ISIT ; Conference date: 07-07-2019 Through 12-07-2019",

url = "https://2019.ieee-isit.org/",

}

Mårtensson, E 2019, The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors. in IEEE International Symposium on Information Theory (ISIT)., 8849218, IEEE - Institute of Electrical and Electronics Engineers Inc., pp. 2579-2583, 2019 IEEE International Symposium on Information Theory, Paris, France, 2019/07/07. https://doi.org/10.1109/ISIT.2019.8849218

The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors. / Mårtensson, Erik.
IEEE International Symposium on Information Theory (ISIT). IEEE - Institute of Electrical and Electronics Engineers Inc., 2019. p. 2579-2583 8849218.

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

TY - GEN

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

AU - Mårtensson, Erik

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

U2 - 10.1109/ISIT.2019.8849218

DO - 10.1109/ISIT.2019.8849218

M3 - Paper in conference proceeding

SN - 978-153869291-2

SP - 2579

EP - 2583

BT - IEEE International Symposium on Information Theory (ISIT)

PB - IEEE - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE International Symposium on Information Theory

Y2 - 7 July 2019 through 12 July 2019

ER -

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

Abstract

Conference

Subject classification (UKÄ)

Access to Document

Fingerprint

Research output

Some Notes on Post-Quantum Cryptanalysis

Cite this