**Reference:**
*The 5nd Theory of Cryptography Conference - TCC'08.*
Lecture Notes in Computer Science, vol. 4948, pages 19-36, Springer, 2008.

**Abstract: **
We investigate a new notion of security for "cryptographic functions" that
we term *seed incompressibility* (SI). We argue that this notion
captures some of the intuition for the alleged security of constructions
in the random-oracle model, and indeed we show that seed incompressibility
suffices for some applications of the random oracle methodology. Very
roughly, a function family *f_s*(*) with *|s|=n* is seed
incompressible if given (say) *n/2* bits of advice (that can depend
on the seed *s*) and an oracle access to *f_s*(*), an adversary
cannot "break *f_s*(*)" any better than given only oracle access to
*f_s*(*) and no advice.

The strength of this notion depends on what we mean by "breaking
*f_s*(*)". We first show that for any family *f_s* there exists
an adversary that can distinguish *f_s*(*) from a random function
using *n/2* bits of advice, so seed incompressible pseudo-random
functions do not exist. Then we consider the weaker notion of
seed-incompressible correlation intractability. We show that although
the negative results can be partially extended also to this weaker
notion, they cannot rule it out altogether. More importantly, the
settings that we cannot rule out still suffice for many applications.
In particular, we show that they suffice for constructing
collision-resistant hash functions and for removing interaction from
Σ-protocols (3-round honest verifier zero-knowledge protocols).

** Availability: **
Paper available as PDF (253 Kbyte).

Shai Halevi's home page.