Welcome to the resource topic for 2019/968
Title:
There Are 10 Types of Vectors (and Polynomials): Efficient Zero-Knowledge Proofs of “One-Hotness” via Polynomials with One Zero
Authors: William Black, Ryan Henry
Abstract: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 \mathbb{Z}_p^n. 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 \Theta(\lg{n}) group operations plus \Theta(n) field operations and sends just \Theta(\lg{n}) group and field elements, while the verifier evaluates one n-base multiexponentiation plus \Theta(\lg{n}) additional group operations and sends just 2(\lambda+\lg{n}) bits to obtain a soundness error less than 2^{-\lambda}. (A 5-move variant of the protocol reduces prover upload to just 2\lambda+\lg{n} 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).
ePrint: https://eprint.iacr.org/2019/968
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .