Consider a joint distribution on a set . We show that for any family of distinguishers , there exists a simulator such that
\begin{enumerate}
\item no function in can distinguish from with advantage ,
\item is only times less efficient than the functions in .
\end{enumerate}
For the most interesting settings of the parameters (in particular, the cryptographic case where has superlogarithmic min-entropy, is negligible and consists of circuits of polynomial size), we can make the simulator \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.
@misc{cryptoeprint:2013/869,
author = {Dimitar Jetchev and Krzysztof Pietrzak},
title = {How to Fake Auxiliary Input},
howpublished = {Cryptology {ePrint} Archive, Paper 2013/869},
year = {2013},
url = {https://eprint.iacr.org/2013/869}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.