Paper 2025/202

Distributed Non-Interactive Zero-Knowledge Proofs

Alex B. Grilo, Laboratoire de Recherche en Informatique de Paris 6
Ami Paz, Université Paris-Saclay, CNRS, LISN,
Mor Perry, The Academic College of Tel-Aviv-Yaffo
Abstract

Distributed certification is a set of mechanisms that allows an all-knowing prover to convince the units of a communication network that the network's state has some desired property, such as being 3-colorable or triangle-free. Classical mechanisms, such as proof labeling schemes (PLS), consist of a message from the prover to each unit, followed by on-e round of communication between each unit and its neighbors. Later works consider extensions, called distributed interactive proofs, where the prover and the units can have multiple rounds of communication before the communication among the units. Recently, Bick, Kol, and Oshman (SODA '22) defined a zero-knowledge version of distributed interactive proofs, where the prover convinces the units of the network’s state without revealing any other information about the network’s state or structure. In their work, they propose different variants of this model and show that many graph properties of interest can be certified with them. In this work, we define and study distributed non-interactive zero-knowledge proofs (dNIZK); these can be seen as a non-interactive version of the aforementioned model, and also as a zero-knowledge version of PLS. We prove the following: - There exists a dNIZK protocol for -coloring with -bit messages from the prover and -size messages among neighbors. This disproves a conjecture from previous work asserting that the total number of bits from the prover should grow linearly with the number of edges. - There exists a family of dNIZK protocols for triangle-freeness, that presents a trade-off between the size of the messages from the prover and the size of the messages among neighbors. Interestingly, we also introduce a variant of this protocol where the message size depends only on the maximum degree of a node and not on the total number of nodes, improving upon the previous non-zero-knowledge protocol for this problem. - There exists a dNIZK protocol for any graph property in NP in the random oracle models, which is secure against an arbitrary number of malicious parties. Previous work considered compilers from PLS to distributed zero-knowledge protocol, which results in protocols with parameters that are incomparable to ours.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
zero-knowledgedistributed computingproof labeling schemes
Contact author(s)
alex bredariol-grilo @ lip6 fr
amipaz cs @ gmail com
morpy @ mta ac il
History
2025-02-12: approved
2025-02-11: received
See all versions
Short URL
https://ia.cr/2025/202
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/202,
      author = {Alex B. Grilo and Ami Paz and Mor Perry},
      title = {Distributed Non-Interactive Zero-Knowledge Proofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/202},
      year = {2025},
      url = {https://eprint.iacr.org/2025/202}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.