Generating Hard Instances of Lattice Problems

Generating Hard Instances of Lattice Problems

1996 | M. Ajtai
This paper presents a class of random lattices in $ \mathbb{Z}^n $, where each lattice can be generated along with a short vector. The key result is that if there exists a probabilistic polynomial-time algorithm that finds a short vector in a random lattice from this class with probability at least $ \frac{1}{2} $, then there also exists a probabilistic polynomial-time algorithm that solves three fundamental lattice problems in every lattice in $ \mathbb{Z}^n $ with probability exponentially close to one. These problems are: (1) finding the length of the shortest nonzero vector in an n-dimensional lattice up to a polynomial factor; (2) finding the shortest nonzero vector in a lattice where it is unique in the sense that any other vector of length at most $ n^c ||v|| $ is parallel to it; and (3) finding a basis with minimal length up to a polynomial factor. The paper also discusses implications of these results, including the existence of one-way functions and the hardness of the randomized subset sum problem. The main idea is to show that if a probabilistic polynomial-time algorithm can solve these lattice problems, then it can also solve other hard problems like the subset sum problem. The proof involves constructing a random class of lattices and showing that solving these problems in this class implies solving them in all lattices. The paper also provides detailed lemmas and proofs for the construction of these lattices and the algorithms used to solve the problems.This paper presents a class of random lattices in $ \mathbb{Z}^n $, where each lattice can be generated along with a short vector. The key result is that if there exists a probabilistic polynomial-time algorithm that finds a short vector in a random lattice from this class with probability at least $ \frac{1}{2} $, then there also exists a probabilistic polynomial-time algorithm that solves three fundamental lattice problems in every lattice in $ \mathbb{Z}^n $ with probability exponentially close to one. These problems are: (1) finding the length of the shortest nonzero vector in an n-dimensional lattice up to a polynomial factor; (2) finding the shortest nonzero vector in a lattice where it is unique in the sense that any other vector of length at most $ n^c ||v|| $ is parallel to it; and (3) finding a basis with minimal length up to a polynomial factor. The paper also discusses implications of these results, including the existence of one-way functions and the hardness of the randomized subset sum problem. The main idea is to show that if a probabilistic polynomial-time algorithm can solve these lattice problems, then it can also solve other hard problems like the subset sum problem. The proof involves constructing a random class of lattices and showing that solving these problems in this class implies solving them in all lattices. The paper also provides detailed lemmas and proofs for the construction of these lattices and the algorithms used to solve the problems.
Reach us at info@study.space