{'fraction_non_alphanumeric': 0.03078378220254695, 'fraction_numerical': 0.005801821479415723, 'mean_word_length': 4.425329312807491, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Unified Framework For Quantum Unforgeability

In this paper, we continue the line of work initiated by Boneh and Zhandry at CRYPTO 2013 and EUROCRYPT 2013 in which they formally define the notion of unforgeability against quantum adversaries specifically, for classical message authentication codes and classical digital signatures schemes. We develop a general and parameterised quantum game-based security model unifying unforgeability for both classical and quantum constructions allowing us for the first time to present a complete quantum cryptanalysis framework for unforgeability. In particular, we prove how our definitions subsume previous ones while considering more fine-grained adversarial models, capturing the full spectrum of superposition attacks. The subtlety here resides in the characterisation of a forgery. We show that the strongest level of unforgeability, namely existential unforgeability, can only be achieved if only orthogonal to previously queried messages are considered to be forgeries. In particular, we present a non-trivial attack if any overlap between the forged message and previously queried ones is allowed. We further show that deterministic constructions can only achieve the weaker notion of unforgeability, that is selective unforgeability, against such restricted adversaries, but that selective unforgeability breaks if general quantum adversaries (capable of general superposition attacks) are considered. On the other hand, we show that PRF is sufficient for constructing a selective unforgeable classical primitive against full quantum adversaries. Moreover, we show similar positive results relying on Pseudorandom Unitaries (PRU) for quantum primitives. These results demonstrate the generality of our framework that could be applicable to other primitives beyond the cases analysed in this paper.


Introduction
Recent advances in quantum technologies threaten the security of many widelydeployed cryptographic primitives. This calls for quantum-secure cryptographic schemes. Usually, two main security models are considered when analysing the security of cryptographic primitives against quantum adversaries: the standard security model, often also termed post-quantum security, where the adversary only has classical access to the primitive but can locally perform quantum computations; or the quantum security model where the adversary has further quantum access to the primitive, i.e. they can issue quantum queries. In the quantum setting, and more specifically in the quantum security model, the quantum nature of interaction with the primitives, enables a broader range of attack scenarios, making the task of transposing security definitions to the quantum setting highly non-trivial and subtle [1,2,3,4,5]. One of the key elements of the quantum security model is the fact that the adversary can query the oracle with quantum states in superposition. Superposition queries are more likely to lead to non-trivial attacks [6,7] that are not possible in the classical regime. Another important aspect is that having access to the input-output pairs of the oracle in the form of quantum states enables the adversary to run quantum algorithms and take advantage of quantum speedup. Of course, a possible countermeasure against superposition attacks is to forbid any kind of quantum access to the oracle through measurements. However, in such a setting the security relies on the physical implementation of the measurement tool which itself could be potentially exploited by a quantum adversary. Thus, and as it has previously been advocated in [1,2,3,5], providing security guarantees in the quantum security model is crucial. In this paper, we pursue the line of work initiated by Boneh and Zhandry in [1,2], as well as Alagic et al. in [5] on formalizing the notion of unforgeability in the quantum security model. This notion is the security property desired for many primitives such as Message Authentication Codes, Digital Signatures, or Physical Unclonable Functions. Informally, unforgeability ensures that the adversary cannot produce valid input-output pairs of the oracle without access to the full description of its circuit. These previous definitions, as we will see, do not, however, capture the full spectrum of possible superposition attacks. Unforgeability is also a key security property for quantum primitives, such as Quantum Physical Unclonable Functions (qPUF) and Quantum Money; however, previous definitions [1,2,5] again do not apply to such quantum primitives.

Different levels of Classical and Quantum Unforgeability
Goldwasser et al. [8] define different notions of unforgeability for digital signatures. They consider various types of attacks including: chosen message attacks (cma) where the adversary is allowed access to the signing oracle on a list of messages chosen by the adversary. They define existential forgery as the attack where the adversary can forge a valid signature for at least one new message; and the notion of selective forgery as an attack where the adversary can forge a valid signature with non-negligible probability for a particular message chosen by the adversary prior to accessing the signing oracle.
An et al. [9] define a slightly stronger notion of unforgeability called strong unforgeability that requires the adversary not only to be unable to generate a valid signature on a"new" message but also to be unable to generate even a valid "new" signature on an already signed message. Strong Existential Unforgeability (SEUf ), also called strong unforgeability, has formally been defined in [10] by Boneh et al.
Bellare et al. [11] define the notion of Strong Existential Unforgeability under chosen message and chosen verification queries attack (SEUF-cmva) for message authentication codes (MACs). In both of these attack models, the adversary is allowed a chosen message oracle access, as defined for digital signatures in [8]. Although in the later attack model for message authentication codes, the experiment also allows verifying queries through oracle access. This model is justified for MACs as unlike digital signatures, where the verification algorithm is public, the adversary cannot run the verification algorithm on their own. (Weak) Existential Unforgeability (EUf ) under chosen message attacks is a natural definition for MACs defined by Bellare et al. [12] and comes by extending the one for digital signatures [8].
A yet weaker notion called universal unforgeability requires the adversary to produce a fresh tag for a uniformly random message given as challenge to the adversary [14]. This notion again can be considered against both attack models: chosen message and chosen verification queries attack (UniUF-cmva) and chosen message attack (UniUF-cma). Table 1 summarizes all these different classical notions of unforgeability.
In the quantum regime, the definition of unforgeability defined by Boneh and Zhandry [1,2] (denoted by BZ), is described as a quantum analogue of strong existential unforgeability and it is in the chosen message attack (cma) model. The definition of Blind unforgeability (BU) by Alagic et al. [5] has been defined as (weak) quantum existential unforgeability but they have also presented the extension of the definition to strong existential unforgeability. In this paper, we present a unified and parameterised definition that extends to different levels of unforgeability. Our Quantum Generalised Existential Unforgeability (µ-qGEU) has been defined as a quantum analogue of (weak) existential unforgeability, although we will show that it can be extended to capture the strong case as well. Further we investigate the quantum analogue of selective and universal unforgeability, namely Quantum Generalised Selective Unforgeability (µ-qGSU) and Quantum Generalised Universal Unforgeability (qGUU). Our formal definitions have been defined in the cma attack model similar to previous ones although the structure of our game easily allows for weaker attack models, namely random message attack (rma) in which the adversary instead of choosing arbitary queries, is given a set of randomly selected quantum states from a distribution, and their respective query outputs. This attack model is most relevant for quantum primitives, with potential interest for some classical primitives studied in the quantum security model as well. Nevertheless, we will not discuss this attack model in details in the current paper. Finally, we also study an adaptive attack model which is specific to universal unforgeability and allows the adversary to continue querying the oracle after receiving a randomly picked message as a challenge. Table 2 shows a summary of different levels of quantum unforgeability introduced in previous works, as well as the current paper.

Our Contributions
We propose a general and unified definition of quantum unforgeability for both classical and quantum cryptographic primitives. Our definition captures any quantum adversary, covering the full spectrum of superposition attacks. We present our definitions in the quantum-game based framework in the spirit of [2,16,17]. Our framework generalises the notion of unforgeability in three aspects. First, by generalising the message space to both the classical message space and Hilbert spaces, and allowing a wider range of quantum oracle access types, we unify the notion of quantum unforgeability for both quantum and classical primitives. Second, our framework captures different levels of unforgeability as quantum analogues of the unforgeability notions studied in the classical setting. These levels correspond to different attacker capabilities and have different practical applications. More precisely, previous definitions of quantum unforgeability only capture strong and weak existential unforgeability, while our framework further captures the notions of selective and universal unforgeability for the first time. We formally show the hierarchy between these definitions through our framework.
Finally, our framework precisely captures the quantum capabilities of the adversary in terms of overlap between the challenge and the queried states in the learning phase. This formalizes the full spectrum of unforgeability from classical to fully quantum, revealing new non-trivial attacks. Our parameterised definitions of µ-existential and µ-selective unforgeability allow the adversary to forge a "new" µ-distinguishable challenge. The notion of µ-distinguishability captures the overlap between the challenge and the learning phase and allows characterising "new" challenges in a fine-grained manner. This contrasts with previous definitions which characterise "new" challenges, respectively, through counting the queries like Boneh-Zhandry [1,2]. This approach is too weak as previously pointed by Alagic et al. [5], and does not fully explore the advantage that a quantum adversary can gain through quantum queries and the fact that some quantum queries are being consumed during the attack. Moreover, we formally show that the definition of [5] is a special instance of our definition. We then explore the applicability and relevance of our definitions through several novel possibility and impossibility results. Here we give a summary of our key findings.
Generalised Existential Unforgeability (µ-qGEU): We show that this notion of unforgeability can only be achieved in the most restricted case (µ = 1) where the adversary is not allowed any overlap between their queries to the oracle (during the learning phase) and the target forgery message. For any other value of µ, we show the existence of a general superposition attack and hence that no quantum or classical primitive can satisfy existential unforgeability. Nevertheless, as we show the equivalence with BU for µ = 1, we inherit the positive results from [5] for this case.
Generalised Selective Unforgeability (µ-qGSU): This is a weaker unforgeability notion, where the adversary needs to commit their selected messages before querying the oracle in the learning phase. Here our results show a non-intuitive impossibility as well as a separation between randomised and non-randomised constructions. Our definition carefully discards the probability of trivial attacks, to only capture effective adversaries. First, we prove that no classical or quantum primitive with a deterministic evaluation algorithm satisfies this notion of unforgeability. To establish our impossibility result, we show an attack based on the Universal Quantum Emulator Algorithm [18]. This type of attack was first studied in the context of quantum physical unclonable functions [19]. Here we show that similar attacks apply to some levels of unforgeability for classical primitives too. Concretely, our no-go result implies that deterministic Message Authentication Codes constructions such as HMAC, NMAC, etc. cannot satisfy µ-qGEU nor µ-qGSU except for quantum adversaries restricted to orthogonal challenges (case where µ = 1). Hence these classical primitives are always vulnerable against more powerful quantum adversaries, or in other words when these distinguishability conditions cannot be efficiently checked and implemented in practice. On the other hand, we show that Pseudorandom Functions (PRFs) are sufficient for constructing a quantum selective unforgeable classical primitive against full quantum adversaries (for all reasonable degrees of µ) by proposing a randomised construction. Similarly, we present a randomised quantum primitive that can satisfy the same unforgeability level relying on the assumption of Pseudorandom Unitaries (PRU). For our quantum construction, we also characterize the quantum randomised oracle and propose a construction in the circuit model.
Generalised Universal Unforgeability (qGUU): Here the notion of unforgeability is further weakened requiring the adversary to forge the response to a message picked uniformly at random by the challenger. We show general positive results for both quantum and classical primitives wrt this notion, provided their evaluation algorithm is a quantum secure PRF or a PRU. We note that even though this notions is weaker than the previous ones, it is much easier to achieve in practice and has applications in many scenarios such as quantum identification protocols [20].

Preliminaries
In this section, we discuss the previous definitions for quantum unforgeability, as well as some of the main concepts and definitions that we rely upon in the paper.

Quantum accessible oracles for classical primitives
A quantum oracle is a unitary transformation O over a D-dimensional Hilbert space that can be queried with quantum queries. The quantum oracle can grant quantum access to the evaluation transformation of a classical or quantum primitive. For classical primitives we follow the standard definition of quantum oracle [1,2,4,21,22] In the standard quantum-query model, the adversary A has black-box access to a reversible version of f , which is a classical-polynomial-time computable deterministic or randomised function of the evaluation E, through an oracle RO E f which is a unitary transformation. The evaluation oracle can be represented as: This is also referred to as Standard Oracle. Here m is the message and y is the ancillary system required for unitarity. In general the standard oracle can also capture randomised evaluations with a randomness r picked from R ⊆ {0, 1} l as the randomness space, although in this case the oracle may not be a unitary transformation. The unitary representation of the standard oracle has been introduced in several works such as [4,21,22] with slightly different approaches that lead to equivalent adversary's state, which is totally mixed with respect to the randomness subspace. Although in this work, to emphasise that the adversary cannot gain access to the internal randomness register of the oracle directly and avoid some potential artificial entanglement attacks, we opt for the approach of [21] and consider the randomness as an internal state of the oracle which is re-initiated for each query with a new classical value r. This choice is also due to the fact that the oracle needs to output the randomness register as a separable state, otherwise an unwanted entanglement will be created between the adversary's output state and the internal register of the oracle, as also mentioned in [21]. Moreover if the primitive requires that the randomness is returned to the adversary for each query (as a classical bit-string or a function of r), it can be recorded in the adversary's auxiliary state y that can be extended to also capture the randomness space. An example of such construction will be introduced later in the paper. Finally, we specify that for deterministic primitives (denoted by O E f ), the structure is similar except that the randomness register is not used.

Quantum oracle for quantum primitives
The evaluation between these states of a quantum primitive can be directly defined as a unitary transformation. Hence the deterministic oracle can be modeled as follows: where {|m i } are a basis (not necessary computational basis) for H D that the unitary operates upon. We note that the quantum primitives can perform an arbitrary rotation of the bases. The analogue of this type of oracles for classical primitives, are type-2 oracles (also called minimal oracles) [4,21]. A randomised quantum primitive can also be defined similar to the classical case. Here we give an abstract notation of a general randomised quantum primitive, but we further clarify the realisation of such oracles in the upcoming sections. We denote a general randomised unitary oracle for quantum primitives as follows: Hence a RO E is a unitary over the joint space of the oracle's randomness register and the main input state, which consist of a family of smaller unitaries parameterised by a random internal parameter r.

Formal definitions of BU and BZ
The definition of existential unforgeability under quantum chosen-message attacks (EUF-qCMA) for digital signatures has been presented in [2,1]  Another definition of unforgeability against quantum adversaries called blind unforgeability was proposed in [5]. This more recent definition aims to capture some attacks that are not captured by BZ. This notion defines an algorithm to be forgeable if there exists an adversary who can use access to a "partially blinded" oracle to validate responses of the messages that are in the blinded region and hence only respond to the queries that are not in this region. A blinded operation for a function f : X → Y and a subset of messages B ⊆ X is defined as: Where in particular for the definition of unforgeability, the elements of X are placed in B independently at random with a particular probability , denoted by B . Then the security game of unforgeability has been defined as follows with the adversary having access to the blinded oracle. From this game blind-unforgeability is defined as follows. A MAC scheme Π is blind-unforgeable (BU) if for every polynomial-time uniform adversary (A, ) P r[BlindF orge A,Π (n, (n)) = 1] ≤ negl(n). and the probability is taken over the choice of key, the choice of blinding set, and any internal randomness of the adversary.
Thus, in this definition, a forgery happens if the adversary can produce a valid tag for a message within the blinded region. We refer to this definition of unforgeability as BU. This definition imposes that the challenge be orthogonal to the previously queried messages.
We also recall the following theorem from [5] which we will use later in the paper: [5]] Let A be a QPT such that supp(A) ∩ R = ∅ 3 for some R = ∅. Let MAC be a MAC, and suppose A MAC k (1 n ) outputs a valid pair (m, Mac k (m)) with m ∈ R with non-negligible probability. Then MAC is not BUsecure.

