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

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceedingPeer review

Sammanfattning

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.
Originalspråkengelska
Titel på värdpublikationIEEE International Symposium on Information Theory (ISIT)
FörlagIEEE - Institute of Electrical and Electronics Engineers Inc.
Sidor2579-2583
ISBN (tryckt)978-153869291-2
DOI
StatusPublished - 2019
Evenemang2019 IEEE International Symposium on Information Theory - Paris, Frankrike
Varaktighet: 2019 juli 72019 juli 12
https://2019.ieee-isit.org/

Konferens

Konferens2019 IEEE International Symposium on Information Theory
Förkortad titelISIT
Land/TerritoriumFrankrike
OrtParis
Period2019/07/072019/07/12
Internetadress

Ämnesklassifikation (UKÄ)

  • Annan elektroteknik och elektronik

Fingeravtryck

Utforska forskningsämnen för ”The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors”. Tillsammans bildar de ett unikt fingeravtryck.

Citera det här