then this holds as well for all $x$. However, unwanted collisions might occur in $f_K(IV, \cdot)$.

Assuming that $M_m$ is full rank, we can express the probability of unwanted partial periods for $f_K(IV, F(\cdot))$ as the probability of such unwanted collisions for $f_K(IV, \cdot)$:

$$ 
\begin{aligned}
p &= \max_{t, M_m \times t \neq 0} \Pr_{x \in \{0,1\}^l} [f_K(IV, F(x \oplus t)) = f_K(IV, F(x))] \\
&= \max_{t, M_m \times t \neq 0} \Pr_{x \in \{0,1\}^l} [f_K(IV, F(x) \oplus M_m \times t) = f_K(IV, F(x))] \\
&= \max_{u \neq 0} \Pr_{x \in \{0,1\}^l} [f_K(IV, F(x) \oplus u) = f_K(IV, F(x))] \\
&= \max_{u \neq 0} \Pr_{y \in \{0,1\}^n} [f_K(IV, y \oplus u) = f_K(IV, y)] .
\end{aligned}
$$

Even if the output is truncated to less than $n$ bits, $p \le \frac{1}{2}$ follows trivially from the fact that $f_K(IV, \cdot)$ should not admit a differential of such high probability. To conclude, it is precisely the fact that the termination function $f_K(IV, \cdot)$ is a good PRF, and does not admit an interfering period, that allows to apply easily Simon's algorithm in our case.

Thus, by making a polynomial number of Q2 queries to the MAC construction, we can obtain such an $\alpha$. This allows to create forgeries as follows.

**Forgeries without IVs.** We first make $n$ queries to find a valid $\alpha$ with Simon's algorithm (with constant probability of success). Then, the knowledge of this $\alpha$ allows us, for each tag $x$ queried, to output a forged tag $x \oplus \alpha$. Thus we can double the number of tags that we produce compared to the number of queries we make. This breaks the PO notion as soon as, making $r+n$ queries, we have $2r \ge r+1+n$ tags, thus with $2n+2$ queries in total. Note that by breaking PO, we are actually showing that the MAC construction is not a qPRF (if it were, it would be PO-secure).

**Forgeries with IVs.** As long as the IV (or nonce) is used only in the keyed post-processing, we can recover a value $\alpha$ and run the attack as above. We will indeed output more triples $\{IV, \text{message}, \text{tag}\}$ than the number of queries made, although some IVs are repeated in the outputs.

**Universal Forgeries.** Instead of taking the arbitrary values $b_i||0$ in message blocks, we can take any pair of values for each of them. That way, we can even start from any $m$-block message $y_1, \dots, y_m$, and then define a function of $x = b_1 \dots b_m$ that inputs $y_i$ in block $i$ if $b_i = 1$ and an arbitrary value 0 otherwise. Using Simon's algorithm, we will find a subset of the $y_i$ such that the $\tilde{E}_{K,i}(y_i)$ have the same XOR as the $\tilde{E}_{K,i}(0)$. Hence, we can produce a new message having the same tag as $y_1, \dots, y_m$. This works as soon as $m \ge n$ (there just needs to be enough message blocks for our attack).

# 4 Applications to Parallelizable MACs

In this section, we apply the quantum linearization attack to many parallelizable MACs of the literature. In particular, we show that the attack can be extended to
parallelizable beyond birthday-bound (BBB) MACs, although they have a larger internal state. Here is a summary of MACs attacked in this section (usually in time quadratic in the internal state size $n$), whose previous best quantum attack was exponential:

LightMAC [47], LightMAC+ [54], Deoxys [38], ZMAC [37], PMAC_TBC3k [53]

On the contrary, here are some MACs on which, to the best of our knowledge, our attack does not apply: SUM-ECBC [62], 2K-ECBC-Plus [24], 3kf9 [63]. The best Q2 attacks on these remain exponential-time (usually $\tilde{O}(2^{n/2})$ or $O(2^{k/2})$ where $n$ is the internal block size, and $k$ the key size).

## 4.1 First Examples

We will consider MAC designs with or without IVs or nonces. When there is no IV, then the attack of Section 3.3 breaks them in the PO notion. This also shows that even though they usually yield classical PRFs, these constructions are not quantum-secure PRFs. When there is an IV, the MAC may be insecure as a PRF but still secure as a MAC (since the IV is changed at each query, and not repeated). Despite that, our attack may still yield a break, as we showed in the example of $\Theta$CB above. In that case, the period that is recovered with Simon's algorithm is independent of the IV, and can be reused to forge a new valid (message, tag) pair under any previously queried IV.

**LightMAC.** LightMAC [47] is based on an $n$-bit block cipher and separates the message in blocks of $n-s$ bits, where $s \le n/2$ is some parameter that limits the maximal message size. The function is the following:

$$ \text{LightMAC}(m_1, \dots, m_\ell) = \text{Trunc}_t \left( E_{K_2} \left( (m_\ell 10^*) \oplus \bigoplus_{i=1}^{\ell-1} E_{K_1}(i_s m_i) \right) \right), $$

where the $i_s$ are $s$-bit constants. Calling LightMAC with single-bit blocks and using Simon's algorithm, we immediately obtain a sequence of indices $j_1, \dots, j_v$ such that $E_{K_1}(i_{j_1}1) \oplus \dots \oplus E_{K_1}(i_{j_v}1) = E_{K_1}(i_{j_1}0) \oplus \dots \oplus E_{K_1}(i_{j_v}0)$ and thus, we can produce existential forgeries, and universal forgeries of messages with a linear number of blocks.

**Deoxys.** Due to the similarity of its MAC with $\Theta$CB, our attack applies to all versions of Deoxys-II [38], one of the finalists of the CAESAR competition (it also applies to Deoxys-I).

