Random Oracles and Non-Uniformity
Random Oracles and Non-Uniformity
复制标题
随机预言和不均匀性
DOI：
10.1007/978-3-319-78381-9_9
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
J. Steinberger
中科院分区：
文献类型：
--
作者：
Sandro Coretti;Y. Dodis;Siyao Guo;J. Steinberger
在辅助输入随机预言模型中，攻击者可以在攻击系统之前计算关于随机预言的任意S泄漏比特，然后在攻击过程中使用额外的T预言查询来计算关于随机预言的任意S泄漏比特。该模型在传统的随机预言机证明没有用处的情况下具有自然的应用：(A)针对非一致攻击者的安全性；(B)针对预处理的安全性。我们得到了一些关于AI-ROM的新结果：
Unruh(Crypto‘07)引入了预采样技术，它通常将AI-ROM中的安全证明简化为一个简单得多的P比特固定随机预言模型(BF-ROM)，其中攻击者可以在一些P坐标上任意固定\(\数学O\)的值，但随后随机选择剩余的坐标。Unruh在此转换中的安全损失为\(\sqrt{ST/P}\)。我们将这一损失改进到最佳值O(ST/P)，为AI-ROM中的各种不可区分应用获得了几乎严格的界。
虽然基本的预采样技术不能给出不可预测应用的严格界限，但我们引入了一种新的“乘法版本”的预采样，它允许将预采样集合的P的大小大大减少到\(P=O(ST)\)，并为AI-ROM中的各种不可预测应用产生几乎严格的安全界。定性地，它证实了Unruh的“多项式预抽样猜想”--Dodis等人一般反驳了这个猜想。(EUROCRYPT‘17)-适用于不可预测应用的特殊情况。
利用我们的技术，我们几乎反驳了Dodis等人得到的几乎所有的AI-ROM界。(使用更费力的压缩技术)，但我们也将其应用于压缩技术不适用(例如，计算缩减)或看起来难以处理(例如，Merkle-Damgard散列)的许多设置。
证明了对任意m比特输出的盐化Merkle-Damgard哈希函数，存在一个大小为(varTheta(2^{m/3}))(以盐为输入)的碰撞发现回路，它显著低于针对一致攻击者的生日安全性猜想。
我们构建了两个编译器来一般地将在传统ROM中证明的应用程序的安全性扩展到AI-ROM。一位编译器简单地将公共盐预先添加到随机预言机中，这表明加盐通常可以证明会使预处理失败。
We revisit security proofs for various cryptographic primitives in the auxiliary-input random-oracle model (AI-ROM), in which an attacker \(\mathcal A\) can compute arbitrary S bits of leakage about the random oracle \(\mathcal O\) before attacking the system and then use additional T oracle queries to \(\mathcal O\) during the attack. This model has natural applications in settings where traditional random-oracle proofs are not useful: (a) security against non-uniform attackers; (b) security against preprocessing. We obtain a number of new results about the AI-ROM:
Unruh (CRYPTO’07) introduced the pre-sampling technique, which generically reduces security proofs in the AI-ROM to a much simpler P-bit-fixing random-oracle model (BF-ROM), where the attacker can arbitrarily fix the values of \(\mathcal O\) on some P coordinates, but then the remaining coordinates are chosen at random. Unruh’s security loss for this transformation is \(\sqrt{ST/P}\). We improve this loss to the optimal value O(ST / P), obtaining nearly tight bounds for a variety of indistinguishability applications in the AI-ROM.
While the basic pre-sampling technique cannot give tight bounds for unpredictability applications, we introduce a novel “multiplicative version” of pre-sampling, which allows to dramatically reduce the size of P of the pre-sampled set to \(P=O(ST)\) and yields nearly tight security bounds for a variety of unpredictability applications in the AI-ROM. Qualitatively, it validates Unruh’s “polynomial pre-sampling conjecture”—disproved in general by Dodis et al. (EUROCRYPT’17)—for the special case of unpredictability applications.
Using our techniques, we reprove nearly all AI-ROM bounds obtained by Dodis et al. (using a much more laborious compression technique), but we also apply it to many settings where the compression technique is either inapplicable (e.g., computational reductions) or appears intractable (e.g., Merkle-Damgard hashing).
We show that for any salted Merkle-Damgard hash function with m-bit output there exists a collision-finding circuit of size \(\varTheta (2^{m/3})\) (taking salt as the input), which is significantly below the \(2^{m/2}\) birthday security conjectured against uniform attackers.
We build two compilers to generically extend the security of applications proven in the traditional ROM to the AI-ROM. One compiler simply prepends a public salt to the random oracle, showing that salting generically provably defeats preprocessing.