Paper 2022/1523

Your Reputation's Safe with Me: Framing-Free Distributed Zero-Knowledge Proofs

Carmit Hazay, Bar-Ilan University
Muthuramakrishnan Venkitasubramaniam, Georgetown University
Mor Weiss, Bar-Ilan University
Abstract

Distributed Zero-Knowledge (dZK) proofs, recently introduced by Boneh et al. (CYPTO`19), allow a prover $P$ to prove NP statements on an input $x$ which is distributed between $k$ verifiers $V_1,\ldots,V_k$, where each $V_i$ holds only a piece of $x$. As in standard ZK proofs, dZK proofs guarantee Completeness when all parties are honest; Soundness against a malicious prover colluding with $t$ verifiers; and Zero Knowledge against a subset of $t$ malicious verifiers, in the sense that they learn nothing about the NP witness and the input pieces of the honest verifiers. Unfortunately, dZK proofs provide no correctness guarantee for an honest prover against a subset of maliciously corrupted verifiers. In particular, such verifiers might be able to ``frame'' the prover, causing honest verifiers to reject a true claim. This is a significant limitation, since such scenarios arise naturally in dZK applications, e.g., for proving honest behavior, and such attacks are indeed possible in existing dZKs. We put forth and study the notion of strong completeness for dZKs, guaranteeing that true claims are accepted even when $t$ verifiers are maliciously corrupted. We then design strongly-complete dZK proofs using the ``MPC-in-the-head'' paradigm of Ishai et al. (STOC`07), providing a novel analysis that exploits the unique properties of the distributed setting. To demonstrate the usefulness of strong completeness, we present several applications in which it is instrumental in obtaining security. First, we construct a certifiable version of Verifiable Secret Sharing (VSS), which is a VSS in which the dealer additionally proves that the shared secret satisfies a given NP relation. Our construction withstands a constant fraction of corruptions, whereas a previous construction of Ishai et al. (TCC`14) could only handle $k^{\varepsilon}$ corruptions for a small $\varepsilon<1$. We also design a reusable version of certifiable VSS that we introduce, in which the dealer can prove an unlimited number of predicates on the same shared secret. Finally, we extend a compiler of Boneh et al. (CRYPTO`19), who used dZKs to transform a class of ``natural'' semi-honest protocols in the honest-majority setting into maliciously secure ones with abort. Our compiler uses strongly-complete dZKs to obtain identifiable abort.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2023
Keywords
Distributed Zero KnowledgeSecure Multiparty ComputationMPC-in-the-headVerifiable Secret SharingIdentifiable Abort
Contact author(s)
carmit hazay @ biu ac il
vmuthu @ gmail com
mor weiss @ biu ac il
History
2024-02-25: last of 3 revisions
2022-11-03: received
See all versions
Short URL
https://ia.cr/2022/1523
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1523,
      author = {Carmit Hazay and Muthuramakrishnan Venkitasubramaniam and Mor Weiss},
      title = {Your Reputation's Safe with Me: Framing-Free Distributed Zero-Knowledge Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1523},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1523}},
      url = {https://eprint.iacr.org/2022/1523}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.