From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs

Moni Naor and Omer Reingold


This paper studies the relationship between unpredictable functions (which formalize the concept of a MAC) and pseudo-random functions . We show an efficient transformation of the former to the latter using a unique application of the Goldreich-Levin hard-core bit (taking the inner-product with a random vector r): While in most applications of the GL-bit the random vector r may be public, in our setting this is not the case. The transformation is only secure when r is secret and treated as part of the key. In addition, we consider weaker notions of unpredictability and their relationship to the corresponding notions of pseudo-randomness. In particular, this gives a simple construction of a private-key encryption scheme from the standard challenge-response identification scheme.

Postscript , gzipped Postscript .

Back to On-Line Publications

Back Home