@conference {634293,
	title = {Randomness condensers for efficiently samplable, seed-dependent sources},
	booktitle = {Ronald Cramer, editor, Proceedings of the 9th IACR Theory of Cryptography Conference (TCC {\textquoteleft}12), Lecture Notes on Computer Science},
	volume = {7194},
	year = {2012},
	pages = {618-635},
	publisher = {Springer-Verlag},
	organization = {Springer-Verlag},
	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\&nbsp;\(\mathsf{Cond} : \{0,1\}^n \times \{0,1\}^d \to \{0,1\}^m\)such that if we choose a random seed\&nbsp;\(S \gets \{0,1\}^d\), and a source\&nbsp;\(X = \mathcal{A}(S)\) is generated by a randomized circuit\&nbsp;\(\mathcal{A}\)\&nbsp;of size\&nbsp;\(t\)\&nbsp;such that\&nbsp;\(X\)\&nbsp;has min- entropy at least\&nbsp;\(k\)\&nbsp;given\&nbsp;\(S\), then\&nbsp;\(\mathsf{Cond}(X ; S)\) should have min-entropy at least some\&nbsp;\(k{\textquoteright}\)\&nbsp;given\&nbsp;\(S\). The distinction from the standard notion of randomness condensers is that the source\&nbsp;\(X\)\&nbsp;may be correlated with the seed \(S\)\&nbsp;(but is restricted to be efficiently samplable). Randomness\&nbsp;extractors of this type (corresponding to the special case where\&nbsp;\(k{\textquoteright} = m\)) have been implicitly studied in the past (by Trevisan and Vadhan, FOCS {\textquoteleft}00).



	We show that:



	
		
			Unlike extractors, we can have randomness condensers for samplable, seed-dependent sources whose computational complexity is smaller than the size\&nbsp;\(t\)\&nbsp;of the adversarial sampling algorithm\&nbsp;\(\mathcal{A}\). Indeed, we show that sufficiently strong collision-resistant hash functions are seed-dependent condensers that produce outputs with min-entropy \(k{\textquoteright} = m {\textendash} \mathcal{O}(\log t)\), i.e. logarithmic\&nbsp;entropy deficiency.
		
	
	
		
			Randomness condensers suffice for key derivation in many cryptographic applications: when an adversary has negligible success probability (or negligible {\textquotedblleft}squared advantage{\textquotedblright} [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.
		
	

},
	url = {https://link.springer.com/chapter/10.1007/978-3-642-28914-9_35},
	author = {Yevgeniy Dodis and Thomas Ristenpart and Salil Vadhan}
}
