SPEAKER: Yevgeniy Dodis New York University TITLE: Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources 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 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 interactive 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.