Search for: All records

The field of distributed certification is concerned with certifying properties of distributed networks, where the communication topology of the network is represented as an arbitrary graph; each node of the graph is a separate processor, with its own internal state. To certify that the network satisfies a given property, a prover assigns each node of the network a certificate, and the nodes then communicate with one another and decide whether to accept or reject. We require soundness and completeness: the property holds if and only if there exists an assignment of certificates to the nodes that causes all nodes to accept. Our goal is to minimize the length of the certificates, as well as the communication between the nodes of the network. Distributed certification has been extensively studied in the distributed computing community, but it has so far only been studied in the information-theoretic setting, where the prover and the network nodes are computationally unbounded. In this work we introduce and study computationally bounded distributed certification: we define locally verifiable distributed SNARGs (LVD-SNARGs), which are an analog of SNARGs for distributed networks, and are able to circumvent known hardness results for information-theoretic distributed certification by requiring both the prover and the verifier to be computationally efficient (namely, PPT algorithms). We give two LVD-SNARG constructions: the first allows us to succinctly certify any network property in P, using a global prover that can see the entire network; the second construction gives an efficient distributed prover, which succinctly certifies the execution of any efficient distributed algorithm. Our constructions rely on non-interactive batch arguments for NP (BARGs) and on RAM-SNARGs, which have recently been shown to be constructible from standard cryptographic assumptions. 

In a key-agreement protocol whose security is proven in the random oracle model (ROM), the parties and the eavesdropper can make bounded number of queries to a shared random function (an “oracle”). Such protocol are the alternative to key-agreement protocols whose security is based on “public-key assumptions”, assumptions that being more structured are presumingly more vulnerable to attacks. Barak and Mahmoody [Crypto ’09] (following Impagliazzo and Rudich [STOC ’89]) have shown the ROM key-agreement protocols can only guarantee limited secrecy: the key of any `l-query protocol can be revealed by an O(l^2 )-query adversary, a bound that matches the gap obtained by the Merkle’s Puzzles two-message protocol of Merkle [CACM ’78]. While this quadratic gap might not seem like much, if the honest parties are willing to work “hard enough” and given continuousness improvement in common hash functions evaluation time, this gap yields a good enough advantage (assuming the security of the protocol holds when initiating the random function with a fixed hash function). In this work we consider the communication complexity of ROM key-agreement protocols. In Merkle’s Puzzles, the honest parties need to exchange Ω(l) bits (ignoring logarithmic factors) to obtain secrecy against an eavesdropper that makes roughly l^2 queries, which makes the protocol unrealizable in many settings. We show that for protocols with certain natural properties, such high communication is unavoidable. Specifically, this is the case if the honest parties’ queries are independent and uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Since two-round key-agreement protocol are equivalent to public-key encryption scheme (seeing the first message as the public-key), the latter result bounds the public-key and encryption size of public-key encryption scheme whose security is proven in the ROM. 

Interactive proof systems allow a resource-bounded verifier to decide an intractable language (or compute a hard function) by communicating with a powerful but untrusted prover. Such systems guarantee that the prover can only convince the verifier of true statements. In the context of centralized computation, a celebrated result shows that interactive proofs are extremely powerful, allowing polynomial-time verifiers to decide any language in PSPACE. In this work we initiate the study of interactive distributed proofs: a network of nodes interacts with a single untrusted prover, who sees the entire network graph, to decide whether the graph satisfies some property. We focus on the communication cost of the protocol — the number of bits the nodes must exchange with the prover and each other. Our model can also be viewed as a generalization of the various models of “distributed NP” (proof labeling schemes, etc.) which received significant attention recently: while these models only allow the prover to present each network node with a string of advice, our model allows for back-and-forth interaction. We prove both upper and lower bounds for the new model. We show that for some problems, interaction can exponentially decrease the communication cost compared to a non-interactive prover, but on the other hand, some problems retain non-trivial cost even with interaction.