Cryptographic Hashing From Strong One-Way Functions
Cryptographic Hashing From Strong One-Way Functions
复制标题
来自强单向函数的加密散列
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Alex Lombardi
中科院分区：
文献类型：
--
作者：
Justin Holmgren;Alex Lombardi
从单向函数构造抗碰撞哈希族（CRHF）是理论密码学中一个长期存在的开放问题和挫折的来源。事实上，有很强的负面结果：从单向函数的黑盒分离是2−（1−o（1））n-安全的，对多项式时间的对手（Simon，EURONTEPT '98），甚至从不可混淆性混淆（Asharov和Segev，FOCS '15）。在这项工作中，我们制定了一个温和的加强指数安全的单向函数，我们从这样的功能构建CRHF。具体来说，我们的安全概念要求每个多项式时间算法最多有2−n ·n（n）的概率反转两个独立的挑战。更一般地，我们考虑同时反演k个函数f1，. . .，fk，我们称其构成“单向乘积函数”（OWPF）。我们证明了足够硬的OWPF产生的哈希家庭是多输入相关棘手的（Canetti，Goldreich和Halevi，STOC '98）相对于所有稀疏（有界arity）的输出关系。此外，假设不可分割性混淆，我们构建哈希家族，实现更广泛的概念的相关性棘手，扩展Kalai，Rothblum和Rothblum（NITPTO '17）最近的工作。特别是，这些家庭是足够的实例化的菲亚特-沙米尔启发式在平原模型的自然类的交互式证明。我们的结果的一个有趣的后果是一个潜在的新途径绕过黑盒分离。特别是，证明（必须使用非黑盒技术）平行重复放大了特定单向函数的难度-例如，所有单向排列-足以直接绕过西蒙的不可能性结果。
Constructing collision-resistant hash families (CRHFs) from one-way functions is a long-standing open problem and source of frustration in theoretical cryptography. In fact, there are strong negative results: black-box separations from one-way functions that are 2−(1−o(1))n-secure against polynomial time adversaries (Simon, EUROCRYPT ’98) and even from indistinguishability obfuscation (Asharov and Segev, FOCS ’15). In this work, we formulate a mild strengthening of exponentially secure one-way functions, and we construct CRHFs from such functions. Specifically, our security notion requires that every polynomial time algorithm has at most 2−n · negl(n) probability of inverting two independent challenges. More generally, we consider the problem of simultaneously inverting k functions f1, . . . , fk, which we say constitute a “one-way product function” (OWPF). We show that sufficiently hard OWPFs yield hash families that are multi-input correlation intractable (Canetti, Goldreich, and Halevi, STOC ’98) with respect to all sparse (bounded arity) output relations. Additionally assuming indistinguishability obfuscation, we construct hash families that achieve a broader notion of correlation intractability, extending the recent work of Kalai, Rothblum, and Rothblum (CRYPTO ’17). In particular, these families are sufficient to instantiate the Fiat-Shamir heuristic in the plain model for a natural class of interactive proofs. An interesting consequence of our results is a potential new avenue for bypassing black-box separations. In particular, proving (with necessarily non-black-box techniques) that parallel repetition amplifies the hardness of specific one-way functions – for example, all oneway permutations – suffices to directly bypass Simon’s impossibility result.