Computer Science/Discrete Mathematics Seminar I

In distributed certification, our goal is to certify that a network has a certain desired property, e.g., the network is connected, or the internal states of its nodes encode a valid spanning tree of the network. To this end, a prover generates certificates that are stored at each network node, and the nodes can then interact with one another in order to check their certificates and verify that the property holds. This can be viewed as a distributed analog of NP. However, like most theoretical models of distributed computing, the traditional model for distributed certification is information-theoretic: the prover and the network nodes are computationally unbounded, and the only efficiency measures we consider are the length of the certificates and the communication required to verify them. The information-theoretic nature of the model sets the area of distributed certification apart from classical complexity theory, and also makes it subject to strong lower bounds from the world of nondeterministic communication complexity.

In this talk, I will describe a computationally sound version of distributed certification, where the prover and the network nodes are required to run in polynomial time in the size of the network. Introducing computational restrictions allows us to leverage cryptography, and we show that any network property in P can be certified using certificates of polylogarithmic length by a global prover that sees the entire network. Ideally, however, we would like the prover to also be distributed, and we show that this can be done as well: any polynomial distributed algorithm can efficiently certify its own execution with low overhead in terms of communication and rounds. The main challenge in the distributed setting is that no single network node can see the entire execution of the algorithm.

This is joint work with Eden Aldema Tshuva, Elette Boyle, Ran Cohen and Tal Moran. No background in cryptography is assumed for the talk.