Paper 2013/869
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 minentropy, $\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 leakageresilient streamcipher 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 ZeroKnowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform minmax theorem.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published by the IACR in TCC 2014
 Keywords
 pseudoentropyleakageresiliencechainrules
 Contact author(s)
 krzpie @ gmail com
 History
 20131229: received
 Short URL
 https://ia.cr/2013/869
 License

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} }