Distinguishability of quantum states
An important difference between quantum and classical bits is the impossibility of creating perfect copies of general unknown quantum states, known as the no-cloning theorem [23]. This is an important limitation imposed by quantum mechanics which is particularly relevant for cryptography. A variation of the same feature states that it is impossible to obtain the exact classical description of a quantum state by having a single copy of it. Therefore, there exists a bound on how well one can derive the classical description of quantum states depending on their dimension and the number of available copies. Hence, distinguishing between unknown quantum states can be achieved only probabilistically. A useful and relevant notion of quantum distance that we exploit in this paper is fidelity. Generally the fidelity of mixed states ρ and σ is defined by the Uhlmann fidelity: Which gives F (|ψ , |φ ) = | ψ| φ | 2 for two pure quantum states |ψ and |φ . Distinguishability and indistinguishability are well known concepts in quantum information and have been stated with different quantum distance measures such as trace distance or fidelity. Here we use the fidelity-based notion of µdistinguishability defined as follows: Definition 3 (µ-distinguishability). Let F (·, ·) denote the fidelity, and 0 ≤ µ ≤ 1 the distinguishability threshold respectively. We say two quantum states ρ and σ are µ-distinguishable if 0 ≤ F (ρ, σ) ≤ 1 − µ.

Verifying quantum states
Due to the impossibility of perfectly distinguishing between all quantum states according to the above definition, checking equality of two completely unknown states is a non-trivial task. This is one major difference between classical bits and qubits. Nevertheless, a probabilistic comparison of unknown quantum states can be achieved through the simple quantum SWAP test algorithm [24]. The SWAP test and its generalisation to multiple copies introduced recently in [25]. We also give an abstract definition for a general quantum test algorithm and define its necessary conditions. Definition 4 (Quantum Testing Algorithm). Let ρ ⊗κ1 and σ ⊗κ2 be κ 1 and κ 2 copies of two quantum states ρ and σ, respectively. A Quantum Testing algorithm T is a quantum algorithm that takes as input the tuple (ρ ⊗κ1 ,σ ⊗κ2 ) and accepts ρ and σ as equal (outputs 1) with the following probability where F (ρ, σ) is the fidelity of the two states and f (κ 1 , κ 2 , F (ρ, σ)) satisfies the following limits: with Err(κ 1 , κ 2 ) characterising the error of the test algorithm.

Quantum Emulation Algorithm
In this section, we describe the Quantum Emulation (QE) algorithm presented in [18] as a quantum process learning tool and used in [19] for the first time as an attack algorithm against a quantum primitive, namely quantum physical unclonable functions. The main purpose of quantum emulation is to mimic the action of an unknown unitary transformation on an unknown input quantum state by having some of the input-output samples of the unitary. An emulator is not trying to completely recreate the transformation or simulate the same dynamics. Instead, it outputs the action of the transformation on a quantum state. This task is done by construction of some controlled-reflection gates that first project the input state in the subspace of the input samples while encoding the information in ancillary systems. Then by using controlled-reflection around the output state the components of the state are retrieved while the unitary is applied to the state.
We are interested in the fidelity of the output state |ψ QE of the algorithm and the intended output U |ψ to estimate the success. Hence we recall two main theorems from [18] and [19] which we use in the proof of Theorem 9.
The first theorem states that the final fidelity is lower-bounded by the square root of the success probability of the projection into the input subspace in the first step. Theorem 2. [18] Let E U be the quantum channel that describes the overall effect of the algorithm presented above. Then for any input state ρ, the Uhlmann fidelity of E U (ρ) and the desired state UρU † satisfies: where ρ QE = |ψ QE ψ QE | is the main output state (tracing out the ancillas) after the first step. E U (ρ) is the output of the whole circuit without the post-selection measurement in the second stage and P succ−stage1 is the success probability of the first step.
Also the success probability of Stage 1 is calculated as follows, Where |χ f is the final overall state of the emulation's algorithm first stage on input state |ψ , and |φ r is the reference state as defined in [19]. We also recall a simplified version of a theorem in [19] as follows: [19] (simplified) Let |χ 1 be the final overall state of the circuit after one block. The final state is of the following form: Having a precise expression for |χ f from Theorem 3, one can calculate P succ−step1 of equation (7) by tracing out the ancillary systems from the density matrix of |χ f χ f |.

Quantum-secure Pseudorandom Function (qPRF)
Quantum-secure Pseudorandom Functions are families of functions that look like truly random functions to QPT adversaries. Formally, qPRFs are defined as follows.

Definition 5.
[Quantum-Secure Pseudorandom Functions(PRF): [26]] Let K, X , Y be the key space, the domain and range respectively, all implicitly depending on the security parameter λ. A keyed family of functions {P RF k : X → Y} k∈K is a quantum-secure pseudorandom function (PRF) if for any polynomial-time quantum oracle algorithm A, P RF k with a random k ← K is indistinguishable from a truly random function f ← Y X in the sense that:

