Shorter and Faster Post-Quantum Designated-Verifier zkSNARKs from Lattices
Shorter and Faster Post-Quantum Designated-Verifier zkSNARKs from Lattices
复制标题
来自莱迪思的更短、更快的后量子指定验证者 zkSNARK
DOI：
10.1145/3460120.3484572
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Wu, David J.
中科院分区：
文献类型：
--
作者：
Ishai, Yuval;Su, Hang;Wu, David J.
Zero-knowledge简洁的知识参数（zkSNARKs）使一般NP语言的成员资格的有效隐私保护证明成为可能。我们在这项工作中的重点是后量子zkSNARKs，重点是最小化证明大小。目前，最好的前量子构造和最好的后量子构造之间的证明大小有1000倍的差距。在这里，我们在指定验证者预处理模型中开发并实现了新的基于格的zkSNARKs。使用我们的构造，在初始预处理步骤之后，大小为2^20的NP关系的证明刚刚超过16 KB。我们的证明比以前的一般NP语言的后量子zkSNARKs短10.3倍。与以前的基于格的zkSNARKs（也在指定验证者预处理模型中）相比，我们在证明大小上减少了42倍，在证明器的运行时间上减少了60倍，同时实现了更高水平的可靠性。与Groth（Eurocrypt 2016）的最短前量子zkSNARKs相比，我们基于格的构造中的证明大小长131倍，但证明器和验证器都更快（分别为1.2倍和2.8倍）。我们的构造遵循Bitansky等人（TCC 2013）和Boneh等人（Eurocrypt 2017）的总体蓝图，将线性概率可检查证明（线性PCP）与线性向量加密方案结合在一起。我们开发了一个具体有效的格为基础的实例化这个编译器考虑二次扩展领域的温和的特点，并使用线性向量加密秩2模块格。
Zero-knowledge succinct arguments of knowledge (zkSNARKs) enable efficient privacy-preserving proofs of membership for general NP languages. Our focus in this work is on post-quantum zkSNARKs, with a focus on minimizing proof size. Currently, there is a 1000x gap in the proof size between the best pre-quantum constructions and the best post-quantum ones. Here, we develop and implement new lattice-based zkSNARKs in the designated-verifier preprocessing model. With our construction, after an initial preprocessing step, a proof for an NP relation of size 2^20 is just over 16 KB. Our proofs are 10.3x shorter than previous post-quantum zkSNARKs for general NP languages. Compared to previous lattice-based zkSNARKs (also in the designated-verifier preprocessing model), we obtain a 42x reduction in proof size and a 60x reduction in the prover's running time, all while achieving a much higher level of soundness. Compared to the shortest pre-quantum zkSNARKs by Groth (Eurocrypt 2016), the proof size in our lattice-based construction is 131x longer, but both the prover and the verifier are faster (by 1.2x and 2.8x, respectively). Our construction follows the general blueprint of Bitansky et al. (TCC 2013) and Boneh et al. (Eurocrypt 2017) of combining a linear probabilistically checkable proof (linear PCP) together with a linear-only vector encryption scheme. We develop a concretely-efficient lattice-based instantiation of this compiler by considering quadratic extension fields of moderate characteristic and using linear-only vector encryption over rank-2 module lattices.
登录
查看更多内容
DOI：
10.1145/3460120.3484767
发表时间：
2021-11
期刊：
Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security
影响因子：
--
作者：
Jiaheng Zhang;Weijie Wang;Yinuo Zhang;Yupeng Zhang
通讯作者：
Jiaheng Zhang;Weijie Wang;Yinuo Zhang;Yupeng Zhang
随机预言模型中的次二次 SNARG
DOI：
--
发表时间：
2021
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
A. Chiesa;E. Yogev
通讯作者：
E. Yogev
基于错误学习的密码系统的空间有效变体
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
S. Galbraith
通讯作者：
S. Galbraith
DOI：
--
发表时间：
2020-10
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Srinath T. V. Setty;Jonathan Lee
通讯作者：
Srinath T. V. Setty;Jonathan Lee
基于格的 SNARG 及其在更有效的混淆中的应用
DOI：
--
发表时间：
2017
期刊：
International Conference on the Theory and Application of Cryptographic Techniques
影响因子：
--
作者：
D. Boneh;Yuval Ishai;A. Sahai;David J. Wu
通讯作者：
David J. Wu