# An Attack on [PERSON]'s Quantum Authentication Scheme
## 4 A Key Space Reduction Attack on Zawadzki's Protocol  
Before discussing the specific attack, let \(B\) be a set of orthogonal bases in \(\mathbb{C}^{2}\) and consider the following fact. If a quantum state is prepared in a basis \(b\in B\) with value \(v\in\{0,1\}\), then an adversary may always remove one possible combination of \(b\) and \(v\) with a single measurement. Upon measuring in basis \(b^{\prime}\in B\) an adversary obtains \(v^{\prime}\in\{0,1\}\). The adversary is then certain the original pair \((b,v)\) was not \((b^{\prime},1\oplus v^{\prime})\), as when measured in the basis \(b\) the qubit prepared by \(b\) and \(v\) will yield \(v\) with certainty. Note that the adversary cannot say with certainty how the qubit was prepared, but he can always remove one possible option. This is an example of conclusive exclusion discussed in [28] in the case of two measurement bases. Suppose now that instead of sampling at random for \(b\) and \(v\), the qubit is prepared using a private key \(k\in K\) and a set of public parameters \(p\), namely \(b=b(k,p)\) and \(v=v(k,p)\). An adversary once again measures in basis \(b^{\prime}\in B\) (chosen or taken at random) to obtain \(v^{\prime}\in\{0,1\}\), they may then determine a basis/value pair in which the qubit was not prepared. Because the adversary is assumed to be computationally unbounded they may then compute \(b(\hat{k},p)\) and \(v(\hat{k},p)\) for all \(\hat{k}\in K\). Whenever these computations output the impossible pair \(k^{\prime},v^{\prime}\) the adversary becomes aware that \(\hat{k}\
eq k\), hence reducing the key space. The extent to which the key space is reduced depends on the number of basis in \(B\). If the distribution of basis choices in \(B\) is low entropy the attack may be accomplished as described while if \(B\) is high entropy then a probabilistic version decreases the space of likely keys. The assumption that the adversary is computationally unbounded may be lifted if \(k\) is low entropy (for he can then indeed test all possible values for \(k\)--given there are only a polynomial set of candidates), however assuming a computationally bounded adversary immediately removes unconditional security as an end goal. Let us now apply this key space reduction to the QIA protocol proposed in [7], in this case the private key is \(k\) and the public parameters are \(r\) and \(H\). Suppose an [PERSON] has no a priori knowledge of the key except its existence in \(K\). After receiving \(r\) and \(H\) over the classical channel she measures all qubits \(|\varphi_{i}\rangle\) received from [PERSON] in the horizontal/vertical basis and records the outputs as \(M\). In the case where [PERSON] is utilizing man-in-the-middle, she is done. If she is impersonating [PERSON], she accepts or rejects the protocol. After the protocol finishes the adversary may then compute \(h_{\hat{k}}=H(r||\hat{k})\) for all \(\hat{k}\in K\). Suppose the first qubit [PERSON] measured in \(M\) was \(|0\rangle\). She now examines the first two bits of each \(h_{\hat{k}}\), those that begin 00, 10, or 11 are all possible of obtaining the qubit \(|0\rangle\) after measurement. The first of these three tuples will yield \(|0\rangle\) with certainty and the later two with a probability of 0.5. The final tuple 01 however is not possible as that would imply that the qubit started in the state \(|1\rangle\) and measured in \(|0\rangle\). Thus, [PERSON] knows that any \(\hat{k}\) such that \(h_{\hat{k}}\) begins 01 is not the key. The hash function is assumed to be independent and identically distributed so this removes approximately \(\frac{1}{4}\) of all possible keys. Repeat this process for all qubits. After completion of all hash and check operations the adversary has obtained a subset of the key space which contains the key, hence causing information leakage.