IP: well, there goes our free lunch...

[David Farber <farber () cis upenn edu>]

Date: Sun, 18 May 1997 19:20:11 -0400 (EDT)
From: Timothy Finin <finin () cs umbc edu>
To: farber () central cis upenn edu


> From Netsurfer Digest: Vol. 03, #16, Sat, 17 May 1997:
 
A BACK DOOR INTO QUANTUM CRYPTOGRAPHY 


As a landmark bill which would criminalize certain types of
cryptography winds its way through the vapid US Congress, science
continues its relentless assault on cryptosystems. In this case, it
appears that there may be a back door into a new and promising area of
crypto science dealing with quantum cryptography. To vastly simplify
the situation, it seems possible to break a certain crypto schema
called bit commitment, in which two people who don't trust each other
can swap data without revealing their hands. Check out this reasonably
readable account of the situation in Science magazine. The article
notes that this hole could compromise "a range of protocols, notably
the 'post-Cold War' ones in which you don't trust your friends." Would
that include our elected officials?
<http://sciencenow.sciencemag.org/html/970506d.htm>



--


<http://sciencenow.sciencemag.org/html/970506d.htm>
Tuesday, 6 May 1997, 7:00 p.m.


Fickle Photons Hobble Quantum Cryptography


Scientists have devised a way to breach the security of
information that might be encoded in photons. The findings,
reported in the current issue of Physical Review Letters, appear
to undermine one form of quantum cryptography, which harnesses
the principles of quantum mechanics to guard secrets.


Like the tape that self-destructs in Mission: Impossible, a
photon's wave function--a quantum-mechanical property--collapses
when it is measured, destroying the information it
contains. Researchers hoped this phenomenon would make quantum
cryptography the premier tool for encoding information in a
scheme called bit commitment, in which two people who don't
trust each other can swap data without revealing their hands.
Physicist Richard Hughes of Los Alamos National Laboratory in
New Mexico explains one hypothetical scenario: "Suppose Alice
wants to prove she can make a prediction about the stock market,
but wants to make sure that Bob can't use the information to
... make a killing for free."


To do so, Alice can send Bob a string of photons, all of them
polarized diagonally (45 or 135 degrees, indicating a 1) or
rectilinearly (0 or 90 degrees, indicating a 0). If Bob views
diagonal photons through a rectilinear filter or vice versa,
he'll get a random string of readings, indistinguishable from
useful ones. As a result, Bob gets no information until Alice
chooses to reveal whether she sent a 1 or a 0. Bob can then
verify, after the fact, that Alice indeed had sent the bit that
she claimed she did, by looking at the photons he measured with
the "right" filter; if Alice has told the truth, his readings
will agree with hers. Thus, Alice has to commit herself to a
value for the bit but doesn't need to show her hand until later.


Unfortunately, this scheme has a gaping hole. Computer scientist
Dominic Mayers of Princeton University, physicist Hoi-Kwong Lo
of Hewlett-Packard, and physicist H. F. Chau of the University
of Hong Kong have found a way for Alice to cheat. Instead of
producing a single photon, the researchers found, she might
prepare an Einstein-Podolsky-Rosen pair: two photons with
polarizations that are linked, even as they travel in different
directions. Alice might store one half of the pair while sending
the other half to Bob, then measure her stored photon later,
which reveals Bob's measurement of the counterpart. Thus, she
could avoid bit commitment--or change her commitment late in the
game, after sending Bob the photons.


This weak spot in bit commitment would compromise a range of
protocols, notably the "post-Cold War" ones in which you don't
trust your friends. "I'm very disappointed with this result,"
says Claude Crepeau, a quantum cryptographer at the University
of Montreal. "There was a lot of research centered on
[quantum-bit commitment]. It's no longer possible to achieve
this goal."