Supersingular Curves You can Trust
Original Paper Link:
Supersingular Curves You Can Trust
生成一条超奇异椭圆曲线,可以确保没有人知道它的自同态环,尽管有几个基于同构的协议依赖于这样一个对象,但是生成这样的曲线很困难
可信设置通常被提议作为一种变通方法,但有几个方面尚不清楚,本文开发了实际运行这种分布式可信设置仪式所需的工具
本文的关键贡献是第一个与任何基本域兼容的同胚知识的统计零知识证明,为了证明统计ZK,本文引入了具有Borel水平结构的同胚图,并证明了它们具有Ramanujan性质
其次,本文在简化的通用可组合性框架中,基于本文的ZK证明,分析了分布式可信设置协议的安全性
本文开发了ZK证明的优化实现,并提出了一种具体部署可信设置协议的策略
On Valiant’s Conjecture: Impossibility of Incrementally Verifiable Computation from Random Oracles
Original Paper Link:
On Valiant’s Conjecture: Impossibility of Incrementally Verifiable Computation from Random Oracles
Paul Valiant在2008年TCC大会上发表的具有里程碑意义的论文中引入了“增量可验证计算”的概念,该概念使证明者能够增量计算(潜在的)长期运行过程的正确执行的简洁证明,在没有任何进一步计算假设的情况下,该结构在随机预言机模型中被证明是安全的
然而,总体证明是使用随机预言机方法的非标准版本给出的,其中有时哈希函数是随机预言机,有时它作为电路有一个简短的描述,Valiant明确指出,这个模型是非标准的,但推测标准的随机预言方法是不够的
这个推测已经公开了14年,本文证明:如果证明系统可以以增量方式接收长见证作为输入,并且也是零知识,则推测为真,Valiant最初的结构没有这些性质,但可以很容易地扩展到模型中
本文将本文的结果与SNARK和增量可验证计算的最新可能性和不可能性结果联系起来
Speed-Stacking: Fast Sublinear Zero-Knowledge Proofs for Disjunctions
Original Paper Link:
Speed-Stacking: Fast Sublinear Zero-Knowledge Proofs for Disjunctions
基于最近用于零知识的析取编译器,本文提出了一种新的编译器,当应用于亚线性大小的证明时,可以在亚线性证明时间内产生亚线性大小析取零知识,且不会显著地增加证明大小
本文注意到,次线性零知识证明系统中的模拟可以比诚实证明者更快(无论是具体的还是渐进的)
本文讲本文的编译期应用于两类$O(\log n)$轮的协议:交互式预言机证明(Aurora和Fractal)和folding论证(压缩$\Sigma$-协议和Bulletproof)
本文的研究验证了编译器可以带来显著的节约,本文还发现编译器可以提供一个新的视角,通过它来理解ZKP,具有相同“独立”复杂性的协议的多个例子证明了这一点,这些协议在堆叠时表现得非常不同
HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates
Original Paper Link:
HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates
Plonk是一个广泛使用的简洁的非交互式证明系统,使用单变量多项式承诺,Plonk非常灵活:它支持具有低级“自定义”门的电路以及具有查找门的电路(查找门确保其输入包含在预定义的表中),对于大型电路,生成Plonk证明的瓶颈是需要计算大型FFT
本文提出了HyperPlonk,它是Plonk对布尔超立方体的一种自适应,使用了多线性多项式承诺,HyperPlonk保留了Plonk的灵活性,但提供了许多额外的好处
首先,它避免了在证明生成过程中需要FFT,更重要的是它支持比Plonk更高程度的自定义门,而不会影响证明程序的运行时间,这两种方法都可以显著加快证明器的运行时间
由于HyperPlonk依赖于多线性多项式承诺,我们重新审视了两种结构:Orion和Virgo,本文展示了如何将Orion的揭示验证大小减少到10kb以下(几乎提高了1000倍),并展示了如何讲Virgo FRI的揭示验证做到更简单、更短
Spartan and Bulletproofs are Simulation-Extractable for free!
Original Paper Link:
Spartan and Bulletproofs are simulation-extractable for free!
越来越多的高级零知识证明系统,尤其是zksNARK的部署,对其抵御现实世界攻击的安全性提出了关键问题
实践中有两类值得关注的攻击是自适应稳健性攻击和延展性攻击,在自适应稳健性攻击中,攻击者可以通过在生成证明后选择其公共输入来证明虚假陈述;在延展性攻击中,攻击者可以使用有效证明来创建另一个它自己不可能创建的有效证明
先前的工作表明,模拟可提取性(SIM-EXT)是证明系统的一个强有力的安全概念,可以排除这些攻击
本文证明了两个透明的、基于离散对数的zksNARK,Spartan和Bulletproof,如果离散对数假设在底层组中成立,则在随机预言机模型中是模拟可提取的(SIM-EXT)
由于需要这些假设来证明Spartan和Bullet-proof的标准安全性财产,本文的研究表明,SIM-EXT在这些方案中是free的
本文的Spartan结果为第一个SIM-EXT证明,包括线性和次线性验证器变体,Bulletproof的结果包括了聚合范围证明和算术电路变体,并且是第一个不依赖代数群模型(AGM)的结果,解决了Ganesh等人提出的一个悬而未决的问题
此外,本文对Attema等人(TCC'22)的树生成器提取定理进行了推广,可能具有独立的意义