Quantum Computation and Quantum Information 10th Anniversary Edition

Cryptography is the art of enabling two parties to communicate in private. For example, a consumer wishing to make a purchase on the internet wants to transmit their credit card number over the internet in such a way that only the company they are purchasing from gains access to the number. Rather more ominously, in wartime each of the warring parties wants the means to carry on private communication. To achieve privacy a cryptographic protocol or cryptosystem is used. Effective cryptosystems make it easy for parties who wish to communicate to do so, but make it very difficult for third parties to ‘eavesdrop’ on the contents of the conversation.

A particularly important class of cryptosystems are the public key cryptosystems. The basic idea of public key cryptography is illustrated by the analogy depicted in Figure A5.1. Alice sets up a mailbox with the property that anybody can send her mail, by putting it into the mailbox, but only she can retrieve mail out of the mailbox. To achieve this she gives the mailbox two doors. On top of the mailbox is a locked trap door. Any person able to open the trap door can drop mail into the box. However, the chute from the trap door into the box is one way, so they can't reach into the box and fish mail out. Alice makes the key to the trapdoor freely available to the public – it is a public key – so that she can receive mail from absolutely anybody.