**Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems**

*Nicolas Gama and Malika Izabachene and Phong Q. Nguyen and Xiang Xie*

**Abstract: **In lattice cryptography, worst-case to average-case reductions rely on two problems: Ajtai's SIS and Regev's LWE,
which both refer to a very small class of random lattices related to the group $G=\mZ_q^n$.
We generalize worst-case to average-case reductions to all integer lattices of sufficiently large determinant,
by allowing $G$ to be any (sufficiently large) finite abelian group.
In particular, we obtain a partition of the set of full-rank integer lattices of large volume
such that finding short vectors in a lattice chosen uniformly at random from any of the partition cells is as hard as finding short vectors in any integer lattice.
Our main tool is a novel generalization of lattice reduction, which we call structural lattice reduction: given a finite abelian group $G$ and a lattice $L$,
it finds a short basis of some lattice $\bar{L}$ such that $L \subseteq \bar{L}$ and $\bar{L}/L \simeq G$.
Our group generalizations of SIS and LWE allow us to abstract lattice cryptography, yet preserve worst-case assumptions: as an example, we provide a somewhat conceptually simpler
generalization of the Alperin-Sheriff-Peikert variant of the Gentry-Sahai-Waters homomorphic scheme.
We introduce homomorphic mux gates, which
allows us to homomorphically evaluate any boolean function with a noise overhead
proportional to the square root of its number of variables,
and bootstrap the full scheme using only a linear noise overhead.

**Category / Keywords: **Lattices, Worst-case to Average-case Reductions, Homomorphic Encryption, LWE, SIS, Hidden Number Problem

**Date: **received 23 Apr 2014, last revised 5 May 2015

**Contact author: **Phong Nguyen at inria fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20150505:135546 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]