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 $\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$.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. Minor revision.
Keywords
LWElattice-based cryptanalysishomomorphic encryption
Contact author(s)
gavin @ univ-lyon1 fr
History
2019-08-08: received
Short URL
https://ia.cr/2019/902
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/902,
      author = {Gérald Gavin and Stéphane Bonnevay},
      title = {Fractional LWE: a nonlinear variant of LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2019/902},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/902}},
      url = {https://eprint.iacr.org/2019/902}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.