Paper 2017/652

Pseudorandom Functions: Three Decades Later

Andrej Bogdanov and Alon Rosen

Abstract

In 1984, Goldreich, Goldwasser and Micali formalized the concept of pseudorandom functions and proposed a construction based on any length-doubling pseudorandom generator. Since then, pseudorandom functions have turned out to be an extremely influential abstraction, with applications ranging from message authentication to barriers in proving computational complexity lower bounds. In this tutorial we survey various incarnations of pseudorandom functions, giving self-contained proofs of key results from the literature. Our main focus is on feasibility results and constructions, as well as on limitations of (and induced by) pseudorandom functions. Along the way we point out some open questions that we believe to be within reach of current techniques.

Note: This survey appeared in the book Tutorials on the Foundations of Cryptography, published in honor of Oded Goldreich’s 60th birthday.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. Tutorials on the Foundations of Cryptography (Dedicated to Oded Goldreich)
DOI
10.1007/978-3-319-57048-8_3
Keywords
pseudorandom functions
Contact author(s)
alon rosen @ idc ac il
History
2017-07-05: received
Short URL
https://ia.cr/2017/652
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/652,
      author = {Andrej Bogdanov and Alon Rosen},
      title = {Pseudorandom Functions: Three Decades Later},
      howpublished = {Cryptology ePrint Archive, Paper 2017/652},
      year = {2017},
      doi = {10.1007/978-3-319-57048-8_3},
      note = {\url{https://eprint.iacr.org/2017/652}},
      url = {https://eprint.iacr.org/2017/652}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.