Yevgeniy Dodis
New York University

Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources

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 Cond : {0,1}^n x {0,1}^d -> {0,1}^m such that
if we choose a random seed S in {0,1}^d and a source X=A(S) is
generated by a randomized circuit A of size t, such that X has min-entropy
at least k given S, then 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:

1) 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 A. Indeed, we show that
sufficiently strong collision-resistant hash functions are seed-dependent
condensers that produce outputs with min-entropy k' = m - O(log t),
i.e. logarithmic *entropy deficiency*.

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

3) 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
proof system. (and thus imply that such proof systems cannot be zero knowledge).
In fact, this only  requires condensers for "leaky sources" --- ones
that are uniform
prior to conditioning on the adversary's side information --- and we
show that such
condensers are also *necessary* for soundness of the Fiat--Shamir Heuristic.

Joint workwith Tom Ristenpart and  Salil Vadhan.