7
$\begingroup$

I was hoping somebody could explain some issues I have with quantum key exchange that I don't quite understand. I've read bits and pieces about BB84 but I'm sure my questions probably apply to other schemes also. My understanding of quantum key exchange is the following (please correct me if I'm wrong):

  1. Alice creates a random bit string and for each bit, selects a random filter (say x or +).

  2. she encodes these choices as a polarized photon and sends over the quantum channel to Bob

  3. Bob guesses which filter to use, if he guesses correctly (assuming no Eve messing around for the moment), he'll get the bit Alice intended. If he guesses the wrong filter, it's 50% chance he gets the bit Alice intended

  4. Alice and Bob exchange what filters Bob should have used; they ignore the bits where Bob used the wrong filter

  5. Alice and Bob then pick a sample of their bits and find out if there are any discrepancies, if there are a lot, they try the key exchange again. If there aren't that many, they proceed to do parity checks to agree on the exact right key, then then use the leftover hash lemma to make sure Eve doesn't know anything much

Please correct me if I'm wrong with the above. My questions are the following:

  1. What's to guarantee authentication or message integrity (particularly when Alice and Bob are exchanging which filters were correct and so on)?

  2. If Alice and Bob only count the bits where they have the same filter, then isn't it 50/50 whether or not Eve guesses the correct filter also? So can't Eve see about half the key without Alice or Bob even knowing!?

  3. What proportion of discrepancies is too much and why?

  4. We always assume Eve is passively observing, can't she do more than that (like change the polarization to whatever she likes and so on)?

  5. How does the leftover hash lemma actually work?

Apologies if any of the above are stupid questions but I'm very confused with this protocol. 1) and 2) are particularly important to me because they seem like major, major problems I can't seem to understand and I can't find a good article that really explains it properly so an explanation from here would be great.

Many thanks for any help with any question.

