Brief Announcement: Distributed Non-Interactive Zero-Knowledge Proofs

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 a desired property, such as being 3-colorable or free of a predefined subgraph. Classical mechanisms, such as proof labeling schemes (PLS), consist of a message from the prover to each unit, followed by one round of communication among 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 that the network satisfies the property without revealing any additional information about the network's state or structure.