Cryptology ePrint Archive: Report 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.
Category / Keywords: foundations / pseudorandom functions
Original Publication (with minor differences): Tutorials on the Foundations of Cryptography (Dedicated to Oded Goldreich)
DOI: 10.1007/978-3-319-57048-8_3
Date: received 1 Jul 2017
Contact author: alon rosen at idc ac il
Available format(s): PDF | BibTeX Citation
Note: This survey appeared in the book Tutorials on the Foundations of Cryptography, published in honor of Oded Goldreich’s 60th birthday.
Version: 20170705:214144 (All versions of this report)
Short URL: ia.cr/2017/652
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]