*13:17*[Pub][ePrint] How to Fake Auxiliary Input, by Dimitar Jetchev and Krzysztof Pietrzak

Consider a joint distribution $(X,A)$ on a set ${\\cal X}\\times\\{0,1\\}^\\ell$. We show that for any family ${\\cal F}$ of distinguishers $f \\colon {\\cal X} \\times \\{0,1\\}^\\ell \\rightarrow \\{0,1\\}$, there exists a simulator $h \\colon {\\cal X} \\rightarrow \\{0,1\\}^\\ell$ such that

\\begin{enumerate}

\\item no function in ${\\cal F}$ can distinguish $(X,A)$ from $(X,h(X))$ with advantage $\\epsilon$,

\\item $h$ is only $O(2^{3\\ell}\\epsilon^{-2})$ times less efficient than the functions in ${\\cal F}$.

\\end{enumerate}

For the most interesting settings of the parameters (in particular, the cryptographic case where $X$ has superlogarithmic min-entropy, $\\epsilon > 0$ is negligible and ${\\cal F}$ consists of circuits of polynomial size), we can make the simulator $h$ \\emph{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.