[14168] in cryptography@c2.net mail archive

home help back first fref pref prev next nref lref last post

Re: quantum hype

daemon@ATHENA.MIT.EDU (John S. Denker)
Sat Sep 13 18:08:05 2003

X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Sat, 13 Sep 2003 17:43:00 -0400
From: "John S. Denker" <jsd@av8n.com>
To: martin f krafft <madduck@madduck.net>,
	David Wagner <daw@cs.berkeley.edu>
Cc: crypto list <cryptography@metzdowd.com>
In-Reply-To: <20030913195231.GA9614@diamond.madduck.net>

On 09/13/2003 03:52 PM, martin f krafft wrote:
 > ... any observation of the quantum stream is immediately
 > detectable -- but at the recipient's side, and only if checksums are
 > being employed, which are not disturbed by continual or sporadic
 > photon flips.
 >
 > someone will have
 > access to the 20 bytes before the recipient can look at the 20
 > bytes, decide they have been "tampered" with, and alert the sender.
 > So I use symmetric encryption and quantum cryptography for the key
 > exchange... the same situation here. Maybe the recipient will be
 > able to tell the sender about the junk it receives, but Mallory
 > already has read some of the text being ciphered.

1) As the subject: line suggests, there is indeed a lot
of hype in the quantum crypto business.  But there is
also a kernel of reality behind it.

2) Typically people use a combination of quantum and non-quantum
techniques.

3) Typically there is a multi-stage process:
  -- Exchange several blocks of keying material.
  -- Check for tampering;  reject blocks that show tampering.
  -- Do some post-processing to reduce vulerability
     to undetected tampering.
  -- Use the result to encrypt your actual data.  This
     is the first stage at which valuable data is exposed
     in any way.

Consider the possibilities:
   *) In each block, Mallory has a 50/50 chance of being able
   to copy a bit without being detected.
   *) More generally, Mallory has a 2^-C chance of being able
   to copy C bits without being detected.

As an easy-to-understand example:
You (Alice and Bob, the good guys) choose a C big enough
that 2^-C looks negligible to you.  Alice sends Bob a
bunch of bits (N>>2C).  Bob tells Alice (in the clear) what
receiver settings he used.  Alice then knows which bits
Bob should have been able to receive correctly.  Alice
tells Bob (in the clear) to check a randomly-chosen set
of C bits, checking that they have the values Alice
thinks they should have.  If this test is passed, it
puts an upper bound on how greedy Mallory has been.
Then Alice tells Bob (in the clear) to use another
(disjoint) set of C bits.  Bob XORs these bits together
and calls it one bit of key.  There is only one chance
in 2^-C that Mallory knows this bit.  The efficiency of the
key-exchange is roughly one part in 2C.  So there is an
exponential security/efficiency tradeoff.  Not too shabby.

The foregoing assumed an error-free channel.  Things get
much worse if the good guys need to do error correction.

There are snake-oily products out there that throw in
some "mild" cryptographic assumptions in order to increase
the efficiency.  So beware.

On 09/13/2003 05:06 PM, David Wagner wrote:
 >
 > Quantum cryptography *assumes* that you
 > have an authentic, untamperable channel between sender and receiver.

Not true.  The signal is continually checked for
tampering;  no assumption need be made.

Not all the world's oil comes from snakes.
Some does, some doesn't.

 > if we want end-to-end security, one can't
 > stick classical routers or other such equipment in the middle of the
 > connection between you and I.

That's true.  A classical router is indistinguishable
from a tap.


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

home help back first fref pref prev next nref lref last post