Information-Theoretically Secure Data Origin Authentication with Quantum and Classical Resources

Abstract

In conventional cryptography, information-theoretically secure message authentication can be achieved by means of universal hash functions, and requires that the two legitimate users share a random secret key, which is at least twice as long as the tag. We address the question of whether quantum resources can offer any advantage over classical unconditionally secure message authentication codes. It is shown that a broad class of symmetric prepare-and-measure quantum message-authentication schemes cannot do better than their classical counterparts.

1. Introduction

One of the main information security objectives is to provide assurance about the original source of a received message [1,2,3,4]. This goal is usually referred to as data origin authentication, and it is a stronger version of another cryptographic goal, the so-called data integrity. The latter addresses the unauthorized (including accidental) alteration of the message, from the time it was created, transmitted or stored by an authorized user. Data origin authentication, on the other hand, provides assurance of the identity of the sender of the message, in addition to data integrity. From another point of view, data origin authentication implicitly provides data integrity, in the sense that if the message is somehow modified, then essentially the source of the message has changed.

Another security objective that is closely related to data origin authentication, is the so-called non-repudiation, which prevents the original sender of a specific message from denying to a third party his/her action. This is a stronger requirement than data origin authentication, because the latter provides this assurance to the receiver of the message, but it does not provide any evidence that could be presented to a third party in order, for example, to resolve a dispute between the sender and the receiver.

In modern cryptography, data origin authentication is provided by message-authentication codes (MACs), which require the two legitimate users (sender and receiver) to share a common secret key [1,2,3,4,5]. Typically, MACs are built from block ciphers [1,6] or hash functions [1,3,4,5,7]. A MAC takes as input the message and the key, and produces an authentication tag, which is sent from the sender to the receiver, together with the message. MACs that rely on block ciphers or collision resistant hash functions offer computational security, as opposed to the Wegman and Carter scheme, which exploits universal hash functions and offers information-theoretic (unconditional) security [3,4,5,7]. On the other hand, digital signature schemes are the main mechanism for providing non-repudiation and they typically rely on public-key cryptography [1,2]. Both MACs and digital-signature schemes offer data origin authentication, but only the latter can ensure non-repudiation. Hence, digital-signature schemes are of vital importance in cases where the sender and the receiver of the message do not trust each other (e.g., business applications), and there is the potential of dispute over the message. MACs are widely used in every task, when non-repudiation is not an issue (e.g., in authenticated end-to-end communication), mainly because the computational cost associated with the generation and the verification of a tag is considerably smaller than for digital signatures. It is worth noting, however, that MACs can provide non-repudiation in certain realistic scenarios e.g., when a trusted third party is involved [4].

Data origin authentication and data integrity have also been discussed in a quantum setting. More precisely, Curty and Santos have proposed an authentication protocol for 1-bit message, which requires the two legitimate users to share a maximally entangled state of qubits [8]. To the best of our knowledge, this is the only quantum MAC (QMAC) scheme in the literature, which claims an advantage over the Wegman–Carter scheme. The first quantum digital-signature scheme has been proposed by Gottesman and Chuang [9], and relies on the notion of a quantum one-way function, which maps classical bit strings (private keys) on quantum public keys (see also [10,11,12] for other applications of quantum public keys). Various authors improved on the original scheme of Gottesman and Chuang, by removing the need for quantum memory, for authenticated quantum channels, etc. [10,13,14,15,16]. These develpments go beyond the scope of the present work, and the interested reader may refer to Refs. [17,18], for an extensive list of publications related to quantum digital signatures. It is worth noting, however, that until now all of these quantum digital-signature schemes have been far less efficient than classical schemes, which renders them impractical [19,20].

By contrast to the thorough investigation of quantum digital-signature schemes, QMACs remain largely unexplored. The main question we address in the present work is whether prepare-and-measure QMACs can outperform classical schemes for information-theoretically secure data origin authentication. To address this question, we define a rather general theoretical framework for symmetric prepare-and-measure QMACs, which is absent from the literature. Subsequently, we show that such schemes cannot do better than their classical counterparts. This result is rather general, and implies that the QMAC scheme of Curty and Santos cannot outperform classical MACs.

The paper is organized as follows. For the sake of completeness, Section 2 contains a brief summary of unconditionally secure classical MACs. In Section 3, we discuss prepare-and-measure QMACs, and our main results are presented in Section 4. A summary with concluding remarks is given in Section 5.

2. Unconditionally Secure Classical MACs

Two honest users, Alice and Bob, share a common secret random key k, which is uniformly distributed over the set $\mathbb{K}$. The distribution of the secret key is not our concern here, since it can be achieved by various classical or quantum means that go beyond the scope of data origin authentication.

