SPARKs: Succinct Parallelizable Arguments of Knowledge
SPARKs: Succinct Parallelizable Arguments of Knowledge
复制标题
SPARKs：简洁的可并行知识论证
DOI：
10.1145/3549523
复制
发表时间：
2022
影响因子：
2.5
通讯作者：
Pass, Rafael
中科院分区：
文献类型：
--
作者：
Ephraim, Naomi;Freitag, Cody;Komargodski, Ilan;Pass, Rafael
我们引入了一个简洁的知识论证（SPARK）的概念。这是一个知识的论点，具有以下三个效率属性，用于计算和证明一个（非确定性，多项式时间）并行RAM计算，可以在最多处理器的并行时间T中计算：-证明器的（并行）运行时间是。(In换句话说，证明器的运行时间基本上是T大计算时间！）-证明者使用的处理器最多。-通信和验证器的复杂性都是，三者的结合是可取的，因为它提供了一种方法来利用并行度的适度增加，以支持接近最佳的运行时间。我们强调，即使是一个因素两个开销的证明者的并行运行时间是不允许的。我们的主要贡献是一个通用的建设SPARKs从任何简洁的参数的知识，其中证明者的并行运行时间是当使用pprocessors，假设抗碰撞哈希函数。当适当地实例化我们的建设，我们实现了一个四轮SPARK为任何并行RAM计算假设只有碰撞阻力。此外，假设存在一个简洁的非交互式知识库（SNARK），我们构造了一个非交互式SPARK，它也保留了底层计算的空间复杂度高达factors。首先，它们立即意味着具有接近最佳证明器（并行）运行时间的委托协议。这反过来又提供了一种从任何序列函数构造可验证延迟函数（VDF）的方法。当顺序函数也是存储器硬的时，这产生存储器硬VDF的第一构造。
We introduce the notion of aSuccinct Parallelizable Argument of Knowledge(SPARK). This is an argument of knowledge with the following three efficiency properties for computing and proving a (non-deterministic, polynomial time) parallel RAM computation that can be computed in parallel timeTwith at mostpprocessors:—The prover’s (parallel) running time is. (In other words, the prover’s running time is essentiallyTfor large computation times!)—The prover uses at mostprocessors.—The communication and verifier complexity are both.The combination of all three is desirable, as it gives a way to leverage a moderate increase in parallelism in favor of near-optimal running time. We emphasize that even a factor two overhead in the prover’s parallel running time is not allowed.Our main contribution is a generic construction of SPARKs from any succinct argument of knowledge where the prover’s parallel running time iswhen usingpprocessors, assuming collision-resistant hash functions. When suitably instantiating our construction, we achieve a four-round SPARK foranyparallel RAM computation assuming only collision resistance. Additionally assuming the existence of a succinctnon-interactiveargument of knowledge (SNARK), we construct a non-interactive SPARK that also preserves the space complexity of the underlying computation up tofactors.We also show the following applications of non-interactive SPARKs. First, they immediately imply delegation protocols with near optimal prover (parallel) running time. This, in turn, gives a way to construct verifiable delay functions (VDFs) from any sequential function. When the sequential function is also memory-hard, this yields the first construction of a memory-hard VDF.
登录
查看更多内容
DOI：
--
发表时间：
2017
期刊：
Theory of Cryptography Conference
影响因子：
--
作者：
J. Alwen;Björn Tackmann
通讯作者：
Björn Tackmann
DOI：
10.1145/2699436
发表时间：
2015-09
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
S. Goldwasser;Y. Kalai;G. Rothblum
通讯作者：
S. Goldwasser;Y. Kalai;G. Rothblum
接近见证长度的局部证明[扩展摘要]
DOI：
--
发表时间：
2020
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Noga Ron;Ron D. Rothblum
通讯作者：
Ron D. Rothblum
能隙放大 PCP 定理
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
B. Vesenmayer
通讯作者：
B. Vesenmayer
多证明者交互式证明的简洁论证及其效率优势
影响因子：
3
作者：
Nir Bitansky;A. Chiesa
通讯作者：
A. Chiesa