Fwd: Re: Quantum Computing Puts Encrypted Messages at Risk

[Jaap-Henk Hoepman]

On Sun, 14 Jul 2002 15:24:48 +0200 Amir Herzberg <amir at herzberg.name> writes:
> >1. Quantum key encryption seems to require huge amounts of truly random
> >bits at both sender and receiver. This seems impractical as (almost) truly 
> >random bits are hard to produce (especially at high speeds). Is there a fix?

All practical proposals for QKD are photon based. The biggest practical problem
so far with these systems is the generation of a single photon at high enough
rates. It's this problem that makes the bitrate of QKD so low. The number of
random bits required is proportional to the length of the key to be
established, but depends on the amount of eavesdropping taking place. From
memory, without eavesdropping, you need ~4 random bits for each bit of shared
key established. This is not much more than the number of random bits required
for a one-time pad of the same length.

> >2. After the transmission, the receiver is supposed to tell the sender how 
> >it set its polarization; how is this authenticated? If it isn't we are 
> >obviously susceptible to man in the middle attack.

Yes. QKD does not solve the authentication problem. It merely establishes a
shared key between two parties.

> >3. It seems the quantum link must connect directly from sender to 
> >receiver. How can this help provide end to end security on the Internet? 
> >Or are we back to private networks?

Yes, photon polarisation based QKD systems by definition require a direct link
between sender and receiver (a repeater would be an all-catching eavesdropper
;-). I do believe that QKD systems based on entanglement and teleportation
allow for repeaters; but i havent studied these systems so far.

> >4. As to quantum computation signalling the end of `crypto as we know 
> >it`... Is it fair to say this may end only the mechanisms built on 
> >discrete log and/or factoring, but not shared key algorithms like AES and 
> >some of the other public key algorithms?

Grover's search techniques will reduce the effective bit-length of symmetric
key systems by a factor 2. All known quantum computing algorithms that are
truly more efficient (giving exponential or subexponential speedup) than known
classical solutions for the same problem appear to be based on being able to do
fast fourier transforms efficiently. Factoring and discrete log can be solved
faster using this. It is unclear whether other systems will ever be affected.

The interesting question to me is whether quantum computing can be used to
_construct_ efficient yet more secure public key cryptosystems.

> In particular I'm considering whether I should and can 
> cover this area in my book. 

In my opinion, it would be a valuable addition if you did (although to do this
subject justice, you would have to include a substantial amount of background
material concerning physics and quantum computing basics).

Regards,
Jaap-Henk

-- 
Jaap-Henk Hoepman             | Come sail your ships around me
Dept. of Computer Science     | And burn your bridges down
University of Twente          |       Nick Cave - "Ship Song"
Email: hoepman at cs.utwente.nl === WWW: www.cs.utwente.nl/~hoepman
Phone: +31 53 4893795 === Secr: +31 53 4893770 === Fax: +31 53 4894590
PGP ID: 0xF52E26DD  Fingerprint: 1AED DDEB C7F1 DBB3  0556 4732 4217 ABEF


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com