Cryptology ePrint Archive: Report 2018/171
On the Complexity of Simulating Auxiliary Input
Yi-Hsiu Chen and Kai-Min Chung and Jyun-Jie Liao
Abstract: We construct a simulator for the simulating auxiliary input problem with
complexity better than all previous results and prove the optimality up to
logarithmic factors by establishing a black-box lower bound. Specifically, let
$\ell$ be the length of the auxiliary input and $\epsilon$ be the
indistinguishability parameter. Our simulator is
$\tilde{O}(2^{\ell}\epsilon^{-2})$ more complicated than the distinguisher family.
For the lower bound, we show the relative complexity to the distinguisher of a
simulator is at least $\Omega(2^{\ell}\epsilon^{-2})$ assuming the simulator is
restricted to use the distinguishers in a black-box way and satisfy a mild
restriction.
Category / Keywords: Leakage Simulation Lemma, Simulating Auxiliary Input, Leakage-Resilient Stream-Cipher, Leakage Chain Rule, Dense Model Theorem, Impagliazzo's Hardcore Lemma, Computational Min-Entropy
Original Publication (in the same form): IACR-EUROCRYPT-2018
Date: received 8 Feb 2018, last revised 12 Feb 2018
Contact author: jjliao at iis sinica edu tw
Available format(s): PDF | BibTeX Citation
Version: 20180214:124502 (All versions of this report)
Short URL: ia.cr/2018/171
[ Cryptology ePrint archive ]