patternMinor
what’s wrong with this quantum key distribution scheme?
Viewed 0 times
thisschemewhatwithwrongdistributionkeyquantum
Problem
I’m reading about the BB84 quantum key distribution scheme, and I’m surprised that it’s conceptually more complicated than seems necessary to me. What’s wrong with this conceptually simpler scheme?
-
Alice chooses two random strings $x,y \in \{ 0,1\}^{2n}$
-
Alice encodes $x$ into qbits, choosing the basis in which to encode the ith qbit according to whether $y_i$ is 0 or 1.
-
Alice sends the qbits to Bob (Bob himself doesn’t generate any random strings).
-
Once Bob confirms to Alice (on an insecure but authenticated channel) that he’s received the qbits, Alice sends $y$ to Bob (on an insecure but authenticated channel).
-
Bob decodes all the qbits using $y$. He then chooses $n$ bits at random from $x$, and sends these $n$ classical bits to Alice (using the insecure channel), together with an encoding of which bits he picked.
-
Alice confirms whether the first $n$ qbits are indeed the same as the first $n$ bits in $x$. If they are, then they know that Oscar didn’t observe the qbits, and they use the other $n$ bits as the key. If one of them is not the same, they know that Oscar meddled with the process.
Does this work?
-
Alice chooses two random strings $x,y \in \{ 0,1\}^{2n}$
-
Alice encodes $x$ into qbits, choosing the basis in which to encode the ith qbit according to whether $y_i$ is 0 or 1.
-
Alice sends the qbits to Bob (Bob himself doesn’t generate any random strings).
-
Once Bob confirms to Alice (on an insecure but authenticated channel) that he’s received the qbits, Alice sends $y$ to Bob (on an insecure but authenticated channel).
-
Bob decodes all the qbits using $y$. He then chooses $n$ bits at random from $x$, and sends these $n$ classical bits to Alice (using the insecure channel), together with an encoding of which bits he picked.
-
Alice confirms whether the first $n$ qbits are indeed the same as the first $n$ bits in $x$. If they are, then they know that Oscar didn’t observe the qbits, and they use the other $n$ bits as the key. If one of them is not the same, they know that Oscar meddled with the process.
Does this work?
Solution
No, not really. The main problem with this protocol is that it is less practical than BB84.
Less practical
Bob is a benign party. To measure a q-bit, you need to know what basis to measure it in before you can measure it (e.g., before you can measure a photon, you need to have your measurement apparatus set up in the appropriate basis). Ordinarily, we'd like to measure it as soon as we receive it. Your protocol doesn't allow that.
Your protocol requires Bob to receive the q-bit and then decide later what basis to use to measure it. That means Bob will need some way to store the q-bit for later measurement. There might be a way to do that (e.g., put the photon into a long delay loop), but it will probably increase complexity and expense.
It's not reasonable to expect legitimate parties to have to do that just to communicate. And in any case, BB84 doesn't require parties to jump through those hoops. So your scheme is less practical than BB84.
Side note on security:
With your protocol, it is important that step 4 (including Bob's confirmation) be over an authenticated channel. Without that, there is a security problem.
BB84 provides the following security property: if the final reconciliation phase is done over an authenticated channel (not necessarily secret; it can be public communication; but it does need to be authenticated), and if the parties don't abort, then the resulting secret will be known only to Alice and Bob. In particular, no adversary -- not even an active man-in-the-middle attacker -- can arrange to learn the secret.
Your protocol doesn't offer that guarantee, if step 4 happens over an insecure channel. With your protocol, there's a trivial way that a man-in-the-middle can arrange to learn the secret, with zero chance of being detected. When Alice sends the q-bits, the adversary Mallet intercepts and stores them. Mallet then sends a confirmation that the q-bits were received to Alice (pretending that this came from Bob). When Alice sends $y$, Mallet intercepts and learns $y$. Now Mallet decodes all the q-bits using $y$, and learns $x$. In the second phase, Mallet encodes $x$ into new q-bits and sends those q-bits to Bob (pretending they came from Alice). When Bob responds that he has received them, Mallet sends $y$ to Bob (pretending it came from Alice). Now Bob will decode his q-bits, obtain the same value $x$, send back some of the bits of $x$ to Alice, everything will match, and both Alice and Bob will think that they have obtained a secure key -- but Mallet actually knows that secret key, since Mallet has learned $x$. This attack works even if steps 5 and 6 are done over an authenticated channel.
I suspect it suffices to require step 4 to also go over an authenticated channel (I'm not 100% sure; that would require proof; but it looks like it to me).
Less practical
Bob is a benign party. To measure a q-bit, you need to know what basis to measure it in before you can measure it (e.g., before you can measure a photon, you need to have your measurement apparatus set up in the appropriate basis). Ordinarily, we'd like to measure it as soon as we receive it. Your protocol doesn't allow that.
Your protocol requires Bob to receive the q-bit and then decide later what basis to use to measure it. That means Bob will need some way to store the q-bit for later measurement. There might be a way to do that (e.g., put the photon into a long delay loop), but it will probably increase complexity and expense.
It's not reasonable to expect legitimate parties to have to do that just to communicate. And in any case, BB84 doesn't require parties to jump through those hoops. So your scheme is less practical than BB84.
Side note on security:
With your protocol, it is important that step 4 (including Bob's confirmation) be over an authenticated channel. Without that, there is a security problem.
BB84 provides the following security property: if the final reconciliation phase is done over an authenticated channel (not necessarily secret; it can be public communication; but it does need to be authenticated), and if the parties don't abort, then the resulting secret will be known only to Alice and Bob. In particular, no adversary -- not even an active man-in-the-middle attacker -- can arrange to learn the secret.
Your protocol doesn't offer that guarantee, if step 4 happens over an insecure channel. With your protocol, there's a trivial way that a man-in-the-middle can arrange to learn the secret, with zero chance of being detected. When Alice sends the q-bits, the adversary Mallet intercepts and stores them. Mallet then sends a confirmation that the q-bits were received to Alice (pretending that this came from Bob). When Alice sends $y$, Mallet intercepts and learns $y$. Now Mallet decodes all the q-bits using $y$, and learns $x$. In the second phase, Mallet encodes $x$ into new q-bits and sends those q-bits to Bob (pretending they came from Alice). When Bob responds that he has received them, Mallet sends $y$ to Bob (pretending it came from Alice). Now Bob will decode his q-bits, obtain the same value $x$, send back some of the bits of $x$ to Alice, everything will match, and both Alice and Bob will think that they have obtained a secure key -- but Mallet actually knows that secret key, since Mallet has learned $x$. This attack works even if steps 5 and 6 are done over an authenticated channel.
I suspect it suffices to require step 4 to also go over an authenticated channel (I'm not 100% sure; that would require proof; but it looks like it to me).
Context
StackExchange Computer Science Q#97452, answer score: 4
Revisions (0)
No revisions yet.