There Are 10 Types of Vectors (and Polynomials): Efficient Zero-Knowledge Proofs of "One-Hotness" via Polynomials with One Zero
There Are 10 Types of Vectors (and Polynomials): Efficient Zero-Knowledge Proofs of "One-Hotness" via Polynomials with One Zero
复制标题
DOI：
10.1145/3338498.3358640
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
W. Black;Ryan Henry
中科院分区：
文献类型：
--
作者：
W. Black;Ryan Henry
我们提出了一个新的4步特殊诚实验证者零知识证明系统，用于证明Pedersen承诺向量从Zpn向所谓的“一热”向量（即从标准正交基向向量）开放。对这种证明的需求出现在对称私有信息检索（SPIR）、端到端可验证投票（E2E）以及保护隐私的数据聚合和分析等上下文中。新协议的关键洞见是关于有限域上有界次多项式根的稀少性的一个简单观察。新协议速度快，并产生简洁的证明：对于长度为n的向量，证明者计算Θ（Θlgn）组操作加上Θ(n)字段操作，并仅发送Θ（Θlgn）组和字段元素，而验证者计算一个n基多重幂加上Θ（łlgn）额外的组操作，并仅发送2（λ+lgn）位，以获得小于2-λ的稳健性误差。（对于相同的可靠性错误，该协议的5步变体将证明者上传减少到仅λlgn位。）我们已经实现了我们的新协议和文献中最接近的竞争对手；根据我们的分析结果，实验证实，除了最短的向量（粗略地说，对于超过16-32个元素的向量）之外，新协议在所有方面都轻松优于现有协议。
We present a new 4-move special honest-verifier zero-knowledge proof of knowledge system for proving that a vector of Pedersen commitments opens to a so-called "one-hot'' vector (i.e., to a vector from the standard orthonormal basis) from Zpn. The need for such proofs arises in the contexts of symmetric private information retrieval (SPIR), end-to-end verifiable voting (E2E), and privacy-preserving data aggregation and analytics, among others. The key insight underlying the new protocol is a simple observation regarding the paucity of roots of polynomials of bounded degree over a finite field. The new protocol is fast and yields succinct proofs: For vectors of length n, the prover evaluates Θ(Θlgn) group operations plus Θ(n) field operations and sends just Θ(Θlgn) group and field elements, while the verifier evaluates one n-base multiexponentiation plus Θ(łlgn) additional group operations and sends just 2(λ+lgn) bits to obtain a soundness error less than 2-λ. (A 5-move variant of the protocol reduces prover upload to just λlgn bits for the same soundness error.) We have implemented both our new protocol and its closest competitors from the literature; in accordance with our analytic results, experiments confirm that the new protocols handily outperform existing protocols for all but the shortest of vectors (roughly, for vectors with more than 16-32 elements).