A Simple Public Key System

1. Create a graph with a known perfect code
   • We draw a set of dominating edges
   • Add more edges around each edge
   • Add more verices between the non-dominating edges
   • The graph is our public key
   • The exact dominating set the private key
   • Determining whether the graph as a dominating set is NP-complete
2. Simple example: fair coin tossing over the phone
   • Alice sends map to Bob
   • Bob guesses whether number of dominating edges is odd or even
   • Alice reveals the solution
3. Public key encryption and decryption
   • To transmit a secret number
     • Randomly distribute the number on all edges
     • For each edge send the sum of all its immediate neighbours and itsself
   • To decrypt
     • Sum the values of the dominating set

• PreviousCase Study: Public Key Cryptography
• Contents
• NextBibliography

 Last change: Monday, June 21, 2004 3:51 pm
 Unless otherwise expressly stated, all original material on this page created by Diomidis Spinellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Greece License.