Paper 2013/869

How to Fake Auxiliary Input

Dimitar Jetchev and Krzysztof Pietrzak

Abstract

Consider a joint distribution (X,A) on a set X×{0,1}. We show that for any family F of distinguishers f:X×{0,1}{0,1}, there exists a simulator h:X{0,1} such that \begin{enumerate} \item no function in F can distinguish (X,A) from (X,h(X)) with advantage ϵ, \item h is only O(23ϵ2) times less efficient than the functions in F. \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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in TCC 2014
Keywords
pseudoentropyleakage-resiliencechain-rules
Contact author(s)
krzpie @ gmail com
History
2013-12-29: received
Short URL
https://ia.cr/2013/869
License
Creative Commons Attribution
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},
      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.