Simulating Auxiliary Inputs, Revisited
Simulating Auxiliary Inputs, Revisited
复制标题
DOI：
10.1007/978-3-662-53641-4_7
复制
发表时间：
2015-03
期刊：
影响因子：
--
通讯作者：
M. Skorski
中科院分区：
文献类型：
--
作者：
M. Skorski
对于任何一对相关的随机变量，我们可以把Z看作是X的随机化函数。如果Z的域很小，则可以通过允许它仅近似正确来使该函数在计算上有效。在民间传说中，这个问题是已知的模拟辅助输入。这种模拟辅助信息的想法被证明是一种非常有用的工具，在复杂性理论、密码学、伪随机性和零知识中找到了应用。在本文中，我们重新审视这个问题，取得了以下结果：（a）我们提出了一种新的升压算法构建的模拟器。这个提升证明是独立的兴趣，因为它展示了如何在下降算法中通过移动计数器来构造概率测度时处理“负质量”问题。我们的技术基本上修复了TCC'14论文“如何伪造辅助输入”中的缺陷。（B）我们的模拟器的复杂性比以前的作品，包括来自一致的最小-最大定理由于Vadhan和郑的结果更好。为了实现不可区分性，我们需要时间/电路大小的复杂度，这将之前的界限提高了一个系数。特别是，我们得到了有意义的可证明的安全性EUROPENTPT '09泄漏弹性流密码实例与标准的256位块密码，如。我们的提升技术采用了两步的方法。在第一步中，我们移动当前结果（如梯度或次梯度下降算法），并在单独的步骤中，我们修复最大的非负质量约束违反（如果适用）。
For any pair (X,Z) of correlated random variables we can think ofZas a randomized function ofX. If the domain ofZis small, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known assimulating auxiliary inputs. This idea of simulating auxiliary information turns out to be a very usefull tool, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results:(a)We present a novel boosting algorithm for constructing the simulator. This boosting proof is of independent interest, as it shows how to handle “negative mass” issues when constructing probability measures by shifting distinguishers in descent algorithms. Our technique essentially fixes the flaw in the TCC’14 paper “How to Fake Auxiliary Inputs”.(b)The complexity of our simulator is better than in previous works, including results derived from the uniform min-max theorem due to Vadhan and Zheng. To achieve-indistinguishability we need the complexityin time/circuit size, which improve previous bounds by a factor of. In particular, with we get meaningful provable security for the EUROCRYPT’09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like.Our boosting technique utilizes a two-step approach. In the first step we shift the current result (as in gradient or sub-gradient descent algorithms) and in the separate step we fix the biggest non-negative mass constraint violation (if applicable).