LWE is as Hard as Continuous LWE \& a Search-to-Decision Reduction

본문 미리보기

In 2021, Bruna, Regev, Song and Tang introduced the continuous analogue of LWE, CLWE. Shortly after, Gupte, Vafa, and Vaikuntanathan showed a classical reduction from LWE to CLWE and from discrete-CLWE (secret from a discrete set) to LWE. In this paper, we show two results. The first result is a search-to-decision reduction for CLWE. The search-to-decision reduction works similarly to the standard reduction for LWE. The main difference between the reductions is the continuous nature of the CLWE