Coded-BKW with Sieving

Qian Guo; Thomas Johansson; Erik Mårtensson; Paul Stankovski

doi:10.1007/978-3-319-70694-8_12

Coded-BKW with Sieving

Qian Guo, Thomas Johansson, Erik Mårtensson, Paul Stankovski

Forskningsoutput: Kapitel i bok/rapport/Conference proceeding › Konferenspaper i proceeding › Peer review

Sammanfattning

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.

Originalspråk	engelska
Titel på värdpublikation	Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Förlag	Springer
Sidor	323-346
ISBN (elektroniskt)	978-3-319-70694-8
ISBN (tryckt)	978-3-319-70693-1
DOI	https://doi.org/10.1007/978-3-319-70694-8_12
Status	Published - 2017
Evenemang	23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017 - Hong Kong, Kina Varaktighet: 2017 dec. 3 → 2017 dec. 7 Konferensnummer: 23 https://asiacrypt.iacr.org/2017/index.html

Publikationsserier

Namn	Lecture Notes in Computer Science
Förlag	Springer
Volym	10624
ISSN (tryckt)	0302-9743

Konferens

Konferens	23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017
Förkortad titel	ASIACRYPT
Land/Territorium	Kina
Ort	Hong Kong
Period	2017/12/03 → 2017/12/07
Internetadress	https://asiacrypt.iacr.org/2017/index.html

Ämnesklassifikation (UKÄ)

Annan elektroteknik och elektronik

Tillgång till dokument

10.1007/978-3-319-70694-8_12

Citera det här

@inproceedings{83815ef3610c4764a30817871218ea81,

title = "Coded-BKW with Sieving",

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.",

keywords = "LWE, BKW, Coded-BKW, Lattice codes, Lattice sieving",

author = "Qian Guo and Thomas Johansson and Erik M{\aa}rtensson and Paul Stankovski",

year = "2017",

doi = "10.1007/978-3-319-70694-8_12",

language = "English",

isbn = "978-3-319-70693-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "323--346",

booktitle = "Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "Germany",

note = "23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017, ASIACRYPT ; Conference date: 03-12-2017 Through 07-12-2017",

url = "https://asiacrypt.iacr.org/2017/index.html",

}

Guo, Q , Johansson, T , Mårtensson, E & Stankovski, P 2017, Coded-BKW with Sieving. i Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science, vol. 10624, Springer, s. 323-346, 23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017, Hong Kong, Kina, 2017/12/03. https://doi.org/10.1007/978-3-319-70694-8_12

Coded-BKW with Sieving. / Guo, Qian ; Johansson, Thomas ; Mårtensson, Erik et al.

Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer, 2017. s. 323-346 (Lecture Notes in Computer Science; Vol. 10624).

Forskningsoutput: Kapitel i bok/rapport/Conference proceeding › Konferenspaper i proceeding › Peer review

TY - GEN

T1 - Coded-BKW with Sieving

AU - Guo, Qian

AU - Johansson, Thomas

AU - Mårtensson, Erik

AU - Stankovski, Paul

N1 - Conference code: 23

PY - 2017

Y1 - 2017

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

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

KW - LWE

KW - BKW

KW - Coded-BKW

KW - Lattice codes

KW - Lattice sieving

U2 - 10.1007/978-3-319-70694-8_12

DO - 10.1007/978-3-319-70694-8_12

M3 - Paper in conference proceeding

SN - 978-3-319-70693-1

T3 - Lecture Notes in Computer Science

SP - 323

EP - 346

BT - Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

PB - Springer

T2 - 23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017

Y2 - 3 December 2017 through 7 December 2017

ER -

Coded-BKW with Sieving

Sammanfattning

Publikationsserier

Konferens

Ämnesklassifikation (UKÄ)

Tillgång till dokument

Fingeravtryck

Citera det här