How to Fake Auxiliary Input

Abstract

Abstract. Consider a joint distribution (X,A) on a set X ×{0, 1}ℓ. We show that for any family F of distinguishers f: X × {0, 1}ℓ → {0, 1}, there exists a simulator h: X → {0, 1}ℓ such that 1. no function in F can distinguish (X,A) from (X,h(X)) with advantage ǫ, 2. h is only O(23ℓǫ−2) times less efficient than the functions in F. For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, ǫ> 0 is negligible and F consists of circuits of polynomial size), we can make the simulator h deterministic. As an illustrative application of this theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt’09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES. Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem. 1