Post-Quantum zk-SNARK for Arithmetic Circuits using QAPs
Post-Quantum zk-SNARK for Arithmetic Circuits using QAPs
复制标题
使用 QAP 的算术电路的后量子 zk-SNARK
DOI：
10.1109/asiajcis50894.2020.00017
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Naganuma Ken; Yoshino Masayuki; Inoue Atsuo; Matsuoka Yukinori; Okazaki Mineaki; Kunihiro Noboru
中科院分区：
文献类型：
--
作者：
Hasegawa Natsuki;Fujie Shumpei;Horii Naoki;Uchida Masataka;Toyama Yuta;Inoue Kenichiro;Sanada Kiyoshi;Hamaoka Takafumi;Iemitsu Motoyuki;柿澤 昌;Naganuma Ken; Yoshino Masayuki; Inoue Atsuo; Matsuoka Yukinori; Okazaki Mineaki; Kunihiro Noboru
近年来，零知识证明和零知识简洁非交互论证(ZK-SNARK)作为隐私增强技术在各个领域引起了广泛的关注，特别是在加密货币行业和可验证计算领域。Gennaro等人提出了一种用于布尔电路的后量子指定验证器类型零知识简明非交互论元(ZK-SNARK)。在ACM CCS`18中。然而，该方案不包括算术电路。此外，它很难在各种应用中使用。他们的论文描述了从二次算术程序(QAP)构造算术电路的后量子指定验证器ZK-SNARK是一个公开问题。最近，Nitulescu提出了一种用于平方算术程序算术电路的后量子指定验证器ZK-SNARK，这是QAP的特例。本文给出了这个问题的另一个答案，并提出了一个用于QAP算术电路的后量子指定验证器ZK-SNARK方案。我们的方案使用QAP，零知识证明包括三个错误学习(LWE)密文。我们使用libsnark库实现了我们提出的方案和其他已知方案。实验结果表明，对于一个由216个门组成的算术电路，我们的方案可以在50个S的处理时间内生成一个零知识证明，这被称为ZK-snark的瓶颈，比Gennaro等人的后量子ZK-snark快了近3倍。或者比尼图列斯库的速度快两倍。
In recent years, the zero-knowledge proof and zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) have drawn significant attention as privacy-enhancing technologies in various domains, especially the cryptocurrency industry and verifiable computations. A post-quantum designated verifier type zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) for Boolean circuits was proposed by Gennaro et al. in ACM CCS `18. However, this scheme does not include arithmetic circuits. Furthermore, it is difficult to use it in various applications. Their paper described the construction of a post-quantum designated verifier zk-SNARK for arithmetic circuits from quadratic arithmetic programs (QAPs) as an open problem. Recently, Nitulescu proposed a post-quantum designated verifier zk-SNARK for arithmetic circuits using square arithmetic programs (SAPs), which are the special cases of QAPs.In this paper, we give another answer to this problem and propose a post-quantum designated verifier zk-SNARK scheme for arithmetic circuits using QAPs. Our proposal, which employs QAPs, the zero-knowledge proof comprises three learning with errors (LWE) ciphertexts. We implemented our proposed scheme and the other known schemes using the libsnark library. Our experimental results show that our scheme can generate a zero-knowledge proof, which is known as the bottleneck of zk-SNARK, for an arithmetic circuit that comprises 216gates in a processing time of only 50 s, which is approximately three times faster than that of the post-quantum zk-SNARKs by Gennaro et al. or two times faster than the one by Nitulescu.