<p>I suggest you look at a survey by Oded Goldreich, called <a href="http://www.wisdom.weizmann.ac.il/~oded/PDF/samplers.pdf" rel="nofollow">A computational perspective on sampling</a>. In that survey he presents some basic facts on expanders (along with pointers to more extensive material). These facts seem to be sufficient to at least understand the "Security Preserving Amplification of Hardness" paper. In particular, in appendix A he surveys random walks on expanders, and in C.4 he presents the expander hitter, which is what is essentially done in that paper. </p>

CC BY-SA 2.5
2010-12-06T20:14:36.737Z
2010-12-06T20:14:36.737Z
Alon Rosen
<p>The survey by Hoory, Linial and Wigderson mentioned in the comments is highly recommended. In addition, the following two references each provide a really short introduction:   </p>

<p>Michael Nielsen: <a href="http://www.qinfo.org/people/nielsen/blog/archive/notes/expander_graphs.pdf" rel="nofollow">Introduction to expander graphs</a></p>

<p>Peter Sarnak: <a href="http://www.ams.org/notices/200407/what-is.pdf" rel="nofollow">WHAT IS...an Expander</a>, Notices of the AMS, August 2004</p>

CC BY-SA 2.5
2010-12-06T19:12:43.617Z
2010-12-06T19:12:43.617Z
Hermann Gruber
<p>I want to read papers on cryptography like 
<a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=63486" rel="nofollow noreferrer">How to Recycle Random Bits</a>
or <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=89550" rel="nofollow noreferrer">Security Preserving Ampliﬁcation of Hardness</a>. They use random walks on expander graphs.</p>

<p>I need a short introduction to the subject of expander graphs and random walks on them. I prefer one that has cryptography in mind.</p>

<p><strong>PS:</strong> In <a href="https://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read/1402#1402">another post</a>, Dai Le introduced the paper <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" rel="nofollow noreferrer">Expander graphs and their applications, S. Hoory, N. Linial, and A. Wigderson</a> as an excellent paper on expander graphs. Unfortunately, it is too long (123 pages) to be useful for me.</p>

CC BY-SA 2.5
2010-12-06T14:11:28.483Z
If I were you, I would just read *the relevant parts* of Avi, Nati and Shlomo's course/survey/book. It's true that crypto wasn't what they had in mind when writing, but it's an excellent basic text about expanders.
Dana Moshkovitz
CC BY-SA 2.5
2010-12-06T16:28:41.797Z
Is there any particular aspect of the theory of expanders that is specifically targed towards crypto in your mind ?
Suresh Venkat
CC BY-SA 2.5
2010-12-06T20:06:34.360Z
@Dana: Thanks a lot. @Suresh: Well, I just know that they used random walks. I'm too unfamiliar with the subject, but in addition to the above uses, I found the sentence "In cryptography too, expander graphs are used to construct hash functions" in Wikipedia.
Sadeq Dousti
CC BY-SA 2.5
2010-12-06T20:25:44.370Z
A construction of hash functions from expanders was indeed proposed by by Denis Charles, Eyal Goren, Kristin Lauter (http://research.microsoft.com/en-us/um/people/klauter/hashmarch13%202007.pdf). It has been subsequently cryptanalyzed by Tilich and Zemor (https://www.ircert.cc/upload/files/rnr_15.pdf) and Lauter et al. (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.153.2366&rep=rep1&type=pdf).
Alon Rosen
<graph-theory><reference-request><cr.crypto-security><expanders>
Resources on Cryptographic Applications of Expander Graphs
Sadeq Dousti
# Resources on Cryptographic Applications of Expander Graphs

(Asked by: username_0 on 2010-12-06)

I want to read papers on cryptography like
[How to Recycle Random Bits](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=63486)
or [Security Preserving Ampliﬁcation of Hardness](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=89550). They use random walks on expander graphs.

I need a short introduction to the subject of expander graphs and random walks on them. I prefer one that has cryptography in mind.

**PS:** In [another post](https://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read/1402#1402), Dai Le introduced the paper [Expander graphs and their applications, S. Hoory, N. Linial, and A. Wigderson](http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf) as an excellent paper on expander graphs. Unfortunately, it is too long (123 pages) to be useful for me.

**Tags:** graph-theory, reference-request, cr.crypto-security, expanders

> **Comments:**
> **username_1**: If I were you, I would just read *the relevant parts* of Avi, Nati and Shlomo's course/survey/book. It's true that crypto wasn't what they had in mind when writing, but it's an excellent basic text about expanders.  
> **username_2**: Is there any particular aspect of the theory of expanders that is specifically targed towards crypto in your mind ?  
> **username_0**: @Dana: Thanks a lot. @Suresh: Well, I just know that they used random walks. I'm too unfamiliar with the subject, but in addition to the above uses, I found the sentence "In cryptography too, expander graphs are used to construct hash functions" in Wikipedia.  
> **username_3**: A construction of hash functions from expanders was indeed proposed by by Denis Charles, Eyal Goren, Kristin Lauter (http://research.microsoft.com/en-us/um/people/klauter/hashmarch13%202007.pdf). It has been subsequently cryptanalyzed by Tilich and Zemor (https://www.ircert.cc/upload/files/rnr_15.pdf) and Lauter et al. (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.153.2366&rep=rep1&type=pdf).  

---

## 2 answers

### Answer by username_3 on 2010-12-06. Score: 8 | Accepted answer

I suggest you look at a survey by Oded Goldreich, called [A computational perspective on sampling](http://www.wisdom.weizmann.ac.il/~oded/PDF/samplers.pdf). In that survey he presents some basic facts on expanders (along with pointers to more extensive material). These facts seem to be sufficient to at least understand the "Security Preserving Amplification of Hardness" paper. In particular, in appendix A he surveys random walks on expanders, and in C.4 he presents the expander hitter, which is what is essentially done in that paper.


---

### Answer by username_4 on 2010-12-06. Score: 2

The survey by Hoory, Linial and Wigderson mentioned in the comments is highly recommended. In addition, the following two references each provide a really short introduction:

Michael Nielsen: [Introduction to expander graphs](http://www.qinfo.org/people/nielsen/blog/archive/notes/expander_graphs.pdf)

Peter Sarnak: [WHAT IS...an Expander](http://www.ams.org/notices/200407/what-is.pdf), Notices of the AMS, August 2004


---