Quantum Pseudorandomness
Pseudorandomness is a central concept is modern cryptography which has also been extended to the quantum regime. We have defined the notion of quantumsecure Pseudorandom Functions in Section 2. Here we define its quantum analogue, namely quantum Pseudorandom Unitaries (PRU), as well as another related notion called Unknown Unitary (UU). -Efficient computation. There is an efficient quantum algorithm Q such that forall k and any state |ψ ∈ S(H), Q(k, |ψ ) = U k |ψ . -Pseudorandomness. U k with a random key k is computationally indistinguishable from a Haar random unitary operator. More precisely, for any efficient quantum algorithm A that makes at most polynomially many queries to the oracle: where µ is the Haar measure on S(H). Note that here we focus on the Pseudorandomness condition of the PRU definition.
We also mention a relevant notion to PRU, called family of Unknown Unitaries (UU) defined in [19], that can also be interpreted as single-shot pseudorandomness.
Definition 7 (Unknown Unitary Transformation). We say a family of unitary transformations U u , over a D-dimensional Hilbert space H D is called Unknown Unitaries, if for all QPT adversaries A the probability of estimating the output of U u on any randomly picked state |ψ ∈ H D is at most negligibly higher than the probability of estimating the output of a Haar random unitary operator on that state:  In the remainder of the paper, we will let λ denote the security parameter. A non-negative function negl(λ) is negligible if, for any constant c, negl(λ) ≤ 1 λ c for all sufficiently large λ.

Generalized Quantum Unforgeability
The game-based security framework is a standard model for formally defining security properties of cryptographic primitives such as encryption algorithms, digital signature schemes or physical unclonable functions [2,4,17,27,28]. Classical cryptographic primitives have also widely been studied in a quantum game-based framework, where parties are Quantum Turing Machines (QTM) [2,16,17,28]. Inspired by these works, we generalise the quantum game-based framework to define quantum unforgeability. Our definitions unify different levels of unforgeability as well capturing quantum and classical primitives. In this section we mostly focus on classical primitives. In Section 5, we show how the framework can naturally cater for quantum primitives as well.

Motivations for Generalised Quantum Unforgeability
The first motivation for a new definition lies within the intuitive meaning of unforgeability definition in classical cryptography and its difference within the quantum world. Existential unforgeability is a security notion that formally describes conditions for a function to be unpredictable against an adversary who gets access to some query information of that function. To capture this unpredictability at the highest level, an adversary should not be able to produce the output of the function even for a message of his choice. Although to avoid trivial attacks, this message should be "new", or not equal to any of the queries in the learning phase. This condition can easily be checked by string equality. On the other hand, when translating to the quantum world and giving the adversary quantum access to the oracle, the "new challenge" can no longer be intuitively defined as before, since the learning phase queries belong to the Hilbert space that can include any desired superposition of classical messages and consequently information from several classical queries. This means an adversary by querying the superposition of all messages can access the output of the function for all of the classical queries in the superposition. Nevertheless, this information needs to be extracted from the quantum state by procedures that are probabilistic in their quantum nature such as measurements. Also, a measurement in the computational basis leads to the collapse of the state into one of the basis states. Hence due to the nature of the measurement and the no-cloning theorem, no more than one classical output can be extracted from such queries by measurements [29]. As mentioned in the preliminaries, the first intuitive quantum definition of unforgeability given by BZ aims to eliminate trivial attacks by counting the adversary's queries and forcing them to output q + 1 "classical" input-output pairs from any q quantum queries. For several reasons, this approach does not properly deal with quantum queries. As also mentioned in [5], many quantum algorithms need to consume or destroy the quantum states to extract some useful information, such as symmetry in the oracle. As a result, the definition seems to be more restrictive than necessary on a quantum adversary and potentially miss some meaningful attacks. We can also demonstrate this through an example. Assume the adversary issues the following queries to a deterministic oracle and receives the corresponding outputs: where m 1 , m 2 are bit-strings of length n and |m out i are outputs of the oracle's unitary evaluation. And let's assume the oracle is the deterministic quantum oracle corresponding to a MAC algorithm. In that case, |m out i = U M AC |m i , y = |m i , M AC(m i ) ⊕ y . Now assume that the adversary is trying to forge message m 2 . One trivial strategy is that the adversary measures the output superposition query and as long as the overlap with m 2 is non-negligible, can forge with non-negligible measurement probability. However, as we show in the proof of Theorem 9, there exists more sophisticated quantum attacks for the adversary where they can forge m 2 , with non-negligible probability even if one excludes the success probability of such trivial attacks. More specifically, for some specific values of σ and γ, there is a quantum emulation attack that produces the output forgery with probability almost 1, and hence will always have a gap with the trivial measurement attacks. We note that such attacks are fairly general and independent of the structure of the underlying deterministic primitive, and hence it is desired for a primitive to resist such attacks. We show later that having schemes that can resists such attacks is possible using randomisation in an effective way, which prevents the adversary to mount emulation or machine learning types of attacks.
Moreover, the BZ definition inherently only captures classical challenges and cannot be used for cases where the challenge can be any generic quantum state on an arbitrary basis. Examples of this case are many quantum primitives that use conjugate bases like quantum money [30,31,32] or general input states like quantum PUFs [19].
In the BU approach, some of the issues of BZ have been resolved as this definition does not count the queries and defines the notion of "new" message in a more natural way using the blind oracle defined in the Preliminary section (Definition 2). This definition however, is also only applicable to classical primitives and morally as we will show later, is equivalent to the case where forgeries have no overlap with the adversary's subspace. This definition leads to interesting results, although we believe that some of the attacks we will present, cannot be captured by BU either.
Following the literature on quantum information, we capture this difference of queries and challenges by a distance measure between the respective quantum states. This allows working with natural properties of quantum states irrespective of any assumption on the primitive that generates their output, as well as smoothly capturing all the possible levels of unforgeability as far as the adversary's capabilities go, and hence closing the existing gap. Moreover, having a definition of unforgeability based on quantum distance measures such as fidelity and trace distance allows us to use the quantum information toolkit more easily and intuitively in proofs. Finally, we believe our general unforgeability provides a quantum counterpart for all the different levels of classical unforgeability presented in Table 1. This will also allow us to show which levels of unforgeability and under what assumptions can be achieved in the quantum world.

Framework and Formal definitions
Let F = (S, E, V) be a classical or quantum primitive with S, E, and V being the setup, evaluation, and verification algorithms respectively. Here we focus on classical primitives, and the generalisation can be found in Section 5. We specify unforgeability as a game between a challenger C (that models the honest parties) and an adversary A (that captures the corrupted parties). The adversary's goal is to closely approximate the output of the evaluation algorithm E on a new challenge such that it passes the verification with high probability. As we work in the quantum regime, where the adversary has quantum oracle access to the primitive, we adopt the technique of quantum oracles defined in [1,33] for formalizing quantum query-response interaction between the adversary and the challenger.
The security game considered here consists of several phases. First, C runs the setup algorithm S to generate the parameters required throughout the game, and instantiates the evaluation oracle O E , the verification oracle O V , and the message space M. The learning phase defines the threat model (we only consider chosen message attacks here). The challenge phase determines the security notion captured by the game. The formal specification of our quantum games is presented in Figure 1. But let us first go informally over each phase of the game.
Setup. In the setup phase, C generates the parameters required in subsequent phases by running the setup algorithm of the primitive F on input λ (the security parameter), and the oracles are being instantiated accordingly.
Learning phase. In the learning phase, the adversary interacts with the evaluation oracle. Here we only focus on chosen-message attack (cma) security, yet the game can be easily generalised to weaker models such as random-message queries. A requires the oracle evaluation on any input state ρ in i . The oracle evaluations are handled by C who issues the requests on ρ in i to O E and forwards to A the respectively received outputs ρ out i , where i = {1, . . . , q = poly(λ)}. We also note that A can have an internal register σ and we allow for creating entanglement between A's register and output queries. Specifically for classical primitives, each ρ in i = |φ in i φ in i | where |φ in i = mi,yi |m i , y i is usually a pure state with m i being the message and y i the ancillary system. If the queries are being generated by A, in most cases it can be assumed that they have the classical information underlying them, while output queries need to be considered as unknown quantum states to the adversary.
Challenge phase. In this phase, the challenge that the adversary has to respond to, is chosen in three different ways, each corresponding to a specific level of unforgeability. Similar to classical notions of unforgeability, the strongest notion is existential unforgeability denoted by qEx in the game, and whereby the adversary picks the message for which it will produce a forgery. On the other hand, in selective unforgeability, denoted qSel, the adversary picks the challenge but needs to commit to it before interacting with the oracle. Hence in Figure 1 the selective challenge phase happens before the learning phase. A further way of weakening the unforgeability notion is when the challenge message is chosen by the challenger C uniformly at random from the set of all the messages. In any case a classical message m ∈ M is selected (for classical primitives) where M is the set of classical messages.
We impose different conditions on the challenge phases which will be formalized later in the guess phase. These conditions prevent the adversary from mounting trivial attacks.
Guess phase. In this phase, the adversary submits their forgery t for challenge m. They win the game if the output pair (m, t) passes the verification algorithm with high probability. In addition, for qSel, the message m should be the same as the message submitted in the challenge phase. Here the condition in the challenge phase that we have mentioned is formally checked. The quantum challenge phase needs to be carefully specified to avoid capturing trivial attacks such as sending one of the previously learnt states as the challenge of the adversary. As a result, we have introduced the notation m ∈ µ ρ in denoting µ-distinguishability from all the input learning phase states. When m is a classical bit-string the same condition should hold for the quantum encoding of m into a computational basis i.e. |m (or |m, 0 ). Note that the case µ = 1 implies the challenge quantum state has no overlap with any of the quantum states queried in the learning phase.
We emphasize that we do not specify how the challenger could check whether the adversary meets the condition or not. Implementing this check is not crucial for our security analysis, where we only need to be able to characterise the instances that might present a security violation. The key point to note is that this can effectively be checked given a run against a given adversary. Indeed, then ρ in i and ρ out i can be characterised allowing proofs of security and exhibition of attacks.
Regarding the verification oracle, for classical primitives the forgery pair (m, t) is classical and the verification oracle O V f runs the classical verification algorithm V = Ver(k, m, t, r). Here r is the randomness if the primitive is randomised.
We omit the parameter q when we consider arbitrarily polynomially many queries to the evaluation oracle issued by A. We can now formally define Existential, Selective and Universal Unforgeability of primitives as instances of our game as follows.
Definition 8 (µ-qGEU). A cryptographic primitive F provides µ-quantum existential unforgeability if the probability of any QPT adversary A of winning the game G F qEx,µ (λ, A) is at most negligible in the security parameter, We also define a stronger security notion for existential unforgeability which considers any overlap µ.
Definition 10 (µ-qGSU). A cryptographic primitive F provides µ-quantum selective unforgeability if for any q the advantage of any QPT adversary A of winning the game G F q,qSel,µ (λ, A) over P ov (q) is at most negligible in the security parameter, The game G F q,c,µ (λ, A) a Setup phase: First learning phase: For the classical message m ∈ {0, 1} n , the condition should hold for |m , i.e. the quantum encoding of m in computational basis.  ) where λ is the security parameter, q the number of queries issued to the evaluation oracle in the learning phase, µ the overlap allowed between the challenge and previously queries messages, and c the level of unforgeability.
We call P ov (q, µ) the "overlap probability" describing the probability for trivial attacks via the overlap allowed by the parameter µ. 4 The need for allowing an adversary to win with probability P ov (q, µ) is similar to the classical definitions where the adversary is required to boost the success probability from some trivial value such as random guess. Here, by allowing the adversary to create an overlap between the learning phase space and challenge, some unavoidable attacks exist which are independent of the actual primitive at hand, and as such needs to be extracted to characterise the gap between trivial and effective adversaries and hence precisely define a proper distancebased definition.
Definition 11 (P ov for classical primitives). For all q for all µ For a classical primitive where the evaluation oracle is a standard oracle O E f , for any overlap µ the overlap probability for q-query games is equal to P ov (q, µ) = 1 − µ q .
A similar notion for quantum primitive is defined in Section 5. When selective unforgeability holds for any overlap µ we say that the primitive is quantum selective unforgeable.
Definition 13 (qGUU). A cryptographic primitive F is quantum universally unforgeable if the probability of any QPT adversary A of winning the game Note that the µ-distinguishability condition is not necessary for Universal Unforgeability, as the challenge is chosen by the challenger, independently of the adversary's queries and the probability is taken over all the choices of the challenge state hence it is no longer meaningful to count for possible overlaps as trivial attacks.

