Coded-BKW with Sieving

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Annan elektroteknik och elektronik

Nyckelord

Originalspråkengelska
Titel på värdpublikationAdvances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
FörlagSpringer
Sidor323-346
ISBN (elektroniskt)978-3-319-70694-8
ISBN (tryckt)978-3-319-70693-1
StatusPublished - 2017
PublikationskategoriForskning
Peer review utfördJa
Evenemang23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017 - Hong Kong, Kina
Varaktighet: 2017 dec 32017 dec 7
Konferensnummer: 23
https://asiacrypt.iacr.org/2017/index.html

Publikationsserier

NamnLecture Notes in Computer Science
FörlagSpringer
Volym10624
ISSN (tryckt)0302-9743

Konferens

Konferens23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017
Förkortad titelASIACRYPT
LandKina
OrtHong Kong
Period2017/12/032017/12/07
Internetadress