ZKP Relevant

A Detailed Analysis of Fiat-Shamir with Aborts

Link：A Detailed Analysis of Fiat-Shamir with Aborts (iacr.org)

Lyubashevky签名基于FS终止范式（Fiat-Shamir with Aborts），该范式通过重复执行，直到循环迭代未触发终止条件，将终止概率不可忽略的交互式协议转换为签名（非交互式中将抗碰撞Hash函数建模为随机预言机，并用其代替Verifier的挑战）

之前的研究大多数考虑了具有有界终止次数的设置（如果在规定次数的循环迭代中未输出签名，则签名失败），部分实例化（比如Dilithium）会一直运行直到输出签名为止（终止次数无界的情况）

如果将RO与循环迭代相结合，在有界和无界的情况下都会引发技术问题，包括方案的正确性，协议时间和安全性

本文首先分析了现有研究结果中的错误，其次分析了有界情况的QROM中两个情况（基于Kiltz等然在Eurocrypto 18和Crilo等人在Asiacrypt 21的研究）

本文证明了底层Sigma协议实现了比通常考虑的具有终止Sigma协议更强的零知识性质，从而校正分析结果

本文的另一个贡献是对无界情况进行了详细的分析

A Note on Non-Interactive Zero-Knowledge from CDH

Link：Unpublished

在CDH亚指数困难性假设下，本文为所有NP建立了非交互式零知识和ZAP论证，合理性在无限多个安全参数和对抗统一的敌手（Uniform Adversaries）时成立

在CDH假设和LPN假设的多项式假设下，本文还证明了具有这些相同性质的NIZK论证的存在性，且这两种情况下CDH假设无需配对群

Infinitely-often 统一安全性是常用的非黑盒技术的标准副产物，这些技术建立在一些（不安全）原语之间的析取上

在本文的证明过程中，本文开发了这些非黑盒技术的新变体，并得到了下列结果：获得了显示构造（以前的研究仅表明存在），其中安全性适用于相对密集的一组安全参数（而非任意无限组安全参数）

本文证明了本文的结果可能有超出本文主要结论的应用

Brakedown: Linear-time and field-agnostic SNARKs for R1CS

Link：Brakedown: Linear-time and post-quantum SNARKs for R1CS (iacr.org)

本文提出了NP语言的第一个线性Prover Time的SNARK，Prover构造证明时只需要$O(N)$次域运算（$N$表示R1CS实例大小），无需可信设置，且似乎满足后量子安全

Brakedown可以兼容任意满足大小的有限域，这是一个目前已知的证明系统中的新的性质

Brakedown借鉴了$[BCG20]$中基于线性时间编码的多项式承诺的相关思想，将其于线性时间交互式证明系统相结合，得到了一个线性时间IOP和对应的SNARK

除此之外，本文还基于RS码，实现了Brakedown的一个变体，本文称该变体为Shockwave，但是Shockwave不是线性时间的SNARK，不过它比Brakedown的证明大小和验证时间都要短

这一篇在Database中的标题和eprint中2021/1043的标题不一样，摘要大致是一致的，Link里面给的Publication Info是Preprint,Minor，不知道录用的这篇有多少修改

Correlation Intractability and SNARGs from Sub-exponential DDH

Link：Correlation Intractability and SNARGs from Sub-exponential DDH (iacr.org)

本文基于亚指数DDH假设，为批处理NP和P提供了SNARG的构造，证明大小为对数多项式阶

本文通过FS范式的安全实例化的相关困难性框架来得到本文的结论

本文的研究结果和相关研究方向为：基于亚指数DDH，为TC0中可验证的小输入（Small Input）乘积关系构建一个新的相关难处理的Hash函数

Horst Meets Fluid-SPN: Griffin for Zero-Knowledge Applications

Link：Horst Meets Fluid-SPN: Griffin for Zero-Knowledge Applications (iacr.org)

ZKP是现代密码学中的一个重要组成部分，且密码学Hash函数通常会作为主要组成部分

过去的研究为了降低Hash函数在ZKP协议中的开销，构建了许多新的Hash函数，包括但不限于Poseidon、Rescue，这些Hash函数与AES、SHA系列的设计不同，他们都在素数域上完成计算，而非二进制域

而且Poseidon和Rescue这两者都具有相似的特征，例如采用了SPN架构和可逆幂映射（Invertible Power Maps）来实例化非线性层，这些特征允许设计者为方案提供足够的安全性，但是也会带来一定的限制，从而影响具体应用中的性能

本文提出了Horst架构，在Feistel架构中引入了乘法，原版的Feistel架构为$(x,y)=(y+F(x),x)$，Horst架构为$(x,y)=(y*G(x)+F(x),x)$

通过分析SNARK和STARK中的性能标准，本文展示了如何将扩展Horst方案与类Rescue的SPN方案相结合，从而在目标应用中提供足够的安全性，捅死降低效率

