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.

## Abstract

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 |

Location: | AMALFI, ITALY |

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 |

UCL classification: | UCL > School of BEAMS > Faculty of Engineering Science > Computer Science |

Archive Staff Only: edit this record