Paper 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.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Latticesworst-case to average-case reductionsSISLWE
- Contact author(s)
- pnguyen @ di ens fr
- History
- 2016-05-15: last of 2 revisions
- 2014-04-24: received
- See all versions
- Short URL
- https://ia.cr/2014/283
- License
-
CC BY