On Seed-Incompressible Functions

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).