Dodis, YevgeniyRistenpart, ThomasVadhan, Salil2014-02-102012Dodis, Yevgeniy, Thomas Ristenpart, and Salil Vadhan. 2012. "Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources." Lecture Notes in Computer Science 7194: 618-635. Presented at the 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Also appears in Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources. Springer-Verlag. doi:10.1007/978-3-642-28914-9_35. http://dx.doi.org/10.1007/978-3-642-28914-9_35.978-3-642-28913-2978-3-642-28914-90302-9743http://nrs.harvard.edu/urn-3:HUL.InstRepos:11688764We initiate a study of randomness condensers for sources that are efficiently samplable but may depend on the seed of the con- denser. That is, we seek functions Cond : {0, 1}n ×{0, 1}d → {0, 1}m such that if we choose a random seed S ← {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 ran- domness 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 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. – Randomness condensers suffice for key derivation in many crypto- graphic applications: when an adversary has negligible success proba- bility (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.en-USConference Paper2014-02-1110.1007/978-3-642-28914-9_35