**Protected Counter Sums.** In [5], Bernstein defined the protected counter sum construction, which uses a pseudorandom function $f: \{0,1\}^{d+c} \to \{0,1\}^c$ to build a pseudorandom function with message space of at most $2^c - 1$ blocks of length $d$:

$$ f'(m_1, \dots, m_\ell) = f(0 \parallel f(1 \parallel m_1) \oplus \dots \oplus f(\ell \parallel m_\ell)). $$

The quantum linearization attack essentially shows that this construction, while classically sound, does not yield a quantum-secure pseudorandom function (even if $f$ itself is a qPRF).
## 4.2 Attacks on BBB MACs

We consider here a variant of the previous construction typically used to design Beyond Birthday MACs. We focus on deterministic MACs, but as before, the same forgery attacks apply if IVs are used in the final processing of the tag.

In the most generic setting, the input $x_1, \dots, x_m$ is processed with a TBC $\tilde{E}_{K,i}$, then combined in two different ways:

$$ (x_1, \dots, x_m) \mapsto f_K \left( \bigoplus_i \tilde{E}_{K,i}(x_i), \bigoplus_i 2^i \tilde{E}_{K,i}(x_i) \right). $$

Here $f_K$ is a function whose details are insignificant for our attack.

A similar observation as above applies. By calling the MAC in superposition with messages of the form $x = b_1||0, \dots, b_m||0$, we will obtain a periodic function. Indeed, there are now two matrices $M_m$ and $M'_m$ with $n$ rows and $m$ columns, and two column vectors $C, C'$ such that:

$$ F(x) = F(b_1, \dots, b_m) := f_K \left( M_m \times \begin{pmatrix} b_1 \\ \vdots \\ b_m \end{pmatrix} \oplus C, M'_m \times \begin{pmatrix} b_1 \\ \vdots \\ b_m \end{pmatrix} \oplus C' \right), $$

where the columns of $M_m$ correspond to $\tilde{E}_{K,i}(0) \oplus \tilde{E}_{K,i}(1)$ and the columns of $M'_m$ correspond to $2^i(\tilde{E}_{K,i}(0) \oplus \tilde{E}_{K,i}(1))$. Then, as soon as $m \ge 2n+1$, the matrix: $\begin{pmatrix} M_m \\ M'_m \end{pmatrix}$ has $2n$ rows and at least $2n+1$ columns, and so, it has a non-trivial kernel. There exists a non-zero vector $\alpha$ such that

$$ M_m \alpha = M'_m \alpha = \begin{pmatrix} 0 \\ \vdots \\ 0 \end{pmatrix}. $$

This $\alpha$ is a boolean period of $F$, for which $MAC(x \oplus \alpha) = MAC(x)$. Again, the further we increase $m$, the bigger the subspace of periods will become. This whole space can be recovered using Brassard and Høyer's extension of Simon's algorithm [20] in polynomial time.

**Related works.** In [30], Guo, Wang, Hu and Ye used combinations of Simon's algorithm and Grover's algorithm to design forgery attacks on many BBB MACs, in the Q2 setting. With this technique, they found two things. First, state-recovery attacks of complexity $\tilde{O}(2^{n/2})$ where $n$ is the block size of the underlying block cipher, and the internal state is $2n$ bits in total. This comes from the fact that the same input blocks are processed in two branches separately. The standard use of Simon's algorithm, where a controlled message block $x$ is XORed to an uncontrolled value, allows only to recover this value in one of the branches. The $n$ bits on the other branch have to be guessed with a Grover search, and so, the attack is a Grover-meets-Simon [46] instance. And next, partial key-recovery attacks for parallelizable MACs, of complexity $\mathcal{O}(2^{k/2})$, where $k$ is the partial
<figure><img src="image_165.png" /><figcaption>Fig. 3. LightMAC+ with three keys $K, K_1, K_2$.</figcaption></figure>

key size (the total key size ranges from 3k to 5k). They consist in guessing part of the key and breaking the MAC by using a symmetry of the branches. To these attacks correspond classical partial key-recoveries of complexity $O(2^k)$.

Our attack has completely different requirements and offers different results. We need longer messages (of roughly 2n blocks in this setting), but when it applies, the complexity is always polynomial. Note that there are constructions targeted by Guo et al., such as SUM-ECBC, that we cannot attack since the blocks are processed sequentially and not linearly in parallel as we require.

LightMAC+. LightMAC+ [54], as its name suggests, is a BBB extension of LightMAC.

As shown in Figure 3, it processes $\ell$ message blocks $m_1, \dots, m_\ell$ as follows:

$$ \text{LightMAC}+(m_1, \dots, m_\ell) = E_{K_1}(E_K(1_s \| m_1) \oplus \dots \oplus E_K(\ell_s \| m_\ell)) \\ \oplus E_{K_2}(2^{\ell-1} \odot E_K(1_s \| m_1) \oplus \dots \oplus 2^0 \odot E_K(\ell_s \| m_\ell)), $$

where the multiplications are done in the finite field $\mathbb{F}_{2^n}$. This falls into our framework and is thus forgeable in quadratic time (about 2n blocks are required to embed a vector space in both branches, and this can then be recovered in a linear number of queries).

PMAC+. It is a double-block hash-then-sum construction similar to LightMAC+, which also falls into our framework. In full generality, there are three keys $K_1, K_2, K_3$. The message blocks $m_1, \dots, m_\ell$ are processed as follows: $y_i = m_i \oplus 2^i \odot E_{K_1}(0) \oplus 2^{2^i} \odot E_{K_1}(1)$ and then:

$$ \text{PMAC}+(m_1, \dots, m_\ell) = E_{K_2}(E_{K_1}(y_1) \oplus \dots \oplus E_{K_1}(y_\ell)) \\ \oplus E_{K_3}(2 \odot E_{K_1}(y_1) \oplus \dots \oplus 2^\ell \odot E_{K_1}(y_\ell)). $$

