UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Efficient zero-knowledge proofs for some practical graph problems

Desmedt, Y; Wang, YG; (2003) Efficient zero-knowledge proofs for some practical graph problems. In: Cimato, S and Galdi, C and Persiano, G, (eds.) SECURITY IN COMMUNICATION NETWORKS. (pp. 290 - 302). SPRINGER-VERLAG BERLIN

Full text not available from this repository.


From a cryptographic aspect zero-knowledge protocols for graph isomorphisms, graph non-isomorphisms, and graph-coloring are artificial problems, that received lots of attention. Due to recent work in network security in a broadcast setting, it seems important to design efficient zero-knowledge protocols for the following graph problems: independent set problem, neighbor independent set problem, and disjoint broadcast lines problem. In this paper, we will introduce a new concept of k-independent set problem which is a generalization of independent set and neighbor independent set problems, and we will present efficient zero-knowledge protocols for these problems. In the end of the paper we will give some cryptographic applications of k-independent set. Especially, we will point out the applications to the concept of "threshold" and appropriate access structures. Note that k-independent set also has applications outside cryptography, such as biology, methodology of scientific research, ethics, etc., which are beyond the scope of this paper.

Type:Proceedings paper
Title:Efficient zero-knowledge proofs for some practical graph problems
Event:3rd International Conference on Security in Communication Networks
Dates:2002-09-11 - 2002-09-13
Keywords:zero-knowledge, graph theory, secret sharing, key-escrow, complexity, SECURE COMMUNICATION, INTERACTIVE PROOF, CHANNELS, SYSTEMS
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record