[Cryptography] QM giveth, QM taketh away

[Jerry Leichter]

>> 2. Quantum key distribution supposedly enables guaranteed
>> private distribution of OTP keys.
> 
> Kinda surprised no one mentioned this, but QKD requires a shared key
> material (either symetric or asymetric) to be distributed to the end
> points first before you can start passing keys...  You need both the
> quantum channel, but also a way to securely transmit the states that
> were observed to the other party, and agree what those states mean...
> 
> QKD still uses a lot of traditional crypto to carry out it's operation,
> so it's not as pure as some people think..
Eh?  I suppose there may be variations that work that way, but it's certainly not the basic algorithm.

The underlying idea is simple:  One can produce pairs of particles that are guaranteed to have correlated quantum states.  So Alice and Bob both observer a stream of such paired particles.  Each randomly measures one of two non-commuting variables, say vertical or horizontal polarization.  Imagine that each variable can have a value of 0 or 1.  The rules of QM guarantee several things:

1.  If you look at the actual values measured by either Alice or Bob, they are random with a 50/50 probability of 0/1.
2.  If both Alice and Bob happened to measure the same variables, the always get the same values.
3.  If they happen to measure different variables, the values they see are uncorrelated - the same half the time, different the other half, at random.  (This is what "non-commuting" means, and yes I'm grossly simplifying *everything* here.  If it really worked exactly like this, secure implementations would be easy.)

So the algorithm is:  Both Alice and Bob randomly, with 50/50 probability, measure one of the two variables for 256 successive particles and record the values they see.  Then each announces, publicly, their 256 choices of variable (NOT the values they saw, just the variables they chose to measure).  Each looks at the other's announcement, and finds the (on average, but let's assume exactly) 128 particles for which they happened to measure the same variable.  Obviously, they'll find the same 128 particles.  By property 2, the values they measured in those cases will be the same; and by property 1 they will be randomly distributed.  Those 128 bits are the shared key.  Extend as required.

If Mallory lets the particles go by untouched and looks only at the publicly shared lists of choices he learns nothing at all - those are simply 256 random bits from each of Alice and Bob that are never used for anything but choosing the particles.  I've ignored what happens if Mallory tries to measure anything about the particles going to, say, Bob.  Basically, half the time he randomizes the value that Bob sees. (Again, gross oversimplification.)  Alice and Bob can choose to "burn" half the bits they've agreed on, publishing them.  They'd better all match; if they don't, we know Mallory has been at work.

So:  No cryptography, no pre-exchanged values.  Besides a source of paired particles, the parties need a shared, public channel to reveal their choices and the "burned" check bits; and they need a lot of real randomness - but QM provides that.  The real difficulties in realization come about from such details as:  How do Alice and Bob know which particle is which?  If you send them slowly enough, this is easy because you can count time fairly inaccurately and still know which particle that Alice receives goes with which particle Bob receives.  But that kills your data rate.  If you send quickly, keeping the ends sufficiently synchronized becomes difficult - and the particles themselves provide no help.  More fundamentally, you don't get nice clean numbers like 50/50 distributions and 100% or 0% correlation.  You get something  complicated, and you have to work out all the math to make sure that you get enough good bits while at the same time that you stand a good chance of correctly identifying Mallory.
                                                        -- Jerry