# An Attack on [PERSON]'s Quantum Authentication Scheme
## 1 Introduction
### Our Contribution  
Recently, an original work about authentication without entanglement by [PERSON] et al. in [PERSON] et al. (2018) was improved by [PERSON] using tools from classical cryptography in [PERSON] (2017). In [PERSON]'s protocol, there are two parties, [PERSON] and [PERSON], who share a common secret bitstring \(k\). In order to achieve entity authentication from [PERSON] to [PERSON], they run a non-interactive protocol in which [PERSON] first computes a hash value \(h_{a}\), which depends on \(k\) and a random nonce \(r\); then [PERSON] sends \(r\) to [PERSON] so he can reproduce the computation obtaining a hash value \(h_{b}\) (which must equal \(h_{a}\) if there is no adversarial interference). Next [PERSON] sequentially sends quantum states to [PERSON], which she prepares as a function of consecutive pairs of bits of \(h\). At reception, [PERSON] measures these states choosing each time a basis which depends on the value \(h\). If all measures' outcomes are the expected ones, [PERSON] concludes that the other party must know \(k\) and, therefore, identifies it as being [PERSON].  
Our theoretical analysis of the protocol shows its insecurity, but in a non-constructive way (e.g., it does not help finding a concrete successful adversarial strategy). However, we are in addition able to show an explicit attack against the protocol, based on conclusive exclusion on quantum measurements, which we describe in Section 4. There we analyze in detail how the attack halves the size of the key space after only three verification attempts.  
Note that, when analyzing [PERSON]'s protocol, we deal only with its theoretical design. Both the impossibility results we invoke and our attack do not take advantage of physical aspects, such as distance or timing, they hold independently of the implementation. It is indeed interesting to study in depth how identification protocols could be practically deployed in the real world, and what weaknesses could be exploited, but this is beyond the scope of this work. These physical issues, present in attacks against QKD, such as, for example, time-shift attacks [18], phase-remapping attacks [19] or synchronization attacks [20], would also naturally arise for quantum identification protocols.  
Finally, we discuss the applicability of the impossibility results and the explicit attack to other QIA protocols, such as [4; 5; 8; 21; 22; 23; 24]. For instance, we point out that the protocol from [PERSON] et al. [8], in which [PERSON]'s protocol is based upon, is vulnerable to the same attack we describe against the latter. On the other hand, the rest of the protocols cited, for different reasons discussed later, are neither affected by the impossibility results nor vulnerable to our attack.  
The main contribution that arises from this work is that our theoretical analysis evidences an implication of the proven impossibility of identification schemes, such as [PERSON]'s design. Thus, we stress that fundamental changes in the original proposal, beyond preventing our particular attack, would be needed in order to derive a secure identification scheme.