Citation:
IACR2012.pdf  302 KB 
Abstract:
We initiate a study of randomness condensers for sources that are efficiently samplable but may depend on the seed of the condenser. That is, we seek functions \(\mathsf{Cond} : \{0,1\}^n \times \{0,1\}^d \to \{0,1\}^m\)such that if we choose a random seed \(S \gets \{0,1\}^d\), and a source \(X = \mathcal{A}(S)\) is generated by a randomized circuit \(\mathcal{A}\) of size \(t\) such that \(X\) has min entropy at least \(k\) given \(S\), then \(\mathsf{Cond}(X ; S)\) should have minentropy at least some \(k'\) given \(S\). The distinction from the standard notion of randomness condensers is that the source \(X\) may be correlated with the seed \(S\) (but is restricted to be efficiently samplable). Randomness extractors of this type (corresponding to the special case where \(k' = m\)) have been implicitly studied in the past (by Trevisan and Vadhan, FOCS ‘00).
We show that:

Unlike extractors, we can have randomness condensers for samplable, seeddependent sources whose computational complexity is smaller than the size \(t\) of the adversarial sampling algorithm \(\mathcal{A}\). Indeed, we show that sufficiently strong collisionresistant hash functions are seeddependent condensers that produce outputs with minentropy \(k' = m – \mathcal{O}(\log t)\), i.e. logarithmic entropy deficiency.

Randomness condensers suffice for key derivation in many cryptographic applications: when an adversary has negligible success probability (or negligible “squared advantage” [3]) for a uniformly random key, we can use instead a key generated by a condenser whose output has logarithmic entropy deficiency.

Randomness condensers for seeddependent samplable sources that are robust to side information generated by the sampling algorithm imply soundness of the FiatShamir Heuristic when applied to any constantround, publiccoin interactive proof system.