Paper 2022/082

Feta: Efficient Threshold Designated-Verifier Zero-Knowledge Proofs

Carsten Baum, Dept. Computer Science, Aarhus University, Aarhus, Denmark.
Robin Jadoul, imec-COSIC, KU Leuven, Leuven, Belgium.
Emmanuela Orsini, imec-COSIC, KU Leuven, Leuven, Belgium.
Peter Scholl, Dept. Computer Science, Aarhus University, Aarhus, Denmark.
Nigel P. Smart, imec-COSIC, KU Leuven, Leuven, Belgium.

Zero-Knowledge protocols have increasingly become both popular and practical in recent years due to their applicability in many areas such as blockchain systems. Unfortunately, public verifiability and small proof sizes of zero-knowledge protocols currently come at the price of strong assumptions, large prover time, or both, when considering statements with millions of gates. In this regime, the most prover-efficient protocols are in the designated verifier setting, where proofs are only valid to a single party that must keep a secret state. In this work, we bridge this gap between designated-verifier proofs and public verifiability by distributing the verifier. Here, a set of verifiers can then verify a proof and, if a given threshold $t$ of the $n$ verifiers is honest and trusted, can act as guarantors for the validity of a statement. We achieve this while keeping the concrete efficiency of current designated-verifier proofs, and present constructions that have small concrete computation and communication cost. We present practical protocols in the setting of threshold verifiers with $t<n/4$ and $t<n/3$, for which we give performance figures, showcasing the efficiency of our approach.

Note: Added footnote with link to our implementation.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM CCS 2022
zero-knowledge proofsdistributed verifier
Contact author(s)
cbaum @ cs au dk
robin jadoul @ esat kuleuven be
emmanuela orsini @ kuleuven be
peter scholl @ cs au dk
nigel smart @ kuleuven be
2023-08-01: last of 3 revisions
2022-01-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carsten Baum and Robin Jadoul and Emmanuela Orsini and Peter Scholl and Nigel P.  Smart},
      title = {Feta: Efficient Threshold Designated-Verifier Zero-Knowledge Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/082},
      year = {2022},
      doi = {10.1145/3548606.3559354},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.