Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources

DSpace/Manakin Repository

Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources

Citable link to this page

 

 
Title: Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources
Author: Dodis, Yevgeniy; Ristenpart, Thomas; Vadhan, Salil P.

Note: Order does not necessarily reflect citation order of authors.

Citation: Dodis, 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.
Full Text & Related Files:
Abstract: We 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.
Published Version: doi:10.1007/978-3-642-28914-9_35
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAP
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:11688764
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters