Paper 2014/283

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

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


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.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2016
LatticesWorst-case to Average-case ReductionsHomomorphic EncryptionLWESISHidden Number Problem
Contact author(s)
Phong Nguyen @ inria fr
2016-05-15: last of 2 revisions
2014-04-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas Gama and Malika Izabachene and Phong Q.  Nguyen and Xiang Xie},
      title = {Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2014/283},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.