Hierarchy and Relationship to other definitions
To demonstrate the generality of our framework and the full context that our results will apply to, we investigate how our definitions formally relate to the previously proposed ones. In particular, we show that 1-qGEU is equivalent to BU, and hence implies the BZ definition (we draw the latter from [17]). We further formally establish the hierarchy between the different notions of Generalised Unforgeability. In Figure 2, we map out the results presented in this section.
Proof. We show that 1-qGEU implies BU and vice versa. First, we show that if a scheme is not BU unforgeable against a QPT adversary then it is not 1-qGEU unforgeable either. Let A be a QPT adversary who forges a scheme F = (S, E, V) with message set M = {0, 1} n in the BU definition. Following the formal definition of BU provided in Definition 2, A selects an for which the blinded region B is created by selecting each m ∈ M at random with an -related probability. Then there exists a non-empty set B for which A interacts with the blinded oracle associated with it and outputs a pair (m * , t * ) where t * = f (m * ) (where f is the classical function of the evaluation E, for instance a MAC (.)) such that V = V er k (m * , t * ) = acc, and also the m * ∈ B with non-negligible probability in λ = poly(n). By the definition of the blinding oracle, A receives a |⊥ for any of the computational basis that are in the blinded region. As a result, we can write A's input and output queries as follows: Now assuming the quantum encoding of the challenge m * ∈ B to be |m * , 0 and the tag/output to be |m * , t * = |m * , f (m * ) , we can see that m * , t * | φ out i = 0 since m * will have no overlap with the first part of the superposition, and also to the second part due to the blinding. Now, we show that there exists a unitary non-blinding oracle that generates equivalent queries for this scenario. Let U E be the unitary evaluation oracle such that |m * , t * = U E |m * , 0 , and similarly for all the queries. Due to the unitarity, we have that m * , t * | φ out Thus there will also exist an adversary A with equivalent queries except that the target forgery will be always orthogonal to the selected challenge. Hence for this adversary, the condition of 1-qGEU is satisfied. Then by calling A, the adversary A can generate an output state |m * , t * that passes the test algorithm with also non-negligible probability. Hence we have shown that 1-qGEU implies BU.
To prove the other way of implication we need to show whenever there is an attack on 1-qGEU, then there will also be an attack on BU definition and hence the scheme is also BU insecure. This time we consider A to be a QPT adversary who wins 1-qGEU by selecting a challenge state |m * , y where the m * is the classical challenge and y is the ancillary register, and querying a set of states Then by definition, A can output a |m * , t * = U E |m * , y that passes the test algorithm with non-negligible probability. Now an adversary A calls A to win the BU with non-negligible probability.
At this stage we recall the Theorem 1 and we show that an A satisfies the conditions of this theorem. Let us write the learning phase queries in the computational basis as follows: where {|b j } d j=1 is the set of computational bases spanning the effective learning phase subspace. Now we create a non-empty set R by selecting each x ∈ M as follows Where |b j X denotes the input register of the full basis. Note that R will always be non-empty as the basis set will only cover a polynomial-size subspace of the whole Hilbert space of messages. Moreover, since A includes A and m * has no overlap with any of the input queries, it will also have no overlap with the input register of the output queries. As a result, R has at least one element. Hence the set of all input elements that have non-zero overlap with the queries and the elements included in R have no intersection. This shows that supp(A) ∩ R = ∅ if the support is defined for the oracle O f for a fixed randomly picked classical function f (or key k) during the game. Thus we also have supp(A ) ∩ R = ∅ and m * ∈ R. Nevertheless, in [17] has been mentioned that the support is taken to be the union of the support of all the queries over the choice of the function. In this case we can also redefine our set, and the queries of A such that it satisfies the condition of the theorem respectively. We take the set R to only include one element which is the forgery message m * . As in the 1-qGEU the function (or the key for the keyed functions) is selected at random in the setup phase, the success probability of A is inherently taken over the choice of the function. Then A queries all the queries of A for any randomly selected f during the experiment. For any other functions, excludes any queries for which the support will include m * . Now we can see that A can output a valid pair (m * , t * ) by measuring |m * , t * in the computational basis with probability 1 while supp(A ) ∩ R = ∅ and m * ∈ R . Hence A breaks the BU unforgeability and we have shown that BU implies 1-qGEU. This mutual implication shows that these definitions are equivalent and the proof is complete.
From the above theorem and the equivalence of BU and BZ against classical adversaries we derive the following corollary.
Next, we establish the relation between different instances of our game-based definition. First, we emphasise that as expected for both existential and selective unforgeability, the definitions become stronger when decreasing the µ parameter from 1 and hence µ-qGEU implies 1-qGEU.
Proof. The proof is straightforward for qGEU. Let A win against µ 2 -qGEU, Let A be the adversary who wants to attack µ 1 -qGEU. A queries the same learning phase queries as A and then calls A. Since µ 1 ≤ µ 2 any two states that are µ 2 -distinguishable are also µ 1 -distinguishable, then the challenge of A will necessarily satisfy the condition for µ 1 -qGEU. Then A can also win the game with non-negligible probability. For µ-qGSU the distinguishability argument is similar, although there is also the P ov probability that is function of µ. Thus we need to show the following: Which is also equivalent to showing the following statement: The LHS of the inequality is always positive due to the above distinguishability argument, and the P ov is always a non-increasing function of µ for both types of primitives. Take the P ov for the classical primitives for instance, which is equal to 1 − µ q . Therefore, the RHS of the inequality will be equal to µ q 1 − µ q 2 which is always a non-positive value as µ 1 ≤ µ 2 . Then the above inequality holds and the theorem has been proved.
Furthermore, it is easy to observe that for any given µ, µ-qGEU implies µ-qGSU. This is due to the fact that if the adversary wins the game by committing to their favourite message before the learning phase, they will necessarily win when picking the message after the learning phase.
Universal unforgeability is also intuitively weaker than existential unforgeability similarly to their classical counterpart. This holds, despite the winning condition for these two instances being very different. In universal unforgeability, the adversary wins only if they win the game on average over all the different randomly picked messages. Since in our case, we are only interested in QPT adversaries, and as the universal definition is not parameterised by µ, it is not obvious that qGU U is weaker than µ-qGSU. In the following theorem, we formally establish the implication. We prove the theorem for 1-qGSU which in turn implies µ-qGSU for any µ. Here we present the key ideas of the proof. We show if there exists an adversary A that wins the qGUU game then 1-qGEU (1-qGSU) also breaks and the implication to µ-qGEU (µ-qGSU) is straightforward. First, we show that the distinguishability condition for µ = 1 can be satisfied. Thus we write the winning probability of A as the combination of probabilities of winning with respect to the selected message being orthogonal to the learning phase or not: where M is the set of all the challenges with no overlap with the learning-phase states. By calculating this probability we show that P r x∈M [1 ← A(x)] is also nonnegligible. In the second part of the proof we show that as long as the previous average probability holds, we can always construct an efficient adversary A that uses A to win the selective unforgeability game. We prove this by partitioning the space of M into equal polynomial-size subspaces and show that if the average probability over M is non-negligible, then A can always win the 1-qGEU game by randomly picking one of the subsets to pick the message from, as there will exist at least one message that allows A to win the game with non-negligible probability. As a result, A wins the game with non-negligible probability.

Generalised Existentially Unforgeable Schemes
In this section, we turn our attention to 1-qGEU. First, we show a general and intuitive, yet important no-go result for µ-qGEU that is, no classical primitive (deterministic nor randomized) can satisfy this level of unforgeability for any µ = 1. This result states that 1-qGEU, which is equivalent to BU as shown in the previous section, is the strongest notion of existential unforgeability that any classical primitive can achieve.
Theorem 7 (No classical primitive F is µ-qGEU secure). For any classical primitive F and for any µ such that µ ≤ 1− 1 2 n , there exists a QPT adversary Proof. There exists a simple superposition attack that breaks µ-qGEU. Let A issue only one query which is the uniform superposition of all the inputs, which leads to an output of the form 1 √ 2 n m |r O |m, f (m; r) . Then by measuring the first part of the register in the computational basis, the state will collapse to one of the basis and the adversary is able to produce a valid message-tag pair for a classical message with a negligible overlap with the learning phase. Hence A can always win the game for any any µ ≤ 1 − 1 2 n . Nevertheless, it is still possible to have schemes that are 1-qGEU secure through the following positive result: Proof. This is a straightforward result via equivalence of 1-qGEU to BU and Corollary 4 in [5], where it is shown that qP RF s are BU secure.