The masking by $2^i \odot E_{K_1}(0) \oplus 2^{2^i} \odot E_{K_1}(1)$ simply makes the processing of each block different, but this is insignificant for our attack. By recovering a period, we can create forgeries and break PMAC+ as a qPRF.

Note that both LightMAC+ and PMAC+ were classically proven secure up to $2^{3n/4}$ queries [41]. Besides, increasing the number of parallel branches may have
consequences on the bound, but only increases the complexity of our attack by a constant factor. We considered here three-key versions, but of course, the two- and one-key versions [24,25] are similarly broken.

## 4.3 Other MACs

**LAPMAC.** LAPMAC was defined in [51]. The definition depends on some parallelization parameter $\mu$. Successive chunks of $\mu$ message blocks will be processed in parallel through the block cipher $E_K$ (except the last one), then some tweak function depending on their index in the chunk. The results are XORed and encrypted again, before being XORed to the next chunk of $\mu$ message blocks, etc. When $\mu \ge n$, LAPMAC applied to $n$ message blocks becomes similar to LightMAC or PMAC, and there is sufficient parallelization to perform our attack. Whether a variant of the attack applies for smaller values of $\mu$ is an interesting question.

**ZMAC.** ZMAC [37] is a MAC that uses a TBC. It is based on the ZHASH double-block hash construction followed by a finalization function. We can simply focus on the abstraction ZHASH (see Fig. 5 in [37]):

$$ \text{ZHASH}(X_{\ell}^{1}, X_{r}^{1}, \dots, X_{\ell}^{l}, X_{r}^{l}) = \bigoplus_{i} 2^{l+1-i} \tilde{E}_{K}^{i, X_{r}^{i}}(X_{\ell}^{i}), \bigoplus_{i} X_{r}^{i} \oplus \bigoplus_{i} \tilde{E}_{K}^{i, X_{r}^{i}}(X_{\ell}^{i}), $$

where $\tilde{E}_K^t$ is $\tilde{E}_K$ called with a tweak $t$. If we make the tweak inputs constant, then the construction is similar to PMAC+ with a TBC, and different random keyed permutations for each block. Our attack applies as well.

**PMAC with a TBC.** Naito [53] showed that PMAC+ used with a TBC could achieve full PRF security (up to $O(2^n)$ queries). In this variant, the message blocks are processed independently with different tweaks. This has no consequence on our attack, which requires only $O(n)$ queries of about $2n$ blocks each.

# 5 Attacks on MACs based on Universal Hashing

In this section, we focus on some attacks on MACs based on universal hashing. In particular, we give polynomial-time attacks on PolyMAC [36], GCM-SIV2, and we give a superposition attack on Poly1305 requiring about 32 queries.

## 5.1 Overview

Universal hash functions were introduced by Carter and Wegman in 1977 [21] in order to build secure MACs, and are now used in many MAC constructions and security proofs. The first proposal by Wegman and Carter was to hash the message and to encrypt the result with a one-time-pad. This defines a MAC with information-theoretic security, but the use of a one-time-pad is impractical, and it was soon suggested to replace it with the output of a PRF, i.e., to replace the one-time-pad by counter-mode encryption. This results in the Wegman-Carter
construction used in GCM and Poly1305-AES: $M \mapsto H_{K_1}(M) \oplus F_{K_2}(N)$ where $F$ is a secure pseudorandom function family, and $H$ an almost-XOR-universal hash function family.

## 5.2 Universal hash functions and MAC constructions

An almost-XOR-universal hash function family is a family of function $H$ from $\{0, 1\}^*$ to $\{0, 1\}^n$ indexed by a key $K \in \mathcal{K}$ such that:

$$ \forall m \neq m', \forall d \in \{0, 1\}^n, \#\{K \in \mathcal{K} : H_K(m) \oplus H_K(m') = d\} \leq \varepsilon\#\mathcal{K} $$

The most widely used universal hash function construction is polynomial hashing. The input message is interpreted as the coefficients of a polynomial in a field $\mathbb{F}$, and the polynomial is evaluated on the hash key:

$$ \text{PolyHash}_{\mathcal{K}} : \mathbb{F}^{\ell} \to \mathbb{F} \qquad m_1, m_2, \dots m_{\ell} \mapsto \sum_{i=1}^{\ell} K^i \odot m_i $$

Block cipher-based constructions such as the OCB3 MAC can also be analysed as universal hashing-based, using $\oplus_i E_K(A_i \oplus \Delta_i)$ as a universal hash function. There are many different ways to turn a universal hash function into a MAC:

**One-time-MAC: $H_K(M)$**. If the universal hash function satisfies extra properties (it must be strongly universal), it can be used directly as a MAC, if a new key is used for each message. This construction is used in ChaCha20-Poly1305, Grain128A and Grain128AEAD [32].

**Wegman-Carter: $H_{K_1}(M) \oplus F_{K_2}(N)$**. The Wegman-Carter construction is a nonce-based MAC using a universal hash function $H$ and a PRF $F$. It authenticates several messages using the same key, as long as the nonce $N$ is not repeated (the security is lost as soon as two different messages are authenticated with the same key). This construction is used in GMAC. More generally, the construction $H(M) \star F(N)$ with $\star$ a group operation and $F$ almost-$\star$-universal is a secure MAC. This construction is used in Poly1305-AES.

**Hash-then-PRF: $F_{K_2}(H_{K_1}(M))$**. The hash-then-PRF construction builds a deterministic MAC from a universal hash function $H$ and a PRF $F$. The PolyMAC construction discussed below follows this design. More generally, security proofs for several block cipher-based MACs consider the MAC as following the hash-then-PRF construction; in particular this is the case of double-block hash-then-sum constructions [24].

**WMAC: $F_{K_2}(H_{K_1}(M) \parallel N)$**. WMAC [10] is a generalization of the hash-then-PRF construction using an additional nonce input $N$ to the PRF. This requires a PRF with a larger input, but provides higher security when nonces are unique, without breaking down when they are repeated.

