Welcome to the resource topic for 2013/869
Title:
How to Fake Auxiliary Input
Authors: Dimitar Jetchev, Krzysztof Pietrzak
Abstract: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.
ePrint: https://eprint.iacr.org/2013/869
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .