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
ISBN: 3-540-00420-3
Keywords: zero-knowledge, graph theory, secret sharing, key-escrow, complexity, SECURE COMMUNICATION, INTERACTIVE PROOF, CHANNELS, SYSTEMS
URI: http://discovery.ucl.ac.uk/id/eprint/139160
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item