# Post-quantum Security of Key-Alternating Feistel Ciphers

Jyotirmoy Basak, Ritam Bhaumik, Amit Kumar Chauhan, Ravindra

Jejurikar, Ashwin Jha, Anandarup Roy, André Schrottenloher, Suprita

Talnikar

► To cite this version:

Jyotirmoy Basak, Ritam Bhaumik, Amit Kumar Chauhan, Ravindra Jejurikar, Ashwin Jha, et al. Post-quantum Security of Key-Alternating Feistel Ciphers. ASIACRYPT 2025 - 31st International Conference on the Theory and Application of Cryptology and Information Security, Dec 2025, Melbourne, Australia. pp.446-478, 10.1007/978-981-95-5018-0_15. hal-05406482

HAL Id: hal-05406482

https://inria.hal.science/hal-05406482v1

Submitted on 9 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Post-quantum Security of Key-Alternating Feistel Ciphers *

Jyotirmoy Basak¹ Ⓓ Ritam Bhaumik² Ⓓ Amit Kumar Chauhan³ Ⓓ Ravindra Jejurikar² Ashwin Jha⁴ Ⓓ Anandarup Roy⁵ Ⓓ André Schrottenloher⁶ Ⓓ Suprita Talnikar⁵,⁷ Ⓓ

¹ Okinawa Institute of Science and Technology, Okinawa, Japan

² Cryptography Research Centre, Technology Innovation Institute, Abu Dhabi, UAE
`firstname.lastname@tii.ae`

³ QuNu Labs Pvt. Ltd., Bengaluru, India

⁴ Ruhr University Bochum, Bochum, Germany
`firstname.lastname@outlook.de`

⁵ Kyushu University, Fukuoka, Japan

⁶ Univ Rennes, Inria, CNRS, IRISA, Rennes, France
`firstname.lastname@inria.fr`

⁷ Indian Statistical Institute, Kolkata, India

**Abstract.** Since Kuwakado and Morii's work (ISIT 2010 & ISITA 2012), it is known that the classically secure 3-round Luby-Rackoff PRP and Even-Mansour cipher become insecure against an adversary equipped with *quantum* query access. However, while this query model (the so-called Q2 model) has led to many more attacks, it seems that restricting the adversary to classical query access prevents such breaks (the so-called Q1 model). Indeed, at EUROCRYPT 2022, Alagic et al. proved the Q1-security of the Even-Mansour cipher. Notably, such a proof needs to take into account the dichotomy between construction queries, which are classical, and primitive queries, which are quantum (since the random oracle / permutation models a public function that the adversary can compute).

In this paper, we focus on Feistel ciphers. More precisely, we consider Key-Alternating Feistels built from random functions or permutations. We borrow the tools used by Alagic et al. and adapt them to this setting, showing that in the Q1 setting: • the 3-round Key-Alternating Feistel, even when the round functions are the same random oracle, is a pseudo-random permutation; • similarly the 4-round KAF is a strong pseudo-random permutation.

**Keywords:** Feistel networks • Post-quantum cryptography • Symmetric cryptography • Provable security • Q1 security

## 1 Introduction

Due to the progress made by quantum computing devices, it is vital to know how cryptographic algorithms perform against adversaries equipped with quantum computers. In the public key setting, polynomial time quantum algorithms can factor integers and compute discrete logarithms [Sho94], breaking most currently deployed asymmetric schemes that rely on these hardness assumptions. In the symmetric key setting, Grover's search algorithm leads to a quadratic speedup for exhaustive search problems [Gro96], including exhaustive key search, which leads to a halving of security levels for many cryptosystems. However, more powerful quantum attacks exist for many symmetric constructions. By exploiting quantum period-finding, the Even-Mansour cipher and 3-round Luby-Rackoff pseudo-random permutation were found insecure by Kuwakado and Morii [KM10, KM12], despite having classical security proofs. Over the following years, more and more constructions were found to be broken [SS17, KLLN16, BNS19, IHM$^{+}$19, NIDI19, BLNS21].

While the most significant attacks are specific to an adversary equipped with *quantum queries* to secret-key oracles (the so-called Q2 setting), the security of these constructions in the weaker Q1 setting (without quantum queries) does not follow immediately. Indeed, there are known cases where the gap between classical and quantum securities is larger than the generic quadratic speedup of Grover's algorithm [BSS22]. Thus, symmetric constructions need to be re-analyzed case by case to determine the exact security level that they can offer.

<footnote>* ©IACR 2025. This article is the full version of the paper submitted by the author(s) to the IACR and to Springer-Verlag in September 2025. The published version is available from the proceedings of ASIACRYPT 2025.</footnote>
*Key-Alternating Feistels.* Key-Alternating Feistel (KAF) ciphers [LS14] are a fundamental class of block ciphers that are constructed using multiple rounds of Feistel permutations combined with independent round keys. As they are ubiquitous in block cipher design, their classical security has been analyzed and is well understood [BBD+24, SYWL21, GW18, FKSV21]. It is known that 3- and 4-round KAF ciphers are respectively pseudorandom and strong pseudorandom permutations, analogously to the (unkeyed) Luby-Rackoff schemes.

However, in the quantum setting, the first results in this direction were negative. Indeed, the very first break in the Q2 model was that of the 3-round Luby-Rackoff pseudorandom permutation by Kuwakado and Morii [KM10]. They showed that the construction could be distinguished in polynomial time by an adversary making quantum queries to it, using Simon's period-finding algorithm [Sim97]. In addition, Ito et al. [IHM+19] showed a quantum attack to distinguish the 4-round construction, when both forward and backward queries are allowed. Similar attacks break the corresponding 3- and 4-round KAF ciphers.

It is possible to counter these attacks, while remaining in the Q2 setting, by adding more rounds to the Feistel scheme. There has been a claim on the security of 4-round Luby-Rackoff being a quantum pseudorandom permutation [HI19]. However, Bhaumik et al. [BCEJ24] pointed out a technical issue in the proof, and they could only prove security in a restricted setting of a non-adaptive quantum adversary, where the queries have to be decided up front before any query response. Besides, to the best of our knowledge, existing proofs of security for Feistel schemes in the quantum setting have focused on the Luby-Rackoff scheme, not on the KAF ciphers. In the Luby-Rackoff construction, the round functions are random, and the adversary cannot access them. In the KAF setting, the round functions are known.

*Q2 and Q1 Security.* While the Q2 model is non-trivial, with the attacks and proofs of security mentioned above, as of now it is recognized as theoretical: in the near future, cryptographic schemes will continue to be implemented on a classical computer, a system with which interactions can only be classical. This corresponds to the weaker Q1 setting, in which any construction containing the secret key can only be accessed classically.

Interestingly, some constructions which appear broken in the Q2 setting can have their security restored in the Q1 setting. The main questions in the field are therefore to find which constructions are Q2-secure, and for the remaining ones, to prove their conjectured Q1 security.

For constructions relying on *keyed* primitives, Q1 security is quite easy to prove. For instance the proof of security of PRP (resp. SPRP) of Luby-Rackoff can be transferred to the Q1 setting as long as the adversary only has classical access to the construction, and the underlying round functions are modelled as ideal primitives with designated key input, like an ideal cipher or a sufficiently compressing random function. In these scenarios, as long as the key input is independent of adversary's queries, one can safely transfer the classical security results to the Q1 setting at the cost of a key recovery advantage. The latter amounts to black-box quantum exhaustive search, where Grover's algorithm gives a tight solution [BBBV97]. However, this does not hold for constructions based on public primitives without a designated key input, i.e., like a public permutation or a function with short input length. In these cases, the key(s) have to be mixed with adversarial input before the application of the primitive. An enterprising adversary could possibly exploit this mixing beyond the usual Grover's search by issuing quantum queries to the public functions, since they can be implemented on his quantum device.

This is notably the case of the Even-Mansour [ABKM22] and tweakable Even-Mansour ciphers [ABK+24], but also of Feistel and Generalized Feistel block ciphers (e.g., [AIK+00]) where the round function is public and the security relies only on the secrecy of the key. On the Even-Mansour example, ten years elapsed between the Q2 attack and the Q1 proof; while the former is overly simple, the latter needs to handle very subtle technicalities. One notable difficulty is the adaptiveness of the classical queries made by the adversary, and of the ordering of the queries. Indeed, some other Q1 security proofs simplified the situation by considering non-adaptive classical queries, such as the proof for the FX key-extension given in [JST21]. However, the recent literature now offers a better array of tools to handle these issues, such as those of [ABKM22]. A natural question then follows: can these tools be used to prove the security of KAF ciphers, in the Q1 setting? Together with the security of Even-Mansour, such a result could only increase our confidence in the robustness of block cipher designs against quantum adversaries.

**Our Contributions.** In this paper, we answer positively this question and show the security of several KAF constructions, based either on random functions or permutations. In particular, we show that a 3-round KAF cipher, when the round functions are modeled as a random oracle (even if identical), is a PRP in the Q1 setting;
and a 4-round KAF cipher is a strong PRP under the same conditions. These numbers of rounds are tight, since 2-round and 3-round can respectively be broken by classical attacks.

More precisely, for any adversary that makes $q$ classical construction queries and $p$ quantum primitive queries, in the case of independent permutations (resp. functions), we obtain the following results (Section 3.3):

$$ \mathbf{Advt}_{F_{\pi}^{(3)}}^{\text{pq-prp}}(\mathcal{A}) \le 30q\sqrt{\frac{p}{2^n}} + 30p\sqrt{\frac{q}{2^n}} + \frac{3.5^2}{2^n} \quad (3 \text{ rounds, indep. permutations}); $$

$$ \mathbf{Advt}_{F_{\pi}^{(4)}}^{\text{pq-sprp}}(\mathcal{A}) \le 40q\sqrt{\frac{p}{2^n}} + 40p\sqrt{\frac{q}{2^n}} + \frac{4.5q^2}{2^n} \quad (4 \text{ rounds, indep. permutations}); $$

$$ \mathbf{Advt}_{F^{(3)}}^{\text{pq-prp}}(\mathcal{A}) \le 12p\sqrt{\frac{2q}{2^n}} + 9q\sqrt{\frac{2p}{2^n}} + \frac{12.5q^2}{2^n} \quad (3 \text{ rounds, indep. functions}); $$

$$ \mathbf{Advt}_{F^{(4)}}^{\text{pq-sprp}}(\mathcal{A}) \le 16p\sqrt{\frac{2q}{2^n}} + 12q\sqrt{\frac{2p}{2^n}} + \frac{16.5q^2}{2^n} \quad (4 \text{ rounds, indep. functions}). $$

The case where the function used is the same at each round is more important in practice, since it aligns more closely with the design of practical block ciphers. We prove the respective bounds for 3-round KAF and 4-round KAF for the single-function case:

$$ \mathbf{Advt}_{F^{(3)}}^{\text{pq-prp}}(\mathcal{A}) \le 4p\sqrt{\frac{4q}{2^n}} + 12q\sqrt{\frac{2p}{2^n}} + \frac{50q^2}{2^n}; $$

$$ \mathbf{Advt}_{F^{(4)}}^{\text{pq-sprp}}(\mathcal{A}) \le 18q\sqrt{\frac{3p}{2^n}} + 6p\sqrt{\frac{6q}{2^n}} + \frac{94.5q^2}{2^n}. $$

The only case that is missing from our analysis is the single-permutation case, which we leave as an interesting open question.

Regarding the tightness of the bounds, for 3 rounds the bound matches the best known attack, as follows. After three rounds, one of the output branches has the expression:

$$ x \oplus f_2(k_2 \oplus y \oplus f_1(k_1 \oplus x)). $$

By fixing $x$, we obtain a function $f_2(y \oplus k_2 \oplus f_1(k_1 \oplus x))$ where $k_2 \oplus f_1(k_1 \oplus x)$ is an $n$-bit secret. If we make $q \le 2^{n/3}$ classical queries to this function, we can use the offline-Simon [BHN+19] or BHT [BHT98] algorithms to find this secret (thus distinguish from a random permutation) in quantum time $\tilde{O}(\sqrt{2^n/q})$. For 4 rounds, to the best of our knowledge, a matching attack is not known. The main issue is that we would like to find a collision, or a period, in a function defined using the 4-round Feistel, and we cannot transform this into an asymmetric problem with the construction on one side and a round function on the other side.

**Techniques.** The techniques we use are quite generic, suggesting that other classical proofs of security (e.g., for Lai-Massey schemes or Feistel with more lanes) could be transformed similarly in the Q1 setting.

Our proofs rely on the tools established by Alagic et al. [ABKM22] to prove the security of Even-Mansour, with some simplifications and adaptations to our case. Ultimately, the proof relies on a series of hybrids in which both classical construction queries and quantum primitive queries are replaced by the ideal case. The main technicality is to ensure that both queries will still match. Concretely, we use the following tools:

- A result of Don, Fehr and Huang [DFH22] which reduces *adaptive* multi-oracle algorithms (which choose the order of their queries) to *static* ones (which use a fixed ordering of queries). This removes some technicalities of Alagic et al.'s proofs and tools.

- An *arbitrary reprogramming (ARP) lemma* which handles the replacement of a classical query (by reprogramming the random oracle accordingly).

- An *adaptive resampling (ARS) lemma* which handles the replacement of the primitive queries.

The main technical challenge with respect to [ABKM22] is handling bad events. Indeed, the reprogramming of the random oracle may fail if some collisions occur. We also solve this problem with the ARP game, but in order to make the proof easier, we introduce a new interface of *collision-in-the-dark* games (strong and weak versions). In these games, the adversary interacts with a random oracle and returns a set of inputs; later, the challenger samples a key, and the adversary wins only if some relation is satisfied. This interface brings the proof closer to a classical proof of security.
*Organization.* In Section 2 we give definitions and technical preliminaries. In Section 3 we define KAF ciphers and give our results for the case of independent round functions (resp. permutations), which are easier to prove. Later in Section 4, we give the proof for 3-round KAF with identical round functions, and in Section 5, for 4 rounds.

The proof for independent permutations follows from a reduction to the Q1 security of the Even-Mansour cipher [ABKM22]. Similarly, the proof for independent functions uses a reduction to the Q1 security of a blind hash function, which may be of independent interest. The detailed proof is given in Section D.

## 2 Preliminaries

In this section we give various definitions and results required for the Q1 security proofs developed in this paper. Most of them are borrowed or adapted from the literature, except the collision-in-the-dark games (Section 2.5), which are a new interface to the adaptive resampling game, and will be quite useful in our proofs.

### 2.1 Notation

Throughout this paper, we use $[n]$ to denote $\{0, 1, \dots, n-1\}$ and $x \leftarrow_X X$ to indicate that $x$ has been sampled uniformly at random from the set $X$. Other notations specific to Feistel ciphers will be given in Section 3. We usually use $\Gamma$ to denote a random oracle.

For any function $f: \mathcal{X} \to \mathcal{Y}$ and $(x, y) \in \mathcal{X} \times \mathcal{Y}$, define the locally-redefined function $f^{(x,y)}: \mathcal{X} \to \mathcal{Y}$ as