本文为本文的新设计Griffin提供了安全性分析，并与其他方案做了一些比较

LaBRADOR: Compact Proofs for R1CS from Module-SIS

Link：LaBRADOR: Compact Proofs for R1CS from Module-SIS (iacr.org)

用于大型电路的最紧凑的量子安全证明系统是PCP型系统，如Ligero、Aurora和Shockwave，此类方案仅需要很弱的密码假设，即将Hash函数建模为随机预言机

按照预期，应当可以使用更强的假设（比如Module-SIS）来构建更紧凑的证明系统，但是目前为止还不存在此类证明系统

本文通过引入基于格的R1CS的递归摊销证明来解决这个问题，本文称为LaBRADOR，该证明比已知的基于Hash的证明系统具有更紧凑的证明大小

经测试，128位的安全性上，LaBRADOR在证明具有$2^{20}$个约束，模数为$2^{64}+1$的R1CS时，证明大小仅为58KB，比以前的量子安全证明小一个数量级

Lattice-Based Succinct Arguments for NP with Polylogarithmic-Time Verification

Link：Unpublished

实践中，理想的论证系统的证明大小应当比较小，验证很简洁，且要求协议基于标准假设的后量子安全，但是迄今为止的构造均不满足这些要求

比如依赖于Kilian引入的Merkle Hash的简洁论证系统，该方案在实践中的的证明大小会很大，采用同态承诺的方案可以得到较小的证明大小，但是后者要么依赖于不满足后量子安全的假设，要么无法达到简洁的证明大小/验证

本文为NP构造了第一个具有简洁验证交互式论证系统，方案基于格构造，且依赖于格的承诺同态性质，对于具有$N$个门的运算电路，本文基于RSIS问题的困难性，设计了一个具有$polylog(N)$通信量开销和验证时间的方案

本文的核心技术是基于分层双线性模（Leveled Bilinear Modules）的承诺方案构建的委托协议，本文证明了分层双线性模可以从前向量子和后量子的密码假设中实现

Lattice-based Succinct Arguments from Vanishing Polynomials

Link：Unpublished

之前的简洁论证方案基于格构造，不仅具有丰富的代数特性，还可以满足后量子安全，本文的研究提出了一种新的方法来构建高效的基于格的简洁论证

本文的主要技术为一种基于消失多项式的新的承诺方案，本文不仅分析了该承诺方案的安全性，并展示了如何利用承诺中特殊的代数结构来构建新的基于格的简洁论证

本文的主要工作如下

  • 构造了第一个基于线性关系的递归折叠协议（类似于Bulleproof），验证开销为对数多项式时间（Verifier的验证开销一直是协议的效率瓶颈之一，且与采用的基本假设无关）
  • 第一个基于格的可验证延迟函数，基于最近引入的序列关系（Sequential Relation）构造
  • 在预处理模型中，为NP构建了第一个基于格的简洁论证，该方案的合理性基于（知识）K-R-ISIS假设

Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments

Link：Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments (iacr.org)

NIZK中最重要的两个性质是零知识性和简洁性，之前的工作中，Kitagawa等人研究了如何基于NP语言的SNARG构建NIZK，该研究介绍了如何利用论证系统中的简洁性，并将其转换为零知识性（？）

本文研究类似的问题，即利用简洁性来获取零知识性，本文的出发点为NP的批处理论证，批处理论证允许Prover向Verifier证明$T$个NP Statement$x_1,\dots,x_T$，且证明大小与$T$呈亚线性关系

与NP的SNARG不同，批处理论证的NP可以基于群的假设（有配对和无配对都可）构建，也可以基于格的假设构建，但是批处理的挑战在于：证明大小仅均摊到Statement的数量上，不过可以将相关的witness编码到少数实例中

本文介绍了如何基于一个局部伪随机数生成器和双模承诺方案（Dual-Mode Commitment Scheme）来构建NP的批处理论证，以获得NP的NIZK，本文的研究提供了一种新的从简洁性到零知识性的通用方法，并强调了简洁性与零知识性之间的联系

Non-interactive Universal Arguments

Link：Non-interactive Universal Arguments (iacr.org)

2002年Barak和Goldreich引入了通用论证的概念，并基于多项式困难的抗碰撞Hash函数为非确定性计算头建了一个交互式通用论证

近年来，在标准困难假设下，为确定性计算构建非交互式简洁论证的研究方向取得了许多进展，但是研究的方案仅在亚指数假设下才具有普遍性

在多项式困难的全同态加密和一个普遍认为最坏情况的复杂度假设下，本文证明了一个一般提升引理（Lifting Theorem），其表明了所有校友的非交互式简洁论证可以具有普遍性，所需的复杂性假设为Non-Uniformity does not allow arbitrary polynomial speedup（没看懂啥意思），不过在统一敌手的情况下，无需此类额外的假设

