On the Complexity of Simulating Auxiliary Input

Yi-Hsiu Chen; Kai-Min Chung; Jyun-Jie Liao

Paper 2018/171

On the Complexity of Simulating Auxiliary Input

Yi-Hsiu Chen, 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.

Metadata

Available format(s): PDF
Publication info: Published by the IACR in EUROCRYPT 2018
Keywords: Leakage Simulation Lemma Simulating Auxiliary Input Leakage-Resilient Stream-Cipher Leakage Chain Rule Dense Model Theorem Impagliazzo's Hardcore Lemma Computational Min-Entropy
Contact author(s): jjliao @ iis sinica edu tw
History: 2018-02-14: received
Short URL: https://ia.cr/2018/171
License: CC BY

BibTeX

@misc{cryptoeprint:2018/171,
      author = {Yi-Hsiu Chen and Kai-Min Chung and Jyun-Jie Liao},
      title = {On the Complexity of Simulating Auxiliary Input},
      howpublished = {Cryptology ePrint Archive, Paper 2018/171},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/171}},
      url = {https://eprint.iacr.org/2018/171}
}