Secret Sharing for n-Colorable Graphs with Application to Public Key Cryptography

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

At the beginning some results from the field of graph theory are presented. Next we show how to share a secret that is proper n-coloring of the graph, with the known structure. The graph is described and converted to the form, where colors assigned to vertices form the number with entries from Zn. A secret sharing scheme (SSS) for the graph coloring is proposed. The proposed method is applied to the public-key cryptosystem called "Polly Cracker". In this case the graph structure is a public key, while proper 3-colouring of the graph is a private key. We show how to share the private key. Sharing particular n-coloring (color-to-vertex assignment) for the known-structure graph is presented next.
10 pages, 5 figures

Keywords

Cryptography and Security, D.4.6; E.3; K 6.5

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/31848

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0310053
 http://arxiv.org/abs/cs/0310053
 Proceedings of 5th NATO Regional Conference on Military Communication and Information Systems, Capturing New CIS Technologies, RCMIS 2003. 22-24 pazdziernik 2003

Collections

arXiv