**EWCDM: $E_{K_3}(E_{K_2}(N) \oplus N \oplus H_{K_1}(M))$**. The Encrypted Wegman-Carter with Davies-Meyer construction [23] is an alternative construction offering high security with a nonce with graceful degradation when nonces are repeated. Instead of using a $2n$-bit PRF as in WMAC, it uses two calls to an $n$-bit block cipher.
## 5.3 Attacking Wegman-Carter MACs

All MACs following the Wegman-Carter construction are exposed to the attack using Deutsch's algorithm that we presented in Section 3.1. More precisely, an IV-respecting quantum adversary can retrieve the value of $H_{K_1}(M_1) \oplus H_{K_1}(M_2)$ for an arbitrary pair of messages $M_1, M_2$. He can then repeatedly query the tag of $M_1$ under new nonces, and produce corresponding valid tags for $M_2$.

When using the generalization with a group operation $\star$ instead of $\oplus$, this simple attack does not apply. In particular, Poly1305-AES uses a modular addition and cannot be broken with Deutsch's algorithm, but we will show a dedicated attack in Section 5.5, using the fact that it is based on polynomial hashing.

## 5.4 Attacking Algebraic Universal Hash Functions

We can apply our linearization attack to MACs that reuse the same hash key for several messages, whether deterministic (like hash-then-PRF), or nonce-based (like Wegman-Carter, WMAC, and EWCDM). Indeed, it is enough for us to linearize the function $H$, and the attack applies regardless of the security of the operations that are computed afterwards, even if they involve a nonce.

Many Universal Hash Functions based on algebraic operations have a strong linear structure. In particular, polynomial hashing is a linear function of the message, making it a natural target for Simon's algorithm (in characteristic 2) or Shor's algorithm (in general). We describe concrete attacks against a few constructions.

**PolyMAC.** PolyMAC [24] is a double block hash-then-sum construction based on polynomial hashing. The generic construction uses two hashing keys $K_1, K_2$ and two encryption keys $K_3, K_4$. For an $\ell$-block message $m_1, \dots, m_\ell$, this gives:

$$ \text{PolyMAC}(m_1, \dots, m_\ell) = E_{K_3} (K_1 \odot m_\ell \oplus K_1^2 \odot m_{\ell-1} \oplus \dots \oplus K_1^\ell \odot m_1) \\ \oplus E_{K_4} (K_2 \odot m_\ell \oplus K_2^2 \odot m_{\ell-1} \oplus \dots \oplus K_2^\ell \odot m_1) . $$

If a single branch is used, then this looks like the GMAC construction [50] (but without a nonce), using polynomial hashing. GMAC was already attacked in [39] due to its similarities with CBC-MAC, and the fact that the nonce did not influence the embedded hidden shift. However, we can use our attack here. By taking $\ell$-block message inputs with blocks 0 or 1, we will recover with Simon's algorithm a period $b_1 \cdots b_\ell$ such that:

$$ \bigoplus_i b_i K_1^i = 0 \text{ and } \bigoplus_i b_i K_2^i = 0 . $$

This immediately allows a forgery attack, but also, we can recover multiple such periods and solve the corresponding equations to recover $K_1$ and $K_2$.
**PolyMAC with Modular Additions.** Interestingly, our attack applies as well when the polynomial hashing does not use XORs, but modular additions (modulo some value $M$). However, Simon's algorithm has to be replaced by Shor's algorithm. Note that this is specific to polynomial hashing, and does not apply to LightMAC or PMAC-style constructions in general.

We can define:

$$ \text{PolyMAC}+(m_1, \dots, m_\ell) = E_{K_3} (K_1 \odot m_\ell + K_1^2 \odot m_{\ell-1} + \dots + K_1^\ell \odot m_1 \mod M) \oplus E_{K_4} (K_2 \odot m_\ell + K_2^2 \odot m_{\ell-1} + \dots + K_2^\ell \odot m_1 \mod M) . $$

In that case, we can remark that there exists periods $a_1, \dots, a_\ell$ such that:

$$ K_1 a_1 + \dots + K_1^\ell a_\ell \mod M = 0 \text{ and } K_2 a_1 + \dots + K_2^\ell a_\ell \mod M = 0 . $$

More precisely, these periods form a lattice in $\mathbb{Z}_M^\ell$, and for all of them, we have:

$$ \forall m_1, \dots, m_\ell, \text{PolyMAC}+(m_1 + a_1, \dots, m_\ell + a_\ell) = \text{PolyMAC}+(m_1, \dots, m_\ell) . $$

Thus, the generalization by Mosca and Ekert [52] of Shor's algorithm allows to retrieve the full lattice of these periods: we can not only forge, but also recover the internal hashing keys.

**GCM-SIV2.** This is a double-block variant of GCM-SIV defined in [36]. The tag generation combines two independent polynomial hashes (with two keys $K_1, K_2$) with a keyed-dependent combination function $F_K$, of which we shall not study the details. This mode is nonce-based. With an empty associated data, the tag is computed as follows:

$$ \text{GCM-SIV2-MAC}(N, m_1, \dots, m_\ell) = F_K(N \oplus H_{K_1}(m_1, \dots, m_\ell), N \oplus H_{K_2}(m_1, \dots, m_\ell)) , $$

where $H_{K_1}$ and $H_{K_2}$ are polynomial hashes (this would be similar for the tag of an empty message, replacing $M$ by the associated data). Thus, although the MAC is nonce-dependent, it falls into our framework since the periods of the polynomial hashes remain independent of $N$.

**Other algebraic hashing constructions.** There are many alternatives to polynomial hashing based on field operations. Several constructions are linear, such as the dot product construction, and Toeplitz hashing [42].<fnref n="4" />

Some other constructions can be linearized using specially crafted messages. NMH* [31]. The NMH* universal hash function is defined as:

