Secret Sharing for n-Colorable Graphs with Application to Public Key Cryptography
| dc.creator | Kulesza, Kamil | |
| dc.creator | Kotulski, Zbigniew | |
| dc.date | 2003-10-28 | |
| dc.date.accessioned | 2026-07-07T03:20:30Z | |
| dc.date.available | 2026-07-07T03:20:30Z | |
| dc.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. | |
| dc.description | 10 pages, 5 figures | |
| dc.identifier | https://arxiv.org/abs/cs/0310053 | |
| dc.identifier | http://arxiv.org/abs/cs/0310053 | |
| dc.identifier | Proceedings of 5th NATO Regional Conference on Military Communication and Information Systems, Capturing New CIS Technologies, RCMIS 2003. 22-24 pazdziernik 2003 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31848 | |
| dc.subject | Cryptography and Security | |
| dc.subject | D.4.6; E.3; K 6.5 | |
| dc.title | Secret Sharing for n-Colorable Graphs with Application to Public Key Cryptography | |
| dc.type | text |