Does Fiat-Shamir Require a Cryptographic Hash Function?
Does Fiat-Shamir Require a Cryptographic Hash Function?
复制标题
Fiat-Shamir 是否需要加密哈希函数？
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Willy Quach
中科院分区：
文献类型：
--
作者：
Yilei Chen;Alex Lombardi;Fermi Ma;Willy Quach
Fiat-Shamir变换是一种通过用协议副本的确定性散列替换随机验证器消息来减少公共币协议中交互的通用方法。这种转换的可靠性通常是启发式的，缺乏正式的安全性证明。相反，为了论证安全性，人们可以依赖随机预言机方法，该方法非正式地指出，每当随机预言机正确地实例化Fiat-Shamir时，一个“充分非结构化”的散列函数（例如固定长度的SHA-2）就足够了。最后，对于一些特殊的交互式协议，已知如何（1）隔离足以实例化Fiat-Shamir的散列函数的具体安全属性，以及（2）在诸如带错误学习的密码学假设下构建满足该属性的散列函数。在这项工作中，我们放弃了这种方法，并询问Fiat-Shamir是否真的需要加密哈希函数。也许令人惊讶的是，我们表明，在其最常见的两个应用中--构建签名方案以及（通用）非交互式零知识参数--使用极其简单且非加密的哈希函数（例如sum-mod-p或位分解），存在可靠的Fiat-Shamir实例。在某些情况下，我们对交互式协议进行了理想化的假设（即，我们调用通用组模型），而在其他情况下，我们认为在平原模型的合理性。在一个高层次上，每个产生的非交互式协议的安全性来自硬问题已经隐含在原来的交互式协议。另一方面，我们还确定了重要的情况下，加密哈希函数是证明必要的实例化Fiat-Shamir。我们希望这项工作能够更好地理解哈希函数在Fiat-Shamir变换中的确切作用。* 签证研究。电子邮件：chenyilei.ra@gmail.com.（注：麻省理工学院）电子邮件：alexjl@mit.edu。研究部分得到国家发展和社会经济小组研究金的支持。研究部分由NSF赠款CNS-1350619和CNS-1414119支持，并由国防高级研究计划局（DARPA）和美国陆军研究办公室根据合同W 911 NF-15-C-0226和W 911 NF-15-C-0236支持。普林斯顿大学和NTT研究。电子邮件：fermima@alum.mit.edu。东北大学。电子邮件：quach. w@husky.neu.edu。
The Fiat-Shamir transform is a general method for reducing interaction in public-coin protocols by replacing the random verifier messages with deterministic hashes of the protocol transcript. The soundness of this transformation is usually heuristic and lacks a formal security proof. Instead, to argue security, one can rely on the random oracle methodology, which informally states that whenever a random oracle soundly instantiates Fiat-Shamir, a hash function that is “sufficiently unstructured” (such as fixedlength SHA-2) should suffice. Finally, for some special interactive protocols, it is known how to (1) isolate a concrete security property of a hash function that suffices to instantiate Fiat-Shamir and (2) build a hash function satisfying this property under a cryptographic assumption such as Learning with Errors. In this work, we abandon this methodology and ask whether Fiat-Shamir truly requires a cryptographic hash function. Perhaps surprisingly, we show that in two of its most common applications — building signature schemes as well as (general-purpose) non-interactive zero-knowledge arguments — there are sound Fiat-Shamir instantiations using extremely simple and non-cryptographic hash functions such as sum-mod-p or bit decomposition. In some cases, we make idealized assumptions about the interactive protocol (i.e., we invoke the generic group model), while in others, we argue soundness in the plain model. At a high level, the security of each resulting non-interactive protocol derives from hard problems already implicit in the original interactive protocol. On the other hand, we also identify important cases in which a cryptographic hash function is provably necessary to instantiate Fiat-Shamir. We hope that this work leads to an improved understanding of the precise role of the hash function in the Fiat-Shamir transformation. *Visa Research. Email: chenyilei.ra@gmail.com. †MIT. Email: alexjl@mit.edu. Research supported in part by an NDSEG fellowship. Research supported in part by NSF Grants CNS-1350619 and CNS-1414119, and by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under contracts W911NF-15-C-0226 and W911NF-15-C-0236. ‡Princeton University and NTT Research. Email: fermima@alum.mit.edu. §Northeastern University. Email: quach.w@husky.neu.edu.