Leaky Pseudo-Entropy Functions by Yael Kalai, Microsoft
Abstract: Pseudo-random functions (PRFs) introduced by Goldwasser,
Goldreich, and Micali (FOCS 1984), are one of the most important
building blocks in cryptography. A PRF family is a family of seeded
functions {f_s}, with the property that no efficient adversary can
tell the difference between getting oracle access to a random PRF
function f_s, and getting oracle access to a truly random function.
In this work, we consider the problem of constructing pseudo-random
functions that are resilient to leakage. Unfortunately, even if a
single bit about the secret seed s is leaked, then there is no hope to
construct a PRF, since the leakage can simply be the first bit of
f_s(0), and thus f_s(0) is distinguishable from uniform. Therefore,
when dealing with leakage, we must relax the definition. We consider
the following relaxation: Instead of requiring that for each input x,
the value f_s(x) looks random, we require that it looks like it has
high *min-entropy*, even given oracle access to f_s everywhere except
point x. We call such a function family a *pseudo-entropy function*
(PEF) family. In particular, a leakage-resilient PEF family has the
property that given leakage L(s) and given oracle access to f_s, it is
hard to predict f_s on any input that was not queried. We construct
such a leakage-resilient PEF family under the DDH assumption (or more
generally, assuming the existence of lossy functions with the property
that the output size is not much larger than the input size). We also
show that leakage-resilient PEFs imply leakage-resilient
*random-input* PRFs, where the requirement is that for a *random*
input r, the value f_s(r) looks uniform, even given the leakage L(s)
and given oracle access to f_s anywhere accept at point r (the leakage
L(s) is independent of r, but the oracle f_s is present even after the
pair (r,f_s(r)) is given). This is joint work with Mark Braverman and
Avinatan Hassidim.
Joanne Talbot Hanley
Last modified: Mon Aug 16 11:20:40 EDT 2010