$$ \text{NMH}^*(M) = \sum (m_{2i} + K_{2i})(m_{2i+1} + K_{2i+1}) \mod p $$

If we consider messages with blocks with an even index set to arbitrary constants, we obtain a linear function of the odd message blocks. Therefore, Shor's algorithm can break MACs based on this hash function that reuse the hash key.

<footnote n="4">⁴ Grain128A and Grain128AEAD [32] use Toeplitz hashing, but we can only attack them in the nonce-misuse setting because they use the one-time-MAC construction.</footnote>
BRW Hashing [7]. The BRW universal hash function is based on a class of polynomials that can be evaluated with $\ell/2$ multiplications with $\ell$ inputs, using a single key. The construction is defined recursively, depending on the input length:

* $BRW_K() = 0$

* $BRW_K(m_1) = m_1$

* $BRW_K(m_1, m_2) = m_1 \odot K + m_2$

* $BRW_K(m_1, m_2, m_3) = (K + m_1) \odot (K^2 + m_2) + m_3$

* $BRW_K(m_1, m_2, \dots, m_\ell) = BRW_K(m_1, m_2, \dots, m_{t-1}) \odot (K^t + m_t) + BRW_K(m_{t+1}, m_{t+2}, \dots, m_\ell)$ with $t$ a power of 2, and $4 \le t \le n < 2t$.

For instance, with 8 inputs, we obtain

$$(( (K+m_1) \odot (K^2+m_2)+m_3) \odot (K^4+m_4)+(K+m_5) \odot (K^2+m_6)+m_7) \odot (K^8+m_8)$$

This construction can also be linearized by setting message blocks with an even index set to arbitrary constants.

## 5.5 Period-Finding against Poly1305

Poly1305 [6] is a polynomial MAC with some specific constraints that force a dedicated analysis. It has already been cryptanalysed in [18], where the authors proposed an attack in $2^{38}$ time and queries. The authors managed to overcome the specific constraints by leveraging a *hidden shift* structure. The attack we propose here is drastically more efficient, and uses a *hidden period* instead.

Poly1305 uses a hashing key $r$ of 124 bits with at most 106 non-zero bits and a 128-bit cipher key $K$. The MAC of a message $m_1, \dots, m_\ell$ with the nonce $N$ is computed as:

$$\text{Poly1305}(m_1, \dots, m_\ell) = (c_1 r^\ell + c_2 r^{\ell-1} + \dots + c_\ell r^1) \mod 2^{130} - 5 + \text{AES}_K(N) \mod 2^{128},$$

where $c_1, \dots, c_\ell$ are the padded message blocks obtained from the message blocks $m_1, \dots, m_\ell$. When message blocks are full 128-bit blocks, the $c_i$ are simply obtained from the $m_i$ by adding $2^{128}$.

Let us assume that we query with two message blocks. We have:

$$\begin{aligned} \text{Poly1305}(m_1, m_2) &= ((m_1 + 2^{128}) \cdot r^2 + (m_2 + 2^{128}) \cdot r) \mod 2^{130} - 5 \\ &= (( (m_1 \cdot r + m_2) \cdot r + C_1 ) \mod 2^{130} - 5) + C_2 \mod 2^{128}, \end{aligned}$$

where $C_1, C_2$ are constants of our query that depend on $r, K, N$. Since the computation ends with a reduction modulo $2^{128}$, which is smaller than $2^{130} - 5$, we must actually use a *compressed* instance of Shor's algorithm [48]. This increases mildly the number of queries, by less than a factor 2.
Two inputs $(m_1, m_2)$ and $(m'_1, m'_2)$ lead to the same tag if

$$m_1 r + m_2 = m'_1 r + m'_2 \mod 2^{130} - 5 \\ \Leftrightarrow (m_1 - m'_1)r + (m_2 - m'_2) = 0 \mod 2^{130} - 5 .$$

Hence, the periods of the function Poly1305$(m_1, m_2)$ are solutions of $m_1 r + m_2 = 0 \mod 2^{130} - 5$.

As the period is modulo $2^{130} - 5$ but the input is 128-bit long, we cannot do the query expected by Shor's algorithm. Still, the fraction of inputs we can actually query is large enough so that we can still apply Shor's algorithm with a *partial* query, and recover efficiently the period.

The initial query is:

$$\frac{1}{2^{128}} \sum_{m_1, m_2=0}^{2^{128}-1} |m_1\rangle |m_2\rangle |\text{Poly1305}(m_1, m_2)\rangle \\ = \frac{1}{2^{128}} \sum_{m_1, m_2=0}^{2^{128}-1} |m_1\rangle |m_2\rangle |f(m_1 r + m_2)\rangle .$$

Here, $f$ is a function that depends on $r, K, N$. The only relevant point is that it does not depend on $m_1, m_2$ directly, but only on $m_1 r + m_2$. For simplicity, in the following we assume $f$ is a permutation. We will now apply the QFT over $\mathbb{Z}/(2^{130} - 5)$ on the input registers. We note $p = 2^{130} - 5$. We obtain

$$\frac{1}{p} \frac{1}{2^{128}} \sum_{m_1, m_2=0}^{2^{128}-1} \sum_{x,y=0}^{p-1} \exp \left( 2i\pi \frac{xm_1 + ym_2}{p} \right) |x\rangle |y\rangle |f(m_1 r + m_2)\rangle .$$

We can rewrite the state by regrouping components with identical $m_1 r + m_2$:

