There Are 10 Types of Vectors (and Polynomials)

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 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).