Generalised Selectively Unforgeable Schemes
In this section, we establish results for µ-qGSU which restricts the adversary in two ways. First, by requiring the adversary to commit to the challenge before the learning phase, we prevent the adversary to pick any post-measurement state as their forgery challenge. Second, by subtracting the probability of any potential trivial attack, especially for classical primitives, from the winning probability of the game, we make the probability bounds tighter for the adversary. We show that defining unforgeability in this way leads to non-trivial results and establish a separation between randomised and non-randomised constructions.
Non-randomised Schemes We show a general impossibility result using the quantum emulation attack introduced in [19]. Here we only show this no-go result for classical non-randomised primitives to avoid repetitions, but the same result holds for quantum construction too.
Proof (sketch). We show the proof for classical primitives but the same attack and results also holds for quantum primitives. We show that there exists a QPT adversary A who can win the game with non-negligible probability for any µ except when it is negligibly close to 0 or 1. A more detailed version of the proof is given in the Supplementary Materials B.2. The attack we present is an emulation attack based on the universal quantum emulator [18]. First A picks any two messages m, m ∈ M and sets m as the challenge. Then A queries the states |φ 1 = |m , 0 and |φ r = 1 − γ 2 |m , 0 + γ |m, 0 from O E f , where γ is a real value such that 0 ≤ γ ≤ √ 1 − µ and such that the distinguishability condition of the µ-qGSU game is satisfied. After the learning phase, A's output state is σ out = |φ out 1 ⊗ |φ out r where |φ out 1 = U E |φ 1 and |φ out r = U E |φ r . Followed by the fidelity analysis of the attack algorithm given in Supplementary Materials B.2, we show that the success probability of A in producing the output of m i.e. f (m) is P r[1 ← G F 2,qSel,µ (λ, A)] = γ 2 (1 + 4(1 − γ 2 ) 2 ). We also note that for γ = 1 √ 2 , there exists an emulation with success probability 1. Also, we let A to set γ to the maximum value allowed by the overlap condition i.e. γ = γ max = √ 1 − µ. Finally, we need to subtract the P ov from this probability for the adversary to be effective. For this attack we have q = 2 and the P ov (2, µ) = 1−µ 2 according to Definition 11. Thus we have which concludes the proof.
Despite the above no-go result, qPRFs still provide 1-qGSU security, as mentioned in Theorem 8. However, the above theorem shows a fundamental vulnerability of any non-randomised classical primitive against forgeries, since the only way to ensure the security of primitives against such effective attacks is to guarantee that the adversary's forgery message is orthogonal to their learning subspace by relying on the device implementation which is in contradiction with the whole motivation of obtaining security against more powerful quantum adversaries, to begin with. More precisely, our Theorem 9 shows that non-randomised MAC schemes such as HMAC and NMAC do not satisfy existential nor selective unforgeability except for µ = 1 and hence are always vulnerable against more powerful quantum adversaries implementing superposition attacks. At this point, we go back to the same example that we have presented in Section 3.1, which illustrates more clearly why the current definition and the quantum emulation class of attacks shows a forgery that clearly needs to be prevented. We present a slightly different attack to the one exhibited in the proof of Theorem 9 but that makes even more obvious the need for our generalised definition. where the query states have been chosen as follows: Where due to normalisation |δ| 2 + 2|γ| 2 = 1, although we pick the δ = 1 − 2γ 2 and γ to be real values for simplicity, thus γ 2 ≤ 1 2 . Also note that A has two identical copies of |φ out r . The attack consists of running two separate emulations for |m 2 , 0 and |m 3 , 0 .
Let |φ r be the reference state for the emulation, and the target state to be |ψ = |m 2 , 0 or |ψ = |m 3 , 0 . Note that as |φ 1 = |m 1 , 0 is orthogonal to both states and the reference state is symmetric with respect to them, the emulation's fidelity will be the same for both these states. Relying on Theorem 3, the output state of the QE algorithm with only one block will be: Note that | φ 1 | ψ | = 0 and | ψ| φ r | 2 = γ 2 and | φ 1 | φ r | 2 = 1 − 2γ 2 . Then according to Theorem 2, the fidelity of the emulation for both states is: Now we need to compare this probability with the P ov probability which is P ov (3, µ) = 1 − µ 3 since the size of the learning phase includes 3 queries. We write the effective success probability of the adversary as: Finally, we need to do a functional analysis of the above probability to see in which cases it becomes non-negligible. First, we note that the success probability of the emulation attack is not greater than the trivial success probability for all the values of µ which shows that if we allow for too much overlap, the trivial attack already has a very high probability which is higher than the emulation's fidelity in this case. Next, since the highest allowed overlap is achieved when 1 − µ = γ 2 , we substitute the variable µ with 1 − γ 2 to find the degrees of µ for which an effective adversary exists. Hence we rewrite the winning probability of the equation 25 as follows: Noting that the valid range for γ is 0 ≤ γ ≤ √ 2 2 , we plot the above function as it is shown in Figure 3 and we can see that there is exist a valid range for µ such that the above forgery attack happens with non-negligible probability.
But more importantly, now having access to two copies of the reference state, the adversary can actually run the emulation attack twice, and produce the outputs of both m 2 and m 3 at the same time, with non-negligible probability. Thus for these values of µ, we have presented an adversary who can produce effective forgery for three classical messages m 1 , m 2 and m 3 (Note that the first learning phase query is |m 1 , 0 which is basically a classical query and as a result, A will always have the output for m 1 ) from a classical query, and two copies of the same quantum state which shows an intuitive forgery, especially that the presented attack is independent of the size of the messages and the dimensionality of the Hilbert space of the oracle. This sort of attacks cannot be captured in the definitions of unforgeability that count the queries, such as BZ. Nevertheless, our approach in defining the notion of unforgeability is capable of showing such vulnerabilities against strong quantum adversaries.
Randomised Schemes: In this section, we explore how to defend against general superposition adversaries, i.e. that are allowed to exploit overlaps between previously queried messages and the target message. We show that selective unforgeability can be achieved in such a setting, by effective randomization. Concretely, we present a randomized construction for classical primitives that satisfies qGSU (µ-qGSU for any µ). The key ingredient that allows this construction to be secure is that the randomization has been used in an effective way such that the adversary is prevented from creating a known subspace for a specific unitary, even though they can query the challenge message in superposition. First, we formalise the desired characteristic for the family of the classical functions used in our construction.  picked uniformly at random from F k , the probability of A finding an x ∈ X such that F (k, x) = F (k , x), is negligible in the security parameter, i.e. the following condition should hold: Now we show that a PRF family satisfies the above condition.

Lemma 1. A PRF is an inter-function independent family.
Proof. We want to show that any two randomly selected functions from a PRF family, satisfy the required pairwise-independency property of Definition 14. Let F k : K × X → Y be a PRF family of functions where |X | = 2 n and |Y| = 2 m . We want to show that there is no efficient adversary that can find an x such that F (k, x) = F (k , x) for any two different, randomly picked keys k, k . We prove by contradiction. We assume that F k is a PRF but there exist an efficient adversary A that can find at least one x ∈ X such that for any two randomly picked functions from F k we have: Now we construct a new family of functions from F k which is a PRF. Let F k,k : K 2 × X → Y be constructed as follows: It is a well-known example in the literature that if F k is a PRF, then F k,k is also a PRF. Now we show that if the equation (28) holds, then there also exist an adversary who can distinguish F ((k, k ), x) form truly random function. Let A query the same x that has been found by A. If A queries F ((k, k ), x), since F (k, x ) = F (k , x ) with non-negligible probability, then the queries to F ((k, k ), x) on x should return 0 m . On the other hand the queries to the truly random function will return random bit-strings. As a results, A can distinguish F ((k, k ), x) from a truly random function which is a contradiction and hence we have proved that PRF satisfies the Definition 14.
We can now give our construction based on PRFs or more generally, based on any family of classical functions satisfying the Definition 14.
Construction 1. Let F : K × X → Y be a PRF (or any other family satisfying Definition 14). Let R = K = {0, 1} l be the randomness space. And let λ be the security parameter and l be polynomial in λ. The construction is defined by the following key generation algorithm, keyed evaluation algorithm, and keyed verification algorithm: -Key generation: The secret key is picked uniformly at random from K: k $ ← − K -Evaluation: The evaluation under key k on input m picks randomness r and applies F (k ⊕ r, ·) to m. Note that when responding to a quantum query, the same randomness is used for all the states of the superposition: • On input m ∈ X : The verification under key k of a pair (m, (t, r)), runs the evaluation algorithm on m under k with randomness r, and checks equality with t.
Proof. We assume there exists a QPT adversary A who plays the µ-qGSU game where the evaluation is according to Construction 1, and wins with non-negligible probability in the security parameter i.e. A wins the game by producing a valid tag t * for their selected message m * and randomness r * with the following probability: Where the verification algorithm checks if F (k ⊕ r * , m * ) = t * . We introduce the following games: -Game 0. This game is the µ-qGSU for Construction 1, where F (k ⊕ r, .) is picked from F . -Game 1. This game is similar to Game 1, except that A needs to produce forgery for a r * which is one of the previously received random values of {r i } q i=1 in the learning phase.
First, it is straightforward that the probability of the adversary in winning µ-qGSU in Game 0, is at most negligibly higher than winning Game 1. Since r i in both cases have been picked independently and uniformly at random and the probability of producing a forgery for a specific function with no query is negligible. Thus Game 0 and Game 1 are indistinguishable. Now we recall the quantum random oracle for this construction. Let RO E c be the random oracle for both games: Note that in each query a new function has been picked from F , but it is the same for all the messages in the superposition for that query. Now we use the inter-function (pairwise) independent property of the family F . The construction requires the F to be a PRF family which is inter-function independent according to Definition 14, for two randomly selected keys. Now we need to also show that F (k ⊕ r, .) is a PRF as well, with a key k and any randomly selected randomness r, and as a result we can use the inter-function independent property. This is clearly the case as the key k and any randomness r have been picked independently at random and if there exist a non-negligible advantage for the adversary to distinguish a F (k ⊕ r, .) from a truly random function for a value of r, there also exist an equivalent non-negligible advantage to distinguish a F (k , .) where k = k ⊕ r is a key selected uniformly at random. This is still the case even if the value r becomes public after the experiment. This is in contrast with the assumption that the family is PRF, hence we conclude that F (k ⊕ r, .) is a PRF. Now we can rely on the Lemma 1 that F (k ⊕ r, .) also satisfies the inter-function independent property and the following holds for each of the two functions drawn in any of the two queries: As a result, we show that the adversary can at most span a one-dimensional subspace of each U k⊕r . To show this we will calculate the probability of A in spanning at least a 2-dimensional common subspace from two different queries. This means that A needs to find at least two bases mapping to the same 2dimensional subspace in the output Hilbert space. Moreover, we exclude that part of A's register that contains the classical value of the randomness in order to only capture the Hilbert space of each U k⊕r . Thus let the input bases be denoted by |b = |m, z where z is a subset of y excluding the space for the randomness, for a specific m. Let |e i = U k⊕ri |b = |z ⊕ F (k ⊕ r i , m) and |e j = U k⊕ri |b = |z ⊕ F (k ⊕ r j , m) be the output states from two different queries. For these output bases to have overlap, the two functions F (k ⊕ r i , .) and F (k ⊕ r j , .) need to return the same classical output with high probability. Although from equation (32), we have that the probability of finding such inputs that leads to a common basis is negligible: This means that finding an even 2-dimensional common subspace between the different unitaries of the set is hard for A. Also since unitaries are distance preserving operators, this property holds for any sets of orthonormal basis, not necessarily the computational basis. Thus by selecting a uniformly random function for each query, we have shown that no more than a one-dimensional subspace can be spanned for each specific unitary. Now we calculate the upper-bound of A's probability from a single query to a fixed unitary U k⊕r * which we denote by U * for simplicity. We recall that this query should be µ-distinguishable with the quantum encoding of m * . Without loss of generality, let us write A's selected query for r * as follows: where |Ω is a normalised state that includes a superposition of a set of messages m = m * and as a result m * , z| Ω = 0 and A sets the second part of the register to 0, such that the output randomness is a separable state and it can be excluded in the rest of the proof. Due to the fact that U * is unitary, we know that m * , z ⊕ F (k ⊕ r * , m * )| U * |Ω = 0 and hence the probability of outputting F (k ⊕ r * , m * )||r * from |φ out r * is at most the probability of measuring it in the computation basis which is |α| 2 . This probability is maximum when |α| = |α max | which is when A uses the maximum allowed overlap of size √ 1 − µ. Hence we have: But on the other hand we have P ov (1, µ) = 1 − µ, which is the lower bound for P ov (q, µ), and also since there is only one query to each function selected by each r, and equation (64) states that this probability is negligibly higher that 1 − µ.
Thus we have reached a contradiction that concludes our proof.
Theorem 10 shows that in addition to PRF, qPRFs can also be used in the construction to achieve selective unforgeability. Nevertheless, we have also provided a separate security proof for the qPRF family that does not need the Definition 14. This proof can be found in Supplementary Materials B.3.