$$\frac{1}{p} \frac{1}{2^{128}} \sum_{x,y=0}^{p-1} \sum_{c=0}^{p-1} \sum_{\substack{m_1, m_2=0 \\ m_1 r + m_2 = c}}^{2^{128}-1} \exp \left( 2i\pi \frac{xm_1 + ym_2}{p} \right) |x\rangle |y\rangle |f(c)\rangle \\ = -\frac{1}{p} \frac{1}{2^{128}} \sum_{x,y=0}^{p-1} \sum_{c=0}^{p-1} \sum_{\substack{m_1, m_2=0 \\ m_1 r + m_2 = c}}^{2^{128}-1} \exp \left( 2i\pi \frac{xm_1 + y(c - m_1 r)}{p} \right) |x\rangle |y\rangle |f(c)\rangle \\ = -\frac{1}{p} \frac{1}{2^{128}} \sum_{x,y=0}^{p-1} \sum_{c=0}^{p-1} \exp \left( 2i\pi \frac{yc}{p} \right) \sum_{\substack{m_1, m_2=0 \\ m_1 r + m_2 = c}}^{2^{128}-1} \exp \left( 2i\pi \frac{m_1(x - yr)}{p} \right) |x\rangle |y\rangle |f(c)\rangle$$

Now, we can compute the probability to measure a nonzero tuple $(x, y)$ with $x = yr$.
As there are $p-1$ such tuples, the overall probability is

