On Round-Efficient Argument Systems
On Round-Efficient Argument Systems
复制标题
关于轮有效论证系统
DOI：
10.1007/11523468_12
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
H. Wee
中科院分区：
文献类型：
--
作者：
H. Wee
我们考虑构建循环有效的公共硬币论证系统的问题，也就是说，交互式证明系统只有在循环次数不变的情况下才是计算上合理的。我们专注于NTime（T（n））的参数系统，其中通信复杂度或验证器的运行时间在T（n）中是次多项式，例如Kilian的NP参数系统[Kil 92]和通用参数[BG 02，Mic 00]。我们开始的观察，在标准的复杂性假设，这样的论点系统需要至少2轮。接下来，我们将非平凡的2轮论证系统的存在性与NP中的硬平均搜索问题和NP的有效公共硬币零知识论证的存在性联系起来。最后，我们证明了Fiat-Shamir范式[FS 86]和Babai-Moran轮约化[BM 88]未能保持某些3轮和4轮论证系统的计算可靠性。
We consider the problem of constructing round-efficient public-coin argument systems, that is, interactive proof systems that are only computationally sound with a constant number of rounds. We focus on argument systems for NTime(T(n)) where either the communication complexity or the verifier’s running time is subpolynomial in T(n), such as Kilian’s argument system for NP [Kil92] and universal arguments [BG02,Mic00]. We begin with the observation that under standard complexity assumptions, such argument systems require at least 2 rounds. Next, we relate the existence of non-trivial 2-round argument systems to that of hard-on-average search problems in NP and that of efficient public-coin zero-knowledge arguments for NP. Finally, we show that the Fiat-Shamir paradigm [FS86] and Babai-Moran round reduction [BM88] fails to preserve computational soundness for some 3-round and 4-round argument systems.