International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 24 April 2014

Nicolas Gama, Malika Izabachene, Phong Q. Nguyen, Xiang Xie
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.