Goldreich-Micali-Wigderson where the first to provide zero-knowledge interactive proofs for graph theoretic problems. However, these problems seem unrelated to modern cryptography.

Whether reliable and/or private communication is possible or not in the presence of an adversary, depends on the type of graph the communication network forms and on the power of the adversary. In the case the communication is point-to-point and the adversary can control (or destroy, or eavesdrop in) at maximum t different platforms, then the adversary needs to solve an NP-complete problem. In the case the network is a partial broadcast one, such as ethernet, checking whether a sufficient condition to guarantee privacy (the graph contains t neighborhood disjoint lines) is satisfied turns out to be NP-complete.

We present zero-knowledge interactive proofs for both aforementioned problems.

We discuss as potential application the censoring of the internet.