Paper 2018/171 Original: eprint.iacr.org/2018/171 ↗
On the Complexity of Simulating Auxiliary Input
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
- Preprint.
- History
- 2018-02-14: last updated
- 2018-02-14: published
- Short URL
- https://ia.cr/2018/171
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2018/171}
}