Generalised Universally Unforgeable Schemes
In this section, we further weaken the notion of unforgeability and provide a generally positive result for universal unforgeability. We recall that here the adversary receives a challenge picked by the challenger uniformly at random from the full message space.
Despite the fact that universal unforgeability is a weaker notion, it is a practical definition and sufficient for many protocols, especially for the case of quantum primitives and quantum protocols [19,20]. Here as we mostly focus on classical primitives, we mention this definition for the sake of completeness and we specify with the following theorem that qPRF is enough to achieve qGUU, due to the hierarchy of our definition.
Proof. This is a direct implication of Theorem 8 where we have proved that qPRFs are 1-qGSU secure and Theorem 6 showing that 1-qGSU implies qGUU.
In the Supplementary Materials C we also give a general no-go result for the qGUU security of quantum primitive against universal but adaptive attack model, where the adversary can issue learning phase queries after receiving the random challenge that is selected by the challenger. We show that in this case there also exists an interesting entanglement-based attack which leads to breaking qGUU against this adversarial model.

Generalization of the definition to quantum primitives
In this section, we show how our framework can also capture the natural notion of unforgeability for quantum primitives. We refer to quantum primitives as the primitive where the input message space and the output space are both Hilbert spaces, and both the queries and the messages can be any arbitrary quantum state of the input Hilbert space. In addition, the quantum oracle describing the evaluation of quantum primitives are represented more generally as unitary matrices. We describe the generalisation of the primitive to the quantum primitives as follows.
Let F = (S, E, V) be a quantum primitive now, with S, E, and V being the setup, evaluation, and verification algorithms respectively. The game defined in the Figure 1, captures the notion of unforgeability for quantum primitives same as the classical ones, with the following modifications: Setup: In the setup phase the oracles are being instantiated according to the parameters generated by C, Here the evaluation oracle is defined according to Equations 2 and 3 for deterministic and randomised primitives respectively and the verification oracle implements a quantum test algorithm as defined in the Definition 4.
Learning phase: The learning phase is similar to the classical primitives, where {ρ in i } q i=1 represent input chosen message queries and {ρ out i } q i=1 is the respective outputs after the interaction with the oracle sent to A by the challenger.
Challenge phase: Here the main difference is that M = H D is a Hilbert space and m = ρ m ∈ H D is a quantum challenge in the D-dimensional Hilbert space. In the qUni challenge phase where the message is chosen by the challenger C uniformly at random from the set of all the messages, for quantum primitives it should be selected uniformly according to the Haar measure from H D . We also need to mention that for qSel challenge phases, A is required to submit the classical description of the quantum state ρ m . This is important for the verification phase, as it allows the challenger to prepare the required number of copies of the correct output for the verification.
Guess phase: In this phase, the adversary submits their forgery t for challenge m, which are now both quantum states. They win the game if t passes the verification algorithm with high probability. The distinguishability condition on the message with the learning phase queries needs to be satisfied exactly as was the case for classical primitives. Here it can be seen that this is the most natural way of characterising the forgery for quantum primitives since the difference between quantum states is usually measured by their indistinguishably and their quantum distance measures.
The main difference in this phase is the difference between the classical and quantum verification procedure. The verification is fairly simpler for classical primitives since the equality can be easily checked while as for quantum primitives both message and forgery are quantum states and the verification oracle O V U should call a quantum test algorithm T that checks the equality of quantum states as in the Definition 4. Note that the challenger can prepare copies of correct outputs locally.
With the above considerations, one can use the same security game and the definitions of existential, selective and universal unforgeability as defined in Section 3.2. Here we only need to discuss the notion of overlap probability for quantum primitives separately due to the generality of the quantum oracles.
Overlap probability in µ-qGSU Definition for quantum primitives For quantum primitives, it is clear that the adversary's success probability in finding the output by measurement strategy is almost zero and hence defining the P ov as defined by Definition 11 leads to zero overlap probability. However, in this case, as well, there is another scenario that may lead to unavoidable attacks, which is due to the error produced by the quantum test algorithm in distinguishing the states with certain overlap. An example of this is the SWAP test which has a onesided error of 1 2 even for perfectly distinguishable states. This is a fundamental difference between the quantum world and classical primitives where equality can be checked deterministically. To have a general characterisation of P ov for the quantum primitives, this probability needs to be defined concerning the test algorithm as follows.
Definition 15 (P ov for quantum primitives). Let ρ max be the input learning phase query with the maximum overlap with the challenge state |ψ , allowed by the µ-distinguishability condition. Let the O E U be the unitary oracle for the quantum primitive applying U E to the quantum inputs and let O V implement a quantum test algorithm T . Then ρ out max = U E ρ max U E † is the output of the query from the oracle and ρ out = |ψ out ψ out | = U E |ψ ψ| U E † is the correct output of the challenge |ψ . We define the P ov as the error probability of the test algorithm T on distinguishing ρ out max and ρ out as follows: This definition also implies an intuitive and practical approach to determine the desired µ < 1 for quantum primitives, as it states that for any specific quantum primitive or the protocols based on that primitive, the µ should not allow for above overlap attacks with a probability larger than the required security threshold. Nevertheless, if one assumes a reasonably good quantum test algorithm, this probability for quantum primitives is usually less than the classical ones due to quantum state distinguishability and lack of adversary's knowledge over the transformation of the output bases.

Results for Generalised Quantum Unforgeability of Quantum Primitives
In this section, we present unforgeable quantum primitives for each level of our generalised unforgeability framework. Most of our positive results are based on PRU assumption, which is the quantum equivalent of qPRFs.

Existential and Selective unforgeable deterministic quantum primitives
First we show that PRU implies 1-qGEU and 1-qGSUand hence deterministic quantum primitives under this assumption can satisfy this level of unforgeability.
Proof. We prove by contradiction. Let A be an adversary who wins the 1-qGSU game with non-negligible probability (Note that here P ov = 0). A selects a message m before (or after) the learning phase and then outputs the respective t such that it passes the verification test with non-negligible probability. Also by definition of 1-qGSU, m ∈ µ ρ in for µ = 1 and hence the message ρ m is completely orthogonal to all ρ in i . Now we construct an adversary A who is playing the PRU game. Let A first query all the learning phase states of A and then also issue one more query which is ρ m . Then A calls A and receives the input-output pair of (m, t) such that ρ t is non-negligibly close to the actual output, i.e.
Now A can use this last query as a distinguisher between PRU and a unitary picked from Haar measure since A can estimate the output with non-negligible fidelity if the U k had been picked from the family. Let A runs a quantum equality test as described in Definition 4 on the U k |ψ obtained in the learning phase and ρ t . Also note that if U is picked from the Haar measure family, the probability of producing the output is negligible by definition. Thus whenever the test shows equality, A can conclude that the unitary has been picked from PRU. Thus for A we have: Which is a contradiction and the theorem has been proved.

Selective unforgeable randomised quantum primitives
Similar to the classical constructions, for quantum primitives too, we can use randomisation to effectively secure them. The main idea is to select a new unitary transformation for each query using a classical randomness register. In this case, we need to clarify how such randomised quantum oracles can be implemented in a way that the overall transformation remains a specific unitary. By recalling the abstract representation of the randomised quantum oracle that we have given in the preliminary, the input state |ψ m = i α i |m i (where {|m i } is a set of orthonormal bases) is mapped to a state U (r) |ψ m = i β i (r) |m i where U (r) depends on the randomness and different for each query i.e. the oracle uses its internal register |r O to activate different U (r) unitaries. However, for many constructions this randomness value r or a function of it like g(r), will be necessary for verification and hence need to also be outputted. On the other hand, the register |r O is the internal register of the oracle re-initiated for each query and some problems may arise if the adversary gets access to this register (see Preliminary), thus in order to be able to output this value we expand the query space and we allow the input queries to be |0 ⊗ |ψ m . We formulate the oracle as follows: Note that for the purpose of our construction, in what follows, we assume that the ancillary state is initiated as a separable state |0 for simplicity, although if the adversary's ancillary register has not been initiated to zero, the randomness can be XORed to that value. The above oracle can be realised in different ways but we give an explicit example in the circuit model, shown in Figure 4. The input to the unitary evaluation of the oracle consists of two parts; one part includes the query and the second part is the internal randomness register which is initiated to a new value or equivalently to a new basis, for each query. This part in general acts as control qubits for the gates in the other part of the register that leads to apply a new overall unitary on the main query state. We note that the randomness register itself will remain untouched throughout the evaluation and finally its value is recorded in the |0 part of the input query. We note that this last recording part is not in contrast with the no-cloning theorem as the |r O is always in the computational basis. On each input query |0 |ψ m , a new randomness is initialised and the random unitary U (r) acts on |ψ m . The random unitary U (r) consists of single and 2-qubit unitary gates selected at random in the setup phase, from a gate set required to construct any unitary U (r) in the family U specified by the construction. These single and two-qubit gates are controlled by the randomness values |r = |r 1 , r 2 , r 3 . In the last step, the classical value of randomness is recorded in the ancillary qubits of the query to be returned for verification. Now it can be seen that in such randomised oracles, the security of the quantum primitive, lies on the assumptions on the family of U (r)s generated for each r. For instance, it is intuitive that a primitive where U (r) are Haar random unitaries can be secure since the overall adversary's state after issuing polynomial queries to the oracle is almost indistinguishable from a totally mixed state. Although this assumption might be too strong. Hence we give a construction based on PRU which is also the quantum analogue of qPRF that we have used in our previous classical construction. Proof. We prove by contradiction. Let A be a QPT adversary who plays the µ-qGSU game where the evaluation oracle is as shown in the equation( 40), and wins with non-negligible probability in the security parameter i.e. A, wins the game by producing a valid tag ρ t for their selected message ρ m and randomness r * with the following probability, after interacting with the oracle in the learning phase: Where the P ov = P r[1 ← T (ρ out max ) ⊗κ1 , (U E ρ m U E † ) ⊗κ2 ] according to Definition 15, and ρ out max is query with maximum allowed overlap from µ-distinguishability condition. Since the construction implies that P ov = negl(λ), this means: Consequently, A can produce an output ρ t with non-negligible fidelity with the actual output U(r * )ρ m U(r * ) † , for a U r * ∈ U P RU . Now we consider two cases.
Either r * is one of the randomnesses that A has received during the learning phase, which means A can closely approximate the output of a random unitary U (r * ) from a single query, or r * is a new randomness value, for a new random unitary U (r * ) where A has no query on it. We will show that each case leads to a contradiction. First, we show that A's output state after the learning phase, i.e. σ out cannot include more than a one-dimensional subspace of each of the U (r) unitaries. To cover a subspace with a dimension of at least two, A needs to find a common output basis from two different queries. On the other hand, we note that as shown in [34], any PRUs are generators of Pseudorandom Quantum States (PRS) that are a family of quantum states computationally indistinguishable from Haar measure. Hence the joint output states σ out is also indistinguishable from Haar random states for A who is a QPT adversary. Now if A can find a common output subspace, it means that there are at least two states, corresponding to the bases of the 2-dimensional subspace, that are indistinguishable (or 0-distinguishable according to Definition 3), and hence A can use those queries to distinguish the distribution of states σ out and a Haar random distribution which contradicts the fact that the oracle will generate a PRS set of states after q queries. Now we show that each case will lead to a contradiction. We start with the second case where if A produces an indistinguishable (concerning T ) output for a random unitary with no query, then A can perform the learning phase locally without any interaction with the oracle and hence produce the output of any unitary picked from a family indistinguishable to Haar measure, which is a clear contradiction. For the first case, relying on the previous argument, we rewrite the learning phase states of the A after q queries, as follows: where |φ r * is the query associated to U r * for which A produces a forgery and σ q−1 in and σ q−1 out are the input and output states of the remaining q − 1 query respectively. We note that σ q−1 out consists of q − 1 quantum states with a distribution δ over a D -dimensional Hilbert space s.t. δ is Haar-indistinguishable. Furthermore, the ancillary register where the r is encoded consists of q independent random values. Now let us construct an adversary A who is a PRU distinguisher. Let A interact with a unitary U either selected from U P RU or from Haar measure, and query a state |φ r * as described above, and returns U |φ r * together with an ancillary register |r where r picked uniformly at random. Then A also locally creates q − 1 Haar-random states and returns to A as the σ q−1 out . Then A also queries ρ m from the oracle. Now A uses the same test algorithm T to check the output of A i.e. ρ t with the the oracle's output for the last query which is U ρ m U † . From equation (42), we know that this probability is non-negligible, while as for a Haar random unitary the probability is negligible, thus can conclude that which is a contradiction and the theorem has been proved.

Universal unforgeable quantum primitives
It has been previously shown in [19] that certain quantum primitives, like quantum PUFs where their evaluation function satisfies UU condition, can be secure wrt. this level of unforgeability 5 . Here we generalise this result for general quantum primitives to the PRU assumption. Now we establish our general positive result for quantum primitives.
Theorem 14. Deterministic quantum PRU and UU schemes are qGUU secure.
Proof. We prove this implication independent of the results of [19], from our previously established results. From Theorem 8 we know that PRU primitives are 1-qGSU secure. Also from Theorem 6 we have shown that qGUU is weaker than 1-qGSU. Thus any PRU primitive is qGUU secure.

Conclusion and future directions
We have presented new fine-grained definitions of quantum unforgeability that unify different levels of unforgeability, different types of primitives, and better capture the properties of quantum adversaries. In particular, the parameterised definitions for selective and existential unforgeability lead to some non-trivial no-go results. More precisely, our Theorem 9 shows that non-randomised MAC schemes such as HMAC and NMAC cannot satisfy existential and selective unforgeability except for µ = 1 and hence are always vulnerable against more powerful quantum adversaries. On the other hand, our randomised construction shows a fix to this problem and presents an approach towards proper randomization of classical primitives such that they can resist emulation type of attacks. Furthermore, we have shown that a similar technique can be applied to quantum primitives to construct randomised µ-qGSU secure schemes (6.2). Nevertheless, constructing efficient randomised oracles for quantum primitives using random quantum circuits or t-designs is an interesting future research direction. We have also shown that universal unforgeability is a level of security that both deterministic quantum and classical primitives can achieve. Although this is a weaker definition, it is enough for many practical purposes where unforgeability is the desired property, such as identification. Finally, it would be interesting to see the applicability of our definition and framework in practice to specific quantum primitives such as quantum money and classical public-key primitives such as digital signatures, which we also leave as a future research direction. A summary of all the possibility and impossibility results in this paper have been given in Table 3.
Primitives qGU.level 1-qGEU µ-qGEU(µ = 1) 1-qGSU µ-qGSU(µ = 1) qGUU  Table 3: Summary of the possibility and impossibility results in the quantum Generalised Unforgeability definition for classical and quantum primitives. qPRF and PRU refer to non-randomised primitives with an evaluation selected from such families, and × denotes that there are no primitives secure in that level of unforgeability.

Supplementary Materials A Weak and strong Quantum Generalised Unforgeability
We have formally defined our different instances of unforgeability definition as a quantum analogue of weak unforgeability. However, the same definition with small modification can be applied to capture strong unforgeability. First, we note that the difference between strong and weak unforgeability is only relevant to randomised primitives and for non-randomised primitives these definitions are equivalent. In the classical strong unforgeability, it is sufficient for the adversary to output a new pair to win the game and hence the adversary is allowed to pick one of the learning phase messages as the challenge and produce a new output with a fresh randomness. In our definition, it is sufficient to expand the µ-distinguishability condition to the overall input of the oracle including the randomness i.e. adversary's challenge state |r * r * | ⊗ ρ m needs to be µdistinguishable from all the learning phase states with their randomness registers which can be written as |r i r i | ⊗ ρ in i . Once again for µ = 1 this will capture the same definition as is expected. Proof. In order to show this implication we will show that if a QPT adversary A can win in qGUU, then A can also win against µ-qGSU. Although for simplicity we restrict the proof for the case of µ = 1 and the generalisation to any µ is straightforward from the hierarchy of the definition for different µ showed in the previous section. Also we recall that 1-qGSU and 1-qGEU are equivalent. Let A play the game G F qUni (λ, A) by picking a set of learning phase state {|φ i } K i=1 . Let the dimension of the unitary oracle O E be D = 2 n and let the subspace of σ in be of dimension d = poly(n). If A wins the game, then the average probability of A generating the an acceptable output for any x ∈ M picked uniformly at random by C is non-negligible: where P r x∈M [1 ← A(x)] denotes the success probability of the adversary wining the game for input x. Now to be able to translate this game to the 1-qGSU game, first we need to make sure that the set of states that A picks the challenge from them, satisfy the distinguishability condition for µ = 1 i.e. they are orthogonal to all the learning phase states. Let M be the set of all the challenges with no overlap with any of the learning phase states ρ in i . Then we can rewrite the average success probability as follows: since the dimension of the subspace that σ in spans is d and it is polynomial with respect to the size of M then |M | |M| ≈ 1. Hence P r[x ∈ M ] ≈ 1 but P r[x ∈ M ] = 1 − P r[x ∈ M ] = negl(λ). As a result the second term will be negligible and for the whole expression to become non-negligible, the following should hold: Now let A be an adversary who wants to win the game G F qSel,µ (λ, A ) by using A. As A picks the challenge of their choice, we will show that there is a strategy for A to win the game relying on the average success probability of A being non-negligible over M . But also as A is a QPT, we will show there exist a poly size subspace of M in which A will win with non-negligible probability. First we assume that M is partitioned into K different subsets (or subspaces) S i with equal size (or dimension in the quantum case) |S 1 | = · · · = |S K | = l = poly(λ). Note that this partitioning is only for simplicity and any random partitioning of M into the equal size subspace will be enough for our purpose. Now let A pick one of the subsets of message space which consists of picking one of the S i with probability 1 K . We want to show that if A picks the S i at random and calls A on that S i the probability that in the picked subspace the following condition holds is non-negligible: If this is the case, then by the definition of the average probability there exist at least one x * for which the P r[1 ← A(x * )] = non-negl(λ) and hence the A has won the game with a non-negligible probability. Thus we need to find the number of the success probability of A picking a desirable subset. This probability is given by: where Q denotes the number of subsets S i which satisfy the condition and K = O(|M |). We then only need to show that Q K is non-negligible in the security parameter. For simplicity let us replace average probability of A in wining the game over M , with the expected value of wining probability of A over all the different elements of M i.e.

