QUANTUM AND OTHER CRYPTOGRAPHY
----Warren D. Smith Dec 1999---

Cryptography research has historically been 
contaminated by bogus perceptions, such as the asinine
US govt "clipper chip" plan (now abandoned), and US govt attempts
to outlaw freely available already published cryptosystems.
More recently, they apparently tried to totally outlaw all cryptanalysis
(the "digital millenium copyright act") - including outlawing publicizing
10-line programs which, however, could be freely distributed in other 
(non-US) countries.
Dream on. 

Currently there is a popular bogus idea that "quantum computing"
and "quantum cryptography" are worth investigating since
they will be economically important and revolutionary.

The fact is, although quantum cryptography is far far further along 
the road to technical FEASIBILITY than quantum computing, it still
is not an ECONOMICALLY competitive way to do cryptography and it
can never be in the forseeable future. Reasons:

A. Quantum crypto inherently depends on single photon transmission and
thus requires special point-to-point lines between A and B
(electronic switching and routing of signals as is presently done with
recievers and re-transmitters at every "switch," is inherently
impossible). Meanwhile classical crypto can just use the phone 
network of already available not-point-to-point lines. (That means
order NlogN wires for N communicators, not order N^2. Indeed if
we only count LONG wires, only order N.) Or radio broadcast.
(Incidentally, Hughes et al. quant-ph/9905009
can use a tight-beam from a laser to a telescope, in the open air,
even in daylight, as their "point to point line." It won't work
on rainy days nor maybe in air pollution, though, and won't work
over the horizon. This slightly undercuts A, but still leaves
my arguments B,C,D below unaffected.)

B. Even if somebody built a costly special quantum crypto point to point
line, it could easily be disabled/jammed by any opponent capable
of trying to tap the line. (If there were no such opponent - why
did you want crypto anyway?)  Forcing you to use classical crypto.
Meanwhile disabling a classical crypto line would have little or no 
hurtful effect and you would not have needed that line in the
first place anyway.

C. For practical purposes, simple classical crypto algorithms
are available for free, even already coded for you, which are
utterly unbreakable and highly efficient.
(For example the US Govt.'s "advanced encryption standard"  AES
algorithm, or indeed any of the 5 AES finalists, will do - all
are short published algorithms which can be downloaded for free
and used without copyright or other restrictions - and the paranoid 
among us can pipe their secret message through more than one of
these 5 algorithms to get even more security; and
for those of us who want "public key" cryptosystems I would
recommend elliptic curve discrete-log based systems, which
seem to have the best security for short key lengths and
are not patented or copyrighted. One also could use
discrete-log non-elliptic curve systems, or the RSA 
algorithm commonly taught in freshman courses.)

So: The problem is solved. No more research needs to be done. 
Unbreakable classical crypto is available for free, easily
and simply. Done. Over. Finished.
(Of course you could worry that nobody has PROVED the
security of these systems, except under certain unproven assumptions
everybody believes... but if you worry about that, you are 
not a "practical person;" you are an "insane paranoiac.")

D. Quantum-bit communication inherently cannot employ "repeaters"
or "amplifiers" due to no-cloning theorems. That limits it to short ranges.
It has however been argued to me that by use of "quantum teleportation"
one can make repeaters regurgitate stored qubits, thus effectively
being able to build them. Unfortunately... nobody knows how to
store huge numbers of quantum bits ready for instant use, for more
than about a microsecond, nor does anybody have any idea even on the
drawing boards to accomplish that.
So teleportation is, practically speaking, a non-entity.