Alice wants to send an authenticated message m to Bob, and let $\mathbb{M}$ denote the message space, with $\left|\mathbb{M}\right|>1$. To authenticate the message, she evaluates the tag t, through a publicly known function $t:=h(k,m)$. The message and the tag $(m,t)$ are sent to Bob over a classical channel (throughout this work we focus on data origin authentication, and hence we assume that the message is sent in the clear together with the tag. If confidentiality is also an issue, the message has to be encrypted). In general, as a result of forgery or noise, Bob receives $(m^{\prime },t^{\prime })$ and he accepts the message only if $t^{\prime }=h(k,m^{\prime })$. In the framework of MACs, we can define the deception probability $P_l^{\left(\mathrm{D}\right)}$, to be the probability for an adversary (Eve) to produce a successful forgery after observing l valid message-tag pairs. In particular, we can distinguish between an impersonation and a substitution attack (also known as key-only and chosen-message attacks, respectively). In the former attack, the adversary does not have access to any message-tag pair (i.e., $l=0$), and her task is to create a pair, without knowing the secret key k, that will pass Bob’s verification. In the substitution attack, Eve has access to a single valid message-tag pair $(m,t)$, i.e., $l=1$, and her task is to produce another message $m^{\prime }\ne m$, such that $t^{\prime }=h(k,m^{\prime })$. It is straightforward to generalize the substitution attack, by giving Eve access to $l>1$ valid message-tag pairs.

Definition 1.

A MAC is l-time $\epsilon$-secure, if for all (including unbounded) adversaries, $P_l^{\left(\mathrm{D}\right)}\le \epsilon$.

Note that there is no MAC scheme with $P_0^{\left(\mathrm{D}\right)}=0$. Although Eve does not know the actual secret key, she may guess the correct tag for her message m with probability at least $1/|\tilde{\mathbb{T}}|$, where $\tilde{\mathbb{T}}$ denotes the set of different possible tags and it is assumed to be the same for all messages [3,4,5]. Hence, we have

$$\begin{array}{c}\hfill P_0^{\left(\mathrm{D}\right)}\ge \frac{1}{|\tilde{\mathbb{T}}|},\end{array}$$

(1)

and the best we can expect from a MAC scheme is to be l-time $1/|\tilde{\mathbb{T}}|$-secure. One can readily show the following fundamental theorem [4,7].

Theorem 1.

An l-time ε-secure MAC must have keys of length at least $(l+1)|{log}_2\left(\epsilon \right)|$.

A 1-time $1/|\tilde{\mathbb{T}}|$-secure MAC can be obtained by means of the Wegman–Carter construction, and the use of a strongly universal hash function $h_k$ [3,4,7], which is chosen at random from a class of such functions, and it is identified uniquely by the shared secret key k. In this case we have

$$\begin{array}{c}\hfill P_0^{\left(\mathrm{D}\right)}=P_1^{\left(\mathrm{D}\right)}=\frac{1}{|\tilde{\mathbb{T}}|},\end{array}$$

(2a)

which are the lowest deception probabilities one can aim at (it is worth noting, and keeping in mind, that the calculation of deception probabilities for classical MACs typically pertains to the worst-case scenario i.e., it involves a maximization over all possible cheating strategies for Eve). However, the cost one has to pay for attaining these probabilities is that the key scales linearly with the length of the message. More efficient 1-time $\epsilon -$secure MACs can be constructed by means of $\epsilon -$almost strongly universal hash functions, for some $\epsilon >1/|\tilde{\mathbb{T}}|$. For instance, in this context, Wegman and Carter have shown that one can have a 1-time $2/|\tilde{\mathbb{T}}|-$secure MAC with a key length which scales linearly with the length of the tag, and logarithmically with the length of the message i.e., $\left|k\right|\simeq 4{log}_2\left(\right|\tilde{\mathbb{T}}\left|\right){log}_2\left[{log}_2\left(\mathbb{M}\right)\right]$. Various $\epsilon -$almost strongly universal hash functions have been proposed in the literature (e.g., see references in [3,4,5]), and one can readily build a MAC scheme based on each one of them, with

$$\begin{array}{c}\hfill P_0^{\left(\mathrm{D}\right)}=\frac{1}{|\tilde{\mathbb{T}}|},P_1^{\left(\mathrm{D}\right)}=\epsilon .\end{array}$$

(2b)

The precise value of the security parameter $\epsilon$ and the length of the key vary from scheme to scheme. Strongly universal functions can be viewed as $1/|\tilde{\mathbb{T}}|-$almost strongly universal hash functions, and it is only in this case that $\epsilon =1/|\tilde{\mathbb{T}}|$. Finally, universal hash functions have also been exploited in the development of $l-$time unconditionally secure MACs, with $l>1$.

The main question we address in the following section is whether there are QMACs which can, in principle, compete with $\epsilon -$secure classical MACs, in terms of the achievable deception probabilities and/or perhaps the required key lengths. A corollary of Theorem 1 is that there is no MAC with unbounded-length keys that can provide information-theoretic security for an unbounded number of messages. Hence, following standard textbooks in the field [3,4] as well as existing work on QMACs [8] and quantum digital-signature schemes [10,13,14,15,16,17,18], we will focus on the most basic scenario pertaining to the authentication of a single message. Moreover, although losses and imperfections during transmission are inevitable in the realization of any quantum protocol, it is always of vital importance to know beforehand if a task can be achieved at least ideally, in the most basic communication scenario. In this spirit, we address the aforementioned question for an ideal scenario i.e., in the absence of noise and imperfections during the transmission of the quantum states.

3. Theoretical Framework for Unconditionally Secure Prepare-and-Measure QMACs

We begin with a rather general theoretical framework for unconditionally secure prepare-and- measure QMACs, which is absent from the literature. For the sake of consistency, the adopted framework follows closely the one for classical MACs that was summarized in the previous section.

Two honest users, Alice and Bob, share a random secret key k, uniformly distributed over the set $\mathbb{K}$, and Alice wants to send an authenticated classical message $m\in \mathbb{M}$ to Bob, where $\left|\mathbb{M}\right|\ge 2$. The key is independent of the message, and we have the condition

$$\begin{array}{c}\hfill \mathrm{Pr}\left(k\right|m)=\mathrm{Pr}\left(k\right)=\frac{1}{\left|\mathbb{K}\right|},\forall m\in \mathbb{M}.\end{array}$$

(3)

We will assume that the tagging of the message involves the state of a $d-$dimensional quantum system, which is initially prepared in some publicly known quantum state $|{\Psi }_{\mathrm{in}}\rangle$. Typically, a QMAC involves a publicly known set of (unitary) tagging operations $\{{\widehat{\mathcal{E}}}_{\tau }:\tau \in \mathbb{T}\}$, where the classical label is a function of the key and the message i.e., $\tau =f(k,m)$ with publicly known $f:\mathbb{K}\times \mathbb{M}\to \mathbb{T}$. For a given pair $(k,m)$, the operation ${\widehat{\mathcal{E}}}_{\tau }$ is applied on the initial state of the system, thereby obtaining the quantum state

$$\begin{array}{c}\hfill |{\Psi }_{\tau }\rangle :={\widehat{\mathcal{E}}}_{\tau }|{\Psi }_{\mathrm{in}}\rangle .\end{array}$$

(4)

Let ${\mathbb{Q}}_m:=\{|{\Psi }_{\tau }\rangle :\tau =f(k,m),k\in \mathbb{K}\}$ denote the set of possible quantum states corresponding to a given message $m\in \mathbb{M}$. Each quantum state is identified by the label $\tau =f(k,m)$, and the tagging operation is chosen such that for any possible message $m\in \mathbb{M}$ there exist distinct labels $\tau ,{\tau }^{\prime }\in \mathbb{T}$ such that ${\lambda }_{\tau ,{\tau }^{\prime }}:=\left|\langle {\Psi }_{{\tau }^{\prime }}|{\Psi }_{\tau }\rangle \right|>0$. Given that m is fixed, the distinct labels correspond to distinct keys.

The quantum state $|{\Psi }_{\tau }\rangle$ serves as a quantum tag of the message m when Alice and Bob share the secret key k, and it is sent together with the message to Bob. As a result of noise or Eve’s intervention, Bob will receive the pair $(m^{\prime },|\phi \rangle )$, and his task is to infer whether the received message has originated from Alice or not. In prepare-and-measure QMACs, this decision is made based solely on a local measurement, perhaps after a local operation, on the received quantum tag. That is, there is no need for additional communication between Alice and Bob, and the latter accepts the message as authentic only if the outcome of the measurement is consistent with the expected quantum tag $|{\Psi }_{\tau }\rangle$. We are interested in protocols with deterministic decision making, where Bob always accepts (with probability 1) the message-tag pair of honest Alice, with whom he shares the secret key. Completeness/correctness of the protocol implies that the same must also hold if Eve succeeds in guessing a valid message-tag pair. This is because, as far as Bob is concerned, the only feature that discriminates Alice from Eve is the secret key that he shares with Alice. If Eve happens to correctly guess a valid message-tag pair, this feature ceases to exist.

In general, different keys may yield the same label (and thus quantum tag) for the same message. Hence, for a given message m, the key space $\mathbb{K}$ can be partitioned into smaller non-overlapping subspaces

$${\mathbb{K}}_{m,\tau }:=\{k\in \mathbb{K}:\tau =f(k,m)\mathrm{for}m\in \mathbb{M},\tau \in \mathbb{T}\}.$$

Each subspace contains all the keys that lead to the same label $\tau \in \mathbb{T}$ for the given message $m\in \mathbb{M}$, while different subspaces correspond to different labels, and thus we have as many subspaces as labels.

The following discussion focuses on prepare-and-measure QMACs and thus from now on the term prepare-and-measure will be omitted for the sake brevity. For direct comparison to standard $\epsilon -$secure classical MACs (see Section 2), throughout this work we consider symmetric QMACs, which treat equally all of the possible messages and keys. Hence, $|{\mathbb{K}}_{m,\tau }|=L$ for all $m\in \mathbb{M}$, and $\tau \in \mathbb{T}$, while the number of labels is related to the size of the key space as follows $\left|\mathbb{T}\right|=\left|\mathbb{K}\right|/L$. The probability for a quantum tag $|\varphi \rangle$ to be equal to $|{\Psi }_{\tau }\rangle$ for a given m, is given by

