Paper 2019/902

Fractional LWE: a nonlinear variant of LWE

Gérald Gavin and 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 $⟨s,c⟩=x+\mathsf{\text{noise}}(\mathrm{mod}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 $⟨s,u⟩/⟨s,v⟩=x+\mathsf{\text{noise}}(\mathrm{mod}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 $$ 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 $$ is a \textit{small} prime. We then propose lattice-based cryptanalysis showing that $$ could be chosen logarithmic in $$.