# Randomness condensers for efficiently samplable, seed-dependent sources

### Citation:

Dodis, Yevgeniy, Thomas Ristenpart, and Salil Vadhan. “Randomness condensers for efficiently samplable, seed-dependent sources.” In Ronald Cramer, editor, Proceedings of the 9th IACR Theory of Cryptography Conference (TCC ‘12), Lecture Notes on Computer Science, 7194:618-635. Springer-Verlag, 2012.
 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 min-entropy 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, seed-dependent sources whose computational complexity is smaller than the size $$t$$ of the adversarial sampling algorithm $$\mathcal{A}$$. Indeed, we show that sufficiently strong collision-resistant hash functions are seed-dependent condensers that produce outputs with min-entropy $$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 seed-dependent samplable sources that are robust to side information generated by the sampling algorithm imply soundness of the Fiat-Shamir Heuristic when applied to any constant-round, public-coin interactive proof system.

Publisher's Version

Last updated on 06/30/2020