Welcome to the resource topic for 2019/902
Title:
Fractional LWE: a nonlinear variant of LWE
Authors: Gérald Gavin, Stéphane Bonnevay
Abstract:Many cryptographic constructions are based on the famous problem LWE \cite{LWERegev05}. In particular, this cryptographic problem is currently the most relevant to build FHE. In some LWE-based schemes, encrypting x consists of randomly choosing a vector c satisfying \langle s,c\rangle=x+\textsf{noise}\pmod q where s is a secret size-n vector. While the vector sum is a homomorphic operator, such a scheme is intrinsically vulnerable to lattice-based attacks. To overcome this, we propose to define c as a pair of vectors (u,v) satisfying \langle s,u\rangle/\langle s,v\rangle=x+\textsf{noise}\pmod q. This simple scheme is based on a new cryptographic problem intuitively not easier than LWE, called Fractional LWE (FLWE). While some homomorphic properties are lost, the secret vector s could be hopefully chosen shorter leading to more efficient constructions. We extensively study the hardness of FLWE. We first prove that the decision and search versions are equivalent provided q is a \textit{small} prime. We then propose lattice-based cryptanalysis showing that n could be chosen logarithmic in \log q.
ePrint: https://eprint.iacr.org/2019/902
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .