Solving the search-LWE problem over projected lattices

The learning with errors (LWE) problem is one of the hard problems assuring the security of modern lattice-based cryptography. Kannan’s embedding can reduce Search-LWE, the search version of LWE, to a specific case of the shortest vector problem (SVP). Lattice basis reduction is a powerful instrumen...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2022-09, Vol.318, p.69-81
Main Authors: Nakamura, Satoshi, Tateiwa, Nariaki, Yasuda, Masaya, Fujisawa, Katsuki
Format: Article
Language:English
Subjects:
DeepBKZ
Lattice basis reduction
Lattice problems
LWE
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The learning with errors (LWE) problem is one of the hard problems assuring the security of modern lattice-based cryptography. Kannan’s embedding can reduce Search-LWE, the search version of LWE, to a specific case of the shortest vector problem (SVP). Lattice basis reduction is a powerful instrument for solving lattice problems including SVP. We propose a new way for efficiently solving Search-LWE. While a whole basis is reduced in a standard way, ours reduces only a projected basis. To realize our strategy, we also provide an algorithm for reducing projected bases, based on DeepBKZ that is an enhancement of the block Korkine–Zolotarev (BKZ) algorithm. Moreover, we show implementation results for solving some instances within the Darmstadt LWE challenge.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2022.04.018