The Long-Term Future of the Cryptography Policy Debate

[Peter Dare]

At 5pm on a Friday afternoon, at the end of a stressful week, Peter Dar=
e (IBM)
writes:

When I got my physics degree in 1969 I joined the Institute of Physics,=
 and I
have continued in membership ever since, mainly because of the excellen=
t
monthly magazine "Physics World".  This month's edition, pushed through=
 my
letterbox this morning, makes fascinating reading for followers of the
cryptography debate.  There's a picture of Alice and Bob on the cover (=
so we
finally get to know what they look like).  Even more interesting are fo=
ur
separate articles inside on the subject of "Quantum Information".  Asto=
nishing
but credible claims in these articles include the following.  (I tried =
to find
if the articles or references to them are accessible from the IOP websi=
te, but
without any luck.  (www.iop.org))

Quantum physics enables computers to be built that can be really massiv=
ely
parallel.  You build one instance of the computer, but then let it run =
in very
many (and they mean very many) parallel universes at once.  Because of =
the
nature of quantum physics it's possible, for some calculations, to get =
the
instance in each universe to do a different part of the calculation and=
, at the
end, to exploit quantum entanglement to get the answer to the problem b=
ack into
your own universe.  (This is not fantasy or science fiction.  The solid=

physical principles behind all this have been known since the 1930's.  =
What's
new is the idea of building a computer using these principles.)

To quote one of the articles: "By some strange coincidence, several of =
the
superior  features of quantum computers have applications in cryptograp=
hy."
That is, the calculations that are suitable to be performed in many uni=
verses
at once tend to be calculations connected with cryptography.    "... qu=
antum
computers could factorise thousand-digit numbers in a fraction of a sec=
ond, and
the execution time would grow only as the cube of the number of digits =
..."
(With classical computers, the execution time grows exponentially with =
the
number of digits and very soon the problem becomes intractable.)  "... =
any
RSA-encrypted message recorded today will become readable moments after=
 the
first quantum factorisation engine is switched on".

The articles also explain how quantum computers can be used to break sy=
mmetric
algorithms very quickly.  (The example given is DES.)  But the advantag=
e over
classical computers is nowhere near as impressive as for factorisation.=
  I
could find no mention of the other sorts of "difficult" problems on whi=
ch
assymmetric encryption is typically based (the finite field logarithm p=
roblem,
and elliptic curves).

The articles explain other astonishing things as well.  Turing's theory=
 is a
trivial subset of a wider theory about quantum computing.  Information =
theory
will eventually be shown to be a law of physics, not a theorem of mathe=
matics.
Indeed, because quantum computers will be able to prove mathematical th=
eorems
in a way that no classical method ever could, physics will take over fr=
om
mathematics as the basis of human thought.

So what is the implication for crypto policy in the (very) long term?  =
(The
articles predict that quantum computers will be ready in a matter of de=
cades -
but where there is motivation, human beings are actually quite good at =
doing
things faster than predicted.)  If assymmetric cryptography had never b=
een
discovered, we'd be talking now about symmetric key distribution centre=
s, rigid
key management schemes and all the rest.  In such an environment, for e=
xample,
the lawful access argument is very different because two cyberspace str=
angers
could not communicate securely with each other without escrowing a key =
with a
trusted third party.

Will asymmetric encryption one day become unusable?  How will integrity=
 be
guaranteed where there is no secure method of digital signature? When w=
ill the
first quantum engines be built?  Are governments already working on the=
m
secretly?  And the most important question of all: will HMG's cryptogra=
phy
policy be announced before the first quantum switch-on, or are they pla=
ying for
time? :-)

Peter Dare
IBM United Kingdom Limited
=