Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials 学习笔记
1. 引言
Bootle和Groth 2018年论文《Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials》，发表于IACR-PKC-2018。
-
基于discrete logarithm assumption。
-
本文主要关注对 relations between commitments and field elements 的zero-knowledge argument，具有constant-round和fewer group operations，其中构建的polynomials in the relation具有low degree。
-
本文构建了a batch protocol，以支持 many copies of the same relation to be proved and verified in a single argument more efficiently with only a square-root communication overhead in the number of copies O ( N ) O(\sqrt{N}) O(N )，其中 N N N为相同relation的copy数。
-
可实现membership proof，polynomial evaluation proof以及range proof。
1.1 本文主要贡献
如 Bayer和Groth 2013年论文[2]《Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists》 中的用于prover membership 的polynomial evaluation argument和 Groth和Kohlweiss 2015年论文[28]《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》 中的1-out-of-N membership argument，其witness为zeores of low-degree polynomial relations。
-
本文解释了 Groth和Kohlweiss 2015年论文[28]《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》 和 Bootle 等人2015年论文[6]《Short Accountable Ring Signatures Based on DDH》 背后对membership proof的优化思路，然后进一步优化了membership proof和polynomial evaluation proof。
-
本文统一了Groth和Kohlweiss 2015年论文[28]《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》 、 Bootle 等人2015年论文[6]《Short Accountable Ring Signatures Based on DDH》 和 Bayer和Groth 2013年论文[2]《Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists》 中的构建思路，可统一为相同的构建办法。
在这些论文中，构建low degree polynomial relation的方式为：
1）mask an input variable u u u as f u = u x + u b f_u=ux+u_b fu=ux+ub，其中 x x x为challenge， u b u_b ub为random blinder。
2）然后基于 f u f_u fu构建相应的多项式， x x x变量的系数可体现待证明的relation。
3）然后基于该多项式构建zksnark，the communication and computational complexity由 polynomial relation 的degree和input 数量决定。
而the complexity of general arithmetic circuit protocol则由gate 数量决定。
在Bootle等人2016年论文 [7]《Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting》中，将a polynomial evaluation argument for a polynomial of degree
N
N
N 嵌入在 a low degree polynomial with
log
N
\log N
logN inputs and degree
log
N
\log N
logN，最终的argument具有
O
(
log
N
)
O(\log N)
O(logN) communication using 3 moves，需要
O
(
log
N
)
O(\log N)
O(logN) exponentiations in a suitably chosen cryptographic group。
另外，由于a polynomial of degree
N
N
N需要
N
N
N multiplication gates to evaluate in general，因此当前最好的arithmetic circuit protocol [7] 仅能达成
O
(
log
N
)
O(\log N)
O(logN) communication in
O
(
log
N
)
O(\log N)
O(logN) moves and uses
O
(
N
)
O(N)
O(N) group exponentiations。另外，由于discrete logarithm setting下的group exponentiation计算开销远高于 finite-field multiplications计算开销，因此，若能由
O
(
N
)
O(N)
O(N) group exponentiations reduce为
O
(
log
N
)
O(\log N)
O(logN) group exponentiations，则对整体性能的提升明显。
Bayer 2014年博士论文[1]《Practical zero-knowledge Protocols based on the discrete logarithm Assumption》中，利用Lagrange插值来embed many instances of the same relation into a single field element，提供了2种高效的batch proofs for multiplication and polynomial evaluation，其communication cost为
O
(
t
)
O(\sqrt{t})
O(t
)，
t
t
t为the number of proofs to be batched。
这种 利用Lagrange插值来embed many instances of the same relation into a single field element 的方法，也可用于本文的batch proofs for the low-degree relations。此外，结合本文第三章的polynomial commitment subprotocol，相应的batch proof的communication cost由
t
c
\sqrt{t}c
t
c 降为了
t
c
\sqrt{tc}
tc
，其中
c
c
c为the communication cost of the original non-batched proof，
t
t
t为a large number representing the number of proofs to be batched together。
-
本文构建了新的 1-out-of-N membership argument和polynomial evaluation argument，可在保持原有的simple 3-move structure的同时，降低communication cost和reduce prover and verifier computation。
实现了communication 效率最高的 ∑ \sum ∑-protocols for membership or non-membership of a committed value in a public list, in the discrete logarithm setting。 -
本文构建了an argument of range proofs。
-
本文 对 Bootle等人2016年论文 [7]《Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting》中 的polynomial commitment 进行了改进，以支持the prover to commit to a polynomial so that the verifier can learn an evaluation of the polynomial in a secure manner。