$$ \left(\frac{1}{p} \frac{1}{2^{128}}\right)^2 (p-1) \sum_{c=0}^{p-1} \left( \sum_{\substack{m_1, m_2=0 \\ m_1 r + m_2 = c}}^{2^{128}-1} 1 \right)^2 \\ = \frac{p-1}{p^2 2^{256}} \sum_{c=0}^{p-1} \left( \#\{0 \le m_1, m_2 < 2^{128} : m_1 r + m_2 = c \} \right)^2 $$

Now, as $x \mapsto x^2$ is a convex function, we can use Jensen's inequality:

$$ \sum_{i=1}^{n} \frac{1}{n} \alpha_i^2 \ge \left( \sum_{i=1}^{n} \frac{1}{n} \alpha_i \right)^2 . $$

This allows us to lower bound the previous probability by

$$ \frac{p-1}{p^2 2^{256}} p \left( \sum_{c=0}^{p-1} \frac{1}{p} \#\{0 \le m_1, m_2 < 2^{128} : m_1 r + m_2 = c \} \right)^2 \\ = \frac{p-1}{p^2 2^{256}} \left( \frac{1}{p} \#\{0 \le m_1, m_2 < 2^{128} \} \right)^2 = \frac{p-1}{p^2 2^{256}} \left( \frac{2^{256}}{p} \right)^2 = \frac{(p-1) 2^{256}}{p^3} > \frac{1}{16} . $$

Thus, we measure a tuple $(x, y) \ne (0, 0)$ with $x = yr$ with probability at least $1/16$. As $2^{130}-5$ is prime, one such tuple is enough to recover $r$. Hence, we need at most 16 queries on average to recover $r$, assuming $f$ is a permutation. Here, as $f$ is a function, we rely on [48] to bound the increase by a factor 2. Note that as we are only a few bits of output short of having a permutation, this is a very loose bound. Overall, the attack will require no more than 32 queries.

# 6 On Parallelizable Quantum PRFs

Let us take a broader point of view. The deterministic MACs that we attacked in this paper all have common points. Besides allowing inputs of any length (as should be expected of any MAC construction), they • process their input blocks independently; • compute one or more linear functions, with XORs, of these processed input blocks; • process the authentication tag from the outputs of these linear functions.

These characteristics are to be expected from any MAC that is: • of average rate one, meaning that there are as many primitive calls as there are blocks; • parallelizable; • having an internal state of size $O(n)$, independent of the query length. Our attack is easily defeated if the blocks are processed sequentially by calling a compression function, as in the NMAC construction. However, the construction becomes unparallelizable.

It may be possible to obtain a quantum-secure parallelizable qPRF using a tree hashing, where the blocks are placed at the leaves of a binary tree, and each
node is computed by calling a (keyed) compression function on its two children. However, such a construction requires an internal state greater than $O(n)$, and that increases with the amount of data. Typically to traverse the binary tree, we will need to remember $O(\log m)$ nodes, where $m$ is the number of leaves.

*Open Question*. If we stand by the characteristics listed above (efficient, parallelizable, constant internal state size), then it seems that the only solution is to use modular additions in place of XORs in the constructions that we attacked. In that case, our attack does not seem to work anymore, due to the fact that modular additions, contrary to XORs, are not involutive. Thus changing one of the blocks in our *n*-block queries does not modify involutively the result, which breaks the periodicity property that we used with Simon's algorithm.

This makes this option worth investigating, both from a provable security and a cryptanalysis perspective. Note that the situation is different from most attacks with Simon's algorithm, where the replacement of XORs by $+$ changes the attack complexity from polynomial to subexponential (see [2,18]). In our case, it is possible that using $+$ allows an exponential security level.

# 7 Conclusion

In this paper, we introduced a novel way of using quantum period-finding to break parallelizable MAC constructions in the superposition query model, breaking most of them in this setting. In full generality, our attack makes use of multiple blocks to embed a hidden period, a surprisingly simple idea that might have other applications. We gave new polynomial-time forgery or partial key-recovery attacks on LightMAC, LightMAC+, PolyMAC, Poly1305, GCM-SIV2, Dooxys, ZMAC, PMAC_TBC3k. Our attack is not mitigated by the use of multiple parallel branches (as in double-block hash-then-sum MACs). It can be prevented for IV-based MACs if the non-reused IV intervenes in the processing of all message blocks (as done in [9]).

These results show that we cannot obtain a parallelizable quantum-secure PRF by processing independently the message blocks, XORing the results, and then hashing the output. If modular additions are used instead of XORs, our attack does not apply anymore (except on polynomial hashing, which has a simpler structure). Overcoming this limitation, or on the contrary, proving the security of such a PRF, is an interesting open question.

**Acknowledgments** This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 714294 - acronym QUASYModo). A.S. is supported by ERC-ADG-ALGSTRONGCRYPTO (project 740972).

# References

1. Alagic, G., Majenz, C., Russell, A., Song, F.: Quantum-access-secure message authentication via blind-unforgeability. In: EUROCRYPT (3). Lecture Notes in Computer Science, vol. 12107, pp. 788–817. Springer (2020)
2. Alagic, G., Russell, A.: Quantum-secure symmetric-key cryptography based on hidden shifts. In: EUROCRYPT (3). Lecture Notes in Computer Science, vol. 10212, pp. 65–93 (2017)

3. Anand, M.V., Targhi, E.E., Tabia, G.N., Unruh, D.: Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation. In: PQCrypto. Lecture Notes in Computer Science, vol. 9606, pp. 44–63. Springer (2016)

4. Bellare, M., Guérin, R., Rogaway, P.: XOR MACs: New methods for message authentication using finite pseudorandom functions. In: CRYPTO. Lecture Notes in Computer Science, vol. 963, pp. 15–28. Springer (1995)

5. Bernstein, D.J.: How to stretch random functions: The security of protected counter sums. J. Cryptol. 12(3), 185–192 (1999)

6. Bernstein, D.J.: The Poly1305-AES message-authentication code. In: FSE. Lecture Notes in Computer Science, vol. 3557, pp. 32–49. Springer (2005)

7. Bernstein, D.J.: Polynomial evaluation and message authentication (2007), http://cr.yp.to/papers.html#pema

8. Bernstein, E., Vazirani, U.V.: Quantum complexity theory. SIAM J. Comput. 26(5), 1411–1473 (1997)

9. Bhaumik, R., Bonnetain, X., Chailloux, A., Leurent, G., Naya-Plasencia, M., Schrottenloher, A., Seurin, Y.: QCB: efficient quantum-secure authenticated encryption. IACR Cryptol. ePrint Arch. 2020, 1304 (2020)

10. Black, J., Cochran, M.: MAC reforgeability. In: FSE. Lecture Notes in Computer Science, vol. 5665, pp. 345–362. Springer (2009)

11. Black, J., Rogaway, P.: CBC MACs for arbitrary-length messages: The three-key constructions. In: CRYPTO. LNCS, vol. 1880, pp. 197–215. Springer (2000)

12. Black, J., Rogaway, P.: A block-cipher mode of operation for parallelizable message authentication. In: Knudsen, L.R. (ed.) EUROCRYPT. LNCS, vol. 2332, pp. 384–397. Springer (2002)

13. Boneh, D., Zhandry, M.: Quantum-secure message authentication codes. In: EUROCRYPT. Lecture Notes in Computer Science, vol. 7881, pp. 592–608. Springer (2013)

14. Boneh, D., Zhandry, M.: Secure signatures and chosen ciphertext security in a quantum computing world. In: CRYPTO (2). Lecture Notes in Computer Science, vol. 8043, pp. 361–379. Springer (2013)

15. Bonnetain, X.: Quantum key-recovery on full AEZ. In: SAC. Lecture Notes in Computer Science, vol. 10719, pp. 394–406. Springer (2017)

16. Bonnetain, X.: Tight bounds for Simon's algorithm. IACR Cryptol. ePrint Arch. 2020, 919 (2020)

17. Bonnetain, X., Hosoyamada, A., Naya-Plasencia, M., Sasaki, Y., Schrottenloher, A.: Quantum attacks without superposition queries: The offline Simon's algorithm. In: ASIACRYPT (1). Lecture Notes in Computer Science, vol. 11921, pp. 552–583. Springer (2019)

18. Bonnetain, X., Naya-Plasencia, M.: Hidden shift quantum cryptanalysis and implications. In: ASIACRYPT (1). Lecture Notes in Computer Science, vol. 11272, pp. 560–592. Springer (2018)

19. Bonnetain, X., Naya-Plasencia, M., Schrottenloher, A.: On quantum slide attacks. In: SAC. Lecture Notes in Computer Science, vol. 11959, pp. 492–519. Springer (2019)

20. Brassard, G., Høyer, P.: An exact quantum polynomial-time algorithm for Simon's problem. In: ISTCS. pp. 12–23. IEEE Computer Society (1997)

21. Carter, L., Wegman, M.N.: Universal classes of hash functions (extended abstract). In: STOC. pp. 106–112. ACM (1977)
22. Cid, C., Hosoyamada, A., Liu, Y., Sim, S.M.: Quantum cryptanalysis on contracting feistel structures and observation on related-key settings. In: INDOCRYPT. Lecture Notes in Computer Science, vol. 12578, pp. 373–394. Springer (2020)

23. Cogliati, B., Seurin, Y.: EWCDM: an efficient, beyond-birthday secure, nonces misuse resistant MAC. In: CRYPTO (1). Lecture Notes in Computer Science, vol. 9814, pp. 121–149. Springer (2016)

24. Datta, N., Dutta, A., Nandi, M., Paul, G.: Double-block hash-then-sum: A paradigm for constructing BBB secure PRF. IACR Trans. Symmetric Cryptol. 2018(3), 36–92 (2018)

25. Datta, N., Dutta, A., Nandi, M., Paul, G., Zhang, L.: Single key variant of PMAC_Plus. IACR Trans. Symmetric Cryptol. 2017(4), 268–305 (2017)

26. Deutsch, D.: Quantum theory, the church-turing principle and the universal quantum computer. In: Proceedings of the Royal Society London A. vol. 400, pp. 97–117. Springer (1985)

27. Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439(1907), 553–558 (1992)

28. Dong, X., Dong, B., Wang, X.: Quantum attacks on some feistel block ciphers. Des. Codes Cryptogr. 88(6), 1179–1203 (2020)

29. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC. pp. 212–219. ACM (1996)

30. Guo, T., Wang, P., Hu, L., Ye, D.: Attacks on beyond-birthday-bound macs in the quantum setting. In: PQCrypto. Lecture Notes in Computer Science, vol. 12841, pp. 421–441. Springer (2021)

31. Halevi, S., Krawczyk, H.: MMH: software message authentication in the gbit/second rates. In: FSE. Lecture Notes in Computer Science, vol. 1267, pp. 172–189. Springer (1997)

32. Hell, M., Johansson, T., Meier, W., Sönnerup, J., Yoshida, H.: Grain-128 AEAD a lightweight AEAD streamcipher. Submission to NIST-LWC (2nd Round) (2019)

33. Hosoyamada, A., Sasaki, Y.: Quantum demiric-selçuk meet-in-the-middle attacks: Applications to 6-round generic feistel constructions. In: SCN. Lecture Notes in Computer Science, vol. 11035, pp. 386–403. Springer (2018)

34. Ito, G., Hosoyamada, A., Matsumoto, R., Sasaki, Y., Iwata, T.: Quantum chosen-ciphertext attacks against feistel ciphers. In: CT-RSA. Lecture Notes in Computer Science, vol. 11405, pp. 391–411. Springer (2019)

35. Iwata, T., Kurosawa, K.: OMAC: one-key CBC MAC. In: FSE. LNCS, vol. 2887, pp. 129–153. Springer (2003)

36. Iwata, T., Minematsu, K.: Stronger security variants of GCM-SIV. IACR Trans. Symmetric Cryptol. 2016(1), 134–157 (2016)

37. Iwata, T., Minematsu, K., Peyrin, T., Seurin, Y.: ZMAC: A fast tweakable block cipher mode for highly secure message authentication. In: CRYPTO (3). Lecture Notes in Computer Science, vol. 10403, pp. 34–65. Springer (2017)

38. Jean, J., Nikolic, I., Peyrin, T., Seurin, Y.: Deoxys v1. 41. Submitted to CAESAR (2016)

39. Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: CRYPTO (2). Lecture Notes in Computer Science, vol. 9815, pp. 207–237. Springer (2016)

40. Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Quantum differential and linear cryptanalysis. IACR Trans. Symmetric Cryptol. 2016(1), 71–94 (2016)
41. Kim, S., Lee, B., Lee, J.: Tight security bounds for double-block hash-then-sum MACs. In: EUROCRYPT (1). Lecture Notes in Computer Science, vol. 12105, pp. 435–465. Springer (2020)

42. Krawczyk, H.: New hash functions for message authentication. In: EUROCRYPT. Lecture Notes in Computer Science, vol. 921, pp. 301–310. Springer (1995)

43. Krovetz, T., Rogaway, P.: The software performance of authenticated-encryption modes. In: FSE. Lecture Notes in Computer Science, vol. 6733, pp. 306–327. Springer (2011)

44. Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round feistel cipher and the random permutation. In: ISIT. pp. 2682–2685. IEEE (2010)

45. Kuwakado, H., Morii, M.: Security on the quantum-type even-mansour cipher. In: ISITA. pp. 312–316. IEEE (2012)

46. Leander, G., May, A.: Grover meets Simon - quantumly attacking the FX-construction. In: ASIACRYPT (2). Lecture Notes in Computer Science, vol. 10625, pp. 161–178. Springer (2017)

47. Luykx, A., Preneel, B., Tischhauser, E., Yasuda, K.: A MAC mode for lightweight block ciphers. In: FSE. Lecture Notes in Computer Science, vol. 9783, pp. 43–59. Springer (2016)

48. May, A., Schlieper, L.: Quantum period finding is compression robust. CoRR abs/1905.10074 (2019)

49. McGrew, D.A., Viega, J.: The security and performance of the Galois/Counter Mode (GCM) of operation. In: INDOCRYPT. LNCS, vol. 3348, pp. 343–355. Springer (2004)

50. McGrew, D.A., Viega, J.: The security and performance of the galois/counter mode (GCM) of operation. In: INDOCRYPT. Lecture Notes in Computer Science, vol. 3348, pp. 343–355. Springer (2004)

51. Minematsu, K.: A lightweight alternative to PMAC. In: SAC. Lecture Notes in Computer Science, vol. 11959, pp. 393–417. Springer (2019)

52. Mosca, M., Ekert, A.: The hidden subgroup problem and eigenvalue estimation on a quantum computer. In: QCQC. Lecture Notes in Computer Science, vol. 1509, pp. 174–188. Springer (1998)

53. Naito, Y.: Full PRF-secure message authentication code based on tweakable block cipher. In: ProvSec. Lecture Notes in Computer Science, vol. 9451, pp. 167–182. Springer (2015)

54. Naito, Y.: Blockcipher-based MACs: beyond the birthday bound without message length. In: ASIACRYPT (3). Lecture Notes in Computer Science, vol. 10626, pp. 446–470. Springer (2017)

55. Nielsen, M.A., Chuang, I.: Quantum computation and quantum information (2002)

56. NIST: Submission requirements and evaluation criteria for the post-quantum cryptography standardization process (2016), https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

57. Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In: ASIACRYPT. Lecture Notes in Computer Science, vol. 3329, pp. 16–31. Springer (2004)

58. Santoli, T., Schaffner, C.: Using Simon's algorithm to attack symmetric-key cryptographic primitives. Quantum Inf. Comput. 17(1&2), 65–78 (2017)

59. Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: FOCS. pp. 124–134. IEEE Computer Society (1994)

60. Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474–1483 (1997)
61. Song, F., Yun, A.: Quantum security of NMAC and related constructions - PRF domain extension against quantum attacks. In: CRYPTO (2). Lecture Notes in Computer Science, vol. 10402, pp. 283–309. Springer (2017)

62. Yasuda, K.: The sum of CBC MACs is a secure PRF. In: CT-RSA. Lecture Notes in Computer Science, vol. 5985, pp. 366–381. Springer (2010)

63. Zhang, L., Wu, W., Sui, H., Wang, P.: 3kf9: Enhancing 3GPP-MAC beyond the birthday bound. In: ASIACRYPT. Lecture Notes in Computer Science, vol. 7658, pp. 296–312. Springer (2012)