Improved Straight-Line Extraction in the Random Oracle Model With Applications to Signature Aggregation
Improved Straight-Line Extraction in the Random Oracle Model With Applications to Signature Aggregation
复制标题
DOI：
10.1007/978-3-031-22966-4_10
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Yashvanth Kondi;Abhi Shelat
中科院分区：
文献类型：
--
作者：
Yashvanth Kondi;Abhi Shelat
本文的目的是提高随机预言模型中直线抽取技术的效率和适用性。随机预言模型中的直线抽取是指存在一个抽取器，该抽取器在给定某个定理上的先知的随机预言查询的情况下，能够以与产生验证证明的概率大致相同的概率产生证明者。这一概念既适用于零知识协议，也适用于以压缩证明为目标的可验证计算。Pass(Crypto‘03)首先展示了如何使用剪切和选择技术来实现NP的这一性质，该技术在通信中产生了1比特的开销，其中有一个安全参数。Fischlin(Crypto‘05)提出了一种更有效的基于“工作证明”的技术，它降低了这种代价，但只适用于一类具有“准唯一响应”性质的Sigma协议，例如，它不一定包括Sigma协议的标准OR组合。我们对最先进技术的改进范围为70-200，以获得最佳压缩参数。这归功于唯一适合的多项式求值算法，以及对依赖于多冲突和生日悖论的工作证明比反转固定目标更快的洞察。当应用于NIZK设置时，我们基于碰撞的工作证明通常也改善了Prover的随机预言查询的复杂性。除了降低了Fischlin‘s Prover的查询复杂度外，对于一类特殊的Sigma协议，我们还首次给出了一个新的下界.最后，我们扩展了Fischlin的方法，使其适用于一类更一般的强健全Sigma协议，其中包括OR组合.我们通过仔细地随机化Fischlin的技术来实现这一点--我们证明了它目前的确定性性质阻止了它在某些多见证语言中的应用。
The goal of this paper is toimprove the efficiency and applicabilityof straightline extraction techniques in the random oracle model.Straightline extraction in the random oracle modelrefers to the existence of an extractor, which given the random oracle queries made by a proveron some theoremx, is able to produce a witnesswforxwith roughly the same probability thatproduces a verifying proof. This notion applies to both zero-knowledge protocols and verifiable computation where the goal iscompressinga proof.Pass (CRYPTO ’03) first showed how to achieve this property for NP using acut-and-choosetechnique which incurred a-bit overhead in communication whereis a security parameter. Fischlin (CRYPTO ’05) presented a more efficient technique based on “proofs of work” that sheds thiscost, but only applies to a limited class of Sigma Protocols with a “quasi-unique response” property, which for example, does not necessarily include the standard OR composition for Sigma protocols.WithSchnorr/EdDSA signature aggregationas a motivating application, we develop new techniques to improve the computation cost of straight-line extractable proofs. Our improvements to the state of the art range from70–200for the best compression parameters. This is due to a uniquely suited polynomial evaluation algorithm, and the insight that a proof-of-work that relies on multicollisions and the birthday paradox is faster to solve than inverting a fixed target.Our collision based proof-of-work more generally improves the Prover’s random oracle query complexity when applied in the NIZK setting as well. In addition to reducing the query complexity of Fischlin’s Prover, for a special class of Sigma protocols we can for the first time closely match a new lower bound we present.Finally we extend Fischlin’s technique so that it applies to a more general class ofstrongly-soundSigma protocols, which includes the OR composition. We achieve this by carefully randomizing Fischlin’s technique—we show that its current deterministic nature prevents its application to certain multi-witness languages.