Coded-BKW with Sieving

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

Ämnesord

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik -- Annan elektroteknik och elektronik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering -- Other Electrical Engineering, Electronic Engineering, Information Engineering (hsv//eng)

Nyckelord

LWE

BKW

Coded-BKW

Lattice codes

Lattice sieving

Publikations- och innehållstyp

kon (ämneskategori)

ref (ämneskategori)