### There Are 10 Types of Vectors (and Polynomials): Efficient Zero-Knowledge Proofs of "One-Hotness" via Polynomials with One Zero

William Black and 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).

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. 18th Workshop on Privacy in the Electronic Society (WPES'19), November 11, 2019, London, United Kingdom
DOI
10.1145/3338498.3358640
Keywords
Zero-knowledgeefficiencyprivacy-preserving protocols
Contact author(s)
ryan henry @ ucalgary ca
History
Short URL
https://ia.cr/2019/968

CC BY

BibTeX

@misc{cryptoeprint:2019/968,
author = {William Black and Ryan Henry},
title = {There Are 10 Types of Vectors (and Polynomials): Efficient Zero-Knowledge Proofs of "One-Hotness" via Polynomials with One Zero},
howpublished = {Cryptology ePrint Archive, Paper 2019/968},
year = {2019},
doi = {10.1145/3338498.3358640},
note = {\url{https://eprint.iacr.org/2019/968}},
url = {https://eprint.iacr.org/2019/968}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.