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