BB84 Quantum Key Distribution Protocol
This text will be a new chapter for a textbook on the protection of information of the Department of Radio Engineering and Control Systems MIPT (GU). The complete tutorial is available on github . On Habré, I also plan to post new “big” pieces, first, to collect useful comments and observations, and second, to give the community more overview material on useful and interesting topics.
In 1984, Charles Bennett (born Charles Henry Bennett ) and Gilles Brassard (fr. Gilles Brassard ) proposed a new quantum key distribution protocol. Like other protocols, its goal is to create a new session key, which can later be used in classical symmetric cryptography. However, a feature of the protocol is the use of separate provisions of quantum physics to guarantee the protection of the received key from being intercepted by an attacker.
Prior to the start of the next round of session key generation, it is assumed that Alice and Bob, as participants of the protocol, have:
')
The protocol ensures that the intruder’s intervention into the protocol can be noticed until the attacker can control all the channels of communication at once for both reading and recording.
The protocol consists of three parts:
In the first part of the protocol, from the point of view of an experimental physicist, Alice takes a single photon and polarizes under one of four angles: 0, 45, 90, or 135. Let's say that Alice first chose a polarization basis (“+” or “×”), and then I chose one of two polarization directions in this basis:
From the point of view of quantum physics, we can assume that we have a system with two basic states and . The state of the system at any time can be written as . Since the four possible initial states chosen by Alice are non-orthogonal to each other (more precisely, not all are in pairs), two important points follow from the laws of quantum physics:
From the point of view of an information theory specialist, we can assume that Alice uses two independent random variables X A and A with entropy, 1 bit each, to obtain a new random variable Y A = X A + A transmitted to the communication channel.
As an experimental physicist, Eve can try to stand in the middle of the channel and do something with a photon. Maybe try to just destroy the photon or send a random one instead. Although the latter will result in Alice and Bob not being able to generate a common session key, Eve will not extract useful information from this.
Eva can try to pass a photon through one of the polarizers and try to catch the photon with a detector. If Eve knew for sure that a photon can have only two orthogonal states (for example, the vertical " "Or horizontal" "Polarization), then it could insert a vertical polarizer" »And determine whether the photon polarization was vertical (1, there is a signal) or horizontal (0, the photon did not pass through the polarizer and there is no signal) by the presence of a signal on the detector. Eve's problem is that the photon is not two states, but four. And no position of one polarizer and a single detector will help Eve determine exactly which of these four states is accepted by a photon. And skip the photon through two detectors will not work. First, if the photon passed the vertical polarizer, no matter what initial polarization it would have (“ "," "," "), After the polarizer, it will become vertical" "(The second component is" erased "). Secondly, the detector, converting a photon into an electrical signal, thereby destroys it, which makes it difficult to measure it further.
In addition, two or even four detectors for one photon will be small. Distinguish non-orthogonal polarizations " "And" "Can only be statistically, since each of them will pass and vertical" ", And diagonal" »Polarizers, but with different probabilities (100% and 50%).
From the point of view of quantum physics, Eve can try to measure the photon, which leads to the collapse of the wave function (or von Neumann reduction ) of the photon. That is, after the action of the measurement operator on the photon wave function, it inevitably changes, which will lead to interference in the communication channel, which Alice and Bob can detect. The inability to reliably distinguish non-orthogonal states prevent Eve from obtaining complete information about the state of the object, and the prohibition of cloning prevents repeating the measurement with a duplicate system.
From the point of view of information theory, we can consider the actually transmitted state of the photon as some random variable Y A. Eve uses a random variable E (the choice of a pair of orthogonal directions of the polarizer - “+” or “×”) to obtain the value of Y E as the result of measuring Y A. At the same time, for each given initial state, Eve gets the output:
Thus, the conditional entropy of the value Y ', measured by Eve, relative to the value Y, transmitted by Alice, is equal to:
And the mutual information between these values is:
That is 25% of the entropy of the random variable Y transmitted through the channel.
If we consider the value of X E , which Eve is trying to recover from Y E , then from the point of view of information theory, the situation is even worse:
It turns out that the conditional entropy of the sequence X E restored by Eve relative to the initial X A is equal to:
And mutual information
That is ≈19% of the entropy of the initial random variable X A.
The optimal algorithm for Eve's further actions will be to send Bob a photon in the resulting polarization (transfer the random variable Y E to the channel later). That is, if Eve used the vertical polarizer " ", And the detector detected the presence of a photon, then transmit the photon in vertical polarization" "And not try to introduce additional randomness and transmit" " or " ".
Bob, similar to Eve’s actions (although it’s rather Eve trying to imitate Bob), randomly chooses an orthogonal pair of polarization directions (“+” or “×”) and puts a polarizer on the photon’s path (“ " or " ") And detector. In the case of the presence of a signal on the detector, it records the unit, in the absence, it records zero.
Similar to Eve, we can say that Bob introduces a new random variable B (reflects the choice of the polarization basis by Bob) and as a result of the measurements receives a new random variable XB. Moreover, it is not yet known to Bob whether he used the original Y A signal transmitted by Alice or the fake Y E signal transmitted by Eva:
Next, Bob reports via an open, public classical communication channel, which polarization bases were used, and Alice indicates which of them coincided with the initially selected ones. At the same time, the measured values themselves (whether a photon passed through a polarizer or not) are kept by Bob in secret.
It can be said that Alice and Bob publish the values of the random variables A and B generated by them. In about half of the cases, these values will coincide (when Alice confirms the correctness of the choice of the polarization basis). For those photons for which the values of A and B coincide, the values of X A and X B1 will coincide. I.e
For those photons for which Bob chose the wrong polarization basis, the values of X B1 and X A will be independent random variables (since, for example, with the initial diagonal polarization of the photon, it will pass through the vertical and through the horizontal gap with a probability of 50%) :
Consider the case when Eve intervened in the transfer of information between Alice and Bob and sends Bob his own photons, but does not have the ability to change the information that Alice and Bob exchange via the classical communication channel. As before, Bob sends the selected polarization bases (B values) to Alice, and Alice indicates which ones matched the A values she chose.
But now, in order for Bob to get the correct value of X B2 (X B2 = X A ), all of the following conditions for each photon must be met:
Consider, without loss of generality, the variant when Alice used the diagonal polarization "×":
At the same time, Bob and Alice will be sure that in the first and third cases (which from their point of view are no different), Bob correctly restored the photon polarization. Since all these lines are equally probable, it turns out that Bob and Alice after selecting only photons with “guessed” bases (as they are sure) only half of the polarizations (X A and X B2 values) will coincide. In this case, Eve will know these values. The number of “common” sequence bits known to Eve and the proportion of errors in it are linearly dependent on the number of bits intercepted by Eve.
Regardless of the presence or absence of Eve, Alice and Bob are forced to use a pre-agreed error correction procedure. The used error correction code, on the one hand, should correct errors caused by the physical features of the quantum channel. But on the other hand, if the code corrects too many errors, it will hide from us the potential fact of the presence of Eva. It is proved that there are such error correction methods that allow you to safely (without danger of disclosing information to Eve) correct from 7.5% (Myers, 2001) to 11% of errors (Watanabe, Matsumoto, Uyematsu, 2005).
Another interesting option is when Eva can change the information transmitted not only through optical, but also through classical communication channels. In this case, much depends on which way (on whose behalf) Eve can forge messages. In the most negative scenario, when Eve can impersonate both Alice and Bob, there will be a full-fledged man-in-the-middle attack, from which it is impossible to defend in any way if you do not use additional secure communication channels, or not based on information transmitted in advance. However, it will be a completely different protocol.
Summing up, the quantum key distribution protocols (namely, so far all quantum quantum cryptography known today is limited) have both certain features and fatal flaws that make it difficult to use them (and questioning this need):
In 1984, Charles Bennett (born Charles Henry Bennett ) and Gilles Brassard (fr. Gilles Brassard ) proposed a new quantum key distribution protocol. Like other protocols, its goal is to create a new session key, which can later be used in classical symmetric cryptography. However, a feature of the protocol is the use of separate provisions of quantum physics to guarantee the protection of the received key from being intercepted by an attacker.
Prior to the start of the next round of session key generation, it is assumed that Alice and Bob, as participants of the protocol, have:
')
- quantum communication channel;
- classic communication channel.
The protocol ensures that the intruder’s intervention into the protocol can be noticed until the attacker can control all the channels of communication at once for both reading and recording.
The protocol consists of three parts:
- transmission and reception of a photon via a quantum communication channel from Alice to Bob;
- the transfer of information by Bob about the analyzers used;
- transfer to Alice of information about the coincidence of the chosen analyzers and initial polarizations.
Photon generation
In the first part of the protocol, from the point of view of an experimental physicist, Alice takes a single photon and polarizes under one of four angles: 0, 45, 90, or 135. Let's say that Alice first chose a polarization basis (“+” or “×”), and then I chose one of two polarization directions in this basis:
- 0 (“ ") Or 90 (" ") In the first basis;
- 45 (“ ") Or 135 (" ") In the second basis.
From the point of view of quantum physics, we can assume that we have a system with two basic states and . The state of the system at any time can be written as . Since the four possible initial states chosen by Alice are non-orthogonal to each other (more precisely, not all are in pairs), two important points follow from the laws of quantum physics:
- the inability to clone the state of the photon;
- the inability to reliably distinguish non-orthogonal states from each other.
From the point of view of an information theory specialist, we can assume that Alice uses two independent random variables X A and A with entropy, 1 bit each, to obtain a new random variable Y A = X A + A transmitted to the communication channel.
H (A) = 1 bit, the choice of the basis of polarization ("+" or "×")
H (x) = 1 bit, the message itself, the choice of one of the two directions of polarization in the basis.
H (Y A ) = H (X) + H (A) = 2 bits, the message being sent.
Intruder actions
As an experimental physicist, Eve can try to stand in the middle of the channel and do something with a photon. Maybe try to just destroy the photon or send a random one instead. Although the latter will result in Alice and Bob not being able to generate a common session key, Eve will not extract useful information from this.
Eva can try to pass a photon through one of the polarizers and try to catch the photon with a detector. If Eve knew for sure that a photon can have only two orthogonal states (for example, the vertical " "Or horizontal" "Polarization), then it could insert a vertical polarizer" »And determine whether the photon polarization was vertical (1, there is a signal) or horizontal (0, the photon did not pass through the polarizer and there is no signal) by the presence of a signal on the detector. Eve's problem is that the photon is not two states, but four. And no position of one polarizer and a single detector will help Eve determine exactly which of these four states is accepted by a photon. And skip the photon through two detectors will not work. First, if the photon passed the vertical polarizer, no matter what initial polarization it would have (“ "," "," "), After the polarizer, it will become vertical" "(The second component is" erased "). Secondly, the detector, converting a photon into an electrical signal, thereby destroys it, which makes it difficult to measure it further.
In addition, two or even four detectors for one photon will be small. Distinguish non-orthogonal polarizations " "And" "Can only be statistically, since each of them will pass and vertical" ", And diagonal" »Polarizers, but with different probabilities (100% and 50%).
From the point of view of quantum physics, Eve can try to measure the photon, which leads to the collapse of the wave function (or von Neumann reduction ) of the photon. That is, after the action of the measurement operator on the photon wave function, it inevitably changes, which will lead to interference in the communication channel, which Alice and Bob can detect. The inability to reliably distinguish non-orthogonal states prevent Eve from obtaining complete information about the state of the object, and the prohibition of cloning prevents repeating the measurement with a duplicate system.
From the point of view of information theory, we can consider the actually transmitted state of the photon as some random variable Y A. Eve uses a random variable E (the choice of a pair of orthogonal directions of the polarizer - “+” or “×”) to obtain the value of Y E as the result of measuring Y A. At the same time, for each given initial state, Eve gets the output:
- a similar state with a probability of 50% (the probability of choosing a pair of orthogonal directions of the polarizer, coinciding with the selected Alice);
- one of two non-orthogonal original states with a probability of 25% each.
Thus, the conditional entropy of the value Y ', measured by Eve, relative to the value Y, transmitted by Alice, is equal to:
And the mutual information between these values is:
That is 25% of the entropy of the random variable Y transmitted through the channel.
If we consider the value of X E , which Eve is trying to recover from Y E , then from the point of view of information theory, the situation is even worse:
- with a guessed pair of orthogonal polarizer directions with a probability of 50%, we get the initial value in half the cases;
- in case of an unguarded pair, even in a quarter of cases, we also get the initial value (due to the random photon passing through the “wrong” polarizer).
It turns out that the conditional entropy of the sequence X E restored by Eve relative to the initial X A is equal to:
And mutual information
That is ≈19% of the entropy of the initial random variable X A.
The optimal algorithm for Eve's further actions will be to send Bob a photon in the resulting polarization (transfer the random variable Y E to the channel later). That is, if Eve used the vertical polarizer " ", And the detector detected the presence of a photon, then transmit the photon in vertical polarization" "And not try to introduce additional randomness and transmit" " or " ".
The actions of the legal recipient
Bob, similar to Eve’s actions (although it’s rather Eve trying to imitate Bob), randomly chooses an orthogonal pair of polarization directions (“+” or “×”) and puts a polarizer on the photon’s path (“ " or " ") And detector. In the case of the presence of a signal on the detector, it records the unit, in the absence, it records zero.
Similar to Eve, we can say that Bob introduces a new random variable B (reflects the choice of the polarization basis by Bob) and as a result of the measurements receives a new random variable XB. Moreover, it is not yet known to Bob whether he used the original Y A signal transmitted by Alice or the fake Y E signal transmitted by Eva:
- X B1 = f (Y A , B);
- X B2 = f (Y E , B).
Next, Bob reports via an open, public classical communication channel, which polarization bases were used, and Alice indicates which of them coincided with the initially selected ones. At the same time, the measured values themselves (whether a photon passed through a polarizer or not) are kept by Bob in secret.
It can be said that Alice and Bob publish the values of the random variables A and B generated by them. In about half of the cases, these values will coincide (when Alice confirms the correctness of the choice of the polarization basis). For those photons for which the values of A and B coincide, the values of X A and X B1 will coincide. I.e
- H (X B1 | X A ; A = B) = 0 bits
- I (X B1 ; X A | A = B) = 1 bit
For those photons for which Bob chose the wrong polarization basis, the values of X B1 and X A will be independent random variables (since, for example, with the initial diagonal polarization of the photon, it will pass through the vertical and through the horizontal gap with a probability of 50%) :
- H (X B1 | X A ; A ≠ B) = 1 bit
- I (X B1 ; X A | A ≠ B) = 0 bits
Consider the case when Eve intervened in the transfer of information between Alice and Bob and sends Bob his own photons, but does not have the ability to change the information that Alice and Bob exchange via the classical communication channel. As before, Bob sends the selected polarization bases (B values) to Alice, and Alice indicates which ones matched the A values she chose.
But now, in order for Bob to get the correct value of X B2 (X B2 = X A ), all of the following conditions for each photon must be met:
- Eve must guess Alice’s polarization basis (E = A)
- Bob must guess the basis of Eve's polarization (B = E)
Consider, without loss of generality, the variant when Alice used the diagonal polarization "×":
| Polarization Basis Used by Alice | The basis of polarization used by Eva | The basis of polarization used by Bob | result |
|---|---|---|---|
| "×" | "×" | "×" | accepted without error |
| "×" | "×" | "+" | not accepted |
| "×" | "+" | "×" | taken with errors |
| "×" | "+" | "+" | not accepted |
At the same time, Bob and Alice will be sure that in the first and third cases (which from their point of view are no different), Bob correctly restored the photon polarization. Since all these lines are equally probable, it turns out that Bob and Alice after selecting only photons with “guessed” bases (as they are sure) only half of the polarizations (X A and X B2 values) will coincide. In this case, Eve will know these values. The number of “common” sequence bits known to Eve and the proportion of errors in it are linearly dependent on the number of bits intercepted by Eve.
Regardless of the presence or absence of Eve, Alice and Bob are forced to use a pre-agreed error correction procedure. The used error correction code, on the one hand, should correct errors caused by the physical features of the quantum channel. But on the other hand, if the code corrects too many errors, it will hide from us the potential fact of the presence of Eva. It is proved that there are such error correction methods that allow you to safely (without danger of disclosing information to Eve) correct from 7.5% (Myers, 2001) to 11% of errors (Watanabe, Matsumoto, Uyematsu, 2005).
Another interesting option is when Eva can change the information transmitted not only through optical, but also through classical communication channels. In this case, much depends on which way (on whose behalf) Eve can forge messages. In the most negative scenario, when Eve can impersonate both Alice and Bob, there will be a full-fledged man-in-the-middle attack, from which it is impossible to defend in any way if you do not use additional secure communication channels, or not based on information transmitted in advance. However, it will be a completely different protocol.
Summing up, the quantum key distribution protocols (namely, so far all quantum quantum cryptography known today is limited) have both certain features and fatal flaws that make it difficult to use them (and questioning this need):
- Any quantum protocols (as well as any quantum computing in general) require original expensive equipment, which so far cannot be made part of a commodity-device or a regular cell phone.
- Quantum communication channels are always physical communication channels. They have a maximum channel length and a certain level of errors. For quantum channels (today) they did not invent “repeaters” that would allow increasing the length of unconditionally quantum data transmission.
- No quantum protocol (today) can do without an additional classical communication channel. Such a connection requires at least the same level of protection as when using, for example, public key cryptography.
- For all protocols, a particular problem is not only proof of correctness (which is a very nontrivial matter in the case of "fair" interference), but also an engineering task to implement the protocol in hardware. As a brief illustration, for example, there is no easy way to create exactly one photon. The undergeneration of photons leads, obviously, to transmission errors, and the generation of a double in the same time slot leads to the possibility of it being intercepted by the attacker without creating interference in the channel.
Source: https://habr.com/ru/post/333952/
All Articles