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.
Yvo Desmedt received his Ph.D. (Summa cum Laude) from the University of Leuven, Belgium (1984). He is presently the BT Chair of Information Security at University College London, UK. He is also a courtesy professor at Florida State University. His interests include cryptography, network security and computer security. Yvo Desmedt is ranked in the top 5 most prolific authors (out of 1245) in Crypto/Eurocrypt, the two main venues in the area of cryptography. He is program chair of ICITS 2007, was co-program chair of CANS 2005, program chair of PKC 2003, the 2002 ACM Workshop on Scientific Aspects of Cyber Terrorism and Crypto '94. He is editor-in-chief of the IEE Proceedings of Information Security, editor of the Journal of Computer Security, of Information Processing Letters and of Advances in mathematics of Communications. He has given invited lectures at several conferences and workshop in 5 different continents.