On the Complexity of Simulating Auxiliary Input
On the Complexity of Simulating Auxiliary Input
复制标题
论模拟辅助输入的复杂性
DOI：
10.1007/978-3-319-78372-7_12
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Liao, Jyun-Jie Liao
中科院分区：
文献类型：
--
作者：
Chen, Yi-Hsiu;Chung, Kai-Min Chung;Liao, Jyun-Jie Liao
我们构建了一个模拟器来模拟辅助输入问题，其复杂性优于之前的所有结果，并通过建立黑盒下界证明了对数因子的最优性。具体来说，设 为辅助输入的长度，为不可区分性参数。我们的模拟器比区分器系列更复杂。对于下界，我们显示模拟器的区分器的相对复杂性至少假设模拟器被限制以黑盒方式使用区分器并满足温和的限制。
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, letbe the length of the auxiliary input andbe the indistinguishability parameter. Our simulator ismore complicated than the distinguisher family. For the lower bound, we show the relative complexity to the distinguisher of a simulator is at leastassuming the simulator is restricted to use the distinguishers in a black-box way and satisfy a mild restriction.
登录
查看更多内容
关于显示密集模型的查询复杂度
DOI：
--
发表时间：
2011
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Jiapeng Zhang
通讯作者：
Jiapeng Zhang
DOI：
10.1007/978-3-662-53641-4_7
发表时间：
2015-03
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
M. Skorski
通讯作者：
M. Skorski
非均匀和自适应降低的查询复杂性下限显示难度放大
影响因子：
1.4
作者：
Sergei Artemenko;Ronen Shaltiel
通讯作者：
Ronen Shaltiel
硬核集合证明的复杂性
影响因子：
1.4
作者：
Chi;Shi;H. Wu
通讯作者：
H. Wu
DOI：
10.1109/ccc.2009.41
发表时间：
2009
期刊：
2009 24th Annual IEEE Conference on Computational Complexity
影响因子：
--
作者：
L. Trevisan;Madhur Tulsiani;S. Vadhan
通讯作者：
S. Vadhan