On the Impossibility of Algebraic NIZK In Pairing-Free Groups

Link：On the Impossibility of Algebraic NIZK In Pairing-Free Groups (iacr.org)

非交互式零知识证明（NIZK）允许Prover通过只发送一条消息而不传递任何其他信息来说服Verifier，在CRS模型中，已经从群论假设中提出了许多实例

一方面而言，其中一些构造以黑盒的方式使用群结构，但依赖于配对，比如Groth Sahai证明系统，另一方面而言，最近的一项研究采用Correlation Intracoble Hash函数在无配对群中从亚指数DDH中实现了NIZK，但是代价是以非黑盒的形式使用这个群

目前为止仍不知道有什么构造可以同时将其安全性归约至无配对群问题，并且以黑河的方式使用这个群

本文证明了对于一大类的NIZK，要么依赖于使用无配对群表示元素，且以非黑盒的形式，要么安全性会归约至外部的困难假设，具体而言，本文的不可能性适用于下列两个无法比较的情况

  • 第一部分为知识论证（AoK），证明了在给定的单向函数下，前像是已知的
  • 第二部分包含了困难子集问题的NIZK，捕获了DDH、Decision-Linear和矩阵DDH（Matrix-DDH）等关系

Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures From VOLE-in-the-Head

Link：Non-interactive Universal Arguments (iacr.org)

本文提出了一种新的方式，将指定Verifier设置中的ZKP协议转换为公共掷币协议，转化可以是非交互式的和公开可验证的

本文的转换方式适用于大部分基于OT的ZK协议，尤其是本文介绍了其用于基于VOLE的快速协议，并升级这些协议以支持公开可验证性

本文的ZK协议具有线性阶证明大小，且比基于MPC-in-the-head的方法更简单，更小，更快

为了构建VOLE-in-the-head，同时使其支持二进制电路和大型有限域，本文开发了几种新的技术，包括为SoftSpokenOT协议（Crypto 2022）给出了新的安全性证明（该协议将其推广为在大域上的某些VOLE相关性）

其次，本文提出了一种新的ZK协议，该协议利用此类VOLE，并得到了一种公开可验证的VOLE-in-the-head协议，通信开销仅比最好的基于指定Verifier的VOLE协议多一倍，如果使用FS变换来实现非交互式协议时，本文以逐轮分析的方式来分析本文的合理性

对于本文的NIZK的应用，本文提出了FAEST，一种基于AES的后量子签名方案，其是第一个小于SPHINCS+的基于ARS的签名方案，安全级别为128时，签名大小为5.6-6.6KB之间（最小版本的SPHINCS+为7.9KB），不过FAEST验签很慢，签名时间比SPHINCS+快8-40倍左右

SNARGs for Monotone Policy Batch NP

Link：Unpublished

本文基于LWE假设，为单调策略批处理NP（Monotone Policy Batch NP）构建了一个SNARG

MPB-NP是NP的一个子类，其与一个单调策略函数$f:\{0,1\}^k\rarr \{0,1\}$相关，实例记为$(x_1,\dots,x_k)$，若$x_j\in L$，则有$b_j=1$，函数$f$满足$f(b_1,\dots,b_k)=1$

本文的SNARG在非自适应设置中是一个知识论证，且满足部分较新的抵抗自适应敌手的可抽取性

本文的SNARG是该NP子类下第一个基于标准假设的SNARG，该NP子类不具有（计算性）non-signaling PCP，但是本文的方案与这个框架偏离

本文的构造将现有的实例编码方式和新的全局合理性拟论证NP（Quasi-Argument NP）相结合，本文用到的编码方式为谓词可抽取Hash族（Predicate-Extractable Hash Family）

Succinct Arguments for RAM Programs via Projection Codes

Link：Unpublished

为了证明涉及大数据库的子集的Statement，本文引入并研究了投影码（Projection Codes）的概念

标准的纠错码允许将消息$x$编码为码字$X$，若部分码字传输过程中受损，仍然可以恢复消息$x$，投影码可以将这种纠错扩展到$x$的任意比特子集，具体而言，对于$x$到其子集$s$的投影，均存在一个大小相同的子集$S$，使得$x|_S$是消息$x|_s$的鲁棒编码

本文的一个结果是投影码，另一个是在（大的）承诺数据库上计算RAM程序的简洁论证，也即当RAM程序运行时间比数据库大小小得多的情况下，Prover和Verifier的通信开销和运行时间也接近最优

本文的方案仅以黑盒方式使用抗碰撞Hash函数，为以前的非黑盒结构提供了第一个具有类似渐进效率的黑盒替代方案

References

$[1]$ Papers from CRYPTO 2023 (iacr.org)

‍