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).
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.
|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