$\endgroup$
  • 1
    $\begingroup$ Something out-of-scope is to guarantee authentication or message integrity for the classical channel, and nothing is to guarantee authentication or message integrity for the quantum channel. $\:$ It is 50/50 whether or not Eve guesses the correct filter also. $\:$ Due to the leftover hash lemma, Eve can't "see about half the key without Alice or Bob even knowing". $\:$ What is a "proposition of discrepancies"? $\;\;\;\;$ $\endgroup$ – user991 Sep 10 '14 at 0:13
  • $\begingroup$ So you're saying that before the leftover hash lemma, Eve does see about half the key (plus a little more with all the parity checking)? Isn't the leftover hash lemma invalid if Eve knows over half? and Sorry, I meant proportion'' not proposition''. Corrected now $\endgroup$ – Luke Sep 10 '14 at 10:07
  • 1
    $\begingroup$ No. $\:$ My understanding is that if Eve measures a significant fraction of the quanta, then the parties will detect that with overwhelming probability. $\:$ Even if Eve knew most of the key, the leftover hash lemma would still work in this context. $\:$ You may have heard of the half threshold in the context of non-malleable extractors or general privacy amplification. $\;\;\;\;$ $\endgroup$ – user991 Sep 10 '14 at 10:47
  • $\begingroup$ Looking here, if t>n/2 then doesn't this not make sense? en.wikipedia.org/wiki/Leftover_hash_lemma Is quantum key exchange just about trying to exchange a key over and over until you're sure nobody is listening? Seems a little silly to me because then Eve can just close off all communications between Alice and Bob just by listening each time. $\endgroup$ – Luke Sep 10 '14 at 10:54
  • $\begingroup$ Basically, do Alice and Bob exchange keys over and over until it's very likely Eve heard nothing (as she has to guess each time which is unlikely to be right each time after awhile). They check this with the discrepancy checking stuff. Then they use parity checks to agree the correct key (Eve may learn some of the key here). But Eve doesn't learn much, so then you use privacy amplification (somehow, don't know the details) and voila, a one-time pad? But you're assuming you have integrity and authentication in the classical channel, and that you can eventually exchange a secret key from Eve? $\endgroup$ – Luke Sep 10 '14 at 10:57
7
$\begingroup$
  1. What's to guarantee authentication or message integrity (particularly when Alice and Bob are exchanging which filters were correct and so on)?

A pre-authenticated classical channel is an essential requirement in addition to the quantum channel on which the quantum key exchange (QKE) is performed. This implies that Alice and Bob must share an initial secret before commencing QKE. And for this reason, quantum key exchange is more appropriately the process of quantum key growing. But then, this initial secret need not be very big, e.g. a simple password suffices.

  1. If Alice and Bob only count the bits where they have the same filter, then isn't it 50/50 whether or not Eve guesses the correct filter also? So can't Eve see about half the key without Alice or Bob even knowing!?

Sure, Eve can intercept the quantum signals (photons) as and when they propagate on the quantum channel and measure them just like Bob. However, a measurement destroys the state of the photons so Eve has to re- prepare photons and send them to Bob. In this process, commonly known as the intercept and resend attack (IRA), Eve would guess ~50% of the key correctly (as you also suspected). However, in ~25% of the cases where Bob and Alice used the same filters, they will see a mismatch in their respective bits because of Eve's attack. This means a quantum bit error ratio (QBER) of $q = 0.25$ (in the statistical limit) will be incurred by Alice and Bob. It also means that the channels are unsafe and they should abort the communication. While this is obviously not a desirable situation, the fact that Alice and Bob are alerted of Eve's presence and therefore have the chance to protect their secrets is still remarkable. They could try again later or switch to a different communications channel.

  1. What proportion of discrepancies is too much and why?

Let's take the case of IRA again. What would happen if Eve does not perform IRA on every quantum signal? As in, what if she limits to only a fraction $f < 1$. In this case, her information would be $I_E = f*0.5$ while the QBER $q = 0.25*f$. The secret key rate calculated by Alice and Bob becomes zero when $q = q_{0} \approx 0.17$ (the calculation is dependent on $h(q)$ with $h(.)$ being the Shannon's entropy, and the amount of privacy amplification or the 'hashing' that you mentioned). This means if Eve chooses $f < 0.68$, Alice and Bob can still distill a positive secret key at the end of the protocol. Note that the numbers here are illustrative of only this example (read the next para to see what I mean). In general, the job of the privacy amplification step is to ensure that Eve's (partial) knowledge of the key is made infinitesimally small IF the incurred QBER is below the abort threshold.

But even theoretically, Eve is not constrained to just IRAs. She can perform more sophisticated attacks known as coherent attacks. Long story short, there is a QBER threshold above which the security provided by the key cannot be guaranteed and the quantum key exchange should be aborted. Finding the value of this abort threshold is a question explored in security proofs. Based on most security proofs of BB84, this threshold is around 11%, i.e., Alice and Bob could get a secret key if $q < 0.11$ is observed.

  1. We always assume Eve is passively observing, can't she do more than that (like change the polarization to whatever she likes and so on)?

Sure, she can do a lot of things! :) The Pandora box can be opened by uttering the term quantum hacking! This field essentially investigates the deviations between the theoretical model of a QKE system and the actual hardware. These deviations could arise because of technical imperfections (in the hardware) or due to bad assumptions (in the security proofs). Eve could exploit such deviations to hack the system and get information about the secret key without leaving any signature of her attack. The links below belong to some of the research groups that are active in this field. They can guide you to specific cases that have exposed a slew of implementational problems in practical quantum cryptography:

http://www.vad1.com/lab/

http://www.qolah.org/research/hacking/hack.html

http://www.mpl.mpg.de/index.php?id=125&L=0#QH

http://www.comm.utoronto.ca/~hklo/Research.html

