Cryptology ePrint Archive: Report 2014/283

Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions

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 refer to a very small class of random lattices related to the group G=Z_q^n. We generalize worst-case to average-case reductions to (almost) all integer lattices, 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 group 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.

Category / Keywords: foundations / Lattices, worst-case to average-case reductions, SIS, LWE

Date: received 23 Apr 2014

Contact author: pnguyen at di ens fr

Available format(s): PDF | BibTeX Citation

Version: 20140424:223558 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]