Home > Resources > papers > BG13-Polynomial-Evaluation

Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists (Bayer, Groth 2013)

Last modified: 2026-10-27

DOI: 10.1007/978-3-642-38348-9_38 · URL: https://eprint.iacr.org/2015/195

Summary

Gives a public-coin, 3-move honest-verifier zero-knowledge argument that a committed value is a root (or non-root) of a public polynomial, with communication logarithmic in the polynomial degree and relying only on the discrete-log assumption (EUROCRYPT 2013). This yields membership and non-membership proofs against lists of size n in O(log n), enabling anonymous blacklisting — i.e. a ZK non-revocation proof for e-ID without pairings or trusted setup.

Related resources

• Bulletproofs: Short Proofs for Confidential Transactions and More (Bünz et al. 2018) (paper, 2017)
• Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing (Pedersen 1991) (paper, 1991)