Search for: All records

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