Sökning: id:"swepub:oai:lup.lub.lu.se:f96b3942-3d41-4ed8-bd8f-64f4b2e7747b" >
On the Asymptotics ...
On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving
-
- Guo, Qian (författare)
- Lund University,Lunds universitet,Institutionen för elektro- och informationsteknik,Institutioner vid LTH,Lunds Tekniska Högskola,Nätverk och säkerhet,Forskargrupper vid Lunds universitet,Department of Electrical and Information Technology,Departments at LTH,Faculty of Engineering, LTH,Networks and Security,Lund University Research Groups
-
- Johansson, Thomas (författare)
- Lund University,Lunds universitet,Nätverk och säkerhet,Forskargrupper vid Lunds universitet,Networks and Security,Lund University Research Groups
-
- Mårtensson, Erik (författare)
- Lund University,Lunds universitet,Nätverk och säkerhet,Forskargrupper vid Lunds universitet,Networks and Security,Lund University Research Groups
-
visa fler...
-
- Stankovski, Paul (författare)
- Lund University,Lunds universitet,Nätverk och säkerhet,Forskargrupper vid Lunds universitet,Networks and Security,Lund University Research Groups
-
visa färre...
-
(creator_code:org_t)
- 2019
- 2019
- Engelska 16 s.
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 65:8, s. 5243-5259
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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 Blum-Kalai-Wasserman (BKW) algorithm and ideas from sieving in lattices. The new algorithm is analyzed and demonstrates an improved asymptotic performance. For the 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.893n}$ in the standard setting, improving on the previously best known complexity of roughly $2^{0.930n}$. The newly proposed algorithm also provides asymptotic improvements when a quantum computer is assumed or when the number of samples is limited.
Ämnesord
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Signalbehandling (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Signal Processing (hsv//eng)
Nyckelord
- LWE
- BKW
- Coded-BKW
- Lattice codes
- Lattice sieving
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas