Welcome to the resource topic for 2018/171
Title:
On the Complexity of Simulating Auxiliary Input
Authors: Yi-Hsiu Chen, Kai-Min Chung, 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.
ePrint: https://eprint.iacr.org/2018/171
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .