Comment on “quantum identity authentication with single photon”

Quantum cryptography aims for information theoretically secure protocols relying only on noiseless communication and the laws of quantum mechanics. Ever since the pioneering works of Wiesner [1] and Bennett and Brassard [2] this field has produced several proposals to exploit the quirks of quantum information for cryptographic purposes. In particular, quantum authentication [3] has been a popular topic among researchers. It is a valuable cryptographic task, as it allows users to prove their identity to each other or to a server. "Authentication" is an umbrella term encompassing both message authentication and identity authentication. A message authentication code (MAC) is a scheme allowing a receiver to attest the integrity and authenticity of incoming messages. This requires that the sender and receiver pre-share a secret key, which they use to generate message tags to send alongside the messages. On the other hand, identity authentication consists of proving your identity to another user or party. In this work, we focus on the latter type of authentication.

Identity authentication is of practical interest, as it can be used to verify a user’s identity before granting them access to exclusive resources or privileges. For instance, a bank may authenticate its users before letting them access their bank accounts. In this example, authentication ensures that only the legitimate owner of the account has access to it. This is necessary to prevent malicious attackers from accessing the user’s account and causing financial damage.

The concept of identity is hard to rigorously define, and for practical purposes one often resorts to one of three paradigms, namely: authenticate based on knowledge, possession, or biometrics. The first requires users to provide some secret pre-shared information, such as a binary key or a password. Password-based identity authentication is the most widespread, and is used worldwide on a daily basis. Despite its simplicity, its security comes with non-trivial problems, such as the secure storage of password hashes [4]. The second requires users to provide a physical token to prove their identity, such as a physical unclonable function (PUF). Finally, the third paradigm authenticates users based on biometric features, such as their fingerprints.

Thanks to the quirks of quantum information, quantum authentication protocols achieve information-theoretic security. The latter is notoriously the strongest notion of security, as it does not rely on unproven computational assumptions and is effective even against computationally unbounded adversaries. Quantum identity authentication protocols are quite diverse. Some assume pre-shared entanglement [5,6,7,8] as a shared key for authentication. These proposals make use of the non-local correlations of entangled states to attest a user’s identity. Despite their theoretical security, storing entanglement requires reliable quantum memories, an achievement beyond today’s capabilities. Furthermore, many entanglement-based proposals consume entanglement to perform authentication, eventually reaching a case in which parties run out of entanglement and can no longer authenticate their identities.

Alternatively, thanks to the famous no-cloning theorem, one can construct quantum tokens that are efficiently verifiable but not clonable. This idea is known in the literature as quantum money [1, 9, 10], due to the (theoretical) possibility to use this technology to create unforgeable currency. One can distribute said tokens to users and use them as authentication keys, yielding a possession-based authentication. The main advantage of this solution is that, unlike classical keys, quantum tokens are guaranteed to be unclonable. However, as argued for entanglement-based schemes, such proposals are technically challenging due to requiring quantum memories.

Others do not use any entanglement or quantum keys [11,12,13], but encode classical keys into qubits to hide classical information from malicious eavesdroppers. The use of classical keys is an advantage due to removing the need for quantum memories. This class of protocols is quite heterogeneous, with protocols exploiting various quantum properties such as superposition, state indistinguishability, and more. Finally, recent proposals use a physical token for authentication such as a quantum PUF (QPUF) [14, 15]. QPUFs are the quantum extension of classical PUFs, and the resulting authentication schemes are similar to the classical ones. The major advantage is that classical PUFs base their unclonability on the current inability to control manufacturing processes (which may become predictable or controllable at some point in the future), while QPUFs are unclonable due to the laws of physics.

Not long ago Hong et al. [16] proposed a simple and efficient quantum protocol for identity authentication. The protocol requires relatively simple quantum hardware components, and is therefore implementable using currently available technology. Specifically, it only requires hardware to generate BB84 states and a standard measurement device. Unfortunately, few years lately Zawadzki [17] pointed out a few weaknesses in the original design. In the same work, he proposed a simple mitigation based on hash functions, but the latter was found not to be information theoretically secure [18], though nothing prevents it from achieving computational security. In this work we point out a new vulnerability in Hong et al.’s proposal due to a misuse of decoy states.

The paper is organized as follows: Sect. 2 presents preliminary concepts beneficial for the understanding of our argumentation, that is the original protocol in Subsection 2.1 and a vulnerability and its mitigation by Zawadzki in Sect. 2.2; Sect. 3 outlines the new vulnerability; Sect. 4 proposes a mitigation; finally, we draw our conclusions in Sect. 5.

Quantum identity authentication protocols have been proposed since the 1990s [3]. Many proposals exploit one of the most distinctive properties of quantum mechanics, namely entanglement. While being theoretically secure, reliably and cheaply manipulating entangled particles has been a long-lasting challenge from the engineering viewpoint. Thus, researchers have devoted to the design and analysis of simpler alternatives. For instance, Yuan et al.’s protocol [19] was one of the earliest to require the preparation and measurement of independent single-photon states encoding pre-shared classical keys, a paradigm followed by the aforementioned scheme by Hong et al. too. Furthermore, both protocols use BB84 states to hide classical information. However, [19] prescribes a more complex four-stage interaction, during which the authentication key is updated.

2.1 Review of Hong et al.’s protocol

Visual description of Hong et al.’s protocol [16]. Red boxes represent Alice’s actions, while the blue ones represent Bob’s steps. The notation \(\mathcal {U}(S)\) represents the uniform distribution on set S. Adapted from [16] (Color figure online)

Full size image

In the work of Hong et al. [16] a quantum identity authentication protocol was introduced (see Fig. 1), which does not rely on shared entanglement between the party to be authenticated (Alice) and the verifying party (Bob). Instead, this protocol relies on a pre-shared secret bitstring \(s = (s_1, s_2, \dots , s_l)\) with \((l = 2n) \wedge (n \in \mathbb {N})\), i.e. an even number of secret classical bits. From a high-level viewpoint, the protocol’s goal is to compare the key on Alice’s side with that on Bob’s side without revealing its content to an eavesdropper. In practice, this can be useful to implement a sort of quantum username-and-password authentication scheme, e.g. to regulate access to users’ accounts. The protocol has two different operating modes called authentication mode and security mode. Alice chooses randomly between security mode with some probability p or authentication mode with probability \(1-p\). The following protocol is carried out \(l/2 = n\) times, viz. for each pair of two consecutive bits \((s_i, s_{i+1})\) from s for even i. In the different modes the procedure is as follows:

In authentication mode Alice generates a qubit to be sent to Bob from \((s_i, s_{i+1})\). In case \(s_i\) is 0 Alice chooses the rectilinear/computational basis \(\{\vert {0} \rangle , \vert {1} \rangle \}\) for encoding and subsequently chooses the state \(\vert {0} \rangle \) if \(s_{i+1} = 0\) and \(\vert {1} \rangle \) if \(s_{i+1} = 1\). On the other hand, if \(s_i\) is 1 Alice chooses the diagonal/Hadamard basis \(\{\vert {+} \rangle , \vert {-} \rangle \}\) and picks the state \(\vert {+} \rangle = \frac{1}{\sqrt{2}}(\vert {0} \rangle + \vert {1} \rangle )\) if \(s_{i+1} = 0\) and \(\vert {-} \rangle = \frac{1}{\sqrt{2}}(\vert {0} \rangle - \vert {1} \rangle )\) if \(s_{i+1} = 1\). The state is then sent to Bob.

In security mode Alice generates a decoy state \(d_i \in \{\vert {0} \rangle , \vert {1} \rangle , \vert {+} \rangle , \vert {-} \rangle \}\) from the corresponding part of the secret \((s_i, s_{i+1})\) as follows. Again, \(s_i\) determines the choice of basis as before. \(s_i = 0\) implies the choice of the rectilinear basis \(\{\vert {0} \rangle , \vert {1} \rangle \}\) and \(s_i = 1\) implies the diagonal basis \(\{\vert {+} \rangle , \vert {-} \rangle \}\). The difference is now that the second bit \(s_{i+1}\) in the pair is irrelevant for the choice of the state from the respective basis. Alice chooses the state randomly from the selected basis, independent of \(s_{i+1}\). \(d_i\) is now sent to Bob.

This is the procedure on Alice’s side for now. Bob receives a qubit unknown to him. He measures it according to the basis which is dictated by \(s_i\) – again, \((s_i = 0 \Rightarrow \{\vert {0} \rangle , \vert {1} \rangle \}) \wedge (s_i = 1 \Rightarrow \{\vert {+} \rangle , \vert {-} \rangle \})\). \(s_i\) is the same for him and Alice, thus in authentication mode Bob will extract the correct result from the qubit \({100}{\%}\) of the time (for perfect equipment) if the state was not tampered with. Correct in this case means that the measurement result coincides with \(s_{i+1}\). After Bob measured the state he received, Alice communicates what mode she used and in security mode she additionally communicates the decoy state \(d_i\) for Bob to be able to check it. Then Bob will abort the protocol if there is a mismatch in measurement result and his secret/the decoy state, otherwise the procedure will be repeated for every pair of bits in s [16].