$\endgroup$
  • 1
    $\begingroup$ Nice to read a simultaneous, but really similar answer to mine ! $\endgroup$ – Frédéric Grosshans Sep 10 '14 at 15:14
  • $\begingroup$ With regards to your first point, basically are you saying QKE is good because it's like a one-time pad, only you can make it arbitrarily long (so sure, you might want a Currier or something to agree on an initial secret for authentication/integrity, but after that the pad can be extended as long as you like)? in your second point, you're saying it's 25% discrepancy, right? (where Eve uses the wrong filter, sends it along, and then Bob is unlucky with whatever the photon decides to be when he measures it with the same filter as Alice)? That makes sense. $\endgroup$ – Luke Sep 10 '14 at 15:22
  • $\begingroup$ For the third point, are you saying that Eve needs to intercept less than 68% otherwise (it's very likely that) Alice and Bob will detect this and just try again? So if Eve did intercept more than 68%, Alice and Bob would likely just try sending the key again over and over until Eve drops down to being at most 68% ``nosey''? Is it the case that, if Eve intercepts too much, then privacy amplification won't work so tat's why f<0.68? But the exact maths depends on what particularly privacy amplification and what parity checking schemes you do (as that reversals info to Eve as well, right)? $\endgroup$ – Luke Sep 10 '14 at 15:22
  • $\begingroup$ With regards to the fourth point, I merely meant Eve could send photons along in diffrent ways, but i guess if Alice and Bob do a sampling check for discrepency anything other than Eve sending photons along to Bob the way she measured them won't benefit her? Many thanks for your answer. It was really good to read! :) $\endgroup$ – Luke Sep 10 '14 at 15:23
  • $\begingroup$ Yes, the 25% discrepancy arises when Eve measures using the wrong bases(=filters) but Alice's and Bob's bases are compatible. $\endgroup$ – jayann Sep 10 '14 at 18:06
8
$\begingroup$

Let’s take your questions in order. Note that I’m a physicist working in quantum cryptography, so my opinion on this might be biased

1. What about authentication ?

The classical channel between Alice and Bob has to be authenticated in order for the protocol to work. Formally, this is a pre-requisite for quantum key distribution (QKD), and is not part of the protocol.

In practice, we often uses information theoretically secure schemes (see this answer for pointers), which consume secret keys. The point is to generate key through QKD faster than the authentication consume it, making the whole system a key expansion system.

2. Wait ! Can’t Eve guess half of the basis (filters) without being detected ?

No ! That’s the whole point. Eve does indeed know half of the key, but she’s detected by Alice and Bob. Eve choice and Bob’s choice are independent, so, Eve will have chosen the wrong filter for half of the photons kept by Alice and Bob, and this wrong filter choice would change the photon polarization, inducing errors in Alice and Bob strings (in this case $\tfrac12\times\tfrac12=25\%$ error.) detected in step 5. of your description of the protocol. This lead us to the next question .

3. What is the maximal error rate ? And why ?

An exact answer to this question is still a research subject, and is obviously protocol dependent, but the same ideas (with different numbers) are essentially valid for all protocols.

The attack you proposed is known as an intercept-resend attack, describing an attack where Eve measures the photons and resends something to Bob depending on her measurement. It is proved that there is no way for Alice and Bob to extract a secret key when such an attack occurs, which corresponds to 25% error rate for BB84 protocol. However, this is only an upper bound on the tolerable error rate, and this attack has no reason to be optimal.

To find a lower bound, one uses different techniques to optimize over the sets of attacks, which also depend on the exact way the final key is extracted (after error correction and privacy amplification, in order to use the lefover hash lemma). A commonly used lower bound is $e=11\%$ which corresponds to a case where Eve gather as much mutual information on Alice's string as Bob, but some research papers have some way to tolerate a higher error rate.

4. We always assume Eve is passively oberving ...

NO ! The whole point of QKD is that she cannot passively observe ! Heisenberg uncertainty principle ensures that any observation is active and disturbs the system. Usually, we assume Eve can do anything, but the tricky part is to properly define “anything”, and optimize over this set.

5. How does the leftover hash lemma actually work

I’m a physicist, and I will not give you a theoretical answer on this. You can read the publications of Renato Renner to have a rigorous analysis of this lemma in the presence of a quantum adversary.

On a practical point, Alice and Bob use error correcting codes (ECC) to correct the errors in order to have the same key. Doing that, they leak some information to Eve (at most the number $c$ of exchanged ECC bits, $c≥h(e)$ for BB84). This leakage is added to amount of information which has leaked during the photon exchange, and which can be evaluated from the error rate $e$ (at most $h(e)$ for BB84). Alice and Bob pass their key through a universal hash function, with an output small enough ($<1-c-h(e)$) to ensure the leftover hash lemma applies.

Bonus question (from the comments) : is QKD relevant ?

I’m an academic, and I find it interesting from a fundamental point of view. It clearly changes the way physicist think about quantum mechanics, and is relevant in this aspects.

Whether it will soon be relevant to use QKD now in an industrial setting is a question of engineering, economics, future prediction and beliefs on what the NSA actually does ...

QKD is more difficult to implement than classical cryptography, because it needs specific hardware and has a limited range. However, it is indeed possible today to make QKD systems working over 200km, and small networks exist across a few cities. Some people work to make it practical and cheaper, and they may succeed.

In my opinion, the only reasonable application of QKD today is on securing expensive data which should stay secret for more than a decade (i.e. on an horizon where technological evolution is difficult to predict). The two properties which make QKD useful in this case are :

  1. Its security relies on something completely independent than classical cryptography and it is easy to combine the two such that both have to be broken in order to break the scheme.
  2. In order to break an imperfect implementation of quantum cryptography (aka quantum hacking), one need to break it at the moment where the photon exchange take place. You cannot record the messages in the hope that a weakness in the protocol will later be found.
$\endgroup$
  • $\begingroup$ More inforamtion theoretic details about modern security proofs for QKD are available p95 of this ETHZ course, but you’ll need to familiarize yourself with Smothh Quantum Rényi entropies (introduced earlier in the same course) in order to extract something from this link... $\endgroup$ – Frédéric Grosshans Sep 10 '14 at 15:11
  • $\begingroup$ Many thanks for your answer. So, like my comment on the other answer, QKE is great because it's like extending a one-time pad? There seems to be two sides to QKE. On one hand people explain it as if Alice and Bob will find out if they're being spied on (fair enough) and that's all. But I think you're saying that Alice and Bob are prepared to accept being spied on during the key exchange phase a little bit, but not too much (eg no more than 68% in the protocol for the answer above - although the precise percentage will change depending on implementation/protocol)? $\endgroup$ – Luke Sep 10 '14 at 15:28
  • 2
    $\begingroup$ Is it basically that Eve needs to find a balance: If she spies too much there's too high an error rate and Alice and Bob just try again, if she doesn't spy on them enough she's screwed when Alice and Bob correct their keys and use privacy amplification? Many thanks for your answer as well. It was also fantastic to read. :) $\endgroup$ – Luke Sep 10 '14 at 15:30
  • $\begingroup$ On Eve’s Balance : exactly ! This QKD transforms spyinf into a denial of service attack. In practice, the errors will come from technical imperfection, but Alice and Bob cannot be sure. This is what limits in practice the range of QKD $\endgroup$ – Frédéric Grosshans Sep 10 '14 at 15:47
  • 1
    $\begingroup$ @RickyDemer: I don’t really understand your question,but I’ll explain the things in another way, hoping to answer the question by chance ! There exist a (unknown) maximal value $e^*$ for the tolerable error rate. Alice and Bob can exchange a key if and only if their error rate $e$ obeys $e<e^*$. An upper bound $u≥e^*$ is often given by an explicit attack (like $u=25\%$ above), but we want a lower bound $l≤e^*$ ($l=11\%$ above), such that $e<l$ ensures $e<e^*$. Finding $l$ is not trivial, since one has to take account of an adversary smarter than us, to stay on the safe side! $\endgroup$ – Frédéric Grosshans Sep 11 '14 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.