From Unpredictability to Indistinguishability: A Simple Construction
of Pseudo-Random Functions from MACs
Moni Naor and Omer Reingold
Abstract:
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