$$\begin{array}{c}\hfill \mathrm{Pr}(|\varphi \rangle =|{\Psi }_{\tau }\rangle |m)=\frac{(\#k\in \mathbb{K}:|\varphi \rangle =|{\Psi }_{\tau }\rangle \mathrm{given}m)}{\left|\mathbb{K}\right|}=\frac{1}{\left|\mathbb{T}\right|}.\end{array}$$

(5)

The number of different possible quantum tags is the same for any given message $m\in \mathbb{M}$, and moreover, all of the quantum tags are equally probable. There are no preferable (i.e., more probable) messages, keys or tags. Of course, the partition of the key space varies from message to message, in the sense that a key has to yield a different tag for different messages (i.e., $h(k,m)\ne h(k,m^{\prime })$), and thus it will appear at different subspaces (If this is not satisfied, then Eve can easily cheat on Bob by substituting m with $m^{\prime }$, because the details of the protocol are publicly known and the message is sent in the clear).

The impersonation and the substitution attacks in the quantum setting can be defined in complete analogy to the classical setting.

Definition 2.

Impersonation attack—Eve wants to impersonate Alice without knowing the actual secret key k, and without having access to any valid message-tag pair. To this end, she chooses a pair $(m,|{\Psi }_{{\tau }^{\prime }}\rangle )$ with ${\tau }^{\prime }=f(k^{\prime },m)$, and sends it to Bob, hoping that Bob will accept it as a valid message originated from Alice.

Definition 3.

Substitution attack—Eve does not know the secret key k of Alice and Bob, but she has access to a single valid message-tag pair $(m,|{\Psi }_{\tau }\rangle )$. Her task is to produce another message $m^{\prime }\ne m$, such that the pair $(m^{\prime },|{\Psi }_{\tilde{\tau }}\rangle )$ with $\tilde{\tau }=f(k,m^{\prime })$ will be accepted by Bob as a valid message originated from Alice.

In closing, it is worth noting that the theoretical framework that we have just presented includes the unconditionally secure classical MACs discussed in Section 2. More precisely, one recovers the classical MACs when for any $m\in \mathbb{M}$, the possible classical tags $t\in \tilde{\mathbb{T}}$ are encoded on mutually orthogonal quantum states i.e., $t\to |{\Psi }_t\rangle$ with ${\lambda }_{t,t^{\prime }}=\left|\langle {\Psi }_t|{\Psi }_{t^{\prime }}\rangle \right|=0$, $\forall t,t^{\prime }\in \tilde{\mathbb{T}}$ with $t\ne t^{\prime }$. In this case, the security is ensured only by the classical tagging, and not by the encoding on the mutually orthogonal states.

4. Results

At this stage, we have defined a rather general theoretical framework for unconditionally secure QMACs. We can prove the following theorem.

Theorem 2.

For any QMAC that falls within the aforementioned framework and involves deterministic decision making, the deception probability for the impersonation attack is higher than what can be achieved by unconditionally secure classical MACs.

Proof. 

As discussed in Section 2, for unconditionally-secure classical MACs $P_0^{\left(\mathrm{D}\right)}=1/\left|\mathbb{T}\right|$. We will show that this is not possible for the QMACs discussed in Section 3, when Bob always accepts (with probability 1) Alice’s message.

In view of conditions (3) and (5), all of the keys are equally probable, and for any possible message, there are $\left|\mathbb{T}\right|$ different possible quantum tags. For any message, there exist at least two distinct labels, say $\tau$ and ${\tau }^{\prime }$, such that ${\lambda }_{\tau ,{\tau }^{\prime }}>0$, and in this case Bob cannot discriminate perfectly between the quantum states $|{\Psi }_{{\tau }^{\prime }}\rangle$ and $|{\Psi }_{\tau }\rangle$.

The probability for Eve to choose the valid message-tag pair $(m,|{\Psi }_{\tau }\rangle )$ is ${\left|\mathbb{T}\right|}^{-1}$, and in this case, Bob will certainly accept the pair. By contrast to the classical setting, however, in the case of QMACs, there is also a non-vanishing probability for Bob to accept the wrong pair $(m,|{\Psi }_{{\tau }^{\prime }}\rangle )$ as valid, because ${\lambda }_{\tau ,{\tau }^{\prime }}>0$. The maximum probability for successful cheating is given by

$$\begin{array}{c}\hfill P_0^{\left(\mathrm{D}\right)}=\frac{1}{\left|\mathbb{T}\right|}+\left(1-\frac{1}{\left|\mathbb{T}\right|}\right)\underset{\tau ,{\tau }^{\prime },m}{max}\left\{Q\left(\mathrm{acc}\right|\tau ,{\tau }^{\prime },m)\right\}\end{array}$$

(6)

where $Q\left(\mathrm{acc}\right|\tau ,{\tau }^{\prime },m)$ with ${\tau }^{\prime }\ne \tau$, is the conditional probability for Bob to accept Eve’s pair, given that Eve has sent $(m,|{\Psi }_{{\tau }^{\prime }}\rangle )$, whereas the unknown secret key shared with Alice is k so that Bob expects $|{\Psi }_{\tau }\rangle$ for $\tau =h(k,m)$.

In classical unconditionally secure classical MACs, the second term in Equation (6) vanishes, because Bob can perfectly discriminate between different classical tags. So, the probability for Bob to accept the wrong message-tag pair as valid is zero, thereby obtaining $P_0^{\left(\mathrm{D}\right)}=1/\left|\mathbb{T}\right|$. However, for the QMACs of Section 3, there exists at least one message, such that ${\lambda }_{\tau ,{\tau }^{\prime }}>0$. This implies a non-vanishing probability for Bob to accept the wrong pair (i.e., ${max}_{\tau ,{\tau }^{\prime },m}\left\{Q\left(\mathrm{acc}\right|\tau ,{\tau }^{\prime },m)\right\}>0$), and thus $P_0^{\left(\mathrm{D}\right)}>1/\left|\mathbb{T}\right|$, which is worse than what can be achieved in terms of classical unconditionally secure MACs. □

Based on the above, we conclude that one can have $P_0^{\left(\mathrm{D}\right)}=1/\left|\mathbb{T}\right|$ only when the quantum tags with distinct labels $\tau ,{\tau }^{\prime }\in \mathbb{T}$ are mutually orthogonal for any possible message. In this case, however, we essentially deal with a classical MAC, because one can perfectly discriminate between the different quantum tags, and thus the security of the protocol may rely only on the choice of the classical function $f(·)$. The same conclusion can be reached if one works with the average rather than the maximum deception probability. It is also worth emphasizing that these observations and arguments do not depend on the type or the size of the key. This point becomes clearer in the following subsection.

4.1. A QMAC with Quantum Key

Curty and Santos have proposed a QMAC for the authentication of a binary message, by means of a quantum key [8]. In their protocol, Alice (A) and Bob (B) share a pure entangled state

$$\begin{array}{c}\hfill {|\Psi \rangle }_{\mathrm{AB}}=\frac{1}{\sqrt{2}}\left({|01\rangle }_{\mathrm{AB}}-{|10\rangle }_{\mathrm{AB}}\right),\end{array}$$

(7)

which plays the role of a secret key. The message and the tag are carried by a four-dimensional quantum system “C” (e.g., two qubits), and let $\{|{\varphi }_j\rangle :j=0,1,2,3\}$ be an orthonormal basis.

When Alice wants the send message $m\in \{0,1\}:=\mathbb{M}$, she sends state $|{\varphi }_m\rangle$ to Bob, after applying a publicly known tagging operation $\widehat{\mathcal{E}}$ controlled by the state of her half of the entangled state. More precisely, the tagging operation is given by ${\widehat{\mathcal{E}}}_{\mathrm{AC}}=(|0\rangle {\langle 0|}_{\mathrm{A}}{\widehat{\mathbf{1}}}_{\mathrm{C}}+|1\rangle {\langle 1|}_{\mathrm{A}}{\widehat{\mathcal{U}}}_{\mathrm{C}}),$ for a publicly known unitary $\widehat{\mathcal{U}}$, and the overall state becomes

$$\begin{array}{c}\hfill {|\Psi \rangle }_{\mathrm{ABC}}=\frac{1}{\sqrt{2}}\left[{|01\rangle }_{\mathrm{AB}}{|{\varphi }_m\rangle }_{\mathrm{C}}-{|10\rangle }_{\mathrm{AB}}{\widehat{\mathcal{U}}}_{\mathrm{C}}{|{\varphi }_m\rangle }_{\mathrm{C}}\right].\end{array}$$

(8)

Tracing out the entangled state, the state of the transmitted message-tag pair reads

$$\begin{array}{c}\hfill {\tilde{\rho }}_m=\frac{1}{2}\left(|{\varphi }_m\rangle \langle {\varphi }_m|+{\widehat{\mathcal{U}}}_{\mathrm{C}}|{\varphi }_m\rangle \langle {\varphi }_m|{\widehat{\mathcal{U}}}_{\mathrm{C}}^{†}\right).\end{array}$$

(9)

Upon receipt of the message-tag pair, Bob performs the decoding operation ${\widehat{\mathcal{D}}}_{\mathrm{BC}}=(|0\rangle {\langle 0|}_{\mathrm{B}}{\widehat{\mathcal{U}}}_{\mathrm{C}}^{†}+|1\rangle {\langle 1|}_{\mathrm{B}}{\widehat{\mathbf{1}}}_{\mathrm{C}}),$ and subsequently a projective measurement on the orthonormal basis $\{|{\varphi }_j\rangle :j=0,1,2,3\}$. He accepts the pair if the measurement returns one of the first two elements in the basis, i.e., $j\in \{0,1\}$, and rejects it otherwise. One can readily confirm that Bob always accepts Alice’s message with probability 1.

In this protocol, Alice and Bob essentially share a secret key $k\in \mathbb{K}:=\{0,1\}$ in the form of an entangled state. For message m, Alice sends $|{\varphi }_m\rangle$ to Bob if $k=0$, and $\widehat{\mathcal{U}}|{\varphi }_m\rangle$ if $k=1$. The basis state $|{\varphi }_m\rangle$ can be viewed as if obtained from some publicly known initial state $|{\Psi }_{\mathrm{in}}\rangle$ by applying ${\widehat{\mathcal{V}}}_m|{\Psi }_{\mathrm{in}}\rangle :=|{\varphi }_m\rangle$. Hence, the present scheme can be viewed as a special case of the quantum tagging defined in Equation (4), where the function $f(·)$ is the identity function, and ${\widehat{\mathcal{E}}}_{k,m}={\widehat{\mathcal{U}}}_k\otimes {\widehat{\mathcal{V}}}_m$ with ${\widehat{\mathcal{U}}}_0=\widehat{\mathbf{1}}$ and ${\widehat{\mathcal{U}}}_1=\widehat{\mathcal{U}}$. The label $\tau$ is essentially $\tau =(k,m)$ and for a given $m\in \{0,1\}$ it can take two possible values depending on the value of k, namely $\left\{\right(0,m),(1,m\left)\right\}$. According to Theorem 2 and the related proof, the present scheme cannot achieve $P_0^{\left(\mathrm{D}\right)}=1/\left|\mathbb{T}\right|$ for the impersonation attack, unless ${\lambda }_{\tau ,\tau {}^{\prime }}=0$ for all possible messages in $\mathbb{M}$ and $\tau ,{\tau }^{\prime }\in \mathbb{T}$, with $\tau \ne {\tau }^{\prime }$. This condition reduces to

$$\begin{array}{c}\hfill \langle {\varphi }_m|\widehat{\mathcal{U}}|{\varphi }_m\rangle =0,\forall m\in \{0,1\}.\end{array}$$

(10)

(See also Appendix A for an example of the impersonation attack.)

Let us consider now the substitution attack. Suppose that Eve has access to a valid message-tag pair, which is sent from Alice to Bob. Eve’s task is to decide whether the transmitted system is in state $|{\varphi }_m\rangle$ or $\widehat{\mathcal{U}}|{\varphi }_m\rangle$. If she succeeds, then she knows whether Bob will apply ${\widehat{\mathcal{U}}}^{†}$ or not. Given that $\widehat{\mathcal{U}}$ is a publicly known unitary, in this case Eve can cheat successfully by changing m to $m\oplus 1$ and by sending $|{\varphi }_{m\oplus 1}\rangle$ or $\widehat{\mathcal{U}}|{\varphi }_{m\oplus 1}\rangle$ to Bob. In order to prevent such an attack, one needs

$$\langle {\varphi }_m|\widehat{\mathcal{U}}|{\varphi }_m\rangle \ne 0,\forall m\in \{0,1\},$$

(11)

so that Eve cannot perfectly distinguish between $|{\varphi }_m\rangle$ and $\widehat{\mathcal{U}}|{\varphi }_m\rangle$. However, this requirement contradicts the conditions (10), required for attaining $P_0^{\left(\mathrm{D}\right)}=1/\mathbb{T}$. Thus, there is no unitary operation $\widehat{\mathcal{U}}$ that can satisfy both of these conditions simultaneously.

4.2. Decision Making Based on a Symmetry Test

We have seen that a broad class of symmetric QMACs cannot attain $P_0^{\left(\mathrm{D}\right)}=1/\left|\mathbb{T}\right|$, irrespective of the length of the key. The natural question arises as of whether QMACs in the particular class allow for shorter keys than their classical counterparts, at the cost of accepting slightly larger deception probabilities for the impersonation attack. In this context one may, for instance, accept $P_0^{\left(\mathrm{D}\right)}=1/\left|\mathbb{T}\right|+\delta$ in Equation (6), for some small correction $0<\delta \le 1/\left|\mathbb{T}\right|$. The precise value of $\delta$ is determined by the set of overlaps $\{{\lambda }_{\tau ,{\tau }^{\prime }}:\tau ,{\tau }^{\prime }\in \mathbb{T}\mathrm{with}\tau \ne {\tau }^{\prime }\}$, as well as by the strategy based on which Bob accepts/rejects a message-tag pair. In general, $Q\left(\mathrm{acc}\right|\tau ,{\tau }^{\prime },m)$ increases with increasing ${\lambda }_{\tau ,{\tau }^{\prime }}$, which in turn implies increasing deviations of $P_0^{\left(\mathrm{D}\right)}$ from the lowest possible value $1/\left|\mathbb{T}\right|$. To keep $P_0^{\left(\mathrm{D}\right)}$ close to $1/\left|\mathbb{T}\right|$, one would like to have the maximum overlap ${\lambda }_{max}:={max}_{k,k^{\prime },m}\left\{{\lambda }_{\tau ,{\tau }^{\prime }}\right\}$ as small as possible (close to zero) which, however, facilitates Eve’s cheating by means of a substitution attack (states with different $\tau$ become nearly orthogonal).

One way to circumvent this stumbling block for any given $0<{\lambda }_{max}<1$ is to use message-tag pairs of the form $(m,{|{\Psi }_{\tau }\rangle }^{\otimes n-1})$. Hence, the probability for Bob to accept an invalid message-tag pair can be reduced to any $0<ϵ\le 1/\left(\right|\mathbb{T}|-1)$ for a suitable $n=\mathcal{O}\left(\right|{log}_2\left(ϵ\right)\left|\right)$ [9,11], without the necessity for choosing ${\lambda }_{max}$ close to 0.

It is worth noting here that Bob’s task is not to infer the precise state of the quantum tag, but rather to decide on whether this state equals the expected state. In other words, given $(n-1)$ copies of $|{\Psi }_{{\tau }^{\prime }}\rangle$ (received tag) and one copy of the expected tag $|{\Psi }_{\tau }\rangle$ (which can be prepared locally), Bob has to decide whether $|{\Psi }_{{\tau }^{\prime }}\rangle =|{\Psi }_{\tau }\rangle$ or $|\langle {\Psi }_{{\tau }^{\prime }}|{\Psi }_{\tau }\rangle |<1$. In the former (latter) case, he concludes that the received message-tag pair has (not) originated from Alice, and he accepts (rejects) it. This task can be performed, for instance, by means of a symmetry-test [21], which is optimal (with respect to the one-sided error requirement). Bob never rejects a valid message-tag pair, while for $\tau \ne \tau \prime$, the maximum error probability is given by [21,22]

$$\begin{array}{c}\hfill \underset{\tau ,{\tau }^{\prime },m}{max}\left\{Q\left(\mathrm{acc}\right|\tau ,{\tau }^{\prime },m)\right\}=\frac{1}{n}\left[1+(n-1){\lambda }_{max}^2\right].\end{array}$$

(12)

Inserting the resulting expression into Equation (5), and asking for $P_0^{\left(\mathrm{D}\right)}=1/\left|\mathbb{T}\right|+\delta$, we obtain

$$\begin{array}{c}\hfill n=\frac{\left(\right|\mathbb{T}|-1)(1-{\lambda }_{max}^2)}{\delta \left|\mathbb{T}\right|-\left(\right|\mathbb{T}|-1){\lambda }_{max}^2},\end{array}$$

(13)

which is meaningful for ${\lambda }_{max}<\sqrt{\delta \left|\mathbb{T}\right|/\left(\right|\mathbb{T}|-1)}$. Recalling that $\delta \le 1/\left|\mathbb{T}\right|$, we have

$$\begin{array}{c}\hfill n>\left|\mathbb{T}\right|-2,\end{array}$$

(14)

which shows that for any chosen $0<\delta \le 1/\left|\mathbb{T}\right|$, the number of copies n required for attaining $P_0^{\left(\mathrm{D}\right)}=1/\left|\mathbb{T}\right|+\delta$ is more than $\left|\mathbb{T}\right|-2$.

In order to have 1-time $\epsilon -$secure QMAC, the entropy of the tags should be at least $|{log}_2\left(\epsilon \right)|+I_{\mathrm{gain}}$, where $I_{\mathrm{gain}}$ is the information that Eve can extract from $(n-1)$ copies of the $d-$dimensional quantum state $|{\Psi }_{\tau }\rangle$, while according to the Holevo bound, $I_{\mathrm{gain}}\le (n-1){log}_2\left(d\right)$. Given that the message is known, this entropy can originate only from the key, and thus we ask for ${log}_2\left(\right|\mathbb{K}\left|\right)\ge |{log}_2\left(\epsilon \right)|+(n-1){log}_2\left(d\right)$. Using Inequality (14), we find that ${log}_2\left(\right|\mathbb{K}\left|\right)>|{log}_2\left(\epsilon \right)|+(\left|\mathbb{T}\right|-3){log}_2\left(d\right)$, which scales linearly with $\left|\mathbb{T}\right|$. This is in striking contrast to known $1-$time $\epsilon -$ secure classical MACs with $\epsilon \sim 1/\left|\mathbb{T}\right|$, which attain similar deception probabilities for ${log}_2\left(\right|\mathbb{K}\left|\right)\sim {log}_2\left(\right|\mathbb{T}\left|\right)$ (see Section 2 and related references).

5. Summary

We have discussed unconditionally secure data origin authentication by means of classical and quantum resources. The main question we have addressed is whether prepare-and-measure QMACs can outperform classical unconditionally secure MACs. This fundamental question is of pivotal importance for the field, and to the best of our knowledge, it has not been addressed adequately in the literature so far. Although losses and imperfections are inevitable in the realization of any quantum protocol, it is always important to know beforehand if a task can be achieved, at least ideally, in the most basic communication scenario. Hence, the above question has been addressed in the framework of 1-time authentication under an ideal scenario. We showed that even under such favorable conditions, a broad class of prepare-and-measure QMACs cannot do better than their classical counterparts, in the sense that they cannot attain deception probabilities $P_0^{\left(\mathrm{D}\right)}=1/\left|\mathbb{T}\right|$. This result contradicts certain conjectures that have been made in previous related work [8]. Moreover, we showed that the key length required for attaining both $P_0^{\left(\mathrm{D}\right)}=1/\left|\mathbb{T}\right|+\delta$ (with $0<\delta \le 1/\left|\mathbb{T}\right|$) and $P_1^{\left(\mathrm{D}\right)}\sim 1/\left|\mathbb{T}\right|$ increases linearly with the size of the tag space $\left|\mathbb{T}\right|$, as opposed to the logarithmic scaling in known classical schemes with similar deception probabilities.

The present analysis and results pertain to a particular yet rather broad class of symmetric prepare-and-measure QMACs. From practical point of view, such a type of QMACs is of particular interest, because the receiver can decide on the authenticity of the message based solely on the received message-tag pair, and there is no need for additional communication between the sender and the receiver. The present work may serve as a benchmark for future work in the field. More precisely, the generality of the results suggests that any future efforts for the development of unconditionally secure QMACs, which can outperform their classical counterparts, should focus on protocols outside the present class of protocols (this is for instance the case of interactive and/or entanglement-assisted QMACs). An alternative possible direction of research involves the use of physical unclonable functions with quantum readout (e.g., see [23,24] and references therein).