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