### How to Fake Auxiliary Input

Dimitar Jetchev and 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.

Available format(s)
Category
Foundations
Publication info
Keywords
pseudoentropyleakage-resiliencechain-rules
Contact author(s)
krzpie @ gmail com
History
Short URL
https://ia.cr/2013/869

CC BY

BibTeX

@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},
note = {\url{https://eprint.iacr.org/2013/869}},
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.