The security of this protocol is based upon the notions of conjugate coding [1], which is in turn an application of quantum state indistinguishability. Specifically, to an eavesdropper with no information on the secret key, Alice generates random BB84 states. By the principles of quantum information, these qubits provide no information on the corresponding secret key. On the other hand, if Bob knows Alice’s key, he possesses enough information to distinguish the incoming qubits and validate their state. The main advantage is the minimal requirements in terms of quantum hardware. Unlike other quantum proposals, this protocol does not assume complex quantum hardware such as quantum memories or devices for entanglement distillation and management. The involved parties only need to generate BB84 states and perform relatively simple measurements. Overall, modern quantum hardware can easily support both tasks, thus making the protocol implementable in the short term.

2.2 Review of Zawadzki’s attack and mitigation

According to Zawadzki the protocol by Hong et al. does not fulfil the requirements imposed on identity authentication protocols, as with a man-in-the-middle attack where the measurement basis is guessed randomly one bit of the pre-shared secret is leaked per authentication attempt by analysing the behaviour of Bob. Bob aborts the protocol if his measurement result was incorrect, thus leaking that the eavesdropper has chosen the wrong basis (corresponding to an even bit of the secret). Additionally, the bit corresponding to the encoded state (the odd bit of the secret belonging to the leaked even bit) is leaked in the subsequent protocol run. For the entangle-and-measure attack discussed by Hong et al., Zawadzki also shows that 2 bits of information of the secret are leaked per protocol run [17].

Additionally, Zawadzki provides a mitigation of the problems he showed. This mitigation includes the removal of the security mode and usage of a hash function in order to not directly compare the pre-shared secret but a session key. The session key is generated by the hash function from a random number and the pre-shared secret. Thus every authentication looks different and a modified communication behaviour presents any eavesdropper with an all-or-nothing problem every authentication attempt [17].

But it also has to be stated that this approach can just yield computational security. In fact, González-Guillén et al. [18] proved that, even with Zawadzki’s modification, the unconditional security of the protocol would violate the no-go theorems on quantum secure two-party computation [20]. Therefore, this approach must leak some information at each authentication round. González-Guillén et al. showed a concrete attack to reduce the number of candidate keys at each authentication round. The attack itself is not guaranteed to be computationally efficient though, thus opening the door to computationally secure authentication if the hash function is computationally hard to invert.

With this information in mind there seems to be another problem with Hong et al.’s protocol. At least in classical identity authentication protocols it is the normal case that there is a limited amount of pre-shared secret information, which is used multiple times. It seems reasonable to assume that the pre-shared secret is also reused in [16] and it is not stated otherwise in the paper. This is also one of the requirements for identity authentication stated by Zawadzki. But this fact opens up the protocol to some attacks. As mentioned in Sect. 2.2 the behaviour of Bob leads to information leakage, because he reveals some facts about the secret by aborting the protocol under certain conditions.

But one can argue that there is an even simpler attack vector. In every run of the protocol there are some rounds of security mode. Every time in security mode Alice reveals which decoy state \(d_i\) was sent. Even if an eavesdropper (Eve) does not alter any state but only takes note of the classical communication happening between Alice and Bob there is significant leakage of pre-shared secret information.^{Footnote 1} Every \(d_i\) that is communicated reveals the bit \(s_i\) of the corresponding pair of bits used in that instance of security mode directly. Because of this after a certain number of uses of the key Eve knows every even bit in s because statistically every pair \((s_i, s_{i+1})\) was used for security mode at some point. We can apply standard probability theory to estimate such a number.

Let us focus on an index i. During each authentication, the key bit \(s_i\) is revealed with probability p. Let \(N_i\) be a random variable representing the number of rounds after which \(s_i\) is revealed. It is easy to verify that \(N_i\) follows a geometric distribution \(\textrm{Geo}(p)\) so that

This holds for any other index \(j \in \{1,\dots ,n\}\) of the pair in question. Furthermore, each position is independent of all others. Hence the random variables \((N_1, \dots , N_n)\) are independent geometric random variables. The probability that all of them are less or equal than k is the nth power of the cumulative distribution function for the geometric distribution. For integer k, this equals

Figure 2 shows such a probability for a fixed \(n=10^4\) and various values of p. It clearly shows that even for low values of p, about 40 authentications suffice to leak all the key bits in odd position with high probability. For \(p=1/2\) the probability is close to one for \(k \approx 15\).

Probability that all key bits in odd positions are revealed after k rounds or less for various values of p and \(n=10000\) (Color figure online)

Full size image

