IACR News item: 29 December 2013
Dimitar Jetchev, Krzysztof Pietrzak
ePrint Report\\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.
Additional news items may be found on the IACR news page.