Quantum Computing and Quantum
Cryptography
What do they mean for traditional cryptography?

Tim Moses
Director, Advanced Security Technology
Robert Zuccherato
Chief Cryptographer
January 13, 2005
Version 1.1

© Copyright 2005 Entrust. All rights reserved.

Entrust is a registered trademark of Entrust, Inc. in the United States and certain other countries. Entrust is a registered trademark of Entrust Limited in Canada.
All other Entrust product names and service names are trademarks or registered trademarks of Entrust, Inc or Entrust Limited. All other company and product names are trademarks or registered trademarks of their respective owners.

© Copyright 2005 Entrust. All rights reserved.

Quantum Computing and Quantum Cryptography

Table of Contents

1 Introduction ......................................................................................................................... 2
1.1

Classical Physics and Computation....................................................................... 2

2 Quantum Mechanics ........................................................................................................... 2
3 Quantum Cryptography...................................................................................................... 4
3.1

Random Processes .................................................................................................. 4

3.2

The Key Distribution Problem ................................................................................. 4

3.3

The Quantum Solution ............................................................................................. 4

3.4

Quantum vs. Public-Key Cryptography.................................................................. 6

4 Quantum Computing .......................................................................................................... 7
4.1

Realizing a Quantum Computer .............................................................................. 7

4.2

Effect on Information Security Industry ................................................................. 8

5 Conclusions......................................................................................................................... 9
6 About Entrust ...................................................................................................................... 9

© Copyright 2005 Entrust. All rights reserved.
Page 1

Quantum Computing and Quantum Cryptography

1

Introduction

Recently there has been a great deal of attention paid to the emerging and exciting areas of quantum computing and quantum cryptography. Media reports, in particular, have made the advances achieved in these areas sound particularly ominous. It is true that if quantum computing and quantum cryptography do reach their full potential, drastic changes to the state of computation in general and to the security landscape and cryptography in particular will occur.
However, it is difficult to determine from the hype and from the media reports what, exactly, these drastic changes will be and how likely they are to occur. This report attempts to provide some details and perspective on the topics of quantum computing and quantum cryptography and the effect they may have on the information security industry.

1.1

Classical Physics and Computation

More than 25 years ago Dr. Gordon E. Moore, the cofounder of Intel, made a prediction that eventually came to be known as Moore’s Law. He stated that the number of transistors on a microprocessor would double approximately every 18 months. This implies that the computing power of a modern computer will similarly double approximately every 18 months. This prediction has been (more or less) accurate throughout the 1970’s, 80’s and 90’s. For the near future, there seems to be no reason why the trend will not continue. However, if this trend continues for the next 15 or 20 years then transistors will become the size of atoms. What does this