4
$\begingroup$

I want to read papers on cryptography like How to Recycle Random Bits or Security Preserving Amplification of Hardness. 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, Dai Le introduced the paper Expander graphs and their applications, S. Hoory, N. Linial, and A. Wigderson as an excellent paper on expander graphs. Unfortunately, it is too long (123 pages) to be useful for me.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Dana Moshkovitz Dec 6 '10 at 14:11
  • $\begingroup$ Is there any particular aspect of the theory of expanders that is specifically targed towards crypto in your mind ? $\endgroup$ – Suresh Venkat Dec 6 '10 at 16:28
  • $\begingroup$ @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. $\endgroup$ – M.S. Dousti Dec 6 '10 at 20:06
  • 2
    $\begingroup$ A construction of hash functions from expanders was indeed proposed by by Denis Charles, Eyal Goren, Kristin Lauter (research.microsoft.com/en-us/um/people/klauter/…). It has been subsequently cryptanalyzed by Tilich and Zemor (ircert.cc/upload/files/rnr_15.pdf) and Lauter et al. (citeseerx.ist.psu.edu/viewdoc/…). $\endgroup$ – Alon Rosen Dec 6 '10 at 20:25
8
$\begingroup$

I suggest you look at a survey by Oded Goldreich, called A computational perspective on sampling. 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.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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

Peter Sarnak: WHAT IS...an Expander, Notices of the AMS, August 2004

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.