[E-Lang] Quantum computing and capabilities

Ralph Hartley hartley@aic.nrl.navy.mil
Tue, 06 Feb 2001 08:51:00 -0500


hal@finney.org wrote:

> Also, I believe quantum key exchange algorithms require a round trip
> (or maybe two) before the sides can start sending data.  This would be
> a big problem at interstellar distances.

No.

Suppose Bob wants to send a private message to Alice.
For each bit of his key he does the following:

Obtains an "Alice qbit" (a member of an EPR pair Alice has the other 
half of).
Selects an one of his own qbits such that the corresponding Bob qbit is 
convenient to Alice.
Selects a direction.

These selections are sent in the clear to Alice, she will use them to 
get her copy of the key .

To get the key bit he performs a measurement to determine if the two 
qbits are the same in the chosen direction (not the same as measuring 
each and comparing the results). If they are, the key bit is 1 otherwise 
it is 0.

One he has a bunch of key bits, he uses an error correcting code to make 
his key depend on all the key bits, but tolerant of errors (this 
prevents an attacker from getting any information by tampering with just 
a subset of the bits).

On receiving the encoded message and the (unencrypted) key information, 
Alice obtains the specified Bob bits and does the same measurements with 
them and her private bits, uses the same error correction on the 
results, and gets the same key.

The resulting message can only be read by Alice, and could only have 
been sent Bob.

This assumes that Bob actually has the private mates to the Bob qbits 
and the same for Alice. This is exactly like the situation with public 
keys, Bob is assumed to have the private key corresponding to his public 
key.

The Bob bits and Alice bits used to transmit the key are consumed. I 
think that after using 2n qbits to determine n bits of key Bob and Alice 
may be left sharing n qbits, so the efficiency might be improved (by 
measuring each pair in two orthogonal directions?), but the extra bits 
may not be as secure.

Ralph Hartley