At this point Eve can also recover the rest of the secret as follows. If the basis for encoding the key information is known Eve can measure the sent qubits in the appropriate basis and will get a certain measurement result. Because Eve knows that the basis of encoding is correct, after measuring she also knows with certainty (if the equipment is perfect) what state was used in the respective basis, which means she will get back the bit \(s_{i+1}\) of the respective round. Thus she can also create a new qubit in the correct state, which makes it possible for her to hide that the qubit was intercepted and measured.

To the authors’ knowledge nobody seems to comment on this problem. At least the following review of quantum identity authentication protocols [3] only mentions Hong et al.’s protocol [16] itself, Zawadzki’s analysis of it [17], and in turn González-Guillén et al.’s analysis of that [18]. More specifically, [18] even mentions that their attack that reduces the size of the key space is also applicable to Hong et al.’s protocol in authentication mode. Hong et al. themselves only consider three attack strategies, but do not take into account the situation when the secret is reused, which opens it up to the problems mentioned by Zawadzki and us [16].

Zawadzki points out that by running the protocol multiple times it is opened up to the possibility of collecting more and more bits of the secret, albeit not in the same way as we do here. Zawadzki proposes to extract information via looking at when the protocol is aborted, i.e. only one \(s_i\) bit is extracted per run [17].

Thus it is interesting that nobody seems to directly comment on the vulnerability we have shown, even though seemingly more involved attacks were found.

Decoy states have proven to be powerful against eavesdroppers in quantum cryptography ever since their first proposal by Hwang [21]. Due to their value, we show a simple mitigation to Hong et al.’s protocol allowing to generate and send decoy states without leaking precious key bits.

The latter consists of a modification to the decoy state generation policy adopted by Hong et al. (see Fig. 3). Alice still chooses between authentication and security mode at random, with probability p. When in security mode, instead of generating a decoy state whose basis depends on the key bits, decoy states can be uniformly random states from the set of BB84 states \(\{\vert {0} \rangle , \vert {1} \rangle , \vert {+} \rangle , \vert {-} \rangle \}\). Upon generating such a state, say \(\vert {\psi } \rangle \), Alice sends it to Bob. On his side, Bob measures it according to his key bits, as if he was in authentication mode. To avoid confusion: if the ith bit of Bob’s key \(s_i = 0\) he measures in the computational basis, else he measures in the Hadamard basis. Once Bob confirms to Alice that he measured the incoming qubit she announces her mode of operation (security) and the state of her decoy qubit. Bob can now compare this information with his measurement result, and detect the presence of malicious eavesdroppers.

Visual description of our modification. Red boxes represent Alice’s actions, while the blue ones represent Bob’s steps. The notation \(\mathcal {U}(S)\) represents the uniform distribution on set S

Full size image

Unfortunately, this is only possible if Bob’s measurement basis matches the basis of \(\vert {\psi } \rangle \), which only happens with probability \({50}{\%}\). Without loss of generality, suppose Alice prepared a decoy state in the computational basis. If \(s_i=0\), Bob can perform the check after receiving the classical description of \(\vert {\psi } \rangle \). If \(s_i=1\), then Bob cannot conclude anything about malicious eavesdropping, and the check is passed by default. However, if 2m decoy states are sent over one authentication round, on average Bob will guess the correct basis m times. Hence, it suffices to double the number of decoy states to still get the same security guarantees. It is not hard to see why this mitigation works: by making the decoy states independent and uncorrelated from Alice’s key, they convey no information to an adversary. Furthermore, due to the well-known no-signalling theorem [22], Bob’s measurement cannot convey any information on his key to Alice or Eve.

Although our mitigation covers the decoy states vulnerability, the work by Zawadzki [17] highlighted other vulnerabilities in the authentication phase. In the same paper, he suggested another mitigation using a random nonce and a hash function to turn Alice’s key into a randomized one-time session key. Our mitigation addresses an orthogonal problem, and can in principle be combined with Zawadzki’s proposal to increase the overall robustness. Recent work [18] showed that Zawadzki’s proposal cannot achieve information theoretic security, as that would violate Lo’s no-go theorem [20] on secure two-party computation. Nevertheless, one may still combine the two mitigations to achieve computational security through computationally secure hash function for Zawadzki’s modified protocol without removing security mode. A summary of all the described vulnerabilities and their mitigations can be found in Table 1.

This comment points out an additional weakness of Hong et al.’s identity authentication protocol due to a misuse of decoy states. By breaking the dependency between decoy states and the secret key bits one may fix this problem at little to no cost. Furthermore, despite other works pointing out other vulnerabilities, one can combine previously suggested mitigations with ours to result in a secure protocol. However, such a combination can only guarantee at best computational security.