P r x∈M
Now A can run a quantum emulation algorithm by setting the |φ r as the reference state, and picking the target state to be |ψ = |m, 0 . A uses and emulation algorithm with one block and relying on Theorem 3, the output state of Stage 1 of the QE algorithm is: Note that φ 1 | ψ = 0 and | ψ| φ r | 2 = γ 2 and | φ 1 | φ r | 2 = 1 − γ 2 . Then according to Theorem 2, the fidelity of the emulation for both states is:  In general, γ 2 which is the overlap between the challenge state and the learning phase state can be as large as 1 − µ allowed by the definition, thus we set the maximum allowed value of overlap which is γ = γ max = √ 1 − µ. Now we need to also determine P ov and to show whether the adversary can boost the success probability by a non-negligible value. Here one of the queries is orthogonal to the challenge and there is only one query (|φ r ) with overlap, thus according to Theorem 11 we have P ov (2, µ) = 1 − µ 2 . As a result Since 1 4 + non-negl(λ) ≤ µ ≤ 1 − non-negl(λ), then all the terms are nonnegligible in the security parameter and this concludes the proof.

B.3 Proof of µ-qGSU security for Construction 1 with qPRF
In this section we give a complementary proof for a qPRF based construction that does not need the computational definition of inter-function independence defined in Definition 14. Instead, we establish the following lemma for truly random functions: Lemma 2. Let F : X → Y be the family of all the functions with domain X and range Y, where X = {0, 1} n and Y = {0, 1} m . For any two functions f and g picked uniformly at random from F , the following pairwise property holds: Proof. First we calculate the probability of selecting a random f such that f (x) = c where c ∈ Y is a specific element of the range. This probability is equal to the number of all the functions which return c on input x divided by number of all the functions in F which is: Since g has also been picked uniformly and independently from f , the same probability holds for g. As a result P r . Now we are interested in the probability where f and g simultaneously return c which is: (62) Finally, we since we are not interested in any particular c, we get the following probability by considering all c ∈ Y: Thus the proof is complete.
Theorem 15. Construction 1 where F is a qPRF, is µ-qGSU secure for any µ.
Proof. We assume there exists a QPT adversary A who plays the µ-qGSU game where the evaluation is according to Construction 1, and wins with non-negligible probability in the security parameter i.e. A wins the game by producing a valid tag t * for their selected message m * and randomness r * with the following probability: Where the verification algorithm checks if F (k ⊕ r * , m * ) = t * . We introduce the following intermediate games: -Game 1. This game is similar to µ-qGSU for Construction 1, except that A needs to produce forgery for an r * which is one of the previously received random values of {r i } q i=1 in the learning phase. -Game 2. This game is similar to Game 1, but the evaluation oracle picks a new f for each query from truly random functions of the family F : {0, 1} n → {0, 1} m . Note that here the randomness value r, only identifies the function for each query and it is an independent random variable from the function itself. Then A needs to produce forgery t = f (m * ) for the message m * that they have picked earlier in the challenge phase, as well as specify r * of the function (query) for which the forgery has been done.
First, it is straightforward that the probability of the adversary in winning µ-qGSU for Construction 1, is at most negligibly higher than winning Game 1. Since r i in both cases have been picked independently and uniformly at random and the probability of producing a forgery for a specific function with no query is negligible. Thus for Construction 1, Game 1 and µ-qGSU are indistinguishable.
Second, we show that Game 1 and Game 2 are indistinguishable. We prove this by contradiction. We show that if A has a non-negligible advantage in winning Game 1 over Game 2, then there exists also an adversary who can distinguish a qPRF with truly random functions. Let A be such an adversary. Now we construct adversary A who is trying to distinguish a qPRF from truly random functions. First A queries all the learning phase states of A, and then as the last query, but also the challenge message m * selected by A as prescribed by Game 1 and Game 2. Thus due to the non-negligible advantage of A in producing a forgery for the case where the function is a qPRF A can use the last query to distinguish between the two cases and we have: Which is a contradiction and we have shown that Game 1 and Game 2 are indistinguishable. Now we recall the quantum random oracle for Construction 1, and the equivalent oracle for Game 2. Let RO E c be the random oracle for Construction 1 as follows: For each query a new function has been picked from qPRF family of functions, but it is the same for all the messages in the superposition for that query. Now we also present the quantum oracle for Game 2, which is: According to the first part of the proof, the oracles RO E c and O g2 are equivalent. Now using Lemma 2, we show that each query to either of these two oracles, leads to at most a single query to an independent unitary. As a result, the adversary can at most span a one-dimensional subspace of each U fr (resp. U F (k⊕r,.) ) where the unitary acts on the space of the input queries excluding the part that records the randomness. To show this, we recall that each selected message m inside a quantum query of the adversary corresponds to a computational basis of the Hilbert space H D on which U fr (resp. U F (k⊕r,.) ) operates. Due to the pairwise independence property that we have shown in Lemma 2, each two randomly picked U fr map a fixed set of computational basis, to two distinct set of computational basis. We have the following property: where: i | e g i = 0] = negl(λ) Which means that for any randomly picked function f and g, the output set of the basis of the unitary, {e f i } and {e g i } are fully distinguishable sets of computational basis. Also since unitaries are distance preserving operators, this property holds for any sets of basis, not necessarily the computational basis. The above property holds for any two randomly picked functions of the family, i.e. for every two queries and for any subset of the output basis including two bases which covers a 2-dimensional subspace of H D . Thus by selecting a uniformly random function for each query, we have shown that no more than a one-dimensional subspace can be spanned for that specific unitary. As the two oracles are equivalent the same thing holds for when the adversary interacts with RO E c . The rest of the proof is exactly same as the proof of Theorem 10, where we show that with one query to each unitary that satisfies the µ-distinguishability condition with the quantum encoding of m * , the success probability of A is bounded as: Which is a contradiction with the assumption that A breaks the µ-qGSU and the proof is complete.
C No-go result for qGUU security of quantum primitive against adaptive adversaries Another attack model that can be defined against qGUU is when we allow the adversary to use the second learning phase described in the formal definition of game in Figure 1. This attack model is stronger than the usual chosen-message attack considered for universal unforgeability and is particularly interesting for quantum primitives. This is because for a quantum primitive, the adversary receives an unknown quantum state from the challenger and enabling the second learning phase does not lead to a trivial attack. We call this attack model, adaptive-universal attack ( aua). Although we show that a quantum adversary who can use entanglement can break the qGUU security of any deterministic primitive if the second learning phase is allowed. We show this specific instance of the game as G F qUni−aua,µ (λ, A) and we note that again this instance should be parameterised with µ since a trivial attack can happen if A tries to query the challenge phase again in the second learning phase. We present our attack and general no-go result in the following theorem.
Proof. Let A be the QPT adversary playing the game G F qGU U −aua,µ (λ, A) and running the algorithm described in Figure C.
A does not issue any query during the first learning phase. Then A receives an unknown challenge state |ψ m = is a set of complete orthonormal bases for H D . Now, A prepares state |0 and performs a CNOT gate on the first qubit of the unknown challenge state and the ancillary qubit (|0 ) with the control qubit on the challenge state. We can assume the order of the bases is such that in the first half, the first qubit is |0 and in the second half the first qubit is |1 . Then the output entangled state is Now we can compute the final state of the two systems after the second learning phase which is: By rewriting the first qubit in the |+ basis we have The subscript c denotes the challenge and the subscript a denotes the adversary's qubit.
A sends the challenge part of the entangled system, ρc as a query.  Then, the adversary measures his local qubit in the {|+ , |− } bases. If he obtains |+ , the state collapses to U E ( D i=1 α i |b i c ) = U E |ψ m that is the desired state with fidelity 1. If the output of the measurement is |− , half of the terms have a minus sign. In this case, A applies a controlled-Z gate on the second half of the state to obtain again U E |ψ m . As a result, for any κ 1 and κ 2 , we have: P r[1 ← G F qUni−aua,µ (λ, A)] = P r[1 ← T ((U E |ψ m ) ⊗κ1 , |t ⊗κ2 )] = 1.
Now to complete the proof, we show that the µ-distinguishability is satisfied on average. We need to calculate the reduced density matrix of this state and compare it with the density matrix ρ ψ = |ψ ψ| in terms of the Uhlmann's fidelity. The reduced density matrix of the challenge state can be calculated as follows: where T r a denoted the partial trace taken over the adversary's sub-system. And the first sum shows the diagonal terms of the density matrix. As it can be seen these density matrices are different in half of the non-diagonal terms with the ρ ψ . According to the Uhlmann's fidelity definition in the preliminary, and the fact that |ψ is a pure state the fidelity reduce to: By substituting the ρ c from above, the result will be as follows: where |γ i | 2 denoted the square of a quarter of the non-diagonal elements of ρ ψ . This is a positive value and on average over all the state |ψ , non-negligible compared to the dimensionality of the state. Hence: and the distinguishability condition is satisfied and the proof is complete.