<p>You can try reading more recent papers such as <a href="http://cims.nyu.edu/~regev/papers/average.pdf" rel="nofollow">Worst-case to Average-case Reductions based on Gaussian Measures</a> by Miccancio and Regev, or Regev's  <a href="http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/averagecase.pdf" rel="nofollow">lecture notes</a> on the subject (you might want to read through the <a href="http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/" rel="nofollow">entire course</a>).</p>

CC BY-SA 3.0
2014-11-06T04:42:36.830Z
2014-11-08T18:06:32.960Z
2014-11-08T18:06:32.960Z
Yuval Filmus
<p>Replying very late, I really like the exposition of Ajtai's proof in <a href="http://www.wisdom.weizmann.ac.il/%7Eoded/COL/cfh.pdf" rel="nofollow noreferrer">this paper of Goldreich, Goldwasser and Halevi.</a></p>

CC BY-SA 4.0
2021-06-25T20:44:53.090Z
2021-06-25T20:44:53.090Z
Cole_Franks
<p>My question pertains to the proof of Ajtai's main theorem in his groundbreaking 1996 paper, <em><a href="http://dx.doi.org/10.1145/237814.237838">Generating hard instances of lattice problems</a></em>, which indicates a connection between worst-case hard and average-case hard lattice problems.
This proof is  difficult for me to understand. Is there a clear exposition of this proof in the literature? </p>

CC BY-SA 3.0
2014-11-05T14:53:54.183Z
You can try reading more recent papers such as http://www.cims.nyu.edu/~regev/papers/average.pdf, or Oded Regev's lecture notes http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/averagecase.pdf (you might want to read the entire course).
Yuval Filmus
<integer-lattice>
Ajtai's Proof of Theorem 1 in 'Generating Hard Instances of Lattice Problems'
Krishnan Narayanan
# Ajtai's Proof of Theorem 1 in 'Generating Hard Instances of Lattice Problems'

(Asked by: username_0 on 2014-11-05)

My question pertains to the proof of Ajtai's main theorem in his groundbreaking 1996 paper, *[Generating hard instances of lattice problems](http://dx.doi.org/10.1145/237814.237838)*, which indicates a connection between worst-case hard and average-case hard lattice problems.
This proof is difficult for me to understand. Is there a clear exposition of this proof in the literature?

**Tags:** integer-lattice

> **Comments:**
> **username_1**: You can try reading more recent papers such as http://www.cims.nyu.edu/~regev/papers/average.pdf, or Oded Regev's lecture notes http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/averagecase.pdf (you might want to read the entire course).  

---

## 2 answers

### Answer by username_1 on 2014-11-06. Score: 8

You can try reading more recent papers such as [Worst-case to Average-case Reductions based on Gaussian Measures](http://cims.nyu.edu/~regev/papers/average.pdf) by Miccancio and Regev, or Regev's [lecture notes](http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/averagecase.pdf) on the subject (you might want to read through the [entire course](http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/)).


---

### Answer by username_2 on 2021-06-25. Score: 3

Replying very late, I really like the exposition of Ajtai's proof in [this paper of Goldreich, Goldwasser and Halevi.](http://www.wisdom.weizmann.ac.il/%7Eoded/COL/cfh.pdf)


---

