The Ajtai random class of lattices
Ajtai has recently given a reduction from the problem of approximating a short basis for a lattice in the worst case, to the problem of finding a short lattice vector for a uniformly chosen lattice in a certain random class of lattices. Here we give an explicit formula for the number of lattices of the type used by Ajtai. We also prove some results about the average volume of the fundamental cell of such a lattice. (C) 1999 Elsevier Science B.V. All rights reserved.
ajtai random class lattice cryptography provably secure cryptosystem