$$f^{(x,y)}(x') := \begin{cases} y & \text{if } x' = x, \\ f(x') & \text{otherwise.} \end{cases}$$

We extend the notion of locally-redefined function to a partial function $B = \{(x_1, y_1), \dots, (x_k, y_k)\}$ for pairwise distinct $x_1, \dots, x_k$, and denote the corresponding function as $f^B$, defined inductively as $f^B := (f^B \setminus \{(x_k, y_k)\})^{(x_k, y_k)}$.

When an adversary has quantum access to a function $f: \{0, 1\}^n \to \{0, 1\}^m$, this means that the adversary accesses, as a black-box, the $(n+m)$-qubit unitary operator $|x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle$. Sometimes we write $\mathcal{A}^{|f(\cdot)|}$ to explicitly indicate that $\mathcal{A}$ has quantum access to $f$.

### 2.2 PQ-PRP and PQ-SPRP Security

Let $\text{Perm}(\{0, 1\}^n)$ be the set of permutations of $\{0, 1\}^n$. Let $\mathcal{A}^\emptyset$ be an algorithm having access to an oracle $\emptyset$ and making only forward queries $x \mapsto \emptyset(x)$ to it, and outputting a bit. The pseudorandom permutation (PRP) advantage of $\mathcal{A}$ against a family of $n$-bit permutations $F_k$, indexed by a secret key $k \in \{0, 1\}^m$, is defined as:

$$\mathbf{Advt}_{\mathbf{F}}^{\text{prp}}(\mathcal{A}) = \left| \Pr_{k \leftarrow_{\S} \{0,1\}^m} (\mathcal{A}^{F_k} \to 1) - \Pr_{\Pi \leftarrow_{\S} \text{Perm}(\{0,1\}^n)} (\mathcal{A}^{\Pi} \to 1) \right|. \quad (1)$$

In addition, when $\mathcal{A}$ is a quantum algorithm (but access to $\emptyset$ remains classical), we use the notation $\mathbf{Advt}_{\mathbf{F}}^{\text{pq-prp}}(\mathcal{A})$. Next, if $\mathcal{A}$ is an algorithm having both forward and backward ($x \mapsto \emptyset^{-1}(x)$) access to the permutation oracle, Equation 1 defines the strong pseudorandom permutation (SPRP) advantage $\mathbf{Advt}_{\mathbf{F}}^{\text{sprp}}(\mathcal{A})$, and similarly, the PQ-SPRP advantage $\mathbf{Advt}_{\mathbf{F}}^{\text{pq-sprp}}(\mathcal{A})$ when $\mathcal{A}$ is a quantum algorithm.

We consider PQ-PRP and PQ-SPRP definitions when $\mathcal{F}_k$ is a construction, built over a primitive $f$ that is modelled as a random oracle (or a random permutation). In that case, the primitive is chosen uniformly at random before running the game, and $\mathcal{A}$ accesses it via a quantum oracle: $|x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle$, and in the PQ-SPRP game, a quantum oracle: $|x\rangle|y\rangle \mapsto |x\rangle|y \oplus f^{-1}(x)\rangle$. Access to the construction remains the same.

### 2.3 The Arbitrary Reprogramming Game

We give a slightly reformulated version of the arbitrary reprogramming lemma from Alagic et al. [ABKM21]. The version found in [ABKM21] is more technical, because it needs to handle an adaptively chosen number of queries. Due to the use of an adaptive-to-static reduction later on, we only need to handle a fixed number of queries, which simplifies the setting.
ARP (Arbitrary ReProgramming) Game

Let $\Gamma: \mathcal{X} \to \mathcal{Y}$ denote a random oracle, and set $\Gamma_0 = \Gamma_1 = \Gamma$. The arbitrary reprogramming (or ARP) game is a random experiment played by a challenger and a distinguisher $\mathcal{D}$ (see Fig. 5 (left) for the pseudocode).

**Phase 1:** The challenger fixes a bit $b \leftarrow_{\$} \{0,1\}$. $\mathcal{D}$ is given quantum access to $\Gamma_b$ and it returns the description of a randomized algorithm $\mathcal{B}$ whose output is a partial function $B \subset \mathcal{X} \times \mathcal{Y}$. Let $B_1 = \{x | \exists y: (x,y) \in B\}$ and $\epsilon = \max_{x \in \{0,1\}^m} \{\Pr_{B \leftarrow \mathcal{B}}[x \in B_1]\}$. Note that $\epsilon$ is an important parameter.

**Phase 2:** The challenger runs $\mathcal{B}$ and obtains $B$ and sets $\Gamma_1 = \Gamma_1^B$, where $\Gamma_1^B$ is the function locally redefined at $B$. $\mathcal{D}$ is again given quantum access to $\Gamma_b$.

**Phase 3:** $\mathcal{D}$ loses its access to $\Gamma_b$. It receives the randomness $r$ used to invoke $\mathcal{B}$ in phase 2, then outputs a bit $b'$.

The ARP advantage of $\mathcal{D}$ is defined as:

$$ \mathbf{Advt}^{\text{arp}}(\mathcal{D}) := |\Pr(\mathcal{D}^{\Gamma_b} = 1 | b=1) - \Pr(\mathcal{D}^{\Gamma_b} = 1 | b=0)|. \qquad (2) $$

Of course, $\mathcal{D}$ will be able to detect the reprogramming if it queried $\Gamma_b$ with a high amplitude on the preimages of $B$. However, $\mathcal{B}$ is a probabilistic algorithm, and $\mathcal{D}$ only obtains the randomness used to run it after losing access to the oracle. Then, one shows that the advantage of $\mathcal{D}$ only depends on the number of queries during the query phase (phase 1 and 2), and on the probability that a given input appears in the preimages of $B$.

**Proposition 1.** [Arbitrary Reprogramming Lemma] For any p-query ARP-distinguisher $\mathcal{D}$, it holds that

$$ \mathbf{Advt}^{\text{arp}}(\mathcal{D}) \le 2p \cdot \sqrt{\epsilon}. $$

The proof is given in Section B.

## 2.4 The Adaptive Resampling Game

ARS (Adaptive ReSampling) Game

Let $\Gamma: \mathcal{X}_1 \times \mathcal{X}_2 \to \mathcal{Y}$ denote a uniform random function (and the corresponding random oracle thereof), and set $\Gamma_0 = \Gamma_1 = \Gamma$. Let RS denote a probabilistic algorithm defined as follows: on input $c \in \mathcal{X}_1$,

1. sample $(x, y) \leftarrow_{\$} \mathcal{X}_2 \times \mathcal{Y}$;

2. set $\Gamma_1 \leftarrow \Gamma^{(c||x,y)}$;

3. return $x$.

On inputs not in $\mathcal{X}_1$, it just returns $\perp$. This algorithm is stateful, since it modifies the definition of $\Gamma_1$. It may also override a previous definition.

The adaptive resampling (or ARS) game is a random experiment played by a challenger and a distinguisher $\mathcal{D}$ (see Fig. 5 (right) for the pseudocode).

**Phase 1:** The challenger fixes a bit $b \leftarrow_{\$} \{0,1\}$.

**Phase 2:** The distinguisher $\mathcal{D}$ is given quantum access to $\Gamma_b$ (the random oracle) and classical access to RS (the resampler).

**Phase 3:** $\mathcal{D}$ outputs a guess $b'$.

The ARS advantage of $\mathcal{D}$ is defined as:

$$ \mathbf{Advt}^{\text{ars}}(\mathcal{D}) := |\Pr(\mathcal{D}^{\Gamma_b, \text{RS}} = 1 | b=1) - \Pr(\mathcal{D}^{\Gamma_b, \text{RS}} = 1 | b=0)|, \qquad (3) $$

and upper bounded using the following result.
**Proposition 2 (Proposition 1 in [GHHM21]).** For any $\mathcal{D}$ that makes at most $p$ queries to the random oracle and at most $r$ queries to the resampler, it holds that

$$ \mathbf{Advt}^{\text{ars}}(\mathcal{D}) \leq 1.5r \sqrt{\frac{p}{|\mathcal{X}_2|}}. $$

## 2.5 The Collisions-in-the-dark Games

In our proofs, we need to bound the probability that an adversary $\mathcal{A}$, which accesses a random oracle quantumly, can find a set of inputs satisfying a given relation $\mathbb{R}$, when fed into a keyed function based on this random oracle. As this happens on more than one occasion, we formalize this situation through the following games (see Fig. 6 (right) for the pseudocode).

### SCitD (Strong Collisions-in-the-dark) Game

Let $\mathcal{X} = \mathcal{X}_0 \times \mathcal{X}_1$ and $\mathcal{Y}$ be two finite sets, where $\mathcal{X}_1 = \{0,1\}^n$. Let $\Gamma : \mathcal{X}_1 \to \mathcal{Y}$ be a random oracle. Fix some relation $\mathbb{R} \in \mathcal{X}^2 \times \mathcal{Y}^2$. The SCitD game is played between a challenger and an adversary $\mathcal{A}$.

**Phase 1:** The adversary $\mathcal{A}$ makes $p$ quantum queries to the random oracle $\Gamma$ and returns a tuple $(\mathcal{X}^*, x^*)$, where $\mathcal{X}^* \subseteq \mathcal{X}$, $|\mathcal{X}^*| = q$ and $x^* = (x_0^*, x_1^*) \in \mathcal{X}$.

**Phase 2:** The challenger samples a key $k \leftarrow_{\$} \mathcal{X}_1$.

We say that $\mathcal{A}$ wins if the following event holds:

$$ \mathbf{SC}_{\mathbb{R}}(\mathcal{X}^*, x^*) : \exists x = (x_0, x_1) \in \mathcal{X}^* \text{ such that } (x, x^*, \Gamma(k \oplus x_1), \Gamma(k \oplus x_1^*)) \in \mathbb{R}. $$

The advantage of $\mathcal{A}$ in SCitD is defined as $\Pr(\mathbf{SC}_{\mathbb{R}}(\mathcal{X}^*, x^*))$ where the randomness is induced by $\mathcal{A}$'s own randomness, by the oracle $\Gamma$ and by $k$. We prove the following result on strong collisions-in-the-dark.

**Lemma 1.** [Strong Collisions-in-the-dark] For any adversary $\mathcal{A}$ in the strong collisions-in-the-dark game with respect to the relation $\mathbb{R}$, making $p$ queries and returning a set of size $q$:

$$ \Pr_{(\mathcal{X}^*, x^*) \leftarrow \mathcal{A}} (\mathbf{SC}_{\mathbb{R}}(\mathcal{X}^*, x^*)) \leq 1.5 \sqrt{\frac{p}{2^n}} + q \max_{x, x^* \in \mathcal{X}} \Pr_{\substack{r \leftarrow_{\$} \mathcal{Y} \\ s \leftarrow_{\$} \mathcal{X}_1}} ((x, x^*, r, \Gamma(s)) \in \mathbb{R}). $$

The proof is given in Section B. Note that, the second term on the right hand side rules out trivial relations.

### WCitD (Weak Collisions-in-the-dark) Game

Let $\mathcal{X} = \mathcal{X}_0 \times \mathcal{X}_1$ and $\mathcal{Y}$ be two finite sets, where $\mathcal{X}_1 = \{0,1\}^n$. Let $\Gamma : \mathcal{X}_1 \to \mathcal{Y}$ be a random oracle. Fix some relation $\mathbb{R} \in \mathcal{X}^2 \times \mathcal{Y}^2$. The WCitD game is played between a challenger and an adversary $\mathcal{A}$.

**Phase 1:** The adversary $\mathcal{A}$ makes $p$ quantum queries to the random oracle $\Gamma$ and returns a set $\mathcal{X}^* \subseteq \mathcal{X}$ such that $|\mathcal{X}^*| = q$.

**Phase 2:** The challenger samples a key $k \leftarrow_{\$} \mathcal{X}_1$.

We say that $\mathcal{A}$ wins if the following event holds:

$$ \mathbf{WC}_{\mathbb{R}}(\mathcal{X}^*) : \exists x, x' \in \mathcal{X}^*, x \neq x', \text{ such that } (x, x', \Gamma(k \oplus x_1), \Gamma(k \oplus x_1^*)) \in \mathbb{R}. $$

The advantage of $\mathcal{A}$ in WCitD is defined as $\Pr(\mathbf{WC}_{\mathbb{R}}(\mathcal{X}^*))$ where the randomness is induced by $\mathcal{A}$'s coins, the $\Gamma$ and $k$. Note that, WCitD is weaker than SCitD in the sense that any adversary that can win SCitD can also win WCitD. We prove the following result on weak collisions-in-the-dark.
**Lemma 2.** [Weak Collisions-in-the-dark] For any p-query adversary A in the weak collisions-in-the-dark game with respect to the relation R:

$$ \Pr_{\mathcal{X}^* \leftarrow A}(\mathrm{WC}_{\mathbb{R}}(\mathcal{X}^*)) \le 1.5q \sqrt{\frac{p}{2^n}} + q^2 \max_{\substack{x,x' \in \mathcal{X}_1 \\ r \leftarrow \mathcal{S}}} \Pr_{s \leftarrow \mathcal{X}_1}((x, x', r, \Gamma(s)) \in \mathbb{R}). $$

The proof is given in Section B.

## 2.6 Making Multi-Oracle Algorithms Static

We use a result from Don, Fehr and Huang [DFH22]. Let $n \in \mathbb{N}$. Consider an adversary accessing multiple oracles $O_1, O_2, \dots, O_n$, either classical or quantum. We denote as $\mathbf{q} = (q_1, \dots, q_n)$ an upper bound on the total number of queries made to $O_1, \dots, O_n$ respectively. In general, the order in which the (adaptive) adversary queries the different oracles can vary between two executions. The case of a static adversary, which queries the oracles in a fixed order, is much easier to analyze. Fortunately, there is a reduction from adaptive to static adversaries, as follows.

**Proposition 3 (Theorem 1 in [DFH22])**. There exists a polynomial-time interactive oracle algorithm $\mathcal{B}$, such that for any $\mathbf{q} := (q_1, \dots, q_n)$ and any adaptive $\mathbf{q}$-query oracle algorithm $\mathcal{A}^{O_1, \dots, O_n}$, the oracle algorithm $\mathcal{B}[\mathcal{A}](\mathbf{1}^q)$ is a static $\mathbf{nq}$-query oracle algorithm that is functionally equivalent to $\mathcal{A}$ for all stateless instantiations of the oracles $O_1, \dots, O_n$.

This result is valid both for classical and quantum access to the oracles $O_1, \dots, O_n$. It relies on the definition of a fixed sequence of oracle choices with $\mathbf{nq} = (nq_1, \dots, nq_n)$ queries, in which any possible sequence with at most $\mathbf{q}$ queries can be embedded. The oracle algorithm $\mathcal{B}[\mathcal{A}]$ can then adaptively choose to perform a dummy query and discard its result, or to keep it depending on the next query that is asked for by $\mathcal{A}$.

We will use this result for a pair of oracles $O_1, O_2$, where one of them is queried classically and the other quantumly.

# 3 Key-Alternating Feistel Network

In this section, we give formal definitions of permutation- and function-based key-alternating Feistel networks. We also give results on their post-quantum security when the functions (resp. permutations) are independent (Section 3.3).

## 3.1 Function-based Instantiation

For any function $f: \{0,1\}^n \to \{0,1\}^n$, the one-round Key Alternating Feistel (KAF) $F^f: \{0,1\}^n \times \{0,1\}^{2n} \to \{0,1\}^{2n}$ is a keyed permutation based on $f$ that is defined by the mapping:

$$ F_k^f(x_0, x_1) := (x_1, x_0 \oplus f(x_1 \oplus k)), \quad (4) $$

for any $k, x_0, x_1 \in \{0,1\}^n$. For a sequence of functions $f^{(r)} = (f_1, \dots, f_r)$, the $r$-round Key Alternating Feistel $F^{f^{(r)}}: \{0,1\}^{rn} \times \{0,1\}^{2n} \to \{0,1\}^{2n}$ is a keyed permutation based on $f^{(r)}$ that is defined by the mapping:

$$ F_k^{f^{(r)}}(x_0, x_1) := F_{k_r}^{f_r} \circ \dots \circ F_{k_1}^{f_1}(x_0, x_1), \quad (5) $$

for any $k = (k_1, \dots, k_r) \in \{0,1\}^{rn}$, and $x_0, x_1 \in \{0,1\}^n$. See Fig. 1 for an illustration. Throughout the paper, we use notations analogous to Fig. 1 in context of function-based KAF. The input to the $i$-th round function $f_i$ is given by $x_i \oplus k_i$ and the corresponding output must satisfy the relation:

$$ f_i(x_i) := x_{i-1} \oplus x_{i+1} \quad (6) $$

for all $i \in \{1, \dots, r\}$, and $F_k^{f^{(r)}}(x_0, x_1) := (x_r, x_{r+1})$.
<figure><img src="image_2.png" /><figcaption>Fig. 1: Function-based (left) and permutation-based (right) 4-round Key Alternating Feistel. The 3-round version is obtained by removing the last round.</figcaption></figure>

## 3.2 Permutation-based Instantiation

For any permutation $\pi$ of $\{0,1\}^n$, the one-round Key Alternating Feistel $F^f : \{0,1\}^{2n} \times \{0,1\}^{2n} \rightarrow \{0,1\}^{2n}$ is a keyed permutation based on $\pi$ that is defined by the mapping:

$$F_k^{\pi}(x_0, x_1) := (x_1, x_0 \oplus k_2 \oplus \pi(x_1 \oplus k_1)), \qquad (7)$$

for any $k = (k_1, k_2) \in \{0,1\}^{2n}$, and $x_0, x_1 \in \{0,1\}^n$. For a sequence of permutations $\pi^{(r)} = (\pi_1, \dots, \pi_r)$, the r-round Key Alternating Feistel $F^{\pi^{(r)}} : \{0,1\}^{rn} \times \{0,1\}^{2n} \rightarrow \{0,1\}^{2n}$ is a keyed permutation based on $\pi^{(r)}$ that is defined by the mapping:

$$F_k^{\pi^{(r)}}(x_0, x_1) := F_{k_r}^{\pi_r} \circ \dots \circ F_{k_1}^{\pi_1}(x_0, x_1), \qquad (8)$$

for any $k = (k_1, \dots, k_r) \in \{0,1\}^{2rn}$, and $x_0, x_1 \in \{0,1\}^n$, where $k_i = (k_{i1}, k_{i2})$. See Fig. 1 for an illustration of Key Alternating Feistel based on permutations. Throughout the paper, we use the following notations in the context of permutation-based KAF. The input to the i-th round function $\pi_i$ is given by $x_i \oplus k_{i1}$ and the corresponding output must satisfy the relation:

$$\pi_i(x_i) := x_{i-1} \oplus x_{i+1} \oplus k_{i2} \qquad (9)$$

for all $i \in \{1, \dots, r\}$, and $F_k^{\pi^{(r)}}(x_0, x_1) := (x_r, x_{r+1})$.

## 3.3 Initial Observations on the Post-Quantum Security of KAF

In the case where the functions (resp. permutations) used are uniform and independent; it is possible to prove the post-quantum security of KAF using more direct arguments.
**Permutation-based KAF.** We now consider instantiating the sequence of permutations in the definition given by Eq. (8) by a sequence of mutually independent and uniform random permutations $\pi^{(r)}$ over $\{0, 1\}^n$.

Observe that, in a permutation-based KAF, for any $i \in \{1, \dots, r\}$, the mapping $x_i \mapsto x_{i-1} \oplus x_{i+1}$ is given by the well-known Even-Mansour cipher [LR85], which operates using a secret key pair $(k_{i1}, k_{i2})$ and a publicly known permutation $\pi$, and is defined by the mapping:

$$E^{\pi} : (k_{i1}, k_{i2}, x) \mapsto \pi(k_{i1} \oplus x) \oplus k_{i2}.$$

In [ABKM22], Alagic et al. proved the post-quantum security of the Even-Mansour cipher $E^{\pi}$, which we restate in the following theorem (reformulated in our language):

**Theorem 1.** For any adversary $\mathcal{A}$ that makes $q$ classical queries to $E^{\pi}$ and $p$ quantum queries to $\pi$, it holds that

$$\mathbf{Advt}_{E^{\pi}}^{\text{pq-sprp}}(\mathcal{A}) \le 10q\sqrt{\frac{p}{2^n}} + 10p\sqrt{\frac{q}{2^n}}.$$

This leads to the following corollaries on the security of $F^{\pi^{(3)}}$ and $F^{\pi^{(4)}}$, the detailed proofs of which we include in Section C.

**Corollary 1.** For any adversary $\mathcal{A}$ that makes $q$ classical queries to $F^{\pi^{(3)}}$ and $p$ quantum queries to $\pi^{(3)}$, it holds that

$$\mathbf{Advt}_{F^{\pi^{(3)}}}^{\text{pq-prp}}(\mathcal{A}) \le 30q\sqrt{\frac{p}{2^n}} + 30p\sqrt{\frac{q}{2^n}} + \frac{3.5q^2}{2^n}.$$

*Proof (Sketch).* The first step is a boilerplate hybrid argument that replaces the mapping $x_i \mapsto x_{i-1} \oplus x_{i+1}$ for all $i \in [4]$ with the corresponding Even-Mansour instance. Since all these instances are independent, we can implement this replacement with a cost of $3\mathbf{Advt}_{E^{\pi}}^{\text{pq-sprp}}(\mathcal{A})$. Beyond this point the proof simply employs the PRP-PRF switch lemma [BR06] and the well-known Luby-Rackoff bound [LR85]. □

**Corollary 2.** For any adversary $\mathcal{A}$ that makes $q$ classical queries to $F^{\pi^{(4)}}$ and $p$ quantum queries to $\pi^{(4)}$, it holds that

$$\mathbf{Advt}_{F^{\pi^{(4)}}}^{\text{pq-sprp}}(\mathcal{A}) \le 40q\sqrt{\frac{p}{2^n}} + 40p\sqrt{\frac{q}{2^n}} + \frac{4.5q^2}{2^n}.$$

*Proof (Sketch).* Using a similar hybrid argument as above we replace the mapping $x_i \mapsto x_{i-1} \oplus x_{i+1}$ for all $i \in [4]$ with the corresponding Even-Mansour instance. Now, we can simply use the classical SPRP bound from [LR88] to complete the proof. □

**Function-based KAF.** A similar hybrid argument trick will also be used when we instantiate the sequence of functions in the definition given by Eq. (5) by a sequence of mutually independent and uniform random functions $\Gamma^{(r)} : \{0, 1\}^n \to \{0, 1\}^n$.

However, in order to apply this approach, we have to show an appropriate post-quantum security bound for the blind hash construction $\Gamma^{\oplus} : \{0, 1\}^m \times \{0, 1\}^m \to \{0, 1\}^n$ which is defined by the mapping:

$$(k_i, x) \mapsto \Gamma(k_i \oplus x),$$

where $\Gamma$ is a uniform random function from $\{0, 1\}^m$ to $\{0, 1\}^n$. In Section D we prove the following result.

**Theorem 2.** For any computationally unbounded adversary $\mathcal{A}'$ that makes $q'$ classical queries to $\Gamma^{\oplus}$ and $p'$ quantum queries to $\Gamma$, it holds that

$$\mathbf{Advt}_{\Gamma^{\oplus}}^{\text{pq-prf}}(\mathcal{A}') \le 4p'\sqrt{\frac{2q'}{2^m}} + 3q'\sqrt{\frac{2p'}{2^m}} + \frac{4q'^2}{2^m}.$$

With proofs similar to the permutation case (except that there is no PRF-PRP switching), this immediately gives the following corollaries on the security of $F^{\Gamma^{(3)}}$ and $F^{\Gamma^{(4)}}$ by setting $m = n$.
**Corollary 3.** For any adversary $\mathcal{A}$ that makes $q'$ classical queries to the construction and $p'$ quantum queries to $\Gamma^{(3)}$, it holds that

$$ \mathbf{Advt}_{\mathbb{F}^{\Gamma^{(3)}}}^{\text{pq-prp}}(\mathcal{A}) \leq 12p' \sqrt{\frac{2q'}{2^n}} + 9q' \sqrt{\frac{2p'}{2^n}} + \frac{12.5q'^2}{2^n}. $$

**Corollary 4.** For any adversary $\mathcal{A}$ that makes $q'$ classical queries to the construction and $p'$ quantum queries to $\Gamma^{(4)}$, it holds that

$$ \mathbf{Advt}_{\mathbb{F}^{\Gamma^{(4)}}}^{\text{pq-sprp}}(\mathcal{A}) \leq 16p' \sqrt{\frac{2q'}{2^n}} + 12q' \sqrt{\frac{2p'}{2^n}} + \frac{16.5q'^2}{2^n}. $$

# 4 Security of 3-round KAF with Identical Functions

In this section we prove the post-quantum security of 3-round KAF with relaxed assumptions on the primitive, namely, all the primitives are identically instantiated with a single uniform random function $\Gamma: \{0, 1\}^n \to \{0, 1\}^n$. Thus, $\Gamma^{(3)} = (\Gamma, \Gamma, \Gamma)$. We now show that this relaxed variant, which we call $\mathbb{F}_k^{\Gamma}$, achieves post-quantum PRP security when $k = (k_1, k_2, k_3) \leftarrow_{\$} \{0, 1\}^{3n}$.

The proof roughly goes as follows. We use a series of hybrids indexed by $i$ ($\mathbf{H}_i$), where the first $i$ classical queries (and all quantum queries made between them) are answered by random oracles; in addition, each hybrid aborts when the classical query transcript is invalid (or more precisely, answers $\perp$ to subsequent classical queries). The PRP advantage is then expressed depending on the probability to output 1, or to obtain a bad transcript, in all these games. For the last hybrid (all random) we use the collisions-in-the-dark game to bound the probability of a bad transcript.

To hop between two games $\mathbf{H}_i$, we use a hybrid $\hat{\mathbf{H}}_i$ in which the next classical query is reprogrammed. This is where we use first the ARP (Lemma 3), then the ARS (Lemma 4) bounds, and in addition the collisions-in-the-dark game again.

**Theorem 3.** For any computationally unbounded adversary $\mathcal{A}'$ that makes $q'$ classical queries to the construction and $p'$ quantum primitive queries, it holds that

$$ \mathbf{Advt}_{\mathbb{F}^{\Gamma}}^{\text{pq-prp}}(\mathcal{A}') \leq 4p' \sqrt{\frac{4q'}{2^n}} + 12q' \sqrt{\frac{2p'}{2^n}} + \frac{50q'^2}{2^n}. $$

*Proof.* We replace $\mathcal{A}'$ which makes an adaptive choice of the sequence in which it accesses its oracle, with $\mathcal{A}$ that fixes a non-adaptive pattern of oracle access. By Proposition 3, such an adversary $\mathcal{A}$ exists and it makes at most $q = 2q'$ classical queries to the construction and $p = 2p'$ quantum queries to the primitives. Henceforth, we work with this modified adversary $\mathcal{A}$.

Let $\Pi$ denote a uniform random permutation of $\{0, 1\}^{2n}$ sampled independent of $\Gamma$. The goal of $\mathcal{A}$ is to distinguish between the *real world* ($\mathbb{F}^{\Gamma}$, $\Gamma$) and the *ideal world* ($\Pi$, $\Gamma$), where the first oracle from the left in both worlds only allows classical access and the second oracle provides quantum access. For convenience, we write $\mathbb{F}^{\Gamma}$.

We divide $\mathcal{A}$'s query phase into $(q+1)$ epochs $0, \dots, q$, where the $i$-th epoch is represented by the sequence of primitive queries after the $i$-th classical query and before the $(i+1)$-th classical query. In particular, $i=0$ represents the epoch before the first classical query, and $i=q$ represents the epoch after the final classical query. Let $p_i$ denote the number of primitive queries in the $i$-th epoch. We will use the notations developed in Section 3.

For any $i \in \{1, \dots, q\}$, let $\tau_i = \{(x_0^1, x_1^1), (x_3^1, x_4^1)\}, \dots, ((x_0^i, x_1^i), (x_3^i, x_4^i))\}$ denote the set of first $i$ classical query-response tuples, where $(x_0^j, x_1^j)$ denotes the $j$-th query and $(x_3^j, x_4^j)$ denotes the corresponding response for all $j \in [i]$. Let $\tau_0 = \emptyset$. For any $i \in [q]$ and any $k = (k_1, k_2, k_3) \in \{0, 1\}^{3n}$, we define the associated Feistel round-2 set $\nu_{i,k}^{(2)}$ and Feistel round-3 set $\nu_{i,k}^{(3)}$ as follows:

$$ \nu_{i,k}^{(2)} := \{(x_2^1 \oplus k_2, x_1^1 \oplus x_3^1), \dots, (x_2^i \oplus k_2, x_1^i \oplus x_3^i)\}, $$

$$ \nu_{i,k}^{(3)} := \{(x_3^1 \oplus k_3, x_2^1 \oplus x_4^1), \dots, (x_3^i \oplus k_3, x_2^i \oplus x_4^i)\}, $$
where $x_2^j = x_0^j \oplus \Gamma(x_1^j \oplus k_1)$ for all $j \in [i]$. With a slight abuse of notations, we write $x \in \nu_{i,k}^{(j)}$ to mean that there exists a tuple $(x, y) \in \nu_{i,k}^{(j)}$. Let $\nu_{i,k}^{(1)} = \{x_1^j \oplus k_1 : j \in [i]\}$. We further define the associated *reprogramming set* as $\nu_{i,k} := \nu_{i,k}^{(2)} \cup \nu_{i,k}^{(3)}$. We say that $\nu_{i,k}$ is valid if:

- $x_2^1 \oplus k_2, \dots, x_2^i \oplus k_2$ are pairwise distinct,

- $x_3^1 \oplus k_3, \dots, x_3^i \oplus k_3$ are pairwise distinct,

- for all $j, j' \in [q]$ and distinct $r, r' \in \{1, 2, 3\}$, $x_r^j \oplus k_r \neq x_{r'}^{j'} \oplus k_{r'}$,

and invalid otherwise. Note that the first two conditions of validity imply that $\nu_{i,k}^{(2)}$ and $\nu_{i,k}^{(3)}$ define the input-output tuples to $\Gamma$ in a functionally consistent manner, respectively, assuming the transcript $\tau_i$ is obtained using some permutation of $\{0, 1\}^{2n}$ (not necessarily $F_k^\Gamma$). Additionally, the final condition implies that no two distinct round inputs collide. For any valid $\nu_{i,k}$, recall that $\Gamma^{\nu_{i,k}}$ denotes the locally-redefined copy of $\Gamma$.

<table><caption>Fig. 2: Pseudocode for $H_i$ (left) and $\hat{H}_i$ (right) from the proof of Theorem 3.</caption><thead><tr><th>Game H<sub>i</sub>(Π, Γ, A)</th><th>Game ̂H<sub>i</sub>(Π, Γ, A)</th></tr></thead><tbody><tr><td>1: j &larr; 0 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // epoch tracker</td><td>1: j &larr; 0 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // epoch tracker</td></tr><tr><td>2: v &larr; ∅</td><td>2: v &larr; ∅</td></tr><tr><td>3: k &larr; $\{0, 1\}^{3n}$</td><td>3: k &larr; $\{0, 1\}^{3n}$</td></tr><tr><td>4: (k<sub>1</sub>, k<sub>2</sub>, k<sub>3</sub>) &larr; k</td><td>4: (k<sub>1</sub>, k<sub>2</sub>, k<sub>3</sub>) &larr; k</td></tr><tr><td>5: Γ* &larr; Γ</td><td>5: Γ* &larr; Γ</td></tr><tr><td>6: b &larr; A<sup>CO<sub>i</sub>(·)</sup>|<sup>Γ<sup>*</sup>(·)</sup></td><td>6: b &larr; A<sup>hCO<sub>i</sub>(·)</sup>|<sup>Γ<sup>*</sup>(·)</sup></td></tr><tr><td>7: return b</td><td>7: return b</td></tr><tr><td>CO<sub>i</sub>(x<sub>0</sub>, x<sub>1</sub>)</td><td>hCO<sub>i</sub>(x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td>1: j &larr; j + 1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // advance epoch</td><td>1: j &larr; j + 1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // advance epoch</td></tr><tr><td>2: if j &le; i then</td><td>2: if j &le; i + 1 then</td></tr><tr><td>3: (x<sub>3</sub>, x<sub>4</sub>) &larr; Π(x<sub>0</sub>, x<sub>1</sub>)</td><td>3: (x<sub>3</sub>, x<sub>4</sub>) &larr; Π(x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td>4: x<sub>2</sub> &larr; x<sub>0</sub> &oplus; Γ(x<sub>1</sub> &oplus; k<sub>1</sub>)</td><td>4: x<sub>2</sub> &larr; x<sub>0</sub> &oplus; Γ(x<sub>1</sub> &oplus; k<sub>1</sub>)</td></tr><tr><td>5: v &larr; v &cup; {(x<sub>2</sub> &oplus; k<sub>2</sub>, x<sub>1</sub> &oplus; x<sub>3</sub>)}</td><td>5: v &larr; v &cup; {(x<sub>2</sub> &oplus; k<sub>2</sub>, x<sub>1</sub> &oplus; x<sub>3</sub>)}</td></tr><tr><td>6: v &larr; v &cup; {(x<sub>3</sub> &oplus; k<sub>3</sub>, x<sub>2</sub> &oplus; x<sub>4</sub>)}</td><td>6: v &larr; v &cup; {(x<sub>3</sub> &oplus; k<sub>3</sub>, x<sub>2</sub> &oplus; x<sub>4</sub>)}</td></tr><tr><td>7: return (x<sub>3</sub>, x<sub>4</sub>)</td><td>7: if j = i + 1 and v is valid then</td></tr><tr><td>8: elsif j = i + 1 and v is valid then</td><td>8: Γ* &larr; Γ<sup>v</sup></td></tr><tr><td>9: Γ* &larr; Γ<sup>v</sup></td><td>9: endif</td></tr><tr><td>10: return F<sub>k</sub><sup>Γ</sup>(x<sub>0</sub>, x<sub>1</sub>)</td><td>10: return (x<sub>3</sub>, x<sub>4</sub>)</td></tr><tr><td>11: elsif v is invalid then</td><td>11: elsif v is invalid then</td></tr><tr><td>12: return ⊥</td><td>12: return ⊥</td></tr><tr><td>13: else</td><td>13: else</td></tr><tr><td>14: return F<sub>k</sub><sup>Γ</sup>(x<sub>0</sub>, x<sub>1</sub>)</td><td>14: return F<sub>k</sub><sup>Γ</sup>(x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td>15: endif</td><td>15: endif</td></tr></tbody></table>

Now, let $H_0, \dots, H_q$ denote a sequence of $q+1$ hybrids, where $H_i$ is defined as follows (pseudocode in Figure 2):

1. Sample $k = (k_1, k_2, k_3) \leftarrow \{0, 1\}^{3n}$.
2. Answer the first $i$ classical queries from $\mathcal{A}$ using $\Pi$ and the quantum queries from $\mathcal{A}$ in the first $i$ epochs (which ends when the $(i+1)$-st classical query is made) using $\Gamma$.

3. If $\nu_{i,k}$ is invalid then:

(a) Answer all subsequent classical queries from $\mathcal{A}$ with the error symbol $\perp$.

(b) Answer all subsequent quantum queries from $\mathcal{A}$ using $\Gamma$.

4. Else,

(a) Answer all subsequent classical queries from $\mathcal{A}$ using $\mathbb{F}_k^\Gamma$.

(b) Answer all subsequent quantum queries from $\mathcal{A}$ using $\Gamma^{\nu_{i,k}}$.

Since $\tau_0 = \emptyset$, we deduce that $\mathbf{H}_0$ corresponds to $\mathcal{A}$'s interaction with the real world. Similarly, one can easily notice that $\mathbf{H}_q$ corresponds to $\mathcal{A}$'s interaction with the ideal world. Thus, we have

$$ \mathbf{Advt}_{\Gamma}^{\text{pq-prp}}(\mathcal{A}) = |\Pr(\mathbf{E}_0) - \Pr(\mathbf{E}_q)|. \qquad (10) $$

For $i \in \{0, 1, \dots, q\}$, let $\mathbf{F}_i$ denote the event that $\nu_{i,k}$ is invalid, and $\mathbf{E}_i$ denote the event that $\mathcal{A}$ returns 1 in the random experiment $\mathbf{H}_i$. Then, the triangle inequality gives:

$$ \begin{aligned} |\Pr(\mathbf{E}_0) - \Pr(\mathbf{E}_q)| &= |\Pr(\mathbf{E}_0) - \Pr(\mathbf{E}_q \wedge \neg \mathbf{F}_q) - \Pr(\mathbf{E}_q \wedge \mathbf{F}_q)| \\ &\leq |\Pr(\mathbf{E}_0) - \Pr(\mathbf{E}_q \wedge \neg \mathbf{F}_q)| + \Pr(\mathbf{F}_q) \\ &\leq \left( \sum_{i=0}^{q-1} |\Pr(\mathbf{E}_i \wedge \neg \mathbf{F}_i) - \Pr(\mathbf{E}_{i+1} \wedge \neg \mathbf{F}_{i+1})| \right) + \Pr(\mathbf{F}_q). \end{aligned} \qquad (11) $$

*Claim.* We claim:

$$ \Pr(\mathbf{F}_q) \leq 1.5q \sqrt{\frac{p}{2^n}} + \frac{6q^2}{2^n}. \qquad (12) $$

*Proof (of Claim).* Recall that the event $\mathbf{F}_q$ occurs in the hybrid $\mathbf{H}_q$ which can be viewed as a string of oracle calls:

$$ \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{q \text{ classical queries}} $$

Next, we can write $\mathbf{F}_q = \mathbf{bad}_1 \cup \mathbf{bad}_2 \cup \mathbf{bad}_3$, where:

- $\mathbf{bad}_1$: there exists distinct $j, j' \in [q]$ such that $x_2^j = x_2^{j'}$;

- $\mathbf{bad}_2$: there exists distinct $j, j' \in [q]$ such that $x_3^j = x_3^{j'}$;

- $\mathbf{bad}_3$: there exists $j, j' \in [q]$ and distinct $r, r' \in \{1, 2, 3\}$ such that

$$ x_r^j \oplus k_r \neq x_{r'}^{j'} \oplus k_{r'}. $$

Now we have $\Pr(\mathbf{bad}_2) \leq q^2/(2^n - 1)$, since any pair of $j, j'$ satisfy this condition with at most $1/(2^n - 1)$ probability (due to the uniformity of $\Pi$). Next, using the uniformity of $k_r \oplus k_{r'}$, we have that $\Pr(\mathbf{bad}_3) \leq 3q^2/2^n$.

For $\mathbf{bad}_1$ we cannot use the randomness of either the random permutation $\Pi$ or the key $k$ directly. The only randomness here is due to $\Gamma$. So, we have to somehow argue that even after quantum access to $\Gamma$ it is hard for the adversary to produce a pair of inputs $(x_0^j, x_1^j)$ and $(x_0^{j'}, x_1^{j'})$ such that they satisfy the relation $\mathbb{R}$ given by:

$$ x_2^j = \Gamma(x_1^j \oplus k_1) \oplus x_0^j = \Gamma(x_1^{j'} \oplus k_1) \oplus x_0^{j'} = x_2^{j'}. $$

This is where the Collisions-in-the-dark game comes in handy. In particular, given the independence of $\Gamma$ and $\Pi$ we can reinterpret the above event as if the adversary $\mathcal{A}$ is playing the WCitD game with respect to $\mathbb{R}$ and produces the set $\mathcal{X}^* = \{(x_0^1, x_1^1), \dots, (x_0^q, x_1^q)\}$. Then, using Lemma 2, we have

$$ \Pr(\mathbf{bad}_1) = \Pr_{\mathcal{X}^* \leftarrow \mathcal{A}} (\mathrm{WC}_{\mathbb{R}}(\mathcal{X}^*)) $$
$$
\begin{align*}
&\le 1.5q \sqrt{\frac{p}{2^n}} + q^2 \max_{x,x' \in \{(0,1)^n\}^2} \Pr_{\substack{r \leftarrow_S \mathcal{Y} \\ s \leftarrow_S \mathcal{X}_1}} ((x, x', r, \Gamma(s)) \in \mathbb{R}) \\
&\le 1.5q \sqrt{\frac{p}{2^n}} + q^2 \max_{x,x' \in \mathcal{X}_1} \Pr_{\substack{r \leftarrow_S \mathcal{Y} \\ s \leftarrow_S \mathcal{X}_1}} (r \oplus \Gamma(s) = x_0 \oplus x_0') \\
&\le 1.5q \sqrt{\frac{p}{2^n}} + \frac{q^2}{2^n}.
\end{align*}
$$

The claim in Eq. (12) is obtained by accumulating the bound for each of the bad events.

<figure><img src="image_3.png" /></figure>

All that remains is to bound $|\Pr(E_i \wedge \neg F_i) - \Pr(E_{i+1} \wedge \neg F_{i+1})|$ for all $i \in \{0, \dots, q-1\}$, which is incidentally the technical core of this proof (which is also quite similar to the steps done in [ABKM22]). For any $i \in \{0, \dots, q-1\}$, assuming the hybrid does not abort, $\mathbf{H}_i$ can be viewed as a string of oracle calls made by $\mathcal{A}$

$$
\underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \underbrace{F_k^{\Gamma} \Gamma^{\nu_{i,k}} \dots F_k^{\Gamma} \Gamma^{\nu_{i,k}}}_{q-i \text{ classical queries}}
$$

where each occurrence of $\Pi$ (res. $\Gamma^\Gamma$) indicates a single classical query and each occurrence of $\Gamma$ (res. $\Gamma^{\nu_{i,k}}$) indicates
the sequence of primitive queries in the $i$-th epoch. In this representation, we want to compare:

$$
\begin{align*}
\mathbf{H}_i: & \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \quad \underbrace{F_k^{\Gamma} \Gamma^{\nu_{i,k}}}_{q-i-1 \text{ classical queries}} \\
\mathbf{H}_{i+1}: & \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \quad \underbrace{F_k^{\Gamma} \Gamma^{\nu_{i+1,k}}}_{q-i-1 \text{ classical queries}}
\end{align*}
$$

To aid this comparison we introduce an intermediate hybrid $\hat{\mathbf{H}}_i$ which is defined as follows (pseudocode in Figure 2):

1. Sample $k = (k_1, k_2, k_3) \leftarrow \$ \{0, 1\}^{3n}$.

2. Answer the first $i + 1$ classical queries from $\mathcal{A}$ using $\Pi$ and the quantum queries from $\mathcal{A}$ in the first $i$ epochs (which ends when the $(i+1)$-st classical query is made) using $\Gamma$.

3. If $\nu_{i+1,k}$ is invalid then:

(a) Answer all classical queries from $\mathcal{A}$ with the error symbol $\perp$.

(b) Answer all quantum queries from $\mathcal{A}$ using $\Gamma$.

4. Else,

(a) Answer all classical queries from $\mathcal{A}$ using $F_k^\Gamma$.

(b) Answer all quantum queries from $\mathcal{A}$ using $\Gamma^{\nu_{i+1,k}}$.

For $i \in \{0, \dots, q-1\}$, let $\hat{\mathbf{F}}_i$ denote the event that $\nu_{i+1,k}$ is invalid in hybrid $\hat{\mathbf{H}}_i$, and $\hat{\mathbf{E}}_i$ denote the event that $\mathcal{A}$ returns 1 in the random experiment $\hat{\mathbf{H}}_i$. Again assuming the hybrid does not abort, the corresponding string representation is given by

$$
\underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \quad \underbrace{F_k^{\Gamma} \Gamma^{\nu_{i+1,k}} \dots F_k^{\Gamma} \Gamma^{\nu_{i+1,k}}}_{q-i-1 \text{ classical queries}}
$$

Now, we compare the following hybrids in pairs from top to bottom:

$$
\begin{align*}
\mathbf{H}_i: & \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \quad \begin{array}{c} \textcolor{blue}{F_k^{\Gamma}} \\ \Gamma^{\nu_{i,k}} \end{array} \quad \underbrace{F_k^{\Gamma} \Gamma^{\nu_{i,k}} \dots F_k^{\Gamma} \Gamma^{\nu_{i,k}}}_{q-i-1 \text{ classical queries}} \\
\hat{\mathbf{H}}_i: & \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \quad \begin{array}{c} \textcolor{magenta}{\Gamma} \\ \Gamma^{\nu_{i+1,k}} \end{array} \quad \begin{array}{c} \underbrace{F_k^{\Gamma} \Gamma^{\nu_{i+1,k}} \dots F_k^{\Gamma} \Gamma^{\nu_{i+1,k}}}_{q-i-1 \text{ classical queries}} \\ \Gamma^{\nu_{i+1,k}} \end{array} \\
\mathbf{H}_{i+1}: & \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \quad \begin{array}{c} \textcolor{blue}{\Gamma} \\ \Gamma \end{array} \quad \begin{array}{c} \underbrace{F_k^{\Gamma} \Gamma^{\nu_{i+1,k}} \dots F_k^{\Gamma} \Gamma^{\nu_{i+1,k}}}_{q-i-1 \text{ classical queries}} \\ \Gamma^{\nu_{i+1,k}} \end{array}
\end{align*}
$$
In Lemma 3 and 4 we show that:

$$ \left| \Pr(\hat{\mathbf{E}}_i \wedge \neg \hat{\mathbf{F}}_i) - \Pr(\mathbf{E}_{i+1} \wedge \neg \mathbf{F}_{i+1}) \right| \le 2p_{i+1} \sqrt{\frac{2(i+1)}{2^n}}, \quad (13) $$

$$ \left| \Pr(\mathbf{E}_i \wedge \neg \mathbf{F}_i) - \Pr(\hat{\mathbf{E}}_i \wedge \neg \hat{\mathbf{F}}_i) \right| \le 4.5 \sqrt{\frac{p}{2^n}} + \frac{6q}{2^n} + \frac{q}{2^{2n}}. \quad (14) $$

Using the triangle inequality and Eqs. (14) and (13), we have

$$ \left| \Pr(\mathbf{E}_i \wedge \neg \mathbf{F}_i) - \Pr(\mathbf{E}_{i+1} \wedge \neg \mathbf{F}_{i+1}) \right| \le 2p_{i+1} \sqrt{\frac{2(i+1)}{2^n}} + 4.5 \sqrt{\frac{p}{2^n}} + \frac{6.5q}{2^n}. \quad (15) $$

Substituting Eqs. (15) and (12) in Eq. (11), followed by a sum over all the distances, yields the result. □

**Lemma 3.** For all $i \in \{0, \dots, q-1\}$ we have

$$ \left| \Pr(\hat{\mathbf{E}}_i \wedge \neg \hat{\mathbf{F}}_i) - \Pr(\mathbf{E}_{i+1} \wedge \neg \mathbf{F}_{i+1}) \right| \le 2p_{i+1} \sqrt{\frac{2(i+1)}{2^n}}. $$

*Proof.* Recall that under the assumption that the hybrids do not abort we can have the following string representations for the two hybrids.

<figure><img src="image_4.png" /></figure>

It is clear that the two hybrids are identical, except for the $(i+1)$-th epoch, where $\hat{\mathbf{H}}_i$ uses a locally redefined variant $\Gamma^{\nu_{i+1,k}}$ of $\Gamma$ and $\mathbf{H}_{i+1}$ uses the unchanged $\Gamma$. We will show that this small “reprogramming” of $\Gamma$ does not disturb it too much.

More formally, given the adversary $\mathcal{A}$ we construct an ARP distinguisher $\mathcal{D}$ as follows (note that Phases 1, 2, 3 correspond to Phases 1, 2, 3 in the ARP game respectively).

**Phase 1.A.** for all the queries up to and including the $(i+1)$-th classical query:

1. $\mathcal{D}$ samples a uniform random permutation $\Pi$ of $\{0, 1\}^{2n}$.

2. All classical queries from $\mathcal{A}$ are answered using $\Pi$.

3. All quantum queries from $\mathcal{A}$ are answered using $\mathcal{D}$'s random oracle $\Gamma_b$, where $\Gamma_0 = \Gamma_1 = \Gamma$.

**Phase 1.B.** $\mathcal{D}$ defines the randomized algorithm $\mathcal{B}$:

1. $\mathcal{B}$ initializes a flag $\mathbf{A} \leftarrow 0$.

2. $\mathcal{B}$ samples a key $k = (k_1, k_2, k_3) \leftarrow \{0, 1\}^{3n}$ and computes the set $\nu_{i+1,k}$.

3. If $\nu_{i+1,k} \neq \emptyset$ and invalid, then $\mathcal{B}$ sets $\mathbf{A} \leftarrow 1$ and $\nu_{i+1,k} = \emptyset$.

4. $\mathcal{B}$ returns the set $\nu_{i+1,k}$.

**Phase 2.** This covers the queries in the $(i+1)$-th epoch:

1. $\mathcal{B}$ is run to generate $\nu_{i+1,k}$ and $\mathcal{D}$ is given quantum access to $\Gamma_b$, where $\Gamma_0 = \Gamma$ and $\Gamma_1 = \Gamma^{\nu_{i+1,k}}$. If $\mathbf{A} = 0$, it is easy to see that $\nu_{i+1,k}$ is valid.

2. All quantum queries from $\mathcal{A}$ are answered using $\Gamma_b$.

**Phase 3.** for all the queries beyond and including the $(i+2)$-th classical query:

1. $\mathcal{D}$ receives $k$, and it checks the value of $\mathbf{A}$.

2. If $\mathbf{A} = 1$ then:

(a) All classical queries from $\mathcal{A}$ are answered with the error symbol $\perp$.

(b) All quantum queries from $\mathcal{A}$ are answered using $\Gamma_b$.

3. Else:

(a) $\mathcal{D}$ computes the set $\nu_{i+1,k}$.
(b) All classical queries from $\mathcal{A}$ are answered using $F_k^\Gamma$.

(c) All quantum queries from $\mathcal{A}$ are answered using $\Gamma_{b}^{\nu_{i+1,k}}$.

– If $\mathcal{A} = 1$ then $\mathcal{D}$ returns 0, and otherwise it returns whatever $\mathcal{A}$ returns.

Clearly, $\mathcal{D}$ is a valid ARP distinguisher. When $\mathcal{A} = 0$ and $b = 0$, $\mathcal{D}$ correctly simulates $\mathbf{H}_{j+1}$. Similarly, when $\mathcal{A} = 0$ and $b = 1$, $\mathcal{D}$ correctly simulates $\hat{\mathbf{H}}_i$. Furthermore, for the case $\mathcal{A} = 1$, $\mathcal{D}$'s output is independent of $\mathcal{A}$'s output (although perfect simulation still holds). It also holds that $\mathcal{A} = 1 | b = 1$ is equivalent to $\hat{\mathbf{F}}_i$ and $\mathcal{A} = 1 | b = 0$ is equivalent to $\mathbf{F}_{i+1}$. Due to the identical behaviour of the two hybrids for the first $i$ epochs and the $i+1$-th construction query, we have $\hat{\mathbf{F}}_i \iff \mathbf{F}_{i+1}$ for all $i \in \{0, \dots, q-1\}$. Thus, we have

$$ 
\begin{aligned}
\mathbf{Advt}^{\text{arp}}(\mathcal{D}) &= |\Pr(\mathcal{D}^{\Gamma_b} = 1 | b = 1) - \Pr(\mathcal{D}^{\Gamma_b} = 1 | b = 0)| \\
&\geq |\Pr(\mathcal{D}^{\Gamma_b} = 1 \land \mathcal{A} = 0 | b = 1) - \Pr(\mathcal{D}^{\Gamma_b} = 1 \land \mathcal{A} = 0 | b = 0)| \\
&= |\Pr(\hat{\mathbf{E}}_i \land \neg \hat{\mathbf{F}}_i) - \Pr(\mathbf{E}_{i+1} \land \neg \mathbf{F}_{i+1})|
\end{aligned}
\quad (16) $$

where the first inequality follows from the fact $\mathcal{D}$'s output is completely independent of $\mathcal{A}$ when $\mathcal{A} = 1$ and $\mathcal{A} = 1$ is set with identical probabilities in the two worlds; the last equality is simply a rephrasing due to the aforementioned equivalence.

Finally, to apply Proposition 1, we need to bound $\epsilon_B$, the probability that any point $x$ in the domain of $\Gamma$ is reprogrammed. This can be bounded using the fact that $\Gamma^{\nu_{i+1,k}}$ is identical to $\Gamma$ except on the set $\nu_{i+1,k}$. After fixing $\Gamma$ and $\tau_{i+1}$, the probability that any given $x$ is reprogrammed is at most the probability that $x \in \nu_{i+1,k} = \nu_{i+1,k}^{(2)} \cup \nu_{i+1,k}^{(3)}$. Using the fact that $k_2$ and $k_3$ are uniformly distributed in marginal, union bound yields $\epsilon_B \le 2(i+1)/2^n$. The result then follows from using Proposition 1 in Eq. (16). $\square$

**Lemma 4.** For all $i \in \{0, \dots, q-1\}$ we have

$$ |\Pr(\mathbf{E}_i \land \neg \mathbf{F}_i) - \Pr(\hat{\mathbf{E}}_i \land \neg \hat{\mathbf{F}}_i)| \le 4.5 \sqrt{\frac{p}{2^n}} + \frac{6q}{2^n} + \frac{q}{2^{2n}}. $$

*Proof.* Under the assumption that the hybrids do not abort, we can have the following string representations for the two hybrids.

<figure><img src="image_5.png" /></figure>

Given $\mathcal{A}$ we now construct an ARS-distinguisher $\mathcal{D}$ as follows:

**Phase 1.** for all the queries up to and including the $i$-th epoch:

1. $\mathcal{D}$ samples a uniform random permutation $\Pi: \{0, 1\}^{2n} \to \{0, 1\}^{2n}$.

2. All classical queries from $\mathcal{A}$ are answered using $\Pi$.

3. All quantum queries from $\mathcal{A}$ are answered using $\mathcal{D}$'s random oracle $\Gamma_b$.

**Phase 2.** $\mathcal{D}$ resamples:

1. Suppose $\mathcal{A}$'s $(i+1)$-th classical query is $(x_0^{i+1}, x_1^{i+1})$.

2. It samples $k_1 \leftarrow \{0, 1\}^n$, and computes $x_2^{i+1} = \Gamma(x_1^{i+1} \oplus k_1) \oplus x_0^{i+1}$.

3. $\mathcal{D}$ queries RS with $\perp$ (assuming $\mathcal{X}_1 = \emptyset$) and let the output be $s_2$.

4. It sets $k_2 = s_2 \oplus x_2^{i+1}$ and $x_3^{i+1} = \Gamma(s_2) \oplus x_1^{i+1}$.

5. $\mathcal{D}$ queries RS with $\perp$ (assuming $\mathcal{X}_1 = \emptyset$) and let the output be $s_3$.

6. It sets $k_3 = s_3 \oplus x_3^{i+1}$ and $x_4^{i+1} = \Gamma(s_3) \oplus x_2^{i+1}$.

7. At this stage $\mathcal{D}$ computes the set $\nu_{i,k}$ and $\nu_{i,k}^{(1)}$.

**Phase 3.** for all queries beyond and including the $(i+1)$-th classical query:

1. $\mathcal{D}$ initializes $\mathcal{A} \leftarrow 0$.
<table><caption>Fig. 3: Pseudocode for $H_i^b$ from the proof of Lemma 4. $\mathrm{Perm}_{2n}$ denotes the set of all permutations over $\{0, 1\}^{2n}$. The pseudocode for RS can be found in Fig. 5.</caption><thead><tr><th>Game H<sup>b</sup><sub>i</sub>(Γ<sub>b</sub>, A)</th><th>CO<sup>b</sup><sub>i</sub>(x<sub>0</sub>, x<sub>1</sub>)</th></tr></thead><tbody><tr><td>1: Π ← $ \mathrm{Perm}_{2n} $</td><td>1: j ← j + 1</td></tr><tr><td>2: j ← 0</td><td>2: if j ≤ i then</td></tr><tr><td>3: ν ← ∅</td><td>3: (x<sub>3</sub>, x<sub>4</sub>) ← Π(x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td>4: τ ← ∅</td><td>4: τ ← τ ∪ ((x<sub>0</sub>, x<sub>1</sub>), (x<sub>3</sub>, x<sub>4</sub>))</td></tr><tr><td>5: Γ<sup>*</sup> ← Γ<sub>b</sub></td><td>5: return (x<sub>3</sub>, x<sub>4</sub>)</td></tr><tr><td>6: A ← 0</td><td>6: elsif j = i + 1 then</td></tr><tr><td>7: b ← A<sup>CO<sup>b</sup><sub>i</sub>(·), |Γ<sup>*</sup>(·)</sup></td><td>7: k<sub>1</sub> ← {0, 1}<sup>n</sup></td></tr><tr><td>8: if A = 1 then</td><td>8: x<sub>2</sub> ← x<sub>0</sub> ⊕ Γ<sub>b</sub>(x<sub>1</sub> ⊕ k<sub>1</sub>)</td></tr><tr><td>9: return 0</td><td>9: s<sub>2</sub> ← RS(⊥)</td></tr><tr><td>10: else</td><td>10: k<sub>2</sub> ← s<sub>2</sub> ⊕ x<sub>2</sub></td></tr><tr><td>11: return b</td><td>11: x<sub>3</sub> ← x<sub>1</sub> ⊕ Γ<sub>b</sub>(s<sub>2</sub>)</td></tr><tr><td>12: endif</td><td>12: s<sub>3</sub> ← RS(⊥)</td></tr><tr><td></td><td>13: k<sub>3</sub> ← s<sub>3</sub> ⊕ x<sub>3</sub></td></tr><tr><td></td><td>14: x<sub>4</sub> ← x<sub>2</sub> ⊕ Γ<sub>b</sub>(s<sub>3</sub>)</td></tr><tr><td></td><td>15: k ← (k<sub>1</sub>, k<sub>2</sub>, k<sub>3</sub>)</td></tr><tr><td></td><td>16: for ((x'<sub>0</sub>, x'<sub>1</sub>), (x'<sub>3</sub>, x'<sub>4</sub>)) ∈ τ do</td></tr><tr><td></td><td>17: x'<sub>2</sub> ← x'<sub>0</sub> ⊕ Γ<sub>b</sub>(x'<sub>1</sub> ⊕ k<sub>1</sub>)</td></tr><tr><td></td><td>18: ν ← ν ∪ {(x'<sub>2</sub> ⊕ k<sub>2</sub>, x'<sub>1</sub> ⊕ x'<sub>3</sub>)}</td></tr><tr><td></td><td>19: ν ← ν ∪ {(x'<sub>3</sub> ⊕ k<sub>3</sub>, x'<sub>2</sub> ⊕ x'<sub>4</sub>)}</td></tr><tr><td></td><td>20: endfor</td></tr><tr><td></td><td>21: if ν is valid then</td></tr><tr><td></td><td>22: Γ<sup>*</sup> ← Γ<sup>ν</sup><sub>b</sub></td></tr><tr><td></td><td>23: return (x<sub>3</sub>, x<sub>4</sub>)</td></tr><tr><td></td><td>24: else</td></tr><tr><td></td><td>25: A ← 1</td></tr><tr><td></td><td>26: return ⊥</td></tr><tr><td></td><td>27: endif</td></tr><tr><td></td><td>28: elsif ν is invalid then</td></tr><tr><td></td><td>29: A ← 1</td></tr><tr><td></td><td>30: return ⊥</td></tr><tr><td></td><td>31: else</td></tr><tr><td></td><td>32: return F<sup>Γ<sub>b</sub></sup><sub>k</sub>(x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td></td><td>33: endif</td></tr></tbody></table>
2. If $\nu_{i,k}$ is invalid then:

(a) $\mathcal{D}$ sets $\mathbf{A} \leftarrow 1$.

(b) $\mathcal{D}$ answers all remaining classical queries from $\mathcal{A}$ with the error symbol $\perp$.

(c) $\mathcal{D}$ answers all remaining quantum queries from $\mathcal{A}$ with $\Gamma_b$.

3. Else:

(a) $\mathcal{D}$ answers all remaining classical queries from $\mathcal{A}$ using $\mathbf{F}_k^{\Gamma_b}$.

(b) $\mathcal{D}$ answers all remaining quantum queries from $\mathcal{A}$ using $\Gamma_b^{\nu_{i,k}}$.

If $\mathbf{A} = 1$ then $\mathcal{D}$ returns 0, otherwise it returns whatever $\mathcal{A}$ returns.

For $b \in \{0,1\}$, let $\mathbf{H}_i^b$ denote the above described game, and let $\mathbf{E}_i^b$ denote the event that $\mathcal{A}$ returns 1 in game $\mathbf{H}_i^b$. Unless stated otherwise, in the following discussion assume $\mathbf{A} = 0$.

<table><caption>Fig. 4: Pseudocode for $\hat{\mathbf{H}}_i^1$ from the proof of Lemma 4.</caption><thead><tr><th>Game <span style="text-decoration: overline;">H</span><sub>i</sub><sup>1</sup>(Π, Γ, A)</th><th>hCO<sub>i</sub><sup>1</sup>(x<sub>0</sub>, x<sub>1</sub>)</th></tr></thead><tbody><tr><td>1: j &larr; 0</td><td>1: j &larr; j + 1</td></tr><tr><td>2: ν &larr; ∅</td><td>2: <b>if</b> j ≤ i + 1 <b>then</b></td></tr><tr><td>3: k &larr; $\{0, 1\}^{3n}$</td><td>3: <b>if</b> j = i + 1 <b>then</b></td></tr><tr><td>4: (k<sub>1</sub>, k<sub>2</sub>, k<sub>3</sub>) &larr; k</td><td>4: (x<sub>3</sub>, x<sub>4</sub>) &larr; $\{0, 1\}^{2n}$</td></tr><tr><td>5: Γ<sup>*</sup> &larr; Γ</td><td>5: <b>else</b></td></tr><tr><td>6: b &larr; A<sup>hCO<sub>i</sub><sup>1</sup>(·), |Γ<sup>*</sup>(·)|</sup></td><td>6: (x<sub>3</sub>, x<sub>4</sub>) &larr; Π(x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td>7: <b>return</b> b</td><td>7: <b>endif</b><br>8: x<sub>2</sub> &larr; x<sub>0</sub> ⊕ Γ(x<sub>1</sub> ⊕ k<sub>1</sub>)<br>9: ν &larr; ν ∪ {(x<sub>2</sub> ⊕ k<sub>2</sub>, x<sub>1</sub> ⊕ x<sub>3</sub>)}<br>10: ν &larr; ν ∪ {(x<sub>3</sub> ⊕ k<sub>3</sub>, x<sub>2</sub> ⊕ x<sub>4</sub>)}<br>11: <b>if</b> j = i + 1 and ν is valid <b>then</b><br>12: Γ<sup>*</sup> &larr; Γ<sup>ν</sup><br>13: <b>endif</b><br>14: <b>return</b> (x<sub>3</sub>, x<sub>4</sub>)<br>15: <b>else if</b> ν is invalid <b>then</b><br>16: <b>return</b> ⊥<br>17: <b>else</b><br>18: <b>return</b> F<sub>k</sub><sup>Γ</sup>(x<sub>0</sub>, x<sub>1</sub>)<br>19: <b>endif</b></td></tr></tbody></table>

It is clear that the hybrid $\mathbf{H}_i^0$ is identical to $\mathbf{H}_i$. Indeed, in this case $\mathcal{D}$ answers all the remaining classical queries with $F_k^\Gamma$ and the remaining quantum queries with $\Gamma^{\nu_{i,k}}$. Looking at Phase 3.2 we also observe that $\mathbf{A} = 1 | b = 0$ is identical to $\mathbf{F}_i$. Let $F_i^1$ denote the event $\mathbf{A} = 1 | b = 1$. Then, since $\mathcal{D}$ is a valid ARS distinguisher, we have

$$ \begin{aligned} \mathbf{Advt}^{\text{ars}}(\mathcal{D}) &= |\Pr(\mathcal{D}^{\Gamma_{b,\text{RS}} = 1 | b = 1}) - \Pr(\mathcal{D}^{\Gamma_{b,\text{RS}} = 1 | b = 0})| \\ &\geq |\Pr(\mathcal{D}^{\Gamma_{b,\text{RS}} = 1 | \mathbf{A} = 0 | b = 1}) - \Pr(\mathcal{D}^{\Gamma_{b,\text{RS}} = 1 | \mathbf{A} = 0 | b = 0})| \\ &\geq |\Pr(\mathbf{E}_i^1 \wedge \neg \mathbf{F}_i^1) - \Pr(\mathbf{E}_i \wedge \neg \mathbf{F}_i)|, \end{aligned} \quad (17) $$

where at the second inequality we used the fact that $\mathbf{A} = 0 | b = 0$ is exactly the event $\neg \mathbf{F}_i$.

Now, consider the $\mathbf{H}_i^1$ hybrid. In this case the output $(x_3^{i+1}, x_4^{i+1})$ corresponding to the $(i+1)$-th classical query $(x_0^{i+1}, x_1^{i+1})$ is given by

$$ x_3^{i+1} = y_2 \oplus x_1^{i+1}, $$
$$x_4^{i+1} = y_3 \oplus x_2^{i+1},$$

where $y_2, y_3 \leftarrow \{0, 1\}^n$ correspond to the resampled values of $\Gamma(s_2)$ and $\Gamma(s_3)$, respectively. In other words, $(x_3^{i+1}, x_4^{i+1})$ is uniformly distributed over $\{0, 1\}^{2n}$.

Let $\hat{\mathbf{H}}_i^1$ denote a slight modification of $\hat{\mathbf{H}}_i$ that works exactly the same as $\hat{\mathbf{H}}_i$, except at the $(i+1)$-th classical query, where the output is sampled uniformly from $\{0, 1\}^{2n}$ and independent of $\Pi$. Then, it is quite straightforward$^8$ that:

$$|\Pr(\hat{\mathbf{E}}_i \wedge \neg \hat{\mathbf{F}}_i) - \Pr(\hat{\mathbf{E}}_i^1 \wedge \neg \hat{\mathbf{F}}_i)| \le \frac{q}{2^{2n}} \quad (18)$$

where $\hat{\mathbf{E}}_i^1$ denotes the event that $\mathcal{A}$ returns 1 in $\hat{\mathbf{H}}_i^1$.

Coming back to $\mathbf{H}_i^1$, here $\mathcal{D}$ answers the remaining classical queries with $\mathbb{F}_k^\Gamma$ and the remaining quantum queries are answered using $\Gamma_1^{\nu_{i,k}}$. Consider the following two events:

$$\mathbf{bad}_4: \quad x_2^{i+1} \oplus k_2 \in \nu_{i,k} \cup \nu_{i,k}^{(1)}, \quad (19)$$

$$\mathbf{bad}_5: \quad x_3^{i+1} \oplus k_3 \in \nu_{i,k} \cup \nu_{i,k}^{(1)}. \quad (20)$$

We claim that $\mathbf{H}_i^1$ and $\hat{\mathbf{H}}_i^1$ are identical up to $\mathbf{bad}_4 \lor \mathbf{bad}_5$. Indeed, $\neg \mathbf{bad}_4 \wedge \neg \mathbf{bad}_5$ implies that $(x_3^{i+1}, x_4^{i+1})$ is uniformly distributed over $\{0, 1\}^{2n}$ and it is independent of $\Pi$. Furthermore, assuming $\neg (\mathbf{bad}_4 \lor \mathbf{bad}_5)$, the random oracle $\Gamma$ is essentially reprogrammed on $\nu_{i+1,k}^j$ points in $\mathbf{H}_i^1$, where $2i$ points are reprogrammed directly, since they are part of $\nu_{i,k}$, and exactly two points are reprogrammed indirectly due to the resampling at $s_2 = x^{i+1} \oplus k_2$ and $s_3 = x_3^{i+1} \oplus k_3$. Then, using the fundamental lemma of game-playing technique [BR06], we have

$$|\Pr(\hat{\mathbf{E}}_i^1 \wedge \neg \hat{\mathbf{F}}_i) - \Pr(\hat{\mathbf{E}}_i^1 \wedge \neg \hat{\mathbf{F}}_i)| \le \Pr(\mathbf{bad}_4 \lor \mathbf{bad}_5). \quad (21)$$

Then combining Eqs. (17)-(21) and applying Proposition 2 gives:

$$|\Pr(\mathbf{E}_i \wedge \neg \mathbf{F}_i) - \Pr(\hat{\mathbf{E}}_i \wedge \neg \hat{\mathbf{F}}_i)| \le 3\sqrt{\frac{p}{2^n}} + \frac{q}{2^{2n}} + \Pr(\mathbf{bad}_4 \lor \mathbf{bad}_5). \quad (22)$$

For $\mathbf{bad}_4$, note that, we can write $\mathbf{bad}_4 = \mathbf{bad}_{41} \cup \mathbf{bad}_{42}$, where:

- $\mathbf{bad}_{41}$: there exists $j \in [i]$ such that $x_2^{i+1} = x_2^j$,

- $\mathbf{bad}_{42}$: there exists $j \in [i]$, $r \in \{1, 3\}$ such that $x_2^{i+1} \oplus k_2 = x_r^j \oplus k_r$.

First using the uniformity of $k_2$ (since $s_2$, the resampled point, is uniform), we have $\Pr(\mathbf{bad}_{42}) \le 2i/2^n$. Next, observe that $\mathbf{bad}_{41}$ can be interpreted as if the adversary $\mathcal{A}$ is playing the SCitD game with respect to the relation $\mathbb{R}$ such that the adversary has to output a set of $i$ tuples $\{(x_0^1, x_1^1), \dots, (x_0^i, x_1^i)\}$ and a distinguished point $(x_0^{i+1}, x_1^{i+1})$ such that there exists a $j \in [i]$ satisfying:

$$x_2^{i+1} = \Gamma(k_1 \oplus x_1^{i+1}) \oplus x_0^{i+1} = \Gamma(k_1 \oplus x_1^j) \oplus x_0^j = x_2^j.$$

Thus, using Lemma 1, we have

$$\Pr(\mathbf{bad}_{41}) \le 1.5 \sqrt{\frac{p}{2^n}} + \frac{i}{2^n}.$$

where we use the same argument, as used in the proof of Eq. (12) to arrive at the second term on the RHS. Combining both the cases gives:

$$\Pr(\mathbf{bad}_4) \le 1.5 \sqrt{\frac{p}{2^n}} + \frac{3i}{2^n}. \quad (23)$$

Next, we bound the probability of $\Pr(\mathbf{bad}_5 | \neg \mathbf{bad}_4)$. We again divide $\mathbf{bad}_5$ into two events:

- $\mathbf{bad}_{51}$: there exists $j \in [i]$ such that $x_3^{i+1} = x_3^j$,

<footnote>$^8$ The two games are $q2^{-2n}$-close in statistical distance.</footnote>
- bad$_{52}$ : there exists $j \in [i]$, $r \in \{1, 2\}$ such that $x_3^{i+1} \oplus k_3 = x_r^j \oplus k_r$.

Note that, $x_3^{i+1} \oplus k_3 = s_3 = \Gamma(s_2) \oplus x_1^{i+1}$. Since, $s_2$ is fresh (because $\neg$bad$_4$ holds), the corresponding resampled point $y_2$ is sampled uniformly and independently of all other variables, which immediately gives $\Pr(\mathbf{bad}_{51} | \neg \mathbf{bad}_1) \le i/2^n$. Furthermore, using the uniformity of $k_3$, we have $\Pr(\mathbf{bad}_{52} | \neg \mathbf{bad}_4) \le 2i/2^n$. Accumulating both the bounds yields:

$$ \Pr(\mathbf{bad}_5 | \neg \mathbf{bad}_4) \le \frac{3i}{2^n}. \qquad (24) $$

Finally using Eqs. (23) and (24) in Eq. (22) completes the proof. □

# 5 Post-Quantum Security of 4-round Feistel Network

Let $\Gamma$: $\{0, 1\}^n \to \{0, 1\}^n$ denote a uniform random function and $\Gamma^{(4)} = (\Gamma, \Gamma, \Gamma, \Gamma)$. We now show that the resulting 4-round instance, that we refer to as $F_k^\Gamma$, achieves post-quantum SPRP security when $k = (k_1, k_2, k_3, k_4) \stackrel{\$}{\leftarrow} \{0, 1\}^{4n}$.

**Theorem 4.** For any computationally unbounded adversary $\mathcal{A}'$ that makes $q'$ classical queries to the construction and $p'$ quantum primitive queries, it holds that

$$ \mathbf{Advt}_{\Gamma^\Gamma}^{\text{pq-sprp}}(\mathcal{A}') \le 27q' \sqrt{\frac{3p'}{2^n}} + 6p' \sqrt{\frac{6q'}{2^n}} + \frac{139.5q'^2}{2^n}. $$

*Proof outline.* The high level proof approach for the theorem is as follows:

1. We mimic the hybrids as in the case of 3-round post-quantum PRP proof and arrive at equivalent distance lemmata (Lemmata 5 and 6).

2. We still want to reprogram and resample at $\Gamma$ on inputs corresponding to second and third round of the construction.

3. Earlier, we were doing honest simulation of $\Gamma$ for the first round of the construction. Now, we will honestly simulate $\Gamma$ on first and fourth rounds of the construction. In particular, for encryption queries we will start from the first round and for decryption queries we will start from the fourth round.

4. If everything goes as anticipated in steps 2, 3 and 4, then we should have a post-quantum SPRP proof for 4-round Feistel network at the end.

*Proof.* The proof will follow the same steps as in Section 4, with the same hybrid games (and the same notations), but a different handling of bad events. We first use Proposition 3 to replace $\mathcal{A}'$ by a $\mathcal{A}$ with a non-adaptive pattern of oracle access, making at most $q = 3q'$ (forward or inverse) classical queries to the construction and $p = 3p'$ quantum queries to the primitive. We also split the query phase of $\mathcal{A}$ between $(q+1)$ epochs $0, \dots, q$ where the $i^{\text{th}}$ epoch contains all primitive queries between the $i^{\text{th}}$ and the $(i+1)^{\text{th}}$ classical queries.

Let $\Pi$ denote a uniform random permutation of $\{0, 1\}^{2n}$ sampled independent of $\Gamma$. The goal of $\mathcal{A}$ is to distinguish between the *real world* ($F^\Gamma, \Gamma$) and the *ideal world* ($\Pi, \Gamma$), where the first oracle from the left in both the worlds allows classical access in both directions and the remaining oracles provides quantum access. For convenience, we write $F^\Gamma$.

For any $i \in [q]$, let $\tau_i = \{(\delta^1, (x_0^1, x_1^1), (x_4^1, x_5^1)), \dots, (\delta^i, (x_0^i, x_1^i), (x_4^i, x_5^i))\}$ denote the set of first $i$-classical query-response tuples, transcribed according to the following convention:

- for each $j \in [i]$, $\delta^j$ denotes the direction of the $j^{\text{th}}$ query, with 1 indicating a forward query and -1 indicating an inverse query;

- when $\delta^j = 1$, $(x_0^j, x_1^j)$ denotes the $i^{\text{th}}$ query and $(x_4^j, x_5^j)$ denotes the corresponding response;

- when $\delta^j = -1$, $(x_4^j, x_5^j)$ denotes the $i^{\text{th}}$ query and $(x_0^j, x_1^j)$ denotes the corresponding response.
Let $\tau_0 = \emptyset$. For any $i \in [q]$ and any $k = (k_1, k_2, k_3, k_4) \in \{0, 1\}^{4n}$, we define the associated Feistel round-2 set $\nu_{i,k}^{(2)}$ and Feistel round-3 set $\nu_{i,k}^{(3)}$ as follows:

$$ \nu_{i,k}^{(2)} := \{(x_2^1 \oplus k_2, x_1^1 \oplus x_3^1), \dots, (x_2^i \oplus k_2, x_1^i \oplus x_3^i)\}, $$

$$ \nu_{i,k}^{(3)} := \{(x_3^1 \oplus k_3, x_2^1 \oplus x_4^1), \dots, (x_3^i \oplus k_3, x_2^i \oplus x_4^i)\}, $$

where $x_2^j = x_0^j \oplus \Gamma(x_1^j \oplus k_1)$ for all $j \in [i]$. With a slight abuse of notations, we write $x \in \nu_{i,k}^{(j)}$ to mean that there exists a tuple $(x, y) \in \nu_{i,k}^{(j)}$. Let $\nu_{i,k}^{(1)} = \{x_1^j \oplus k_1 : j \in [i]\}$ and $\nu_{i,k}^{(4)} = \{x_3^j \oplus k_3 : j \in [i]\}$. We further define the associated reprogramming set as $\nu_{i,k} := \nu_{i,k}^{(2)} \cup \nu_{i,k}^{(3)}$. We say that $\nu_{i,k}$ is valid if:

- $x_2^1 \oplus k_2, \dots, x_2^i \oplus k_2$ are pairwise distinct,

- $x_3^1 \oplus k_3, \dots, x_3^i \oplus k_3$ are pairwise distinct,

- for all $j, j' \in [i]$ and distinct $r, r' \in [4]$, $x_r^j \oplus k_r \neq x_{r'}^{j'} \oplus k_{r'}$,

and invalid otherwise. Note that a valid $\nu_{i,k}$ implies that $\nu_{i,k}^{(2)}$ and $\nu_{i,k}^{(3)}$ define the input-output tuples to $\Gamma_2$ and $\Gamma_3$ in a functionally consistent manner, respectively, assuming the transcript $\tau_i$ is obtained using $\Gamma_k^\Gamma$. For any valid $\nu_{i,k}$, recall that $\Gamma^{\nu_{i,k}}$ denotes the locally-redefined copy of $\Gamma$.

We let $\mathbf{H}_0, \dots, \mathbf{H}_q$ denote a sequence of $q+1$ hybrids. In $\mathbf{H}_i$, the key is always sampled at random: $k = (k_1, k_2, k_3, k_4) \stackrel{\$}{\leftarrow} \{0, 1\}^{4n}$. In the first $i$ epochs, classical queries are answered using $\Pi$ (in the appropriate direction) and quantum queries using $\Gamma$. Then, if $\nu_{i,k}$ is invalid, subsequent classical queries are answered with $\perp$ and quantum queries with $\Gamma$. If $\nu_{i,k}$ is valid, subsequent queries are answered with $\Gamma_k^\Gamma$ and $\Gamma^{\nu_{i,k}}$ respectively. Like before, $\mathbf{H}_0$ is the real world, and $\mathbf{H}_q$ the ideal world.

For $i \in \{0, 1, \dots, q\}$, let $\mathbf{F}_i$ denote the event that $\nu_{i,k}$ is invalid in hybrid $\mathbf{H}_i$, and $\mathbf{E}_i$ denote the event that $\mathcal{A}$ returns 1 in the random experiment $\mathbf{H}_i$. Without loss of generality assume $\mathbf{E}_i$ holds whenever $\mathbf{F}_i$ occurs. Following the same steps as in Section 4, we have:

$$ \mathbf{Advt}_{\Gamma^\Gamma}^{\text{pq-sprp}}(\mathcal{A}) \le \sum_{i=0}^{q-1} |\Pr(\mathbf{E}_i \wedge \neg \mathbf{F}_i) - \Pr(\mathbf{E}_{i+1} \wedge \neg \mathbf{F}_{i+1})| + \Pr(\mathbf{F}_q). \quad (25) $$

*Claim.* We claim:

$$ \Pr(\mathbf{F}_q) \le 3q \sqrt{\frac{p}{2^n}} + \frac{5q^2}{2^n}. \quad (26) $$

*Proof (of Claim).* Recall that the event $\mathbf{F}_q$ occurs in the hybrid $\mathbf{H}_q$ which can be viewed as a string of oracle calls:

$$ \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{q \text{ classical queries}} $$

Next, we can write $\mathbf{F}_q = \mathbf{bad}_1 \cup \mathbf{bad}_2 \cup \mathbf{bad}_3$, where:

- $\mathbf{bad}_1$: there exists distinct $j, j' \in [q]$ such that $x_2^j = x_2^{j'}$,

- $\mathbf{bad}_2$: there exists distinct $j, j' \in [q]$ such that $x_3^j = x_3^{j'}$,

- $\mathbf{bad}_3$: there exists $j, j' \in [q]$ and distinct $r, r' \in [4]$ such that

$$ x_r^j \oplus k_r \neq x_{r'}^{j'} \oplus k_{r'}. $$

Using the uniformity of $k_r \oplus k_{r'}$, we have that $\Pr(\mathbf{bad}_3) \le 3q^2/2^n$. As for $\Pr(\mathbf{bad}_1)$ and $\Pr(\mathbf{bad}_2)$, we resort to the Collisions-in-the-dark game using a similar argument as used in the proof of Theorem 3. Let $\mathcal{X}_1^* = \{(x_0^1, x_1^1), \dots, (x_0^q, x_1^q)\}$ and $\mathcal{X}_2^* = \{(x_4^1, x_5^1), \dots, (x_4^q, x_5^q)\}$. We characterize the relation $\mathbb{R}_1$ as follows:

$$ x_2^j = \Gamma(x_1^j \oplus k_1) \oplus x_0^j = \Gamma(x_1^{j'} \oplus k_1) \oplus x_0^{j'} = x_2^{j'}, $$
and $\mathbb{R}_2$ as follows:

$$x_3^j = \Gamma(x_4^j \oplus k_4) \oplus x_5^j = \Gamma(x_4^{j'} \oplus k_4) \oplus x_5^{j'} = x_3^{j'}$$

Then, using Lemma 2, we have

$$\begin{aligned} \Pr(\text{bad}_1 \lor \text{bad}_2) &\le \Pr_{\mathcal{X}_1^* \leftarrow \mathcal{A}} (\text{WC}_{\mathbb{R}_1}(\mathcal{X}_1^*)) + \Pr_{\mathcal{X}_2^* \leftarrow \mathcal{A}} (\text{WC}_{\mathbb{R}_2}(\mathcal{X}_2^*)) \\ &\le 3q \sqrt{\frac{p}{2^n}} + \frac{2q^2}{2^n}. \end{aligned}$$

The claim in Eq. (26) is obtained by accumulating the bound for each of the bad events. □

Now we bound $|\Pr(E_i \wedge \neg F_i) - \Pr(E_{i+1} \wedge \neg F_{i+1})|$ for all $i \in \{0, \dots, q-1\}$. For any $i \in \{0, \dots, q-1\}$, assuming the hybrid does not abort, $\mathbf{H}_i$ can be viewed as a string of oracle calls made by $\mathcal{A}$

$$\underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \overbrace{\Gamma_k^\Gamma \Gamma^{\nu_{i,k}} \dots \Gamma_k^\Gamma \Gamma^{\nu_{i,k}}}^{q-i \text{ classical queries}}$$

where each occurrence of $\Gamma$ (res. $\Gamma^\Gamma$) indicates a single classical query and each occurrence of $\Gamma$ (res. $\Gamma^{\nu_{i,k}}$) indicates the sequence of primitive queries in the $i^{th}$ epoch. In this representation, we want to compare:

$$\begin{aligned} \mathbf{H}_i: & \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \overbrace{\Gamma_k^\Gamma \Gamma^{\nu_{i,k}} \dots \Gamma_k^\Gamma \Gamma^{\nu_{i,k}}}^{q-i-1 \text{ classical queries}} \\ \mathbf{H}_{i+1}: & \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \Gamma \overbrace{\Gamma_k^\Gamma \Gamma^{\nu_{i+1,k}} \dots \Gamma_k^\Gamma \Gamma^{\nu_{i+1,k}}}^{q-i-1 \text{ classical queries}} \end{aligned}$$

We introduce an intermediate hybrid $\hat{\mathbf{H}}_i$ with the same definition as in Section 4, except for the modification of the key (a 4-tuple) and the oracles. For $i \in \{0, \dots, q-1\}$, let $\hat{\mathbf{F}}_i$ denote the event that $\nu_{i+1,k}$ is invalid in hybrid $\hat{\mathbf{H}}_i$, and $\hat{\mathbf{E}}_i$ denote the event that $\mathcal{A}$ returns 1 in the random experiment $\hat{\mathbf{H}}_i$. Assuming that the hybrid does not abort, we can represent the games as the following sequences of queries:

$$\begin{aligned} \mathbf{H}_i: & \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \overbrace{\Gamma_k^\Gamma \Gamma^{\nu_{i,k}} \dots \Gamma_k^\Gamma \Gamma^{\nu_{i,k}}}^{q-i-1 \text{ classical queries}} \\ \hat{\mathbf{H}}_i: & \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \Gamma \overbrace{\Gamma_k^\Gamma \Gamma^{\nu_{i+1,k}} \dots \Gamma_k^\Gamma \Gamma^{\nu_{i+1,k}}}^{q-i-1 \text{ classical queries}} \\ \mathbf{H}_{i+1}: & \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \Gamma \overbrace{\Gamma_k^\Gamma \Gamma^{\nu_{i+1,k}} \dots \Gamma_k^\Gamma \Gamma^{\nu_{i+1,k}}}^{q-i-1 \text{ classical queries}} \end{aligned}$$

In Lemma 5 and 6 we show that:

$$|\Pr(\hat{\mathbf{E}}_i \wedge \neg \hat{\mathbf{F}}_i) - \Pr(E_{i+1} \wedge \neg F_{i+1})| \le 2p_{i+1} \sqrt{\frac{2(i+1)}{2^n}}, \qquad (27)$$

$$|\Pr(E_i \wedge \neg F_i) - \Pr(\hat{\mathbf{E}}_i \wedge \neg \hat{\mathbf{F}}_i)| \le 6 \sqrt{\frac{p}{2^n}} + \frac{q}{2^{2n}} + \frac{10i}{2^n}. \qquad (28)$$

Using the triangle inequality, Eqs. (28) and (27), and substituting in Eq. (25), yields:

$$\mathbf{Advt}_{\Gamma^\Gamma}^{\text{pq-sprp}}(\mathcal{A}) \le 9q \sqrt{\frac{p}{2^n}} + 2p \sqrt{\frac{2q}{2^n}} + \frac{15.5q^2}{2^n}. \qquad (29)$$

By replacing $p = 3p'$ and $q = 3q'$ we obtain the result. □
**Lemma 5.** For all $i \in \{0, \dots, q-1\}$ we have

$$|\Pr(\hat{E}_i \wedge \neg \hat{F}_i) - \Pr(E_{i+1} \wedge \neg F_{i+1})| \le 2p_{i+1}\sqrt{\frac{2(i+1)}{2^n}}.$$

*Proof (Sketch).* The proof is identical to the proof of Lemma 3, except that the key to sample is a 4-tuple. For completeness, a proof is available in Section E. □

**Lemma 6.** For all $i \in \{0, \dots, q-1\}$ we have

$$|\Pr(E_i \wedge \neg F_i) - \Pr(\hat{E}_i \wedge \neg \hat{F}_i)| \le 6\sqrt{\frac{p}{2^n}} + \frac{q}{2^{2n}} + \frac{10i}{2^n}.$$

For completeness, a proof is available in Section F.

# 6 Conclusion

In this paper, we showed positive security results for Key-Alternating Feistel ciphers in the Q1 setting. We settled the case of independent round functions, independent round permutations, and identical round functions. Naturally, the most interesting open question is the case of identical round permutations. We conjecture the 3-round KAF should be a Q1 PRP and the 4-round KAF should also be a Q1 SPRP in that case.

One can frame these problems as instances of the Tweakable Even-Mansour (TEM) construction [CLS15], by defining the map $(i, x) \mapsto K_i \oplus P(x \oplus K_i)$ where $K_i$ is selected from $\{K_1, K_2, K_3, K_4\}$ depending on the tweak $i$. At this point, it would have been convenient to use the Q1 results from [ABK$^{+24}$]. However, due to a subtle technicality, this result does not seem to be immediately applicable—it assumes $n$ (or fewer) bits of key, where $n$ is the state size, whereas we have $4n$ bits of key.

On the other hand, one can also view the same as if the Even-Mansour construction is deployed in a multi-user setting, since the round keys are mutually independent. In fact, a similar approach is also possible in the case of identical round functions that is studied in this paper. The overall problem would then reduce to a multi-user security analysis of the Even-Mansour construction (or the blinded hash in case of functions). One can then use the ARP / ARS machinery, that is also central to the results of this paper, to do this analysis. However, we believe that with multiple keys involved, this approach would require some delicate analysis of cross-collision events, similar to the analysis that was needed in Sections 4 and 5.

**Acknowledgments.** We would like to thank the organizers of the ASK 2024 workshop, as well as Suman Dutta for discussions which took place at the workshop. We thank the anonymous reviewers of CRYPTO 2025 and ASIACRYPT 2025 for helpful remarks which improved the paper. This work was (in part) supported by the European Research Council (ERC) project 101097056 (SYMTRUST). A. J. is supported by the German Research Foundation (DFG) within the framework of the Excellence Strategy of the Federal Government and the States — EXC 2092 CASA — 39078197. A. R. is supported by the National Institute of Information and Communications Technology (NICT), Japan, under the NICT International Invitational Program. A. S. is supported by the French Agence Nationale de la Recherche through the QATS project under Contract ANR-24-CE39-7894-01.

# References

ABK$^{+24}$. Gorjan Alagic, Chen Bai, Jonathan Katz, Christian Majenz, and Patrick Struck. Post-quantum security of tweakable even-mansour, and applications. In Marc Joye and Gregor Leander, editors, *Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part I*, volume 14651 of *Lecture Notes in Computer Science*, pages 310-338. Springer, 2024. (Cited on pp. 2 and 22.)

ABKM21. Gorjan Alagic, Chen Bai, Jonathan Katz, and Christian Majenz. Post-quantum security of the even-mansour cipher. *IACR Cryptol. ePrint Arch.*, page 1601, 2021. (Cited on pp. 4 and 26.)
ABKM22. Gorjan Alagic, Chen Bai, Jonathan Katz, and Christian Majenz. Post-quantum security of the even-mansour cipher. In Orr Dunkelman and Stefan Dziembowski, editors, *Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part III*, volume 13277 of Lecture Notes in Computer Science, pages 458-487. Springer, 2022. (Cited on pp. 2, 3, 4, 9, 13, 30, 32, and 33.)

AHU19. Andris Ambainis, Mike Hamburg, and Dominique Unruh. Quantum security proofs using semi-classical oracles. In Alexandra Boldyreva and Daniele Micciancio, editors, *Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part II*, volume 11693 of Lecture Notes in Computer Science, pages 269-295. Springer, 2019. (Cited on p. 33.)

AIK<sup>+00</sup>. Kazumaro Aoki, Tetsuya Ichikawa, Masayuki Kanda, Mitsuru Matsui, Shiho Moriai, Junko Nakajima, and Toshio Tokita. Camellia: A 128-bit block cipher suitable for multiple platforms - design and analysis. In Douglas R. Stinson and Stafford E. Tavares, editors, *Selected Areas in Cryptography, 7th Annual International Workshop, SAC 2000, Waterloo, Ontario, Canada, August 14-15, 2000, Proceedings*, volume 2012 of Lecture Notes in Computer Science, pages 39-56. Springer, 2000. (Cited on p. 2.)

BBBV97. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh V. Vazirani. Strengths and weaknesses of quantum computing. *SIAM J. Comput.*, 26(5):1510-1523, 1997. (Cited on pp. 2 and 26.)

BBD<sup>+24</sup>. Arghya Bhattacharjee, Ritam Bhaumik, Avijit Dutta, Mridul Nandi, and Anik Raychaudhuri. BBB security for 5-round even-mansour-based key-alternating feistel ciphers. *Des. Codes Cryptogr.*, 92(1):13-49, 2024. (Cited on p. 2.)

BCEJ24. Ritam Bhaumik, Benoît Cogliati, Jordan Ethan, and Ashwin Jha. Mind the bad norms - revisiting compressed oracle-based quantum indistinguishability proofs. In Kai-Min Chung and Yu Sasaki, editors, *Advances in Cryptology - ASIACRYPT 2024 - 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9-13, 2024, Proceedings, Part IX*, volume 15492 of Lecture Notes in Computer Science, pages 215-247. Springer, 2024. (Cited on p. 2.)

BHN<sup>+19</sup>. Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia, Yu Sasaki, and André Schrottenloher. Quantum attacks without superposition queries: The offline simon's algorithm. In Steven D. Galbraith and Shiho Moriai, editors, *Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part I*, volume 11921 of Lecture Notes in Computer Science, pages 552-583. Springer, 2019. (Cited on p. 3.)

BHT98. Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. In Claudio L. Lucchesi and Arnaldo V. Moura, editors, *LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings*, volume 1380 of Lecture Notes in Computer Science, pages 163-169. Springer, 1998. (Cited on p. 3.)

BLNS21. Xavier Bonnetain, Gaëtan Leurent, María Naya-Plasencia, and André Schrottenloher. Quantum linearization attacks. In Mehdi Tibouchi and Huaxiong Wang, editors, *Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part I*, volume 13090 of Lecture Notes in Computer Science, pages 422-452. Springer, 2021. (Cited on p. 1.)

BNS19. Xavier Bonnetain, María Naya-Plasencia, and André Schrottenloher. On quantum slide attacks. In Kenneth G. Paterson and Douglas Stebila, editors, *Selected Areas in Cryptography - SAC 2019 - 26th International Conference, Waterloo, ON, Canada, August 12-16, 2019, Revised Selected Papers*, volume 11959 of Lecture Notes in Computer Science, pages 492-519. Springer, 2019. (Cited on p. 1.)

BR06. Mihir Bellare and Phillip Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. In Serge Vaudenay, editor, *Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings*, volume 4004 of Lecture Notes in Computer Science, pages 409-426. Springer, 2006. (Cited on pp. 9, 18, 36, and 42.)

BSS22. Xavier Bonnetain, André Schrottenloher, and Ferdinand Sibleyras. Beyond quadratic speedups in quantum attacks on symmetric schemes. In Orr Dunkelman and Stefan Dziembowski, editors, *Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part III*, volume 13277 of Lecture Notes in Computer Science, pages 315-344. Springer, 2022. (Cited on p. 1.)

CLS15. Benoît Cogliati, Rodolphe Lampe, and Yannick Seurin. Tweaking even-mansour ciphers. In Rosario Gennaro and Matthew Robshaw, editors, *Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I*, volume 9215 of Lecture Notes in Computer Science, pages 189-208. Springer, 2015. (Cited on p. 22.)
DFH22. Jelle Don, Serge Fehr, and Yu-Hsuan Huang. Adaptive versus static multi-oracle algorithms, and quantum security of a split-key PRF. In Eike Kiltz and Vinod Vaikuntanathan, editors, *Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part I*, volume 13747 of Lecture Notes in Computer Science, pages 33–51. Springer, 2022. (Cited on pp. 3 and 7.)

FKSV21. Pooya Farshim, Louiza Khati, Yannick Seurin, and Damien Vergnaud. The key-dependent message security of key-alternating feistel ciphers. In Kenneth G. Paterson, editor, *Topics in Cryptology - CT-RSA 2021 - Cryptographers' Track at the RSA Conference 2021, Virtual Event, May 17-20, 2021, Proceedings*, volume 12704 of Lecture Notes in Computer Science, pages 351–374. Springer, 2021. (Cited on p. 2.)

GHHM21. Alex B. Grilo, Kathrin Hövelmanns, Andreas Hülsing, and Christian Majenz. Tight adaptive reprogramming in the QROM. In Mehdi Tibouchi and Huaxiong Wang, editors, *Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part I*, volume 13090 of Lecture Notes in Computer Science, pages 637–667. Springer, 2021. (Cited on pp. 6 and 33.)

Gro96. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Gary L. Miller, editor, *Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996*, pages 212–219. ACM, 1996. (Cited on p. 1.)

GW18. Chun Guo and Lei Wang. Revisiting key-alternating feistel ciphers for shorter keys and multi-user security. In Thomas Peyrin and Steven D. Galbraith, editors, *Advances in Cryptology - ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part I*, volume 11272 of Lecture Notes in Computer Science, pages 213–243. Springer, 2018. (Cited on p. 2.)

HI19. Akinori Hosoyamada and Tetsu Iwata. 4-round luby-rackoff construction is a qprp. In Steven D. Galbraith and Shiho Moriai, editors, *Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part I*, volume 11921 of Lecture Notes in Computer Science, pages 145–174. Springer, 2019. (Cited on p. 2.)

IHM$^+$ 19. Gembu Ito, Akinori Hosoyamada, Ryutaroh Matsumoto, Yu Sasaki, and Tetsu Iwata. Quantum chosen-ciphertext attacks against feistel ciphers. In Mitsuru Matsui, editor, *Topics in Cryptology - CT-RSA 2019 - The Cryptographers' Track at the RSA Conference 2019, San Francisco, CA, USA, March 4-8, 2019, Proceedings*, volume 11405 of Lecture Notes in Computer Science, pages 391–411. Springer, 2019. (Cited on pp. 1 and 2.)

JST21. Joseph Jaeger, Fang Song, and Stefano Tessaro. Quantum key-length extension. In Kobbi Nissim and Brent Waters, editors, *Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part I*, volume 13042 of Lecture Notes in Computer Science, pages 209–239. Springer, 2021. (Cited on p. 2.)

KLLN16. Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, and María Naya-Plasencia. Breaking symmetric cryptosystems using quantum period finding. In Matthew Robshaw and Jonathan Katz, editors, *Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II*, volume 9815 of Lecture Notes in Computer Science, pages 207–237. Springer, 2016. (Cited on p. 1.)

KM10. Hidenori Kuwakado and Masakatu Morii. Quantum distinguisher between the 3-round feistel cipher and the random permutation. In *IEEE International Symposium on Information Theory, ISIT 2010, June 13-18, 2010, Austin, Texas, USA, Proceedings*, pages 2682–2685. IEEE, 2010. (Cited on pp. 1 and 2.)

KM12. Hidenori Kuwakado and Masakatu Morii. Security on the quantum-type even-mansour cipher. In *Proceedings of the International Symposium on Information Theory and its Applications, ISITA 2012, Honolulu, HI, USA, October 28-31, 2012*, pages 312–316. IEEE, 2012. (Cited on p. 1.)

LR85. Michael Luby and Charles Rackoff. How to construct pseudo-random permutations from pseudo-random functions (abstract). In Hugh C. Williams, editor, *Advances in Cryptology - CRYPTO '85, Santa Barbara, California, USA, August 18-22, 1985, Proceedings*, volume 218 of Lecture Notes in Computer Science, page 447. Springer, 1985. (Cited on p. 9.)

LR88. Michael Luby and Charles Rackoff. How to construct pseudorandom permutations from pseudorandom functions. *SIAM J. Comput.*, 17(2):373–386, 1988. (Cited on p. 9.)

LS14. Rodolphe Lampe and Yannick Seurin. Security analysis of key-alternating feistel ciphers. In *FSE*, volume 8540 of Lecture Notes in Computer Science, pages 243–264. Springer, 2014. (Cited on p. 2.)

NIDI19. Boyu Ni, Gembu Ito, Xiaoyang Dong, and Tetsu Iwata. Quantum attacks against type-1 generalized feistel ciphers and applications to CAST-256. In Feng Hao, Sushmita Ruj, and Sourav Sen Gupta, editors, *Progress in Cryptology - INDOCRYPT 2019 - 20th International Conference on Cryptology in India, Hyderabad, India, December 15-18, 2019, Proceedings*, volume 11898 of Lecture Notes in Computer Science, pages 433–455. Springer, 2019. (Cited on p. 1.)
Sho94. Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In *35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994*, pages 124-134. IEEE Computer Society, 1994. (Cited on p. 1.)

Sim97. Daniel R. Simon. On the power of quantum computation. *SIAM J. Comput.*, 26(5):1474-1483, 1997. (Cited on p. 2.)

SS17. Thomas Santoli and Christian Schaffner. Using simon's algorithm to attack symmetric-key cryptographic primitives. *Quantum Inf. Comput.*, 17(1&2):65-78, 2017. (Cited on p. 1.)

SYWL21. Yaobin Shen, Hailun Yan, Lei Wang, and Xuejia Lai. Secure key-alternating feistel ciphers without key schedule. *Sci. China Inf. Sci.*, 64(1), 2021. (Cited on p. 2.)

Unr14. Dominique Unruh. Revocable quantum timed-release encryption. In Phong Q. Nguyen and Elisabeth Oswald, editors, *Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings*, volume 8441 of *Lecture Notes in Computer Science*, pages 129-146. Springer, 2014. (Cited on p. 33.)

## A Pseudocodes for the Games from Section 2

Here we include pseudocodes for the following games described in Section 2: ARP and ARS, along with the experiment RS (Fig. 5; and the two collisions-in-the-dark games SCitD and WCitD (Fig. 6).

<figure><img src="image_6.png" /><figcaption>Fig. 5: Pseudocode for the games ARP (left) and ARS (right). In the ARP game, ll. 8-9, we formalise $\mathcal{D}$ first having quantum access to $\Gamma_b$ and then 'losing access to $\Gamma_b$ and then getting $\mathcal{B}$'s random coin $r'$ by having $\mathcal{D}^{[\Gamma_b(\cdot)]}$ output an algorithm $g$ and then running $g$ on $r$.</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Fig. 6: Pseudocode for the games $SCitD$ (left) and $WCitD$ (right).</figcaption></figure>

## B Deferred Proofs from Section 2

**Proposition 1.** *[Arbitrary Reprogramming Lemma]* For any p-query ARP-distinguisher $\mathcal{D}$, it holds that

$$ \mathbf{Advt}^{\mathrm{arp}}(\mathcal{D}) \leq 2p \cdot \sqrt{\epsilon}. $$

*Proof.* The proof can be inferred from the proof of Lemma 2 in [ABKM21], but we give it here for completeness, as it relies only on a simple query magnitude argument. Let $|\phi_{p+1}\rangle$ be the final state of $\mathcal{D}$ after running with $\Gamma_0$ and $|\psi_{p+1}\rangle$ the state after running with $\Gamma_1$ (the modified oracle). We have:

$$ \mathbf{Advt}^{\mathrm{arp}}(\mathcal{D}) \leq \mathbb{E}_r (\| |\phi_{p+1}\rangle - |\psi_{p+1}\rangle \|) \qquad (30) $$

where the expectation is taken over the randomness of $\mathcal{B}$, which is given to the distinguisher in Phase 3 of the game. This follows from the fact that the statistical distance is smaller than the trace distance, which is half of the Euclidean distance for pure states.

We then bound this difference query by query. Note that while we are writing this bound, the set of inputs on which the two oracles differ has been fixed (however, it varies depending on $r$). Let $\Pi_{B_1}$ be the projector on the inputs that belong to $B_1$. Let $|\phi_i\rangle$ be the state when running with $\Gamma_0$, after $i$ queries. We obtain that (from an adaptation of Theorem 3.3 in [BBBV97]):

$$ \| |\phi_{p+1}\rangle - |\psi_{p+1}\rangle \| \leq 2 \sum_{i=1}^{p} |\Pi_{B_1} |\phi_i\rangle |. \qquad (31) $$
By combining these last equations we get:

$$ \mathbf{Advt}^{\text{arp}}(\mathcal{D}) \le 2 \sum_{i=1}^{p} \mathbb{E}_r |\Pi_{B_1}| |\phi_i\rangle| . \quad (32) $$

The next step is to use the convexity of the square function, and Jensen's inequality: $\mathbb{E}_r(X) \le \sqrt{\mathbb{E}_r(X^2)}$ for any random variable $X$, which we substitute with $|\Pi_{B_1}| |\phi_i\rangle|$:

$$ \mathbb{E}_r |\Pi_{B_1}| |\phi_i\rangle| \le \sqrt{\mathbb{E}_r |\Pi_{B_1}| |\phi_i\rangle|^2} . $$

Here we can now use the randomness of $\mathcal{B}$ and our assumption on the probability that an element falls in $B_1$. For any of these quantum states $|\phi_i\rangle$ written as $\sum_{x,y} \alpha_{x,y} |x, y\rangle$, we have:

$$ \mathbb{E}_r |\Pi_{B_1}| |\phi_i\rangle|^2 = \mathbb{E}_r \left( \sum_{x,y} |\alpha_{x,y}|^2 \right) = \sum_{x,y} \mathrm{Pr}(x \in B_1) |\alpha_{x,y}|^2 \le \epsilon . \quad (33) $$

Putting everything together, we obtain the claimed bound. $\square$

**Lemma 1.** [Strong Collisions-in-the-dark] For any adversary $\mathcal{A}$ in the strong collisions-in-the-dark game with respect to the relation $\mathbb{R}$, making $p$ queries and returning a set of size $q$:

$$ \mathrm{Pr}_{(\mathcal{X}^*, x^*) \leftarrow \mathcal{A}}(\mathrm{SC}_{\mathbb{R}}(\mathcal{X}^*, x^*)) \le 1.5 \sqrt{\frac{p}{2^n}} + q \max_{\substack{x, x^* \in \mathcal{X} \\ r \leftarrow \mathcal{S} \mathcal{Y} \\ s \leftarrow \mathcal{S} \mathcal{X}_1}} \mathrm{Pr}_{\substack{(x, x^*, r, \Gamma(s)) \in \mathbb{R} \\ s \leftarrow \mathcal{S} \mathcal{X}_1}} $$

*Proof.* We construct an ARS adversary $\mathcal{D}$ that uses $\mathcal{A}$ in a black-box manner and wins with probability roughly the winning probability of $\mathcal{A}$. In this ARS game we define $\mathcal{X}_1$ as $\emptyset$, and $\mathcal{X}_2$ as the set $\mathcal{X}_1$ of $\mathcal{A}$'s strong collisions-in-the-dark game. So the resampler RS transforms the oracle $\Gamma_1$ as $\Gamma_1 := \Gamma_1^{x,y}$ for random $x, y$ and returns $x$.

Specifically, $\mathcal{D}$ operates as follows:

- $\mathcal{D}$ runs $\mathcal{A}$ as a quantum algorithm. All queries to $\Gamma$ made by $\mathcal{A}$ are relayed to $\mathcal{D}$'s oracle, meaning that we replace the unitary corresponding to $\Gamma$ in $\mathcal{A}$ by the one corresponding to $\mathcal{D}$'s random oracle.

- Once $\mathcal{A}$ has made all its $p$ queries, it measures a register and returns the pair $(\mathcal{X}^*, x^*)$ where $\mathcal{X}^*$ has size $q$ and $x^* := (x_0^*, x_1^*)$.

- Now, $\mathcal{D}$ makes an RS query and gets as response a uniformly random $s$.

- $\mathcal{D}$ sets $k = x_1^* \oplus s$. Thus, the marginal distribution of $k$ is uniform.

- Now, if $\mathrm{SC}_{\mathbb{R}}(\mathcal{X}^*, x^*)$ holds then $\mathcal{D}$ returns 0, and 1 otherwise.

When $\mathcal{D}$ is interacting with $\Gamma_0$ (the unmodified oracle), it perfectly simulates the SCitD game for $\mathcal{A}$. Thus,

$$ \mathrm{Pr}_{(\mathcal{D}^{\Gamma_0, \mathrm{RS}} = 1 | b = 0)} = \mathrm{Pr}_{(\mathcal{X}^*, x^*) \leftarrow \mathcal{A}}(\mathrm{SC}_{\mathbb{R}}(\mathcal{X}^*, x^*)) . \quad (34) $$

On the other hand, when $\mathcal{D}$ is interacting with $\Gamma_1$, $\Gamma(x_1^* \oplus k) = \Gamma(s) = r$ is uniformly distributed and independent of all other variables, including $s$. Thus,

$$ \begin{aligned} \mathrm{Pr}_{(\mathcal{D}^{\Gamma_0, \mathrm{RS}} = 1 | b = 0)} &= \mathrm{Pr}_{\substack{r \leftarrow \mathcal{S} \mathcal{Y} \\ s \leftarrow \mathcal{S} \mathcal{X}_1}} (\exists x \in \mathcal{X}^* : (x, x^*, r, \Gamma(s \oplus x_1^* \oplus x_1)) \in \mathbb{R}) \\ &\le \sum_{x \in \mathcal{X}^*} \mathrm{Pr}_{\substack{r \leftarrow \mathcal{S} \mathcal{Y} \\ s \leftarrow \mathcal{S} \mathcal{X}_1}} ((x, x^*, r, \Gamma(s \oplus x_1^* \oplus x_1)) \in \mathbb{R}) \\ &\le q \max_{\substack{x, x^* \in \mathcal{X}_1 \\ r \leftarrow \mathcal{S} \mathcal{Y} \\ s \leftarrow \mathcal{S} \mathcal{X}_1}} \mathrm{Pr}_{\substack{(x, x^*, r, \Gamma(s)) \in \mathbb{R} \\ s \leftarrow \mathcal{S} \mathcal{X}_1}}. \end{aligned} \quad (35) $$

The result follows by subtracting Eq. (35) from Eq. (34) and then using Proposition 2. $\square$
**Lemma 2.** [Weak Collisions-in-the-dark] For any p-query adversary $\mathcal{A}$ in the weak collisions-in-the-dark game with respect to the relation $\mathbb{R}$:

$$ \Pr_{\mathcal{X}^* \leftarrow \mathcal{A}} (\mathrm{WC}_{\mathbb{R}}(\mathcal{X}^*)) \le 1.5q \sqrt{\frac{p}{2^n}} + q^2 \max_{\substack{x,x' \in \mathcal{X}_1 \\ r \leftarrow \mathcal{S}}} \Pr_{\substack{s \leftarrow \mathcal{S} \\ \mathcal{X}_1}} ((x, x', r, \Gamma(s)) \in \mathbb{R}). $$

*Proof.* Let $(x^1, \dots, x^q)$ denote a fixed ordering of $\mathcal{X}^*$. For all $i \in \{1, \dots, q-1\}$, let $\mathcal{X}_i^* := \{x^1, \dots, x^i\}$, and define $\mathbb{E}_i$: there exist $x \in \mathcal{X}_i^*$ such that $(x, x^{i+1}, \Gamma(k \oplus x_1), \Gamma(k \oplus x_1^{i+1})) \in \mathbb{R}$.

Clearly, $\mathrm{WC}_{\mathbb{R}}(\mathcal{X}^*) = \mathbb{E}_1 \vee \dots \vee \mathbb{E}_{q-1}$. Then, we have

$$ \Pr_{\mathcal{X}^* \leftarrow \mathcal{A}} (\mathrm{WC}_{\mathbb{R}}(\mathcal{X}^*)) = \Pr(\mathbb{E}_1 \vee \dots \vee \mathbb{E}_{q-1}) \le \sum_{i=1}^{q-1} \Pr(\mathbb{E}_i). \quad (36) $$

Now, for any fixed $i$, we construct a SCitD adversary $\mathcal{D}_i$ such that its advantage is exactly $\Pr(\mathbb{E}_i)$. Essentially, $\mathcal{D}_i$ simulates $\mathcal{A}$'s oracle using its own random oracle $\Gamma$ and once it receives the set $\mathcal{X}^*$, it returns $(\mathcal{X}_i^*, x^{i+1})$ and ignores the rest. Then,

$$ \Pr_{(\mathcal{X}_i^*, x^{i+1}) \leftarrow \mathcal{D}_i} (\mathrm{SC}_{\mathbb{R}}(\mathcal{X}_i^*, x^{i+1})) = \Pr(\mathbb{E}_i). $$

Thus, by Lemma 1,

$$ \Pr(\mathbb{E}_i) \le 1.5 \sqrt{\frac{p}{2^n}} + i \max_{\substack{x,x' \in \mathcal{X}_1 \\ r \leftarrow \mathcal{S} \\ s \leftarrow \mathcal{S}}} \Pr_{\substack{s \leftarrow \mathcal{S} \\ \mathcal{X}_2}} ((x, x', r, \Gamma(s)) \in \mathbb{R}). \quad (37) $$

Substituting Eq. (37) back in Eq. (36), we have

$$ \begin{aligned} \Pr(\mathrm{WC}_{\mathbb{R}}(\mathcal{X}^*)) &\le \sum_{i=1}^{q-1} \left( 1.5 \sqrt{\frac{p}{2^n}} + i \max_{\substack{x,x' \in \mathcal{X}_1 \\ r \leftarrow \mathcal{S} \\ s \leftarrow \mathcal{S}}} \Pr_{\substack{s \leftarrow \mathcal{S} \\ \mathcal{X}_2}} ((x, x', r, \Gamma(s)) \in \mathbb{R}) \right) \\ &\le 1.5q \sqrt{\frac{p}{2^n}} + q^2 \max_{\substack{x,x' \in \mathcal{X}_1 \\ r \leftarrow \mathcal{S} \\ s \leftarrow \mathcal{S}}} \Pr_{\substack{s \leftarrow \mathcal{S} \\ \mathcal{X}_2}} ((x, x', r, \Gamma(s)) \in \mathbb{R}). \quad \square \end{aligned} $$

## C Permutation-based Feistel Network

In this section, we provide the security proofs for the 3-round and 4-round Feistel constructions based on permutations such as the Even-Mansour cipher. Recall that the Even-Mansour cipher is defined as $E_k^\pi(x) := \pi(x \oplus k_{i1}) \oplus k_{i2}$, where $\pi$ is a public random permutation and $k = (k_{i1}, k_{i2}) \in \{0, 1\}^n \times \{0, 1\}^n$ is a uniform random key. Fig. 7a (resp. Fig. 8a) illustrates the 3-round (resp. 4-round) Feistel construction based on publicly known permutations $\pi_i$.

**Corollary 1.** For any adversary $\mathcal{A}$ that makes $q$ classical queries to $\mathbb{F}^{\pi^{(3)}}$ and $p$ quantum queries to $\pi^{(3)}$, it holds that

$$ \mathbf{Adv}_{\mathbb{F}^{\pi^{(3)}}}^{\mathrm{pq-prp}}(\mathcal{A}) \le 30q \sqrt{\frac{p}{2^n}} + 30p \sqrt{\frac{q}{2^n}} + \frac{3.5q^2}{2^n}. $$

**Corollary 2.** For any adversary $\mathcal{A}$ that makes $q$ classical queries to $\mathbb{F}^{\pi^{(4)}}$ and $p$ quantum queries to $\pi^{(4)}$, it holds that

$$ \mathbf{Adv}_{\mathbb{F}^{\pi^{(4)}}}^{\mathrm{pq-sprp}}(\mathcal{A}) \le 40q \sqrt{\frac{p}{2^n}} + 40p \sqrt{\frac{q}{2^n}} + \frac{4.5q^2}{2^n}. $$
<figure><img src="image_8.png" /><figcaption>Fig. 7: Three-round Feistel constructions, where $\pi_i$ is a public permutation, while $\Pi_i$ are independent and uniform random permutations.</figcaption></figure>

## C.1 Proof of Corollary 1

In this proof, we consider a Q1 adversary $\mathcal{A}$ that makes at most $q$ classical forward queries to $F^{\pi^{(3)}}$, and at most $p$ quantum forward or backward queries to the three independent random permutations $\pi_1, \pi_2, \pi_3$.

The proof involves a sequence of hybrid games $H_0, H_1, H_2, H_3, H_4, H_5$ that are as follows:

**Hybrid $H_0$:** This is the real world where the adversary interacts with the actual 3-round Feistel construction $F^{\pi^{(3)}}$ using Even-Mansour PRPs, namely $E^{\pi_1}, E^{\pi_2}, E^{\pi_3}$ (refer to Fig. 7a).

**Hybrid $H_1$:** In this hybrid game, we replace the Even-Mansour PRP $E^{\pi_1} = k_{i1} \oplus \pi_i(k_{i2} \oplus \cdot)$ in the first round with a truly random permutation $\Pi_1$, while preserving the other two rounds (refer to Fig. 7b). The advantage of the adversary in distinguishing between $H_0$ and $H_1$ is given by

$$ \mathbf{Advt}^{H_0 \to H_1}(\mathcal{A}) = |\Pr(\mathcal{A}(H_0) \to 1) - \Pr(\mathcal{A}(H_1) \to 1)| \\ \le \mathbf{Advt}_{E^{\pi_1}}^{\text{pq-prp}}(\mathcal{A}'), \qquad (38) $$

where $\mathcal{A}'$ be the Q1 adversary who can distinguish between $E^{\pi_1}$ and $\Pi_1$.
**Hybrid H₂:** In this hybrid game, we also replace the Even-Mansour PRP $E^{\pi_2}$ in the second round with a truly random permutation $\Pi_2$, while preserving the last round. The advantage of the adversary in distinguishing between $H_1$ and $H_2$ is given by

$$ \mathbf{Advt}^{H_1 \to H_2}(\mathcal{A}) = |\Pr(\mathcal{A}(H_1) \to 1) - \Pr(\mathcal{A}(H_2) \to 1)| \\ \le \mathbf{Advt}_{E^{\pi_2}}^{\text{pq-prp}}(\mathcal{A}'), \qquad (39) $$

where $\mathcal{A}'$ be the Q1 adversary who can distinguish between $E^{\pi_2}$ and $\Pi_2$.

**Hybrid H₃:** In this hybrid game, we also replace the Even-Mansour PRP $E^{\pi_3}$ in the third round with a truly random permutation $\Pi_3$. Again, The advantage of the adversary in distinguishing between $H_2$ and $H_3$ is given by

$$ \mathbf{Advt}^{H_2 \to H_3}(\mathcal{A}) = |\Pr(\mathcal{A}(H_2) \to 1) - \Pr(\mathcal{A}(H_3) \to 1)| \\ \le \mathbf{Advt}_{E^{\pi_3}}^{\text{pq-prp}}(\mathcal{A}'), \qquad (40) $$

where $\mathcal{A}'$ be the Q1 adversary who can distinguish between $E^{\pi_3}$ and $\Pi_3$.

**Hybrid H₄:** In this hybrid game, we replace each $\Pi_i$ with a random function $F_i$, so the adversary is interacting classically with a 3-round Luby-Rackoff scheme. Note that the adversary only has classical access to the construction, and classical (indirect) access to the functions $F_i$. Therefore, we can use the classical PRP/PRF switching lemma to bound the advantage in distinguishing between $H_3$ and $H_4$:

$$ \mathbf{Advt}^{H_3 \to H_4}(\mathcal{A}) = |\Pr(\mathcal{A}(H_3) \to 1) - \Pr(\mathcal{A}(H_4) \to 1)| \le \frac{q^2}{2^n}. \qquad (41) $$

**Hybrid H₅:** Finally, in the game $H_5$ the adversary is interacting with a random permutation.

The advantage of the adversary $\mathcal{A}$ in distinguishing $F^{\pi^{(3)}}$ from a random permutation is therefore:

$$ \mathbf{Advt}_{F^{\pi^{(3)}}}^{\text{pq-prp}}(\mathcal{A}) = |\Pr(\mathcal{A}^{F^{\pi^{(3)}}} \to 1) - \Pr(\mathcal{A}^{\Pi} \to 1)| \\ \le \mathbf{Advt}^{H_0 \to H_1}(\mathcal{A}) + \mathbf{Advt}^{H_1 \to H_2}(\mathcal{A}) + \mathbf{Advt}^{H_2 \to H_3}(\mathcal{A}) \\ + \mathbf{Advt}^{H_3 \to H_4}(\mathcal{A}) + \underbrace{\mathbf{Advt}^{H_4 \to H_5}(\mathcal{A})}_{\text{Classical Luby-Rackoff bound}} \\ \le \mathbf{Advt}_{E^{\pi_1}}^{\text{pq-prp}}(\mathcal{A}') + \mathbf{Advt}_{E^{\pi_2}}^{\text{pq-prp}}(\mathcal{A}') + \mathbf{Advt}_{E^{\pi_3}}^{\text{pq-prp}}(\mathcal{A}') + \frac{q^2}{2^n} + \frac{q^2}{2^{2n}} \\ \le \frac{30}{2^{n/2}}(p\sqrt{q} + q\sqrt{p}) + \frac{q^2}{2^n} + \frac{q^2}{2^{2n}}, $$

where the last line uses the main result of [ABKM22]. This completes the proof of Corollary 1. □

## C.2 Proof of Corollary 2

The security proof for the 4-round Feistel construction based on permutations involves a sequence of hybrid games $H_0, H_1, H_2, H_3, H_4, H_5, H_6$ that are as follows:

**Hybrid H₀:** This is the real world where the adversary interacts with the actual 4-round Feistel $F^{\pi^{(4)}}$ using Even-Mansour PRPs, namely $E^{\pi_1}, E^{\pi_2}, E^{\pi_3}$ and $E^{\pi_4}$ (refer to Fig. 8a).

**Hybrid H₁:** In this hybrid game, we replace the Even-Mansour PRP $E^{\pi_4}$ in the fourth round with a truly random permutation $\Pi_4$, while preserving the other rounds (refer to Fig. 8b). The advantage of the adversary in distinguishing between $H_0$ and $H_1$ is given by

$$ \mathbf{Advt}^{H_0 \to H_1}(\mathcal{A}) = |\Pr(\mathcal{A}(H_0) \to 1) - \Pr(\mathcal{A}(H_1) \to 1)| \\ \le \mathbf{Advt}_{E^{\pi_4}}^{\text{pq-prp}}(\mathcal{A}'), \qquad (42) $$

where $\mathcal{A}'$ be the Q1 adversary who can distinguish between $E^{\pi_4}$ and $\Pi_4$.
<figure><img src="image_9.png" /><figcaption>Fig. 8: Four-round Feistel constructions, where $\pi$ is a public random permutation, $\Pi$ and $\Pi'$ are independent and uniform random permutations.</figcaption></figure>
**Hybrid H₂:** In this hybrid game, we also replace the Even-Mansour PRP $E^{\pi_3}$ in the second round with a truly random permutation $\Pi_3$, while preserving the last round. The advantage of the adversary in distinguishing between $H_1$ and $H_2$ is given by

$$ 
\begin{aligned}
\mathbf{Advt}^{H_1 \to H_2}(\mathcal{A}) &= |\Pr(\mathcal{A}(H_1) \to 1) - \Pr(\mathcal{A}(H_2) \to 1)| \\
&\leq \mathbf{Advt}_{E^{\pi_3}}^{\text{pq-prp}}(\mathcal{A}'),
\end{aligned}
\quad (43) $$

where $\mathcal{A}'$ be the Q1 adversary who can distinguish between $E^{\pi_3}$ and $\Pi_3$.

**Hybrid H₃:** In this hybrid game, we also replace the Even-Mansour PRP $E^{\pi_2}$ in the third round with a truly random permutation $\Pi_2$. Again, the advantage of the adversary in distinguishing between $H_2$ and $H_3$ is given by

$$ 
\begin{aligned}
\mathbf{Advt}^{H_2 \to H_3}(\mathcal{A}) &= |\Pr(\mathcal{A}(H_2) \to 1) - \Pr(\mathcal{A}(H_3) \to 1)| \\
&\leq \mathbf{Advt}_{E^{\pi_2}}^{\text{pq-prp}}(\mathcal{A}'),
\end{aligned}
\quad (44) $$

where $\mathcal{A}'$ be the Q1 adversary who can distinguish between $E^{\pi_2}$ and $\Pi_2$.

**Hybrid H₄:** In this hybrid game, we also replace the Even-Mansour PRP $E^{\pi_1}$ in the third round with a truly random permutation $\Pi_1$. Again, The advantage of the adversary in distinguishing between $H_2$ and $H_3$ is given by

$$ 
\begin{aligned}
\mathbf{Advt}^{H_3 \to H_4}(\mathcal{A}) &= |\Pr(\mathcal{A}(H_3) = 1) - \Pr(\mathcal{A}(H_4) = 1)| \\
&\leq \mathbf{Advt}_{E^{\pi_1}}^{\text{pq-prp}}(\mathcal{A}'),
\end{aligned}
\quad (45) $$

where $\mathcal{A}'$ be the Q1 adversary who can distinguish between $E^{\pi_1}$ and $\Pi_1$.

**Hybrid H₅:** In this hybrid game, we replace all $\Pi_i$ with random functions. Note that the adversary only accesses these functions classically, thus we can use the classical PRP/PRF switching lemma. The advantage of the adversary in distinguishing between $H_4$ and $H_5$ is therefore given by:

$$ 
\begin{aligned}
\mathbf{Advt}^{H_4 \to H_5}(\mathcal{A}) &= |\Pr(\mathcal{A}(H_4) \to 1) - \Pr(\mathcal{A}(H_5) \to 1)| \\
&\leq \frac{q^2}{2^n}.
\end{aligned}
\quad (46) $$

**Hybrid H₆:** In this game the adversary interacts with a random permutation.

The advantage of the adversary $\mathcal{A}$ in distinguishing $F^{\pi^{(4)}}$ from a random permutation is therefore:

$$ 
\begin{aligned}
\mathbf{Advt}_{F^{\pi^{(4)}}}^{\text{pq-sprp}}(\mathcal{A}) &= |\Pr(F^{\pi^{(4)}} \to 1) - \Pr(\mathcal{A}^{\Pi} \to 1)| \\
&\leq \mathbf{Advt}^{H_0 \to H_1}(\mathcal{A}) + \mathbf{Advt}^{H_1 \to H_2}(\mathcal{A}) + \mathbf{Advt}^{H_2 \to H_3}(\mathcal{A}) \\
&\quad + \mathbf{Advt}^{H_3 \to H_4}(\mathcal{A}) + \mathbf{Advt}^{H_4 \to H_5}(\mathcal{A}) + \underbrace{\mathbf{Advt}^{H_5 \to H_6}(\mathcal{A})}_{\text{Classical Luby-Rackoff bound}} \\
&\leq \mathbf{Advt}_{E^{\pi_4}}^{\text{pq-prp}}(\mathcal{A}') + \mathbf{Advt}_{E^{\pi_3}}^{\text{pq-prp}}(\mathcal{A}') + \mathbf{Advt}_{E^{\pi_2}}^{\text{pq-prp}}(\mathcal{A}') \\
&\quad + \mathbf{Advt}_{E^{\pi_1}}^{\text{pq-prp}}(\mathcal{A}') + \frac{q^2}{2^n} + \frac{q^2}{2^{2n}} \\
&\leq \frac{40}{2^{n/2}}(p\sqrt{q} + q\sqrt{p}) + \frac{q^2}{2^n} + \frac{q^2}{2^{2n}},
\end{aligned}
$$

where the last line uses the main result of [ABKM22]. This completes the proof of Corollary 2. □
# D Post-Quantum Security of Blind Hash

Let $\Gamma$ denote an independent uniform random function from $\{0, 1\}^m$ to $\{0, 1\}^n$. Recall that the blind hash $\Gamma^\oplus$: $\{0, 1\}^m \times \{0, 1\}^m \to \{0, 1\}^n$ is a keyed function which is defined by the mapping:

$$ (k, x) \mapsto \Gamma(k \oplus x). $$

We show that $\Gamma_k^\oplus$ achieves post-quantum PRF security when $k \leftarrow_S \{0, 1\}^m$. The proof uses a sequence of hybrids which is similar to Section 4, but simpler.

We emphasize that a “one-way-to-hiding” (or O2H) styled [Unr14, AHU19] proofs will likely lead to a loss in the security bound. Indeed, Grilo et al. also mention [GHHM21] that solving the so-called “adaptive reprogramming” problem (which inspired the “adaptive resampling game” in our paper, following the terminology from [ABKM22]) only with variants of O2H often leads to a loss in the security bound. More specifically, a Proposition 2 like result is difficult to attain using O2H. Thus, we find it unlikely that the proof could be done in an O2H style while keeping the bound tight.

**Theorem 2.** For any computationally unbounded adversary $\mathcal{A}'$ that makes $q'$ classical queries to $\Gamma^\oplus$ and $p'$ quantum queries to $\Gamma$, it holds that

$$ \mathbf{Advt}_{\Gamma^\oplus}^{\text{pq-prf}}(\mathcal{A}') \le 4p' \sqrt{\frac{2q'}{2^m}} + 3q' \sqrt{\frac{2p'}{2^m}} + \frac{4q'^2}{2^m}. $$

*Proof.* We replace $\mathcal{A}'$ which makes an adaptive choice of the sequence in which it accesses its oracle, with $\mathcal{A}$ that fixes a non-adaptive sequence of oracle access pattern. By Proposition 3, such an adversary $\mathcal{A}$ exists and it makes at most $q = 2q'$ classical queries to the construction and $p = 2p'$ quantum queries to each of the primitives. Henceforth, we work with this modified adversary $\mathcal{A}$.

Let $\Lambda$ denote a uniform random function from $\{0, 1\}^m$ to $\{0, 1\}^n$ sampled independently of $\Gamma$.

The goal of $\mathcal{A}$ is to distinguish between the real world ($\Gamma^\oplus, \Gamma$) and the ideal world ($\Lambda, \Gamma$), where the first oracle from the left in both the worlds only allow classical access and the remaining oracle provides quantum access.

We divide $\mathcal{A}$'s query phase into $(q+1)$ epochs $0, \dots, q$, where the $i$-th epoch is represented by the sequence of primitive queries after the $i$-th classical query and before the $(i+1)$-th classical query. In particular, $i=0$ represents the epoch before the first classical query, and $i=q$ represents the epoch after the final classical query. Let $p_i$ denote the number of primitive queries in the $i$-th epoch. We will use the notations developed in Section 3.

For any $i \in [q]$, let $\tau_i = \{(x_1, y_1), \dots, (x_i, y_i)\}$ be the set of the first $i$ classical query-response tuples, where $x_i$ denotes the $i$-th query and $y_i$ denotes the corresponding response for all $j \in [i]$. Let $\tau_0 = \emptyset$. For any $i \in [q]$ and any $k \in \{0, 1\}^m$, $\nu_{i,k} := \{k \oplus x_j : (x_j, y_j) \in \tau_i\}$ is called the *input set*. Recall that $\Gamma^{\nu_{i,k}}$ denotes the locally-redefined copy of $\Gamma$.

Now, let $\mathbf{H}_0, \dots, \mathbf{H}_q$ denote a sequence of $q+1$ hybrids, where $\mathbf{H}_i$ is defined as follows:

1. Sample $k \leftarrow_S \{0, 1\}^m$.

2. Answer the first $i$ classical queries from $\mathcal{A}$ using $\Lambda$ and the quantum queries from $\mathcal{A}$ in the first $i$ epochs (which ends when the $(i+1)$-st classical query is made) using $\Gamma$.

3. Answer all subsequent classical queries from $\mathcal{A}$ using $\Gamma_k^\oplus$.

4. Answer all subsequent quantum queries from $\mathcal{A}$ using $\Gamma^{\nu_{i,k}}$.

Since $\tau_0 = \emptyset$, we deduce that $\mathbf{H}_0$ corresponds to $\mathcal{A}$'s interaction with the real world. Similarly, one can easily notice that $\mathbf{H}_q$ corresponds to $\mathcal{A}$'s interaction with the ideal world.

For $i \in \{0, 1, \dots, q\}$, let $\mathbf{E}_i$ denote the event that $\mathcal{A}$ returns 1 in the random experiment $\mathbf{H}_i$. Then, the triangle inequality gives

$$ \begin{aligned} \mathbf{Advt}_{\Gamma^\oplus}^{\text{pq-prf}}(\mathcal{A}) &= |\Pr(\mathbf{E}_0) - \Pr(\mathbf{E}_q)| \\ &\le \sum_{i=0}^{q-1} |\Pr(\mathbf{E}_i) - \Pr(\mathbf{E}_{i+1})| \end{aligned} \qquad (47) $$
All that remains is to bound $|\Pr(E_i) - \Pr(E_{i+1})|$ for all $i \in \{0, \dots, q-1\}$, which is incidentally the technical core of this proof. For any $i \in \{0, \dots, q-1\}$, $\mathbf{H}_i$ can be viewed as a string of oracle calls made by $\mathcal{A}$

$$ \underbrace{\Gamma \wedge \Gamma \dots \wedge \Gamma}_{i \text{ classical queries}} \overbrace{\Gamma_k^{\oplus} \Gamma_{\nu_{i,k}} \dots \Gamma_k^{\oplus} \Gamma_{\nu_{i,k}}}^{q-i \text{ classical queries}} $$

where each occurrence of $\wedge$ (res. $\Gamma^\Gamma$) indicates a single classical query and each occurrence of $\Gamma$ (res. $\Gamma^{\nu_{i,k}}$) indicates the sequence of primitive queries in the $i$-th epoch. In this representation, we want to compare:

$$ \mathbf{H}_i: \underbrace{\Gamma \wedge \Gamma \dots \wedge \Gamma}_{i \text{ classical queries}} \Gamma_k^{\oplus} \Gamma_{\nu_{i,k}} \overbrace{\Gamma_k^{\oplus} \Gamma_{\nu_{i,k}} \dots \Gamma_k^{\oplus} \Gamma_{\nu_{i,k}}}^{q-i-1 \text{ classical queries}} $$

$$ \mathbf{H}_{i+1}: \underbrace{\Gamma \wedge \Gamma \dots \wedge \Gamma}_{i \text{ classical queries}} \wedge \Gamma \overbrace{\Gamma_k^{\oplus} \Gamma_{\nu_{i+1,k}} \dots \Gamma_k^{\oplus} \Gamma_{\nu_{i+1,k}}}^{q-i-1 \text{ classical queries}} $$

To aid this comparison we introduce an intermediate hybrid $\hat{\mathbf{H}}_i$ which is defined as follows:

1. Sample $k \leftarrow \$ \{0, 1\}^m$.

2. Answer the first $i+1$ classical queries from $\mathcal{A}$ using $\wedge$ and the quantum queries from $\mathcal{A}$ in the first $i$ epochs (which ends when the $(i+1)$-st classical query is made) using $\Gamma$.

3. Answer all subsequent classical queries from $\mathcal{A}$ using $\Gamma_k^{\oplus}$.

4. Answer all subsequent quantum queries from $\mathcal{A}$ using $\Gamma^{\nu_{i+1,k}}$.

For $i \in \{0, \dots, q-1\}$, let $\hat{\mathbf{E}}_i$ denote the event that $\mathcal{A}$ returns 1 in the random experiment $\hat{\mathbf{H}}_i$. The corresponding string representation is given by

$$ \underbrace{\Gamma \wedge \Gamma \dots \wedge \Gamma}_{i \text{ classical queries}} \wedge \Gamma^{\nu_{i+1,k}} \overbrace{\Gamma_k^{\oplus} \Gamma_{\nu_{i+1,k}} \dots \Gamma_k^{\oplus} \Gamma_{\nu_{i+1,k}}}^{q-i-1 \text{ classical queries}} $$

Now, we do the following comparisons in pairs from top to bottom:

$$ \mathbf{H}_i: \underbrace{\Gamma \wedge \Gamma \dots \wedge \Gamma}_{i \text{ classical queries}} \Gamma_k^{\oplus} \Gamma_{\nu_{i,k}} \overbrace{\Gamma_k^{\oplus} \Gamma_{\nu_{i,k}} \dots \Gamma_k^{\oplus} \Gamma_{\nu_{i,k}}}^{q-i-1 \text{ classical queries}} $$

$$ \hat{\mathbf{H}}_i: \underbrace{\Gamma \wedge \Gamma \dots \wedge \Gamma}_{i \text{ classical queries}} \wedge \Gamma^{\nu_{i+1,k}} \overbrace{\Gamma_k^{\oplus} \Gamma_{\nu_{i+1,k}} \dots \Gamma_k^{\oplus} \Gamma_{\nu_{i+1,k}}}^{q-i-1 \text{ classical queries}} $$

$$ \mathbf{H}_{i+1}: \underbrace{\Gamma \wedge \Gamma \dots \wedge \Gamma}_{i \text{ classical queries}} \wedge \Gamma \overbrace{\Gamma_k^{\oplus} \Gamma_{\nu_{i+1,k}} \dots \Gamma_k^{\oplus} \Gamma_{\nu_{i+1,k}}}^{q-i-1 \text{ classical queries}} $$

In Lemma 7 and 8 we show that:

$$ |\Pr(\hat{\mathbf{E}}_i) - \Pr(\mathbf{E}_{i+1})| \le 2p_{i+1}\sqrt{\frac{(i+1)}{2^m}}, \qquad (48) $$

$$ |\Pr(\mathbf{E}_i) - \Pr(\hat{\mathbf{E}}_i)| \le 1.5 \sqrt{\frac{p}{2^m}} + \frac{i}{2^m}. \qquad (49) $$

Using the triangle inequality and Eqs. (49) and (48), we have

$$ |\Pr(\mathbf{E}_i) - \Pr(\mathbf{E}_{i+1})| \le 2p_{i+1}\sqrt{\frac{(i+1)}{2^m}} + 1.5\sqrt{\frac{p}{2^m}} + \frac{i}{2^m}. \qquad (50) $$

Substituting Eq. (50) in Eq. (47), followed by summing over all the distances, yields the result. $\square$

**Lemma 7.** For all $i \in \{0, \dots, q-1\}$ we have

$$ |\Pr(\hat{\mathbf{E}}_i) - \Pr(\mathbf{E}_{i+1})| \le 2p_{i+1}\sqrt{\frac{(i+1)}{2^m}}. $$
Proof. Recall that we can have the following string representations for the two hybrids.

<figure><img src="image_10.png" /></figure>

It is clear that the two hybrids are identical, except for the (i + 1)-th epoch, where $\hat{\mathbf{H}}_i$ uses a locally redefined variant $\Gamma^{\nu_{i+1,k}}$ of $\Gamma$ and $\mathbf{H}_{i+1}$ uses the unchanged $\Gamma$. We will show that this small “reprogramming” of $\Gamma$ does not disturb it too much.

More formally, given the adversary $\mathcal{A}$ we construct an ARP distinguisher $\mathcal{D}$ as follows:

**Phase 1.A.** This covers all the queries up to and including the (i + 1)-th classical query:

1. $\mathcal{D}$ samples a uniform random permutation $\Lambda$ of $\{0, 1\}^{2n}$.

2. All classical queries from $\mathcal{A}$ are answered using $\Lambda$.

3. All quantum queries from $\mathcal{A}$ are answered using $\mathcal{D}$'s random oracle $\Gamma$.

**Phase 1.B.** This is the step where $\mathcal{D}$ decides whether to reprogram, or not:

1. $\mathcal{D}$ defines the following randomized algorithm $\mathcal{B}$:

(a) Sample $k \leftarrow \$ \{0, 1\}^m$.

(b) Compute and return the set $\nu_{i+1,k}$.

**Phase 2.** This covers the queries in the (i + 1)-th epoch:

1. $\mathcal{B}$ is run to generate $\nu_{i+1,k}$ and for $b \leftarrow \$ \{0, 1\}$, $\mathcal{D}$ is given quantum access to $\Gamma_b$, where $\Gamma_0 = \Gamma$ and $\Gamma_1 = \Gamma^{\nu_{i+1,k}}$.

2. All quantum queries from $\mathcal{A}$ are answered using $\Gamma_b$.

**Phase 3.** This covers the queries starting from the (i + 2)-th classical query and beyond:

1. $\mathcal{D}$ receives $k$ (the randomness used in $\mathcal{B}$), and thus, it can compute the set $\nu_{i+1,k}$.

2. All classical queries from $\mathcal{A}$ are answered using $\Gamma_k^\oplus$.

3. All quantum queries from $\mathcal{A}$ are answered using $\Gamma^{\nu_{i+1,k}}$.

– $\mathcal{D}$ returns what $\mathcal{A}$ returns.

Clearly, $\mathcal{D}$ is a valid ARP distinguisher. When $b = 0$ (i.e. $\Gamma_b = \Gamma$), $\mathcal{D}$ correctly simulates $\mathbf{H}_{j+1}$. Similarly, when $b = 1$ (i.e. $\Gamma_b = \Gamma^{\nu_{i+1,k}}$), $\mathcal{D}$ correctly simulates $\hat{\mathbf{H}}_i$. Thus, we have

$$ \mathbf{Advt}^{\text{arp}}(\mathcal{D}) = |\Pr(\mathcal{D}^{\Gamma_b} = 1 | b = 1) - \Pr(\mathcal{D}^{\Gamma_b} = 1 | b = 0)| \\ = |\Pr(\hat{\mathbf{E}}_i) - \Pr(\mathbf{E}_{i+1})| \qquad (51) $$

where the equality is simply a rephrasing due to the aforementioned equivalence.

Finally, to apply Proposition 1, we need to bound $\epsilon_B$, the probability that any point $x$ in the domain of $\Gamma$ is reprogrammed. This can be bounded using the fact that $\Gamma^{\nu_{i+1,k}}$ is identical to $\Gamma$ except on the set $\nu_{i+1,k}$. After fixing $\Gamma$ and $\tau_{i+1}$, the probability that any given $x$ is reprogrammed is at most the probability that $x \in \nu_{i+1,k}$. Using the fact that $k$ is uniformly distributed, union bound yields $\epsilon_B \le (i+1)/2^m$. The following follows from using Proposition 1 in Eq. 51:

$$ \mathbf{Advt}_{\Gamma \oplus}^{\text{pq-prf}}(\mathcal{A}') \le 2p\sqrt{\frac{q}{2^m}} + 1.5q\sqrt{\frac{p}{2^m}} + \frac{q^2}{2^m}. $$

Finally, we need to replace $p = 2p'$ and $q = 2q'$ in the bound, leading to the result. $\square$

**Lemma 8.** For all $i \in \{0, \dots, q-1\}$ we have

$$ |\Pr(\mathbf{E}_i) - \Pr(\hat{\mathbf{E}}_i)| \le 1.5\sqrt{\frac{p}{2^m}} + \frac{i}{2^m}. $$
Proof. Recall that we can have the following string representations for the two hybrids.

<figure><img src="image_11.png" /></figure>

Now, given $\mathcal{A}$ we construct a ARS-distinguisher $\mathcal{D}$ as follows:

**Phase 1.** This covers all the queries up to and including the $i$-th epoch:

1. $\mathcal{D}$ samples a uniform random function $\Lambda: \{0, 1\}^m \to \{0, 1\}^n$.

2. All classical queries from $\mathcal{A}$ are answered using $\Lambda$.

3. All quantum queries from $\mathcal{A}$ are answered using $\mathcal{D}$'s random oracle $\Gamma_b$.

**Phase 2.** This is the step where $\mathcal{D}$ resamples:

1. Suppose $\mathcal{A}$'s $(i+1)$-th classical query is $x_{i+1}$.

2. $\mathcal{D}$ queries RS with $\perp$ (assuming $\mathcal{X}_1 = \emptyset$) and let the output be $s$.

3. $\mathcal{D}$ sets $k = s \oplus x_{j+1}$.

**Phase 3.** This covers the $(i+1)$-th classical query and beyond:

1. $\mathcal{D}$ answers all remaining classical queries from $\mathcal{A}$ using $(\Gamma_b)_k^{\oplus}$.

2. $\mathcal{D}$ answers all remaining quantum queries from $\mathcal{A}$ using $\Gamma_b^{\nu_{i,k}}$.

– $\mathcal{D}$ returns whatever $\mathcal{A}$ returns.

For $b \in \{0, 1\}$, let $\mathbf{H}_i^b$ denote the above described game, and let $\mathbf{E}_i^b$ denote the event that $\mathcal{A}$ returns 1 in game $\mathbf{H}_i^b$.

When $b = 0$ (i.e. no resampled oracle), $\mathcal{D}$ answers the remaining classical queries with $\Gamma_k^{\oplus}$ and the remaining quantum queries with $\Gamma_{\nu_{i,k}}$. Thus, $\mathbf{H}_i^0$ is identical with $\mathbf{H}_i$. Furthermore, since $\mathcal{D}$ is a valid ARS distinguisher using Proposition 2 we have

$$|\Pr(\mathbf{E}_i) - \Pr(\mathbf{E}_i^1)| = |\Pr(\mathbf{E}_i^0) - \Pr(\mathbf{E}_i^1)| \le \mathbf{Advt}^{\mathcal{ars}}(\mathcal{D}) \le 1.5\sqrt{\frac{p}{2^m}}. \quad (52)$$

When $b = 1$ (i.e. resampled oracle is used), $\mathcal{D}$ answers the remaining classical queries with $(\Gamma_1)_k^{\oplus}$ and the remaining quantum queries are answered using $\Gamma_1^{\nu_{i,k}}$. Consider the following event:

$$\mathbf{bad}_1: x_{i+1} \in \{x_1, \dots, x_i\}.$$

In the event of $\neg \mathbf{bad}_1$, we not that response to the $(i+1)$-th classical query, denoted $z$ (say), is sampled uniformly$^9$ at random and independent of all other variables. Thus, $z$ is identically distributed with $\Lambda(x_{i+1})$, and hence $\nu_{i+1,k}^1 = \nu_{i,k} \cup \{(x_{j+1} \oplus k, z)\}$ in $\mathbf{H}_i^1$ is identically distributed with $\nu_{i+1,k}$ generated in $\hat{\mathbf{H}}_i$, assuming $\neg \mathbf{bad}_1$ holds in $\mathbf{H}_i^1$. Furthermore, assuming $\neg \mathbf{bad}_1$, the random oracle $\Gamma$ is essentially reprogrammed on $\nu_{i+1,k}^1$ points in $\mathbf{H}_i^1$, where $i$ points are reprogrammed directly, since they are part of $\nu_{i,k}$, and one point is reprogrammed indirectly due to the resampling at $s = x_{j+1} \oplus k$. Thus, it is reprogrammed on the same set as $\nu_{i+1,k}$. Then, using the fundamental lemma of game playing [BR06], we have

$$|\Pr(\mathbf{E}_i^1) - \Pr(\hat{\mathbf{E}}_i)| \le \Pr(\mathbf{bad}_1) \le \frac{i}{2^m}, \quad (53)$$

where the last inequality follows from the uniformity of $s$. The result follows by accumulating the bounds in Eqs. (52)-(53). $\square$

<footnote>$^9$ Indeed, the output is resampled here</footnote>
E Proof of Lemma 5

Recall that under the assumption that the hybrids do not abort we can have the following string representations for the two hybrids.

$$
\begin{align*}
\hat{\mathbf{H}}_i: \underbrace{\Gamma \Gamma \dots \Gamma}_{i \text{ classical queries}} \Gamma^{\Gamma_{i+1,k}} \underbrace{\mathbf{F}_k^{\Gamma} \Gamma^{\Gamma_{i+1,k}} \dots \mathbf{F}_k^{\Gamma} \Gamma^{\Gamma_{i+1,k}}}_{q-i-1 \text{ classical queries}} \\
\mathbf{H}_{i+1}: \underbrace{\Gamma \Gamma \dots \Gamma}_{i \text{ classical queries}} \Gamma^{\Gamma_k^{\Gamma_{i+1,k}} \dots \Gamma_k^{\Gamma_{i+1,k}}} \underbrace{\mathbf{F}_k^{\Gamma} \Gamma^{\Gamma_{i+1,k}} \dots \mathbf{F}_k^{\Gamma} \Gamma^{\Gamma_{i+1,k}}}_{q-i-1 \text{ classical queries}}
\end{align*}
$$

It is clear that the two hybrids are identical, except for the (i + 1)th epoch, where $\hat{\mathbf{H}}_i$ uses a locally redefined variant $\Gamma^{\nu_{i+1,k}}$ of $\Gamma$ and $\mathbf{H}_{i+1}$ uses the unchanged $\Gamma$. We will show that this small “reprogramming” of $\Gamma$ does not disturb it too much.

More formally, given the adversary $\mathcal{A}$ we construct an ARP distinguisher $\mathcal{D}$ as follows:

Phase 1.A. for all the queries up to and including the (i + 1)th classical query:

1. $\mathcal{D}$ samples a uniform random permutation $\Pi$ of $\{0, 1\}^{2n}$.

2. All classical queries from $\mathcal{A}$ are answered using $\Pi$.

3. All quantum queries from $\mathcal{A}$ are answered using $\mathcal{D}$'s random oracle $\Gamma_b$, where $\Gamma_0 = \Gamma_1 = \Gamma$.

Phase 1.B. $\mathcal{D}$ defines the randomized algorithm $\mathcal{B}$:

1. $\mathcal{B}$ initializes a flag $\mathbf{A} \leftarrow 0$.

2. $\mathcal{B}$ samples a key $k = (k_1, k_2, k_3, k_4) \stackrel{\$}{\leftarrow} \{0, 1\}^{4n}$ and computes the set $\nu_{i+1,k}$.

3. If $\nu_{i+1,k} \neq \emptyset$ and invalid, then $\mathcal{B}$ sets $\mathbf{A} \leftarrow 1$ and $\nu_{i+1,k} = \emptyset$.

4. $\mathcal{B}$ returns the set $\nu_{i+1,k}$.

Phase 2. This covers the queries in the (i + 1)th epoch:

1. $\mathcal{B}$ is run to generate $\nu_{i+1,k}$ and for $b \stackrel{\$}{\leftarrow} \{0,1\}$, $\mathcal{D}$ is given quantum access to $\Gamma_b$, where $\Gamma_0 = \Gamma$ and $\Gamma_1 = \Gamma^{\nu_{i+1,k}}$. If $\mathbf{A} = 0$, it is easy to see that $\nu_{i+1,k}$ is valid.

2. All quantum queries from $\mathcal{A}$ are answered using $\Gamma_b$.

3. At the end of this phase, $\mathcal{D}$ receives $k$, and it checks the value of $\mathbf{A}$.

Phase 3. for all the queries beyond and including the (i + 2)th classical query:

1. If $\mathbf{A} = 1$ then:

(a) All classical queries from $\mathcal{A}$ are answered with the error symbol $\perp$.

(b) All quantum queries from $\mathcal{A}$ are answered using $\Gamma_b$.

2. Else:

(a) $\mathcal{D}$ computes the set $\nu_{i+1,k}$.

(b) All classical queries from $\mathcal{A}$ are answered using $\mathbf{F}_k^{\Gamma}$.

(c) All quantum queries from $\mathcal{A}$ are answered using $\Gamma_b^{\nu_{i+1,k}}$.

- If $\mathbf{A} = 1$ then $\mathcal{D}$ returns 0, and otherwise it returns whatever $\mathcal{A}$ returns.

Clearly, $\mathcal{D}$ is a valid ARP distinguisher. When $\mathbf{A} = 0$ and $b = 0$, $\mathcal{D}$ correctly simulates $\mathbf{H}_{i+1}$. Similarly, when $\mathbf{A} = 0$ and $b = 1$, $\mathcal{D}$ correctly simulates $\hat{\mathbf{H}}_i$. Furthermore, for the case $\mathbf{A} = 1$, $\mathcal{D}$'s output is independent of $\mathcal{A}$'s output (although perfect simulation still holds). It also holds that $\mathbf{A} = 1 | b = 1$ is equivalent to $\hat{\mathbf{F}}_i$ and $\mathbf{A} = 1 | b = 0$ is equivalent to $\mathbf{F}_{i+1}$. Due to the identical behaviour of the two hybrids for the first $i$ epochs and the $i+1$-th construction query, we have $\hat{\mathbf{F}}_i \iff \mathbf{F}_{i+1}$ for all $i \in \{0, \dots, q-1\}$. Thus, we have

$$
\begin{align}
\mathbf{Advt}^{\mathbf{arp}}(\mathcal{D}) &= |\Pr(\mathcal{D}^{\Gamma_b} = 1 | b = 1) - \Pr(\mathcal{D}^{\Gamma_b} = 1 | b = 0)| \nonumber \\
&\geq |\Pr(\mathcal{D}^{\Gamma_b} = 1 \wedge \mathbf{A} = 0 | b = 1) - \Pr(\mathcal{D}^{\Gamma_b} = 1 \wedge \mathbf{A} = 0 | b = 0)| \nonumber \\
&= |\Pr(\hat{\mathbf{E}}_i \wedge \neg \hat{\mathbf{F}}_i) - \Pr(\mathbf{E}_{i+1} \wedge \neg \mathbf{F}_{i+1})| \tag{54}
\end{align}
$$

where the first inequality follows from the fact $\mathcal{D}$'s output is completely independent of $\mathcal{A}$ when $\mathbf{A} = 1$ and $\mathbf{A} = 1$ is set with identical probabilities in the two worlds; the last equality is simply a rephrasing due to the aforementioned equivalence.
<table><caption>Fig. 9: Pseudocode for $H_i$ (left) and $\hat{H}_i$ (right) from the proof of Theorem 4.</caption><thead><tr><th>Game H<sub>i</sub>(Π, Γ, A)</th><th>Game ̂H<sub>i</sub>(Π, Γ, A)</th></tr></thead><tbody><tr><td>1: j &larr; 0 // epoch tracker</td><td>1: j &larr; 0 // epoch tracker</td></tr><tr><td>2: ν &larr; ∅</td><td>2: ν &larr; ∅</td></tr><tr><td>3: k &larr; $\{0, 1\}^{3n}$</td><td>3: k &larr; $\{0, 1\}^{3n}$</td></tr><tr><td>4: (k<sub>1</sub>, k<sub>2</sub>, k<sub>3</sub>, k<sub>4</sub>) &larr; k</td><td>4: (k<sub>1</sub>, k<sub>2</sub>, k<sub>3</sub>, k<sub>4</sub>) &larr; k</td></tr><tr><td>5: Γ* &larr; Γ</td><td>5: Γ* &larr; Γ</td></tr><tr><td>6: b &larr; A<sup>CO<sub>i</sub>(·),|Γ*(·)|</sup></td><td>6: b &larr; A<sup>hCO<sub>i</sub>(·),|Γ*(·)|</sup></td></tr><tr><td>7: return b</td><td>7: return b</td></tr><tr><td>CO<sub>i</sub>(1, x<sub>0</sub>, x<sub>1</sub>)</td><td>hCO<sub>i</sub>(1, x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td>1: j &larr; j + 1 // advance epoch</td><td>1: j &larr; j + 1 // advance epoch</td></tr><tr><td>2: if j &le; i then</td><td>2: if j &le; i + 1 then</td></tr><tr><td>3: (x<sub>4</sub>, x<sub>5</sub>) &larr; Π(x<sub>0</sub>, x<sub>1</sub>)</td><td>3: (x<sub>4</sub>, x<sub>5</sub>) &larr; Π(x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td>4: x<sub>2</sub> &larr; x<sub>0</sub> &oplus; Γ(x<sub>1</sub> &oplus; k<sub>1</sub>)</td><td>4: x<sub>2</sub> &larr; x<sub>0</sub> &oplus; Γ(x<sub>1</sub> &oplus; k<sub>1</sub>)</td></tr><tr><td>5: x<sub>3</sub> &larr; x<sub>5</sub> &oplus; Γ(x<sub>4</sub> &oplus; k<sub>4</sub>)</td><td>5: x<sub>3</sub> &larr; x<sub>5</sub> &oplus; Γ(x<sub>4</sub> &oplus; k<sub>4</sub>)</td></tr><tr><td>6: ν &larr; ν &cup; {(x<sub>2</sub> &oplus; k<sub>2</sub>, x<sub>1</sub> &oplus; x<sub>3</sub>)}</td><td>6: ν &larr; ν &cup; {(x<sub>2</sub> &oplus; k<sub>2</sub>, x<sub>1</sub> &oplus; x<sub>3</sub>)}</td></tr><tr><td>7: ν &larr; ν &cup; {(x<sub>3</sub> &oplus; k<sub>3</sub>, x<sub>2</sub> &oplus; x<sub>4</sub>)}</td><td>7: ν &larr; ν &cup; {(x<sub>3</sub> &oplus; k<sub>3</sub>, x<sub>2</sub> &oplus; x<sub>4</sub>)}</td></tr><tr><td>8: return (x<sub>4</sub>, x<sub>5</sub>)</td><td>8: if j = i + 1 and ν is valid then</td></tr><tr><td>9: elsif j = i + 1 and ν is valid then</td><td>9: Γ* &larr; Γ<sup>ν</sup></td></tr><tr><td>10: Γ* &larr; Γ<sup>ν</sup></td><td>10: endif</td></tr><tr><td>11: return Γ<sup>Γ</sup><sub>k</sub>(x<sub>0</sub>, x<sub>1</sub>)</td><td>11: return (x<sub>4</sub>, x<sub>5</sub>)</td></tr><tr><td>12: elsif ν is invalid then</td><td>12: elsif ν is invalid then</td></tr><tr><td>13: return ⊥</td><td>13: return ⊥</td></tr><tr><td>14: else</td><td>14: else</td></tr><tr><td>15: return Γ<sup>Γ</sup><sub>k</sub>(x<sub>0</sub>, x<sub>1</sub>)</td><td>15: return Γ<sup>Γ</sup><sub>k</sub>(x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td>16: endif</td><td>16: endif</td></tr><tr><td>CO<sub>i</sub>(-1, x<sub>4</sub>, x<sub>5</sub>)</td><td>hCO<sub>i</sub>(-1, x<sub>4</sub>, x<sub>5</sub>)</td></tr><tr><td>1: j &larr; j + 1 // advance epoch</td><td>1: j &larr; j + 1 // advance epoch</td></tr><tr><td>2: if j &le; i then</td><td>2: if j &le; i + 1 then</td></tr><tr><td>3: (x<sub>0</sub>, x<sub>1</sub>) &larr; Π<sup>-1</sup>(x<sub>4</sub>, x<sub>5</sub>)</td><td>3: (x<sub>0</sub>, x<sub>1</sub>) &larr; Π<sup>-1</sup>(x<sub>4</sub>, x<sub>5</sub>)</td></tr><tr><td>4: x<sub>2</sub> &larr; x<sub>0</sub> &oplus; Γ(x<sub>1</sub> &oplus; k<sub>1</sub>)</td><td>4: x<sub>2</sub> &larr; x<sub>0</sub> &oplus; Γ(x<sub>1</sub> &oplus; k<sub>1</sub>)</td></tr><tr><td>5: x<sub>3</sub> &larr; x<sub>5</sub> &oplus; Γ(x<sub>4</sub> &oplus; k<sub>4</sub>)</td><td>5: x<sub>3</sub> &larr; x<sub>5</sub> &oplus; Γ(x<sub>4</sub> &oplus; k<sub>4</sub>)</td></tr><tr><td>6: ν &larr; ν &cup; {(x<sub>2</sub> &oplus; k<sub>2</sub>, x<sub>1</sub> &oplus; x<sub>3</sub>)}</td><td>6: ν &larr; ν &cup; {(x<sub>2</sub> &oplus; k<sub>2</sub>, x<sub>1</sub> &oplus; x<sub>3</sub>)}</td></tr><tr><td>7: ν &larr; ν &cup; {(x<sub>3</sub> &oplus; k<sub>3</sub>, x<sub>2</sub> &oplus; x<sub>4</sub>)}</td><td>7: ν &larr; ν &cup; {(x<sub>3</sub> &oplus; k<sub>3</sub>, x<sub>2</sub> &oplus; x<sub>4</sub>)}</td></tr><tr><td>8: return (x<sub>0</sub>, x<sub>1</sub>)</td><td>8: if j = i + 1 and ν is valid then</td></tr><tr><td>9: elsif j = i + 1 and ν is valid then</td><td>9: Γ* &larr; Γ<sup>ν</sup></td></tr><tr><td>10: Γ* &larr; Γ<sup>ν</sup></td><td>10: endif</td></tr><tr><td>11: return Γ<sup>Γ<sup>-1</sup></sup>(x<sub>4</sub>, x<sub>5</sub>)</td><td>11: return (x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td>12: elsif ν is invalid then</td><td>12: elsif ν is invalid then</td></tr><tr><td>13: return ⊥</td><td>13: return ⊥</td></tr><tr><td>14: else</td><td>14: else</td></tr><tr><td>15: return Γ<sup>Γ<sup>-1</sup></sup>(x<sub>4</sub>, x<sub>5</sub>)</td><td>15: return Γ<sup>Γ<sup>-1</sup></sup>(x<sub>4</sub>, x<sub>5</sub>)</td></tr><tr><td>16: endif</td><td>16: endif</td></tr></tbody></table>
Finally, to apply Proposition 1, we need to bound $\epsilon_B$, the probability that any point $x$ in the domain of $\Gamma$ is reprogrammed. This can be bounded using the fact that $\Gamma^{\nu_{i+1,k}}$ is identical to $\Gamma$ except on the set $\nu_{i+1,k}$. After fixing $\Gamma$ and $\tau_{i+1}$, the probability that any given $x$ is reprogrammed is at most the probability that $x \in \nu_{i+1,k}^{(2)} \cup \nu_{i+1,k}^{(3)}$. Using the fact that $k_2$ and $k_3$ are uniformly distributed, the union bound yields $\epsilon_B \le 2(i+1)/2^n$. The result then follows from using Proposition 1 in Eq. 54. $\square$

# F Proof of Lemma 6

The proof only slightly differs from the one of Lemma 4. Under the assumption that the hybrids do not abort, we can have the following string representations for the two hybrids.

$$ \mathbf{H}_i: \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \Gamma^{\nu_{i,k}} \quad \underbrace{\Gamma^{\Gamma} \Gamma^{\nu_{i,k}} \dots \Gamma^{\Gamma}}_{q-i-1 \text{ classical queries}} \\ \hat{\mathbf{H}}_i: \underbrace{\Gamma \cap \Gamma \dots \cap \Gamma}_{i \text{ classical queries}} \Gamma^{\nu_{i+1,k}} \quad \underbrace{\Gamma^{\Gamma} \Gamma^{\nu_{i+1,k}} \dots \Gamma^{\Gamma}}_{q-i-1 \text{ classical queries}} $$

Given $\mathcal{A}$ we now construct an ARS-distinguisher $\mathcal{D}$ as follows:

**Phase 1.** for all the queries up to and including the $i^{th}$ epoch:

1. $\mathcal{D}$ samples a uniform random permutation $\Pi: \{0,1\}^{2n} \to \{0,1\}^{2n}$.

2. All classical queries from $\mathcal{A}$ are answered using $\Pi$.

3. All quantum queries from $\mathcal{A}$ are answered using $\mathcal{D}$'s random oracle $\Gamma_b$.

**Phase 2.** $\mathcal{D}$ resamples:

1. It samples $k_1, k_4 \leftarrow \$ \{0,1\}^n$.

2. Suppose $\delta^{i+1} = 1$, i.e., $(i+1)$-th classical query is in the forward direction.

(a) It computes $x_2^{i+1} = \Gamma(x_1^{i+1} \oplus k_1) \oplus x_0^{i+1}$.

(b) $\mathcal{D}$ queries RS with $\perp$ (assuming $\mathcal{X}_1 = \emptyset$); let the output be $s_2$.

(c) It sets $k_2 = s_2 \oplus x_2^{i+1}$ and $x_3^{i+1} = \Gamma(s_2) \oplus x_1^{i+1}$.

(d) $\mathcal{D}$ queries RS with $\perp$ (assuming $\mathcal{X}_1 = \emptyset$); let the output be $s_3$.

(e) It sets $k_3 = s_3 \oplus x_3^{i+1}$, $x_4^{i+1} = \Gamma(s_3) \oplus x_2^{i+1}$ and $x_5^{i+1} = \Gamma(x_4^{i+1} \oplus k_4) \oplus x_3^{i+1}$.

3. Suppose $\delta^{i+1} = -1$, i.e., $(i+1)$-th classical query is in the backward direction.

(a) It computes $x_3^{i+1} = \Gamma(x_4^{i+1} \oplus k_4) \oplus x_5^{i+1}$.

(b) $\mathcal{D}$ queries RS with $\perp$ (assuming $\mathcal{X}_1 = \emptyset$); let the output be $s_3$.

(c) It sets $k_3 = s_3 \oplus x_3^{i+1}$ and computes $x_2^{i+1} = \Gamma(s_3) \oplus x_4^{i+1}$.

(d) $\mathcal{D}$ queries RS with $\perp$ (assuming $\mathcal{X}_1 = \emptyset$); let the output be $s_2$.

(e) It sets $k_2 = s_2 \oplus x_2^{i+1}$ and computes $x_1^{i+1} = \Gamma(s_2) \oplus x_3^{i+1}$, $x_0^{i+1} = \Gamma(x_1^{i+1} \oplus k_1) \oplus x_2^{i+1}$.

4. At this stage $\mathcal{D}$ computes the set $\nu_{i,k}^{(1)}, \nu_{i,k}^{(4)}$.

**Phase 3.** for all queries beyond and including the $(i+1)^{th}$ classical query:

1. $\mathcal{D}$ initializes $\mathcal{A} \leftarrow 0$.

2. If $\nu_{i,k}$ is invalid then:

(a) $\mathcal{D}$ sets $\mathcal{A} \leftarrow 1$.

(b) $\mathcal{D}$ answers all remaining classical queries from $\mathcal{A}$ with the error symbol $\perp$.

(c) $\mathcal{D}$ answers all remaining quantum queries from $\mathcal{A}$ with $\Gamma_b$.

3. Else:

(a) $\mathcal{D}$ answers all remaining classical queries from $\mathcal{A}$ using $\Gamma_b^{\Gamma_b}$.

(b) $\mathcal{D}$ answers all remaining quantum queries from $\mathcal{A}$ using $\Gamma_b^{\Gamma_b}$.

– If $\mathcal{A} = 1$ then $\mathcal{D}$ returns 0, otherwise it returns whatever $\mathcal{A}$ returns.

For $b \in \{0,1\}$, let $\mathbf{H}_i^b$ denote the above described game, and let $\mathbb{E}_i^b$ denote the event that $\mathcal{A}$ returns 1 in game $\mathbf{H}_i^b$. Unless stated otherwise in the following discussion, assume $\mathcal{A} = 0$.
<table><caption>Fig. 10: Pseudocode for $\mathbf{H}_i^b$ from the proof of Lemma 6. $\text{Perm}_{2n}$ denotes the set of all permutations over $\{0, 1\}^{2n}$. The pseudocode for RS can be found in Fig. 5.</caption><thead><tr><th>Game H<sup>b</sup><sub>i</sub>(Γ<sub>b</sub>, A)</th><th>CO<sup>b</sup><sub>i</sub>(1, x<sub>0</sub>, x<sub>1</sub>)</th><th>CO<sup>b</sup><sub>i</sub>(-1, x<sub>4</sub>, x<sub>5</sub>)</th></tr></thead><tbody><tr><td>Π ← $\text{Perm}_{2n}$</td><td>j ← j + 1</td><td>j ← j + 1</td></tr><tr><td>j ← 0</td><td>if j ≤ i then</td><td>if j ≤ i then</td></tr><tr><td>τ ← ∅</td><td>(x<sub>4</sub>, x<sub>5</sub>) ← Π(x<sub>0</sub>, x<sub>1</sub>)</td><td>(x<sub>0</sub>, x<sub>1</sub>) ← Π<sup>-1</sup>(x<sub>4</sub>, x<sub>5</sub>)</td></tr><tr><td>Γ* ← Γ<sub>b</sub></td><td>τ ← τ ∪ ((x<sub>0</sub>, x<sub>1</sub>), (x<sub>4</sub>, x<sub>5</sub>))</td><td>τ ← τ ∪ ((x<sub>0</sub>, x<sub>1</sub>), (x<sub>4</sub>, x<sub>5</sub>))</td></tr><tr><td>A ← 0</td><td>return (x<sub>4</sub>, x<sub>5</sub>)</td><td>return (x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td>b ← A<sup>CO<sup>b</sup><sub>i</sub>(·, |Γ*(·))</sup></td><td>else if j = i + 1 then</td><td>else if j = i + 1 then</td></tr><tr><td>if A = 1 then</td><td>k<sub>1</sub>, k<sub>4</sub> ← {0, 1}<sup>n</sup></td><td>k<sub>1</sub>, k<sub>4</sub> ← {0, 1}<sup>n</sup></td></tr><tr><td>return 0</td><td>x<sub>2</sub> ← x<sub>0</sub> ⊕ Γ<sub>b</sub>(x<sub>1</sub> ⊕ k<sub>1</sub>)</td><td>x<sub>3</sub> ← x<sub>5</sub> ⊕ Γ<sub>b</sub>(x<sub>4</sub> ⊕ k<sub>4</sub>)</td></tr><tr><td>else</td><td>s<sub>2</sub> ← RS(⊥)</td><td>s<sub>3</sub> ← RS(⊥)</td></tr><tr><td>return b</td><td>k<sub>2</sub> ← s<sub>2</sub> ⊕ x<sub>2</sub></td><td>k<sub>3</sub> ← s<sub>3</sub> ⊕ x<sub>3</sub></td></tr><tr><td>endif</td><td>x<sub>3</sub> ← x<sub>1</sub> ⊕ Γ<sub>b</sub>(s<sub>2</sub>)</td><td>x<sub>2</sub> ← x<sub>4</sub> ⊕ Γ<sub>b</sub>(s<sub>3</sub>)</td></tr><tr><td></td><td>s<sub>3</sub> ← RS(⊥)</td><td>s<sub>2</sub> ← RS(⊥)</td></tr><tr><td></td><td>k<sub>3</sub> ← s<sub>3</sub> ⊕ x<sub>3</sub></td><td>k<sub>2</sub> ← s<sub>2</sub> ⊕ x<sub>2</sub></td></tr><tr><td></td><td>x<sub>4</sub> ← x<sub>2</sub> ⊕ Γ<sub>b</sub>(s<sub>3</sub>)</td><td>x<sub>1</sub> ← x<sub>3</sub> ⊕ Γ<sub>b</sub>(s<sub>2</sub>)</td></tr><tr><td></td><td>x<sub>5</sub> ← x<sub>3</sub> ⊕ Γ<sub>b</sub>(x<sub>4</sub> ⊕ k<sub>4</sub>)</td><td>x<sub>0</sub> ← x<sub>2</sub> ⊕ Γ<sub>b</sub>(x<sub>1</sub> ⊕ k<sub>1</sub>)</td></tr><tr><td></td><td>k ← (k<sub>1</sub>, k<sub>2</sub>, k<sub>3</sub>, k<sub>4</sub>)</td><td>k ← (k<sub>1</sub>, k<sub>2</sub>, k<sub>3</sub>, k<sub>4</sub>)</td></tr><tr><td></td><td>for ((x'<sub>0</sub>, x'<sub>1</sub>), (x'<sub>4</sub>, x'<sub>5</sub>)) ∈ τ do</td><td>for ((x'<sub>0</sub>, x'<sub>1</sub>), (x'<sub>4</sub>, x'<sub>5</sub>)) ∈ τ do</td></tr><tr><td></td><td>x'<sub>2</sub> ← x'<sub>0</sub> ⊕ Γ<sub>b</sub>(x'<sub>1</sub> ⊕ k<sub>1</sub>)</td><td>x'<sub>2</sub> ← x'<sub>0</sub> ⊕ Γ<sub>b</sub>(x'<sub>1</sub> ⊕ k<sub>1</sub>)</td></tr><tr><td></td><td>x'<sub>3</sub> ← x'<sub>5</sub> ⊕ Γ<sub>b</sub>(x'<sub>4</sub> ⊕ k<sub>4</sub>)</td><td>x'<sub>3</sub> ← x'<sub>5</sub> ⊕ Γ<sub>b</sub>(x'<sub>4</sub> ⊕ k<sub>4</sub>)</td></tr><tr><td></td><td>ν ← ν ∪ {(x'<sub>2</sub> ⊕ k<sub>2</sub>, x'<sub>1</sub> ⊕ x'<sub>3</sub>)}</td><td>ν ← ν ∪ {(x'<sub>2</sub> ⊕ k<sub>2</sub>, x'<sub>1</sub> ⊕ x'<sub>3</sub>)}</td></tr><tr><td></td><td>ν ← ν ∪ {(x'<sub>3</sub> ⊕ k<sub>3</sub>, x'<sub>2</sub> ⊕ x'<sub>4</sub>)}</td><td>ν ← ν ∪ {(x'<sub>3</sub> ⊕ k<sub>3</sub>, x'<sub>2</sub> ⊕ x'<sub>4</sub>)}</td></tr><tr><td></td><td>endfor</td><td>endfor</td></tr><tr><td></td><td>if ν is valid then</td><td>if ν is valid then</td></tr><tr><td></td><td>Γ* ← Γ<sup>ν</sup><sub>b</sub></td><td>Γ* ← Γ<sup>ν</sup><sub>b</sub></td></tr><tr><td></td><td>return (x<sub>4</sub>, x<sub>5</sub>)</td><td>return (x<sub>0</sub>, x<sub>1</sub>)</td></tr><tr><td></td><td>else</td><td>else</td></tr><tr><td></td><td>A ← 1</td><td>A ← 1</td></tr><tr><td></td><td>return ⊥</td><td>return ⊥</td></tr><tr><td></td><td>endif</td><td>endif</td></tr><tr><td></td><td>else if ν is invalid then</td><td>else if ν is invalid then</td></tr><tr><td></td><td>A ← 1</td><td>A ← 1</td></tr><tr><td></td><td>return ⊥</td><td>return ⊥</td></tr><tr><td></td><td>else</td><td>else</td></tr><tr><td></td><td>return Γ<sup>Γ<sub>b</sub></sup><sub>k</sub>(x<sub>0</sub>, x<sub>1</sub>)</td><td>return Γ<sup>Γ<sub>b</sub>-1</sup><sub>k</sub>(x<sub>4</sub>, x<sub>5</sub>)</td></tr><tr><td></td><td>endif</td><td>endif</td></tr></tbody></table>
<figure><img src="image_12.png" /><figcaption>Fig. 11: Pseudocode for $\hat{\mathbf{H}}_i^1$ from the proof of Lemma 6</figcaption></figure>
It is clear that the hybrid $\mathbf{H}_i^0$ is identical to $\mathbf{H}_i$. Indeed in this case, $\mathcal{D}$ answers all the remaining classical queries with $\mathbf{F}_k^\Gamma$ and the remaining quantum queries with $\Gamma^{\nu_{i,k}}$. Looking at Phase 3.2 we also observe that $A = 1 | b = 0$ is identical to $\mathbf{F}_i$. Let $\mathbf{F}_i^1$ denote the event $A = 1 | b = 1$. Then, since $\mathcal{D}$ is a valid ARS distinguisher, we have

$$ 
\begin{aligned}
\mathbf{Advt}^{\text{ars}}(\mathcal{D}) &= |\Pr(\mathcal{D}^{\Gamma_{b,RS}} = 1 | b = 1) - \Pr(\mathcal{D}^{\Gamma_{b,RS}} = 1 | b = 0)| \\
&\geq |\Pr(\mathcal{D}^{\Gamma_{b,RS}} = 1 \wedge A = 0 | b = 1) - \Pr(\mathcal{D}^{\Gamma_{b,RS}} = 1 \wedge A = 0 | b = 0)| \\
&\geq |\Pr(\mathbf{E}_i^1 \wedge \neg \mathbf{F}_i^1) - \Pr(\mathbf{E}_i \wedge \neg \mathbf{F}_i)|,
\end{aligned}
\quad (55) $$

where at the second inequality, we used the fact that $A = 0 | b = 0$ is exactly the event $\neg \mathbf{F}_i$.

Now, consider the hybrid $\mathbf{H}_i^1$. In this case, the output $(x_4^{i+1}, x_5^{i+1})$ corresponding to the $(i+1)^{\text{th}}$ classical forward query $(x_0^{i+1}, x_1^{i+1})$ is given by

$$ 
\begin{aligned}
x_4^{i+1} &= y_3 \oplus x_2^{i+1}, \\
x_5^{i+1} &= y_2 \oplus x_1^{i+1} \oplus \Gamma(x_4^{i+1}),
\end{aligned}
 $$

where $y_2, y_3 \stackrel{\$}{\leftarrow} \{0,1\}^n$ correspond to the resampled value of $\Gamma(s_2)$ and $\Gamma(s_3)$ and the random value of $\Gamma(x_4^{i+1} \oplus k_4)$, respectively. Thus, $(x_4^{i+1}, x_5^{i+1})$ is uniformly distributed over $\{0,1\}^{2n}$. Similarly, the output $(x_0^{i+1}, x_1^{i+1})$ corresponding to the $(i+1)^{\text{th}}$ classical backward query $(x_4^{i+1}, x_5^{i+1})$ is given by

$$ 
\begin{aligned}
x_0^{i+1} &= y_3 \oplus x_4^{i+1} \oplus \Gamma(x_1^{i+1}), \\
x_1^{i+1} &= y_2 \oplus x_3^{i+1},
\end{aligned}
 $$

Thus, $(x_4^{i+1}, x_5^{i+1})$ is uniformly distributed over $\{0,1\}^{2n}$.

Let $\hat{\mathbf{H}}_i^1$ denote a slight modification of $\hat{\mathbf{H}}_i$ that works exactly the same as $\hat{\mathbf{H}}_i$, except at the $(i+1)^{\text{th}}$ classical query, where the output is sampled uniformly from $\{0,1\}^{2n}$ and independent of $\Pi$. Then, it is straightforward that:

$$ |\Pr(\hat{\mathbf{E}}_i \wedge \neg \hat{\mathbf{F}}_i) - \Pr(\hat{\mathbf{E}}_i^1 \wedge \neg \hat{\mathbf{F}}_i)| \le \frac{q}{2^{2n}} \quad (56) $$

where $\hat{\mathbf{E}}_i^1$ denotes the event that $A$ returns 1 in $\hat{\mathbf{H}}_i^1$.

Coming back to $\mathbf{H}_i^1$, $\mathcal{D}$ answers the remaining classical queries with $\mathbf{F}_k^\Gamma$ and the remaining quantum queries with $\Gamma_{1}^{\nu_{i,k}}$. Consider the following two events:

$$ \text{bad}_4: x_2^{i+1} \oplus k_2 \in \nu_{i,k} \cup \nu_{i,k}^{(1)} \cup \nu_{i,k}^{(4)}, $$

$$ \text{bad}_5: x_3^{i+1} \oplus k_3 \in \nu_{i,k} \cup \nu_{i,k}^{(1)} \cup \nu_{i,k}^{(4)}. $$

We claim that $\mathbf{H}_i^1$ and $\hat{\mathbf{H}}_i^1$ are identical up to $\text{bad}_4 \vee \text{bad}_5$. Indeed, $\neg \text{bad}_4 \wedge \neg \text{bad}_5$ implies that the $(i+1)^{\text{th}}$ classical query output is uniformly distributed over $\{0,1\}^{2n}$ and independent of $\Pi$. Furthermore, assuming $\neg (\text{bad}_4 \vee \text{bad}_5)$, the random oracle $\Gamma$ is essentially reprogrammed on $\nu_{i+1,k}^*$ points in $\mathbf{H}_i^1$, where $2i$ points are reprogrammed directly, since they are part of $\nu_{i,k}$, and exactly two points are reprogrammed indirectly due to the resampling at $s_2 = x_2^{i+1} \oplus k_2$ and $s_3 = x_3^{i+1} \oplus k_3$. Then, using the fundamental lemma of the game-playing technique [BR06], we have

$$ |\Pr(\hat{\mathbf{E}}_i^1 \wedge \neg \hat{\mathbf{F}}_i^1) - \Pr(\hat{\mathbf{E}}_i^1 \wedge \neg \hat{\mathbf{F}}_i)| \le \Pr(\text{bad}_4 \vee \text{bad}_5). \quad (57) $$

Then combining Eqs. (55)-(57) and applying Proposition 2 gives:

$$ |\Pr(\mathbf{E}_i \wedge \neg \mathbf{F}_i) - \Pr(\hat{\mathbf{E}}_i \wedge \neg \hat{\mathbf{F}}_i)| \le 3\sqrt{\frac{p}{2^n}} + \frac{q}{2^{2n}} + \Pr(\text{bad}_4 \vee \text{bad}_5). \quad (58) $$

We write $\text{bad}_4 = \text{bad}_{411} \vee \text{bad}_{412} \vee \text{bad}_{42}$, where:

$$ \text{bad}_{411}: \text{ there exists } j \in [i] \text{ such that } \delta_{i+1} = 1 \text{ and } x_2^{i+1} = x_2^j, $$
- bad$_{412}$: there exists $j \in [i]$ such that $\delta_{i+1} = -1$ and $x_2^{i+1} = x_2^j$,

- bad$_{42}$: there exists $j \in [i]$, $r \in \{1, 3, 4\}$ such that $x_2^{i+1} \oplus k_2 = x_r^j \oplus k_r$.

Similarly, we write bad$_5$ = bad$_{511} \lor bad_{512} \lor bad_{52}$ into three events:

- bad$_{511}$: there exists $j \in [i]$ such that $\delta_{i+1} = -1$ and $x_3^{i+1} = x_3^j$,

- bad$_{512}$: there exists $j \in [i]$ such that $\delta_{i+1} = 1$ and $x_3^{i+1} = x_3^j$,

- bad$_{52}$: there exists $j \in [i]$, $r \in \{1, 2, 4\}$ such that $x_3^{i+1} \oplus k_3 = x_r^j \oplus k_r$.

Using these finer events, we can rewrite $Pr(bad_4 \lor bad_5)$ as follows:

$$ \begin{aligned} \Pr(bad_4 \lor bad_5) &\le \Pr(bad_{411} \lor bad_{412} \lor bad_{42} \lor bad_{511} \lor bad_{512} \lor bad_{51}) \\ &\le \Pr(bad_{42}) + \Pr(bad_{52}) + \Pr(bad_{411}) + \Pr(bad_{511}) \\ &\quad + \Pr(bad_{412} | \neg bad_0) + \Pr(bad_{412} | \neg bad_0), \end{aligned} \quad (59) $$

where bad$_0$ = bad$_{42} \lor bad_{52} \lor bad_{411} \lor bad_{511}$.

First, using the uniformity of $k_2$ and $k_3$ (since $s_2$ and $s_3$, the resampled points, are uniform), we have $Pr(bad_{42}) + Pr(bad_{52}) \le 6i/2^n$.

Next, using a similar argumentation as used in the proof of Lemma 4, we apply Lemma 1 to get

$$ \Pr(bad_{411}) + \Pr(bad_{511}) \le 3\sqrt{\frac{p}{2^n}} + \frac{2i}{2^n}. $$

Finally, conditioned on bad$_0$, $s_3$ is fresh in the backward queries and $s_2$ is fresh in the forward queries. Thus, the corresponding resampled outputs $y_3$ (in the backward queries) and $y_2$ (in the forward queries) are uniform and independent of all other variables. This immediately gives:

$$ \Pr(bad_{412} | \neg bad_0) + \Pr(bad_{412} | \neg bad_0) \le \frac{2i}{2^n}. $$

Substituting all the bounds in Eq. (59) gives:

$$ \Pr(bad_4 \lor bad_5) \le 3\sqrt{\frac{p}{2^n}} + \frac{10i}{2^n}. \quad (60) $$

Finally using Eqs. (60) in Eq. (58) completes the proof. □