Chapter Summary

This chapter is a gentle introduction to the recent applications of quantum computation in public-key cryptography. These developments have both good and bad impacts for cryptologers. It is still a big question whether a quantum computer can ever be manufactured. So at present a study of quantum cryptology is mostly theoretical in nature.

Quantum mechanics is governed by a set of four axioms that define a system and prescribe the properties of a system. A quantum bit (qubit) is a quantum mechanical system that has two orthogonal states |0〉 and |1〉. A quantum register is a collection of qubits of a fixed size.

As an example of what we can gain by using quantum algorithms, we first describe the Deutsch algorithm that determines whether a function f : {0, 1} → {0, 1} is constant by invoking f only once. A classical algorithm requires two invocations.

Next we present the BB84 algorithm for key exchange over a quantum mechanical channel. The algorithm guarantees perfect security. This algorithm has been implemented in hardware, and key agreement is carried out over a channel of length 67 km.

Finally, we describe Shor’s polynomial-time quantum algorithms for factoring integers and for computing discrete logarithms in finite fields. These algorithms are based on a technique called quantum Fourier transform.

If quantum computers can ever be realized, RSA and most other popular cryptosystems described and not described in this book will forfeit all security guarantees. And what will happen to this book? If you don’t possess a copy of this wonderful book, just rush to your nearest book store now—they have not yet mastered the quantum technology!