E. Although we've often been told that quantum crypto is
"unbreakable" due to laws of physics, whereas classical crypto could
conceivably be broken if algorithmic revolutions occur... in reality
 (1) truly unbreakable classical crypto ("one time pads") has been known
  and used since the 1940s. Note, one time pads are a very similar concept
  to the quantum teleportation relay idea with private pre-stored qubits -
  except it's actually practical and easy today.  Since if I visit you I can
  hand you (and you me) a 1-time pad with 80 gigabytes on it costing
  about $250 (year 2000) and actually zero dollars since we can keep
  re-using the same hard disk in future... and since 80 GB probably exceeds
  the volume of all the email I am ever going to send to you...
  this would seem to suffice for most practical point-to-point
  communication purposes between 2 parties who mutually trust each
  other (i.e. precisely the scenario quantum crypto is intended for)
  with no quantum needed, trivial algorithms, and all hardware available now.
 (2) real quantum crypto hardware does not meet the idealized conditions
  required by the unbreakability arguments, and hence IS breakable.
   Example: Say if you transmit 10 photons down a long fiber, 1 photon
  will reach me. In that case an eavesdropper could measure some of the 
  photons and not others thus breaking the code. No way is known
  at present to reliably send only ONE photon per burst. (There are ways 
  known to try to send one photon but sometimes accidentally send 0, or 
  2, or whatever, but later compensating for a small constant
  fraction of such "bad transmissions" by algorithm. But in a highly lossy
  situation where almost EVERY transmission must be bad or else hardly 
  any signal will get through, those techniques will not work except 
  with sufferance of slowdown proportional to the loss factor. Furthermore
  even then an active eavesdropper could defeat you by jamming the
  line precisely on the occasions when he thinks only 1 photon was there.)
   Example: if the receiver and transmitter states are assumed to be
  private and un-knowable by the eavesdropper (who merely could try to
  listen in on the line) then everything is fine. But actually,
  there are easy ways the eavesdropper can try to send signals down
  the line himself (and listen to the echos) in an attempt to interrogate
  this "private" information. Although we've now seen many reports about
  how people have successfully built quantum crypto demo-systems... nobody
  has built, or even tried to build, such a system immune to the 2
  attacks I just described.
 (3) Quantum crypto is not immune to somebody jamming the line in a "denial of
  service" attack. Anybody who can tap the line can jam the line.
  Furthermore, quantum crypto imvolves classical communication too, and
  that phase is not immune to "impersonators." The only known ways to
  make it immune involve A and B privately pre-sharing information - and
  if they were allowed to do that, then why didn't they just use a classical
  one-time pad?
   So even the fundamental theoretical justifications undermining the
whole shebang, are quite questionable.  I personally believe it is possible
to engineer protections against some of these attacks, but: will ANY
such engineering ever be as un-assailable as classical algorithmic
crypto already is?

F. The only remaining open problems in classical cryptography of 
any practical interest are NOT about the usual scenario 
of "A wants to send B a secret message" - I consider that solved - but
instead about much trickier scenarios involving "general purpose
zero knowledge proof systems", "multiparty zero knowledge
computations" etc.

I won't talk about quantum computing here, but suffice it to
say that all "NMR based" quantum computing experiments have
been, essentially, lies (in fact none of them were really doing
a QUANTUM computation, i.e. something "entangled," at all; see
R.Schack & C.M.Caves: Classical model for bulk-ensemble
NMR quantum computation, Phys Rev A60 (1999) 4354-4362;
S.L. Braunstein & 5 others: Separability of very noisy
mixed states and implications for NMR quantum computing,  
Phys.Rev.Lett. 83 (1999) 1054-1057)
and all "ion trap based" quantum computing experiments
so far have not managed to interact even TWO truly-quantum
bits (there were various deceptive reports, but 
really one of the qubits was always at least partly
"simulated") and anyway the ion trap setups so far inherently
involve a 1-dimensional array of qubits allowing
only one q-op at a time - a setup inherently incapable of
"quantum error correction" and "quantum fault tolerance"
(these require "parallelism" for the error correction
to outpace destructive "decoherence" effects)
and hence incapable of ever doing a serious computation. So,
quantum computing is a long way from experimental fruition, if
that is achieveable at all, and the experimenters so far have
always presented rather deceptive statements to the press, to
say the least.   

As a first step it would be nice
to build even a single quantum "logic gate" to interact two
truly quantum (as opposed to partially simulated) bits. 
As opposed to not doing it and saying to the media that you did,
which is by far the most popular current approach.