# Quantum Security of the Legendre PRF

Paul Frixons, André Schrottenloher

► To cite this version:

Paul Frixons, André Schrottenloher. Quantum Security of the Legendre PRF. Mathematical Cryptology, 2022, 1 (2), pp.52–69. hal-03529834

HAL Id: hal-03529834

https://inria.hal.science/hal-03529834

Submitted on 17 Jan 2022

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
# Quantum Security of the Legendre PRF

Paul Frixons<fnref n="1" />,<fnref n="2" />,*, André Schrottenloher<fnref n="3" />

Received: August 17, 2021 | Revised: August 17, 2021 | Accepted: August 17, 2021

**Abstract** In this paper, we study the security of the Legendre PRF against quantum attackers, given classical queries only, and without quantum random-access memories. We give two algorithms that recover the key of a shifted Legendre symbol with unknown shift, with a complexity smaller than the exhaustive search of the key. The first one is a quantum variant of the table-based collision algorithm. The second one is an offline variant of Kuperberg’s abelian hidden shift algorithm. We note that the latter, although asymptotically promising, is not currently the most efficient against practical parameters.

**Keywords:** Legendre PRF, quantum cryptanalysis, quantum algorithms, abelian hidden shift problem, Kuperberg’s algorithm.

**2010 Mathematics Subject Classification:** 94A60, 68Q12, 81P68, 11A15, 11Y16

## 1 INTRODUCTION

Let $P$ be a prime number and $a \in \mathbb{F}_p$. The Legendre symbol of $a$ modulo $P$ is defined as $(\frac{a}{p}) = 1$ if $a$ is a square modulo $P$ and $-1$ otherwise (by convention, $(\frac{0}{p}) = 1$). Its use in cryptography was first proposed by Damgård in [19], who conjectured the hardness of the following problem:

**Problem 1 (Legendre sequence randomness).** Given a sequence of consecutive Legendre symbols starting at some given value $a \in \mathbb{F}_p$, of some length $m \in \text{poly}(\log_2 P)$:

$$ (\frac{a}{p}, (\frac{a+1}{p}), \dots, (\frac{a+m-1}{p}), \text{ then find } (\frac{a+m}{p}). $$

That is, consecutive Legendre symbols form a pseudo-random sequence of bits. A similar problem can be defined for the *Jacobi symbol*, which is a generalization of the Legendre symbol to a composite basis $N = P_1 \times \dots \times P_r$: $(\frac{a}{N}) := \prod_i (\frac{a}{P_i})$.

**The Legendre PRF.** The conjecture of Damgård naturally leads to the definition of a pseudo-random function based on the *shifted Legendre symbol*, as in [18]:

$$ \left\{ \begin{array}{rcl} F_{\text{Leg}} & : & \mathbb{F}_p \times \mathbb{F}_p \rightarrow \{-1, 1\} \\ & & (s, x) \mapsto (\frac{s+x}{p}) \end{array} \right. $$

or as in [21], by remapping $\{-1, 1\}$ on $\{0, 1\}$. For a given secret $s$, distinguishing $F_{\text{Leg}}(s, x)$ from random values is the *decisional shifted Legendre symbol problem* (DSLS), the decisional version of the *shifted Legendre symbol problem* (SLS), which asks for the recovery of $s$. At the moment, no separation between the SLS and the DSLS is known. In this paper, as in previous works, we will focus on solving the SLS.

**Problem 2 (Shifted Legendre Symbol).** Let $P$ be a prime number. Given query access to the function $F_{\text{Leg},s}$ : $x \mapsto (\frac{x+s}{p})$ for some secret $s \in \mathbb{F}_p$, find $s$.

The Legendre symbol PRF has recently regained significant interest with the proposal of Grassi et al. [21] to use it in a multi-party computation scenario. They showed precisely that there existed a simple MPC protocol to compute the PRF on secret-shared data, using the malleability of the Legendre symbol.

Since then, the PRF has been considered for use in the Ethereum blockchain, and the Ethereum foundation has proposed several challenges to encourage cryptanalysis research [20]. While the Ethereum challenges are not

<footnote n="1">¹ Orange Labs, Caen, France</footnote>

<footnote n="2">² Inria, Paris, France</footnote>

<footnote n="3">³ Cryptology Group, CWI, Amsterdam, The Netherlands</footnote>

<footnote>*Corresponding Author: firstname.lastname@inria.fr</footnote>
explicitly concerned with quantum adversaries, this is the case of the LegRoast signature scheme proposed in [5], which adapts the Picnic construction [15] with the Legendre PRF. Solving the SLS problem allows to break these different schemes; however, in both cases the adversary cannot make chosen-plaintext queries to the PRF. In the Ethereum challenges he only knows a (large) sequence of successive Legendre symbols, a condition that can be satisfied by all the algorithms studied in this paper. In LegRoast, he only learns the evaluation of the PRF on a few random, uncontrolled inputs.

In this paper, we focus on the SLS problem, and so, the security of the Legendre PRF, against a quantum adversary. The algorithms considered derive their advantage from making a large number of queries, and so, they do not impact all applications of the PRF in the same way (e.g., LegRoast does not seem to be affected).

**Previous Results.** The SLS problem is a particular case of the *shifted character problem*, where the Legendre symbol is replaced by any multiplicative character of a finite field. This problem was studied by van Dam *et al.* [18] in the quantum setting. When *superposition query access* to the shifted character is given, they showed that the problem could be solved in polynomial time, using a single query.

However, when only *classical* queries are available, the SLS problem is believed to remain intractable for a quantum attacker, and was conjectured so by van Dam *et al.* and by Grassi *et al.*.

In the classical setting, several authors have studied and improved the Legendre PRF key-recovery attacks [27, 25, 6]. We give a summary in Table 1, and recapitulate the detailed complexities in Table 2 in Appendix. The most advanced results were obtained by Beullens *et al.* [6] and concurrently by Kaluderović *et al.* [25, 26]. Given a sequence of *M* Legendre symbols, they recover the secret in about $\tilde{O}(\frac{P}{M^2})$ operations. Their technique is a *table-based collision search*, whose principle will be reviewed in Section 3. Generalizations of the Legendre PRF (e.g. when $x + s$ is replaced by a polynomial in $x$) have also been studied.

Even more recently, Seres, Horváth and Burcsi [35] showed that the problem of recovering the key of a Legendre PRF is equivalent to solving some multivariate quadratic system of equations. So far this approach did not yield better attacks than those of [25, 6], as dedicated algebraic attacks seem inefficient against this system.

**On the use of QRACM.** In the quantum setting, it was proposed [25] to use a quantum version of the table-based collision search (some remarks were also made in [6]). However, in the same way that the classical attack uses a large table, the quantum attack will use a table of similar size. This table requires the model of *classical memory with quantum random-access (QRACM)*. Although this is a powerful memory model, it is required by many quantum algorithms, e.g., for BHT quantum collision search [11], which makes it theoretically worth studying.

No practical, scalable implementation of QRACM exists at the moment, and near-term quantum architectures are expected to consist only of error-corrected quantum circuits of small width. Several authors envision an advantage coming from parallel circuits rather than memory usage [3, 24]. In this context, QRACM can be seen as a conservative assumption, that cannot be always accurate. This is why, more recently, quantum cryptanalytic algorithms have been developed that aim for an advantage over classical algorithms, while using standard computing qubits only.

To our knowledge, there are two main examples of this. The first one is the technique applied in [14] to collision search and [23] for the subset-sum problem. In this setting, QRACM is replaced by a large classical memory, which is accessed sequentially. While QRACM essentially accesses a memory of size *M* in time $polylog(M)$, these algorithms access a memory of size *M* in time $\tilde{O}(M)$. This is the technique that we apply in Section 3.

The second one, much more dependent on the structure of the problem, uses a hidden shift property, as in [10]. In this setting, there is no large-scale memory anymore, neither classical nor quantum. Thus having QRACM or not becomes less of a concern. This is the technique that we apply in Section 5. Although the complexity scales differently with the number of queries, the algorithm eventually reaches the same limit as the QRACM-heavy table-based collision search when *M* increases to $P^{1/3}$. However, it suffers from a subexponential factor in time complexity. But this factor might become competitive compared to the cost of maintaining and accessing a large QRACM.

**Contributions.** We perform the first analysis of quantum algorithms for the SLS problem without QRACM. We give two techniques and we discuss their applicability: first, a *quantum table-based collision search* that builds over the multi-target preimage search of [14]. Second, an *offline decisional abelian hidden shift algorithm*, or *offline-DAHS* for short, which is an offline adaptation of Kuperberg's algorithm [28], similar to the *offline Simon's algorithm* of Bonnetain *et al.* [10]. Although [10] mention this as a possibility, the authors did not perform a precise complexity analysis, leaving notably the subexponential factor to be analyzed.

With this method, the quantum attack on the SLS can reach a time complexity $2^{O(\sqrt{log_2 P})} P^{1/3}$, while using $M = P^{1/3}$ classical queries, with a subexponential number of qubits only. The corresponding classical attack would
<table><caption>Table 1: Lowest time complexity (in $P$) achieved by the known SLS algorithms and corresponding memory and queries. For ease of comparison, we dismiss polynomial factors in $\log_2 P$.</caption><thead><tr><th>Method</th><th>Queries</th><th>Time<br>Classical algorithms</th><th>Memory</th><th>Source</th></tr></thead><tbody><tr><td>Pollard's rho</td><td>√P</td><td>√P</td><td>polylog(P)</td><td>[27]</td></tr><tr><td>Table</td><td>P<sup>1/4</sup></td><td>√P</td><td>√P</td><td>[6, 25]</td></tr><tr><td colspan="5" style="text-align: center;">Quantum algorithms</td></tr><tr><td>Sup. queries</td><td>2</td><td>polylog(P)</td><td>polylog(P)</td><td>[18]</td></tr><tr><td>Table (QRACM)</td><td>P<sup>1/6</sup></td><td>P<sup>1/3</sup></td><td>P<sup>1/3</sup> QRACM</td><td>[25]</td></tr><tr><td>Grover search</td><td>polylog(P)</td><td>√P</td><td>polylog(P) qubits</td><td>Sec. 3.2</td></tr><tr><td>Table (no QRACM)</td><td>P<sup>3/14</sup></td><td>P<sup>3/7</sup></td><td>P<sup>3/14</sup> classical<br>+ polylog(P) qubits</td><td>Sec. 3.3</td></tr><tr><td>Offline-DAHS</td><td>P<sup>1/3</sup></td><td>(2<sup>4/3</sup>√2log<sub>2</sub> 3√log<sub>2</sub> P<sup>1/3</sup>)P<sup>1/3</sup></td><td>2√2log<sub>2</sub> 3√log<sub>2</sub> P<sup>1/3</sup> qubits</td><td>Sec. 5.3</td></tr></tbody></table>

reach a complexity $\tilde{O}(P^{1/2})$ with a classical table of size $O(P^{1/2})$. In fact, when only $M = P^{1/3}$ queries are given, the time-memory product of the classical methods remains at $O(P)$.

Despite the asymptotic efficiency of offline-DAHS, it is quite challenging to optimize. We detail a possible quantum circuit design, perform some cost estimates on small instances and compare with the table-based collision search. So far, we find that the subexponential factor makes it non-competitive for prime sizes smaller than 200 bits. But offline-DAHS seems to offer more room for improvement than the table-based attacks. We leave further optimizations as an open question.

**Organization of the Paper.** We give some technical preliminaries in Section 2. In Section 3, we recall the classical table-based attacks and introduce our first algorithm. In Section 4, we introduce Kuperberg's first algorithm and show how to perform its operations reversibly, which is crucial for offline-DAHS. We finally introduce the full algorithm offline-DAHS in Section 5 and apply it to the SLS problem.

# 2 PRELIMINARIES OF QUANTUM COMPUTING

## 2.1 QUANTUM CIRCUITS

We refer to [31] for an introduction to the quantum circuit model. Our quantum algorithms are described as quantum circuits: the time complexity is counted as the number of basic quantum gates (e.g., Clifford + T gates) and the space complexity is the number of qubits. Sometimes, also, we count the classical memory used. As our considerations are mainly asymptotic, most implementation details remain out of scope of our work. For example, we consider that a modular addition of two $n$-bit values costs $O(n)$ basic gates [17]. Swapping two $n$-qubit registers, comparing two $n$-qubit registers, or comparing a given $n$-qubit register with a classical value all cost $O(n)$ gates. We show in Appendix 9 that the Legendre symbol modulo $P$ can be computed with $O((\log_2 P)^2)$ gates.

Although we perform these gate counts at a rather high level, this does not prevent us from comparing two algorithms by counting the number of $n$-qubit operations that they use (i.e., additions or comparisons). This is what we do in Appendix 11.

We use the term *ancilla* qubits for qubits that are initialized to the state $|0\rangle$, used by the circuit and returned to their initial state. We say that a computation is performed *out of place* if its output is written on an additional register and *in place* otherwise. We routinely use the standard “ket” notation of quantum states $|\psi\rangle$, and standard operators such as the $M$-dimensional Quantum Fourier Transform:

$$ |x\rangle \stackrel{\text{QFT}_M}{\longrightarrow} \frac{1}{\sqrt{M}} \sum_{y \in \mathbb{Z}_M} \chi_M(xy) |y\rangle, \text{ where } \chi_M(z) = \exp(2i\pi z/M), $$

which we assume exact. When $f$ is a boolean function, we use the notation $O_f$ for its *phase oracle* which maps in place: $O_f|x\rangle = (-1)^{f(x)}|x\rangle$. Otherwise, we use $O_f$ for the *standard oracle* which maps: $O_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$.

As quantum states are always normalized, and equivalent up to a global phase, we will omit common amplitude and phase factors for readability.
## 2.2 QUANTUM SEARCH

In this paper, we make use of Amplitude Amplification [12], a powerful generalization of Grover's quantum search [22]. It allows to speed up the search for a "good" output of any probabilistic algorithm, including another quantum algorithm.

**Theorem 1** ([12], Theorem 2 and 4). Let $\mathcal{A}$ be a quantum algorithm that uses no measurements, let $f: X \to \{0, 1\}$ be a boolean function that tests if an output of $\mathcal{A}$ is "good". Let $\mathcal{A}$ be the success probability of $\mathcal{A}$. Let $O_0$ be the "inversion around zero" operator that does: $O_0 |x\rangle = (-1)^{x \neq 0} |x\rangle$ and $O_f$ a quantum oracle for $f$: $O_f |x\rangle = (-1)^{f(x)} |x\rangle$. Let $\theta_a = \arcsin \sqrt{a}$ and $0 < \theta_a \le \frac{\pi}{2}$. Let $t = \lfloor \frac{\pi}{4\theta_a} \rfloor$. Then by measuring $(\mathcal{A}O_0\mathcal{A}^\dagger O_f)^t \mathcal{A}|0\rangle$, we obtain a good result with success probability greater than $\max(1 - a, a)$.

If $a$ is unknown, then an iterated version of the algorithm allows to retrieve a good result with $O(1/\sqrt{a})$ iterations on average.

Next, we use another result on Grover search using an approximate test oracle. This is an important object in the context of offline search algorithms such as offline-Simon [10] or offline-DAHS below.

We consider a boolean function $f: \{0, 1\}^n \to \{0, 1\}$ and an oracle $O_f$ that uses an ancillary state $|\psi\rangle$. This ancillary state is required by the oracle to perform its computations, and it must be preserved. So one would expect to map: $|x\rangle|\psi\rangle \xrightarrow{O_f} (-1)^{f(x)} |x\rangle|\psi\rangle$. However, the exact $O_f$ cannot be implemented, only an approximation $O'_f$.

**Definition 1.** An approximate test oracle for $f$, denoted $O'_f$, is a unitary operator that maps:

$$ \forall x \in \{0, 1\}^n, |x\rangle|\psi\rangle \xrightarrow{O'_f} (-1)^{f(x)} |x\rangle|\psi\rangle + |\delta_x\rangle $$

where $|\psi\rangle$ is the predefined ancillary state which must be preserved by the oracle, and $\max_x |||\delta_x\rangle|| \le \epsilon$.

That is, on each input vector, the oracle incurs a uniform error of amplitude $\epsilon$ (the same for all basis states). If this error is small enough, an Amplitude Amplification using $O'_f$ instead of $O_f$ will not "see" the difference. In our case, contrary to [10], we will also start from an approximate initial state. We summarize these needs with the following.

**Theorem 2** (Quantum search with approximate test). Let $\mathcal{A}, a, t = \lfloor \frac{\pi}{4\theta_a} \rfloor$ be defined as in Theorem 1. Let $f$ be a boolean function that tests if an output of $\mathcal{A}$ is "good", and let $O'_f$ be an approximate oracle for $f$ with error $\epsilon$, using an ancillary state $|\psi\rangle$, as per Definition 1. Let $|\psi'\rangle$ be a quantum state such that $|||\psi\rangle - |\psi'\rangle|| \le v$. We run the following algorithm:

$$ ((1 \otimes \mathcal{A})(1 \otimes O_0)(1 \otimes \mathcal{A}^\dagger)O'_f)^t |\psi'\rangle, $$

that is, $t$ iterations of "approximate" quantum search using $O'_f$, where $t$ is the identity operator applied to the ancillary state $|\psi\rangle$. Then measuring the output yields a good result with probability greater than $(1 - t\epsilon - v)^2 \max(1 - a, a)$.

For completeness, we give a proof of Theorem 2 in Appendix 8. It consists in bounding the euclidean distance, step by step, between the current state of the "ideal" version of the algorithm (starting from $|\psi\rangle$ and applying $O_f$) and the "real" one (starting from $|\psi'\rangle$ and applying $O'_f$).

**Corollary 1.** If $v \le \frac{1}{4}$ and $\epsilon \le \frac{1}{4t}$, then the procedure of Theorem 2 succeeds with probability $\ge \frac{1}{8}$.

*Proof.* We use simply that $\sin^2((2t+1)\theta) \ge \frac{1}{2}$ and $1 - t \max(\epsilon_{FN}, \epsilon_{FP}) - \epsilon \ge 1 - \frac{1}{4} - \frac{1}{4} = \frac{1}{2}$. $\square$

We stress that Theorem 2 and Corollary 1 contain two important features, that are both crucial for solving the SLS problem: • the test oracle can be imperfect, as soon as the error is uniform and exponentially small (when $t$ is exponential); • the ancillary state used by the approximate test can also be approximated, and the corresponding error $v$ can be a constant.

## 3 TABLE-BASED ATTACKS

In this section, we first recall the classical table-based collision search of [6, 25] (Section 3.1), and the idea of early abort in a Grover search (Section 3.2), which is a folklore technique that we will use to save logarithmic factors. Next, we introduce our new quantum table-based collision search. It combines the ideas of the classical attack and the quantum collision search algorithm of [14]. The notations follow those of Beullens et al. [6].
As all the attacks studied in this paper, the table-based collision attacks use chosen, but non-adaptive queries to the Legendre PRF. More precisely, we assume that we can query $M < \sqrt{P}$ consecutive values of the Legendre PRF, of the form $(\frac{x+s}{P})$ where $0 \le x \le M-1$ and $s$ is the secret. This is actually the setting of the Ethereum challenges [20].

## 3.1 CLASSICAL ALGORITHM

We set $m = 3[\log_2 P]$. The attack parses the $M$ sequential Legendre symbols to create $L$-sequences: words of $m$ bits that allow to discriminate a guess of $s$. The definition of $L$-sequences is from [6] and we slightly simplify it. We define:

$$L_a = \left( \left( \frac{a}{P} \right), \left( \frac{a+1}{P} \right), \dots, \left( \frac{a+m-1}{P} \right) \right).$$

Assuming that the Legendre PRF is “sufficiently random”, and that $m$ is big enough, a collision of $L$-sequences implies the equality of their parameters: $L_a = L_b \Rightarrow a = b$. With our choice of $m$, we will assume that no random collisions occur at all. This is a stronger heuristic than the one commonly used in the classical cryptanalysis of the Legendre PRF (see [6], Assumption 1). It will simplify our analysis of quantum algorithms.

**Heuristic 1.** For all $a, b \in \mathbb{Z}_p^*$, $L_a = L_b \Rightarrow a = b$.

In order to recover the secret $s$, one then looks for a collision between an $L$-sequence of unknown parameter (depending on $s$) and an $L$-sequence of known parameter. A basic attack could use the $M$ queries to obtain $M - m$ $L$-sequences, and then, evaluate random $L$-sequences in search for a collision. This would give a complexity $O(M + \frac{P}{M})$ (as two $L$-sequences can only collide with probability $\frac{1}{P}$).

The attacks of [6, 25, 26] improve the trade-off between $M$ and the time complexity, by extracting more $L$-sequences from the available queries. This uses the multiplicativity of the Legendre symbol. The attacks run as follows:

1. From the $M$ consecutive Legendre symbols, extract $\frac{M^2}{m}$ $L$-sequences of the form:

$$\left( \left( \frac{a+s}{P} \right), \left( \frac{a+b+s}{P} \right), \dots, \left( \frac{a+b(m-1)+s}{P} \right) \right) \\ = \left( \frac{b}{P} \right) \left( \left( \frac{a/b+s/b}{P} \right), \left( \frac{a/b+1+s/b}{P} \right), \dots, \left( \frac{a/b+(m-1)+s/b}{P} \right) \right) \\ = \left( \frac{b}{P} \right) L_{(s/b+a/b) \bmod P}.$$

Since we can use $b \le \lfloor \frac{M}{m} \rfloor$ and $a < M - bm + 1$, the number of sequences is increased quadratically with respect to the naive extraction.

2. Store all the extracted sequences $(L_{(s/b+a/b) \bmod P}, a, b)$ in a table.

3. Sample $c$ at random until $(L_c, a, b)$ appears in the table for some $a, b$. Such a collision yields a candidate key $s$ such that: $s/b + a/b = c \Rightarrow s = cb - a \bmod P$. We can then test if this candidate is the good one with a few more computations. With Heuristic 1, there are no false positives, and $s$ is the right key.

This classical attack requires $M^2$ storage for the table, and expectedly $mP/M^2$ samples must be tested in Step 3 before a collision occurs. Thus Step 3 requires $O(m^2P/M^2)$ Legendre symbol computations. Further optimizations allow to reduce the memory to $M^2/m$ and to amortize the cost of computing Legendre symbols in an iteration of the loop.

**Quantum Version with QRACM.** This procedure yields a quantum attack as proposed in [25]. The precomputation stage (Step 1) is unchanged, but now Step 3 is a quantum search. Instead of running $O(mP/M^2)$ classical iterations, we need only $O(\sqrt{mP/M^2})$ iterates, each of which performs $O(m)$ Legendre symbol computations and a memory access. This can only be efficient if we use classical memory with quantum random-access (QRACM).

## 3.2 QUANTUM SEARCH WITH EARLY ABORT

Using the same $M$ classical sequential queries, but without QRACM, the first quantum attack available is a direct quantum search of the secret $s$. We query the $L$-sequence $L_s$ (thus using only $m$ data) and search for $x \in \mathbb{Z}_p^*$ such that $L_x = L_s$. We simply apply Theorem 1, where the amplified algorithm $S_{\mathbb{Z}_p^*}$ consists in sampling an element $x \in \mathbb{Z}_p^*$ at random: $S_{\mathbb{Z}_p^*}|0\rangle = \sum_{x \in \mathbb{Z}_p^*} |x\rangle$, and the test $f$ consists in checking if $L_x = L_s$. By Heuristic 1, there is only one such solution; thus the algorithm requires $O(m\sqrt{P})$ (quantum) Legendre symbol computations, in total $O(m^3\sqrt{P})$ quantum gates.
**Early-aborting.** In a classical search for a sequence matching $L_s$, we can stop the computation of $L_x$ at the first bit that does not match. This reduces the average number of Legendre symbols computed from $m$ to a constant. In the quantum setting, this folklore idea allows to amortize the factor $m$ down to $\log_2 m$.

We select a constant $i \le m$ and define a subset of $Z_p^*$: $X_i = \{x \in Z_p^*, L_x$ and $L_s$ match on the first $i$ bits $\}$.
We know that $s$ belongs to $X_i$, and by the pseudorandomness of the Legendre PRF, that $X_i$ is roughly of size $\frac{P}{2^i}$.
Furthermore, testing if a given $x$ is in $X_i$ requires to compute only $i$ Legendre symbols, not $m$. This allows to filter out most of the incorrect values.

We first use Theorem 1 to create an “inner” search: an algorithm $S_{X_i}$ that samples from $X_i$. This algorithm runs a quantum search over $x \in Z_p^*$, with $O(\sqrt{2^i})$ iterations, computing $i$ Legendre symbols each. Since we do not know exactly the size of $X_i$, we must run the search with a fixed number of iterations, and the output state is not exactly the uniform superposition over $X_i$. However, we only need to sample from $X_i$ with constant probability $\alpha$. Afterwards, the output of $S_{X_i}$ is “good” for us (equal to $s$) with probability $\alpha^{2^i}$, where $\alpha$ is a constant.

We can thus use Theorem 1 again. We amplify $S_{X_i}$, using $O(\sqrt{\frac{P}{2^i}})$ iterations in total. Each iteration contains a computation of $S_{X_i}$ and $m-i$ Legendre symbols. This gives a total complexity:

$$O\left(\sqrt{\frac{P}{2^i}}\left(\sqrt{2^i}(iL) + (m-i)L\right)\right). \text{ Taking } i = 2\log_2 m \text{ and simplifying gives: } O\left(\log_2 m\sqrt{P}L\right).$$

### 3.3 DISTINGUISHED COLLISIONS

Since we do not assume QRACM, we have to modify the table-based collision strategy if we are to beat the square-root complexity given by Grover search. We will use the strategy of [14] for multi-target preimage search, and adapt the algorithm of Section 3.1 as follows:

1. From the $M$ Legendre symbols, extract $\frac{M^2}{m}$ $L$-sequences.

2. Store only the $\frac{M^2}{m2^i}$ “distinguished” sequences that start with $t$ zeroes (an arbitrary choice).

3. Sample $x$ such that $L_x$ is distinguished, until it matches one of the stored sequences.

We use Amplitude Amplification again. First, we built a quantum algorithm $S_D$ that samples $x$ such that $L_x$ is distinguished. We can do that in time: $O(\log_2 t\sqrt{2^t}L)$ using an early-aborted quantum search. Again, $S_D$ is not exact, and if we measure its output, we get a distinguished $L_x$ with constant probability only. But this is enough.

We next estimate the probability that $S_D$ returns a “good” output, that is, an $x$ such that $L_x$ collides with one of the stored sequences. There are on average $P/2^t$ distinguished sequences, and the probability to collide on the table is roughly $\frac{M^2/(m2^t)}{P/2^t}$. Depending on the exact number of distinguished sequences, this probability also deviates from the expectation, but not more than by a constant.

Next, to test if a distinguished $L_x$ matches one of the stored sequences, we use a sequential circuit containing quantum gates controlled by classical values. A single $L_a$ can be compared to the current $L_x$ with a comparator using $O(m)$ gates; we repeat this for all distinguished sequences of our table.

Assuming that we use all the data, this yields an algorithm of complexity:

$$O\left(M^2 + \sqrt{\frac{P}{2^t \times \frac{M^2}{m2^t}}} \left(\log_2 t\sqrt{2^t}L + mL + \frac{M^2}{m2^t}m\right)\right).$$

Note that the outer number of iterations has been reduced, because two distinguished sequences have a higher probability to collide than two random sequences. By taking $t = \frac{4}{3}\log_2(M/m)$ we get a complexity:

$$O\left(M^2 + \sqrt{\frac{Pm}{M^2}} \left(\frac{M}{m}\right)^{2/3} (\log_2 \log_2 M)m^2\right) = O\left(M^2 + \frac{\sqrt{P}}{M^{1/3}} m^{11/6} \log_2 \log_2 M\right).$$

Note that a memory of size $M$ is required during Step 1 (extraction), and $M^{2/3}m$ during Step 3 (search). Both are only classical. Also, the memory of Step 3 is accessed only once per iteration ($\sqrt{\frac{Pm}{M^2}}$ in total) and in a sequential way. The complexity of the classical table-based collision decreases with the available data $M$, from $\tilde{O}(P)$ down to $\tilde{O}(P^{1/2})$ when $M = P^{1/4}$. This quantum variant decreases from $\tilde{O}(P^{1/2})$ to $\tilde{O}(P^{3/7})$, reaching this minimum when $M = P^{3/14}$ data is available.

## 4 A REVERSIBLE VERSION OF KUPERBERG’S ALGORITHM

In this section, we recall the abelian hidden shift problem and Kuperberg’s first algorithm [28]. It is usually depicted with intermediate measurements and classical postprocessing. Our goal is to make it reversible. Thus,
although we ultimately obtain the same asymptotic complexity, our presentation (from Section 4.3 onwards) is new and differs significantly from the ones of [28, 8].

## 4.1 THE ABELIAN HIDDEN SHIFT PROBLEM

Quantum algorithms for *hidden period* or *hidden shift* problems have seen numerous applications in quantum cryptanalysis. As an example, Shor's algorithm [36] solves the *abelian hidden period* (or *abelian hidden subgroup*) problem in polynomial time: given a function *f* with domain (*G*, +), an abelian group, such that *f*(*x* + *s*) = *f*(*x*) for some *s* ∈ *G*, find *s*. But the problem becomes harder if we look for an abelian *shift* between two functions.

**Problem 3 (Abelian hidden shift).** Let (*G*, +) be an abelian group, *X* a set and *f*, *g* : *G* → *X* a pair of injective functions such that: ∃*s*, ∀*x* ∈ *G*, *g*(*x*) = *f*(*x* + *s*). Then find the shift *s*.

As it was already remarked in [18], the SLS problem is an instance of Problem 3, where: $g(x) = L_{s+x}$, obtained by $m$ queries to the PRF $F_{\text{Leg},s}$, and $f(x) = L_x$, obtained by $m$ computations of Legendre symbols modulo $P$. In this paper, we will not use Kuperberg's algorithm to solve directly the SLS, but a *decisional version* of Problem 3.

**Problem 4 (Decisional abelian hidden shift).** Let $f, g : \mathbb{Z}_{2^n} \to X$ be two injective functions such that either: $\exists s, \forall x, f(x + s) = g(x)$, or $\text{Im}(f) \cap \text{Im}(g) = \emptyset$. Decide which is the case.

## 4.2 KUPERBERG'S ALGORITHM MADE REVERSIBLE

In [28], Kuperberg designed a subexponential-time algorithm to solve Problem 3 (and so Problem 4), using quantum oracle access to *f* and *g*. The original algorithm ran in time $\tilde{O}(2^{\sqrt{(2\log_2 3)^{\log_2 |G|}}})$. Multiple subsequent works have changed the value in the exponent and given trade-offs between classical and quantum computations [33, 29, 16, 7, 8, 32, 9]. If queries, classical and quantum time are counted equally, then the best complexity known to date is $\tilde{O}(2^{\sqrt{2n}})$ with Kuperberg's *collimation sieve* [29]. In this paper, we focus on the earliest algorithm for its simplicity, but we believe that further asymptotic improvements might come from the *collimation sieve*.

As we focus on Problem 4, we will work with an abelian group of the form $G = \mathbb{Z}_{2^n}$ for some $n$. We note $M = 2^n$ the cardinality of the group. Note that the generalization to an arbitrary abelian group would be technical, but without significant incidence on the time complexity [9]. The assumption that the functions are injective is also helpful for our study, but not strictly necessary.

**Sample Database.** We define a *sample state* as: $|\psi_{f,g}\rangle = \sum_{0 \le x \le M-1} (|0\rangle|f(x)\rangle + |1\rangle|g(x)\rangle)|x\rangle$, omitting the common amplitude factor for ease of notation. One creates it with a single oracle query to $O_f$ and $O_g$. Kuperberg's algorithm starts by producing $t = \tilde{O}(2^{\sqrt{\alpha n}})$ such states, where $\alpha = 2^{\log_2 3}$ is obtained from the complexity analysis. We name $|\psi_{f,g}\rangle^{\otimes t}$ the *sample database* of $(f,g)$: it contains all the information on $f$ and $g$ that we need to solve Problem 4.

Our goal is to process this state to decide whether $f$ and $g$ are shifted, *without destroying the database*. Measurements can always be removed from a quantum computation. Thus, we know that we can follow the standard operations of Kuperberg's algorithm, but without performing any measurement, and obtain a quantum circuit DAHS that yields the same result.

However, the standard procedure handles a lot of classical data, and performs non-trivial memory operations. This may increase significantly the time complexity in a fully reversible variant, especially since we do not want to rely on quantum RAM. We will show that reversibility costs only at most a polynomial factor in time. Given the *sample database* $|\psi_{f,g}\rangle^{\otimes t}$, the circuit DAHS finds whether $f$ and $g$ are shifted with constant probability of success. This probability can then be boosted by taking a polynomial number of copies of the circuit (or it can be estimated heuristically, as we do in Appendix 11). All in all, we prove the following theorem.

**Theorem 3.** There exists a quantum circuit DAHS that maps:

$$|\psi_{f,g}\rangle^{\otimes t} |b\rangle \mapsto |\psi_{f,g}\rangle^{\otimes t} |b \oplus \text{DAHS}(f,g)\rangle + |\delta_{f,g}\rangle,$$

where DAHS($f, g$) = 1 if and only if $f$ and $g$ are a shifted pair, and $|||\delta_{f,g}\rangle|||$ is bounded by a constant for all $f, g$ satisfying the conditions of Problem 4. With $t = \tilde{O}(2^{\sqrt{(2\log_2 3)^{\log_2 n}}})$, it contains $\tilde{O}(2^{\sqrt{(2\log_2 3)^{\log_2 n}}})$ quantum gates and ancilla qubits. With a factor $r$ in time and memory complexity, we can reduce the bound on $|||\delta_{f,g}\rangle|||$ to $O(2^{-r/2})$.

We devote the rest of this section to the details of this procedure. For now, we will assume that $f$ and $g$ are shifted, and we will go back to the other case at the end of this section.
## 4.3 LABEL STATES AND LABEL QUBITS

The first step in Kuperberg's algorithm is to transform all the independent sample states into label states, by measuring a value a in the second register and applying an M-dimensional QFT on the third register. In the reversible variant, we don't measure this a. We don't write it either for simplicity (after the QFT, it does not intervene further in the algorithm).

Since the functions are injective, there exists a single $x_0$ that maps to a through f and by assumption, $x_0 - s$ maps to a through g. We obtain:

$$ \begin{aligned} |\phi_{f,g}\rangle = \text{QFT}_M(|0\rangle|x_0\rangle + |1\rangle|x_0-s\rangle) &= \sum_{0 \le y \le M-1} (\chi_M(x_0y)|0\rangle + \chi_M((x_0-s)y)|1\rangle)|y\rangle \\ &= \sum_{0 \le y \le M-1} \chi_M(x_0y)(|0\rangle + \chi_M(-sy)|1\rangle)|y\rangle . \end{aligned} $$

Next, we would have measured the register $|y\rangle$ to obtain a random value y and a label qubit: $|\phi_y\rangle = |0\rangle + \chi_M(-sy)|1\rangle$ (up to a global phase factor). Again, we do not measure y. So we simply write label states as $|\phi_y\rangle|y\rangle$, keeping in mind that there is a superposition over y.

A label qubit contains some information about s, but it is not immediately exploitable, unless we can obtain specific values of y. For example, if $y = 2^{n-1}$, then the qubit is either $|0\rangle + |1\rangle$ or $|0\rangle - |1\rangle$ depending on the least significant bit of s. Recall that we are interested in deciding whether there is a shift or not (Problem 4). We can do that from many independent copies of $|\phi_{2n-1}\rangle$.

**Classical Combinations.** The key step in the algorithm is when we create these wanted labels from the random initial ones. In the standard procedure, the values of the labels are known. From two label qubits $|\phi_{y_1}\rangle$ and $|\phi_{y_2}\rangle$, we can obtain $|\phi_{y_1\pm y_2}\rangle$ with a CNOT and a measurement. This destroys both qubits and returns either $y_1 + y_2$, or $y_1 - y_2$, with probability $\frac{1}{2}$. The procedure then consists in combining pairs of labels $(y_1, y_2)$ that maximize the expected valuation of $y_1 \pm y_2$ modulo 2. We let $\text{val}_2(z) = \max\{i, 2^i|z\}$ denote this valuation.

**Complexity.** The complexity analysis in [28] gives that $\tilde{O}(2^{\sqrt{(2\log_2 3)n}})$ initial label qubits are enough. Simulations in [28] showed that $2^{\sqrt{(2\log_2 3)n}}$ were essentially enough to solve Problem 3 with constant probability, for groups of the form $\mathbb{Z}_{2n}$. Interestingly, the algorithm is pseudoclassical: the combination step can be easily simulated by sampling labels at random. This allows to compute precisely how many labels will be needed for a given instance of the problem, and to obtain the corresponding success probability.

## 4.4 COMBINING TWO LABELS REVERSIBLY

When combining two labels, we start from the joint state:

$$ |\phi_{y_1}\rangle |\phi_{y_2}\rangle |y_1\rangle |y_2\rangle = (|0\rangle + \chi_M(-y_1s)|1\rangle)(|0\rangle + \chi_M(-y_2s)|1\rangle)|y_1\rangle |y_2\rangle = (|00\rangle + \chi_M(-y_1s)|10\rangle + \chi_M(-y_2s)|01\rangle + \chi_M(-(y_1+y_2)s)|11\rangle)|y_1y_2\rangle, $$

and we CNOT the first qubit into the second one, mapping $|10\rangle$ to $|11\rangle$ and $|11\rangle$ to $|10\rangle$. We obtain:

$$ (|0\rangle + \chi_M(-(y_1+y_2)s)|1\rangle)|0\rangle|y_1\rangle|y_2\rangle + \chi_M(-y_2s)(|0\rangle + \chi_M(-(y_1-y_2)s)|1\rangle)|1\rangle|y_1\rangle|y_2\rangle. $$

In order to mimic the classical recomputation of labels, we perform a controlled addition or subtraction of $y_2$ in place, on the register that contains $y_1$. We obtain the state:

$$ (|\phi_{y_1+y_2}\rangle|0\rangle|y_1+y_2\rangle + \chi_M(-(y_1-y_2)s)|\phi_{y_1-y_2}\rangle|1\rangle|y_1-y_2\rangle)|y_2\rangle. $$

Once this operation has been performed, we get a qubit $|0\rangle$ or $|1\rangle$ that used to indicate whether we obtained the sum $y_1 + y_2$ or the difference $y_1 - y_2$: here, it is just kept along for reversibility. The register that contains $y_2$ has become entangled with the other and cannot be used for further combinations.

In our DAHS circuit, we will define a “combination circuit” Comb_v (Figure 1 in Appendix). We flag all the label states with additional qubits that inform us whether the label can be used for further combination or not. The circuit Comb_v then first tests that the two labels $y_1, y_2$ have valuation v and that their flags $b_1, b_2$ are equal to 1 (Flag). If this is true, then it performs an addition or subtraction in place (Sub, Add), then NOTs the flag qubit $b_2$ (X), since $y_2$ cannot be used for combination anymore.
**Choosing which Labels to Combine.** Among the pairs of labels $y_1, y_2$ having the same valuation modulo 2, we want to select those which maximize the expected valuation of $y_1 \pm y_2$. We check whether the second to last bit of $y/2^{\text{val}_2(y)}$ is 0 or 1. If it is 0, then our hope is to add $y$ to another label that maximizes the overlap of least significant bits. If it is 1, then our hope is to subtract $y$ to another label that overlaps with $2^n - y$ on as many least significant bits as possible. Thus we can define a function $F$ on labels<fnref n="1" />:

$$F(y) = \begin{cases} (1, 0) & \text{if } y = 0 \text{ or } y \text{ cannot be combined anymore} \\ (-\text{val}_2(y), \text{rev}(2^n - y, n)) & \text{if the second to last bit of } y/(2^{\text{val}_2(y)}) \text{ is 1} \\ (-\text{val}_2(y), \text{rev}(y, n)) & \text{otherwise} \end{cases}$$

where $\text{rev}(y, n)$ reverses the bits in $y$ (for a total of $n$ bits). By sorting the labels according to $F$, we ensure that the best pairs, such that $y_1 \pm y_2$ has the best expected valuation, are put together.

## 4.5 COMBINING ALL LABELS

We start from a list of $t = 2^\ell$ label states for some integer $\ell$. For $v = 0, \dots, n-2$:

* We perform a reversible sorting network for $F$: we compute $F$ in ancillas, perform a sorting network, and then uncompute $F$. We consider that the computation of $F$ can be neglected. The sorting network is a series of comparators and swaps (controlled on the results of the comparators). The labels are moved in place. For reversibility, the outcome of each comparator must be written in a new qubit.

* we apply the combination circuit $\text{Comb}_v$ on each pair of labels at positions $(2i, 2i+1)$ for $i \le 2^\ell-1$. It writes $2\ell$ new qubits that contain carries and inform whether the combinations occurred.

In practice, the combination layer at step $v$ consumes all labels of valuation $v$ and creates labels of higher valuation. The main difference with the classical process is that, although the labels are sorted to ensure a maximal number of zeroes after combination, since we take them 2 by 2 on arbitrary positions we might create a few suboptimal pairs. This does not change the asymptotic complexity of the procedure.

Note that all labels equal to 0 mod $2^n$, and the labels that cannot be combined anymore, are moved to the bottom of the list by sorting. The labels equal to $2^{n-1}$ will be moved to the top. Thus, we know where to look for them.

**Sorting Network.** We use the *odd-even mergesort* of Batcher [2]. On input a list of $2^\ell$ n-bit strings, it uses a total of $S(2^\ell) = 2^{\ell-1} \frac{\ell(\ell-1)}{2} + 2^\ell - 1 = O(\ell^2 2^\ell)$ comparators and controlled SWAPs. In order to be made reversible, it also needs to write $O(\ell^2 2^\ell)$ new qubits.

**The Full Circuit.** The full combination circuit contains $n-1$ layers of sorting, followed by layers of combination circuits: at layer $i$ (starting from 0), we combine only the labels having valuation $i$. The complexity mainly depends on the sorting steps: there are in total $O(n) \times O(n) \times S(2^\ell) = O(n^2 \ell^2 2^\ell)$ quantum gates used, mainly for comparators and SWAPs. The circuit writes $nS(2^\ell) + (n-1)2^\ell$ ancillas. They are uncomputed afterwards.

After the combination, we look at the $r$ first label registers, for some value $r$ to choose later. We expect them to contain $r$ copies of $2^{n-1}$. As we have seen, in the shifted case, the corresponding qubits contain identical copies of $|0\rangle + |1\rangle$, or $|0\rangle - |1\rangle$ depending on the parity of $s$. Thus, we perform a Hadamard transform on them and test if the result is all-zero or all-one.

Note that if the first label registers do not contain the expected copies of $2^{n-1}$, then we *know that the circuit has failed*. The fact that failures are detectable allows to reduce easily the probability of failure with multiple copies of the circuit: we simply take the result that hasn't failed.

## 4.6 BEHAVIOR IN THE NON-SHIFTED CASE

In the non-shifted case, by our assumptions, there is no overlap between the functions $f$ and $g$. Thus, sample states are the sums of two independent parts:

$$|\psi_{f,g}\rangle = \underbrace{(\sum_x |0\rangle |f(x)\rangle |x\rangle)}_{|\psi_f\rangle} + \underbrace{(\sum_x |1\rangle |g(x)\rangle |x\rangle)}_{|\psi_g\rangle},$$

and the whole sample database $|\psi_{f,g}\rangle^{\otimes t}$ can be rewritten as a sum of the $2^t$ states of the form $|\psi_{h_1}\rangle \otimes \dots \otimes |\psi_{h_t}\rangle$ where $h_t \in \{f,g\}$. By linearity, we can focus on the output of DAHS on one of these states only.

<footnote n="1">¹Although we did not find its explicit definition in previous works, it appears in the simulation code of [8].</footnote>
The QFT applied to $|\psi_h\rangle$ yields a state $|b\rangle \sum_y (\sum_x \chi_M(xy) |h(x)\rangle) |y\rangle$ where $b$ depends only on $h$. Therefore, after performing the combination step, and after obtaining labels equal to $2^{n-1}$, the corresponding qubits are not $|0\rangle \pm |1\rangle$, but either $|0\rangle$, or $|1\rangle$, depending on the exact sequence of combinations performed.

Recall that in the shifted case, the $r$ qubits on which we apply the final Hadamard transform contain copies of $|0 \pm 1\rangle$. If the algorithm succeeds, these copies are obtained in all cases, so they are disentangled from the rest of the state. In contrast, in the non-shifted case, we obtain a single $r$-dimensional basis state depending on the sequence of combinations. Thus after applying the Hadamard transform, the total amplitude on $|0^r\rangle$ (resp. $|1^r\rangle$) is equal to $2^{r/2}$.

## 4.7 BOUNDING THE ERRORS

The circuit DAHS is not exact. In the positive (shifted) case, it maps: $|\psi'_{f,g}\rangle |b\rangle \xrightarrow{\text{DAHS}} |\psi'_{f,g}\rangle |b \oplus 1\rangle + |\delta^f_{FN,g}\rangle |b\rangle$ where $\| |\delta^f_{FN,g}\rangle \| \le \epsilon_{FN}$, and $\epsilon^2_{FN}$ is the (small) probability of false negative; and in the negative (non shifted) case, it maps: $|\psi^t_{f,g}\rangle |b\rangle \xrightarrow{\text{DAHS}} |\psi^t_{f,g}\rangle |b\rangle + |\delta^f_{FP,g}\rangle |b \oplus 1\rangle$ where $\| |\delta^f_{FP,g}\rangle \| \le \epsilon_{FP}$ and $\epsilon^2_{FP}$ is the (small) probability of false positive. We now bound both $\epsilon_{FN}$ and $\epsilon_{FP}$ separately, and independently of $f$ and $g$.

**False Negatives.** False negatives come from all the sequences of labels $Y = y_1, \dots, y_t$ on which the combination cannot produce enough labels $2^{n-1}$. As unitary operators preserve the euclidean norm, we can bound $\| |\delta_{FN}\rangle \|$ before the combination step. Let us consider the state:

$$ |\phi_{f,g}\rangle^{\otimes t} = \sum_X \sum_Y \chi_M(X \cdot Y) \left( \bigotimes_{1 \le i \le t} (|0\rangle + \chi_M(-y_i s) |1\rangle) |y_i\rangle \right) |f(X)\rangle, \quad (1) $$

where $X = x_1, \dots, x_t$, $\chi_M(X \cdot Y) = \prod \chi_M(x_i y_i)$ and $f(X) = f(x_1), \dots, f(x_t)$. All the “bad” sequences $Y$ contribute to the probability of false negatives, so we bound:

$$ \left\| \sum_X \sum_Y \chi_M(X \cdot Y) \left( \bigotimes_i (|0\rangle + \chi_M(-y_i s) |1\rangle) |y_i\rangle \right) |f(X)\rangle \right\| \le \sqrt{\frac{|\text{bad } Ys|}{|\text{all } Ys|}} . $$

Thus, if both $f$ and $g$ are injective, we have $\epsilon_{FN} = \sqrt{\frac{|\text{bad } Ys|}{|\text{all } Ys|}}$ (and this does not depend from $f$ and $g$). The classical analysis of Kuperberg's algorithm gives a constant probability of finding a good label if we start from $O(2^{\sqrt{2\log_2 3n}})$ of them. Thus, if we take copies of the combination circuit, we can obtain $r$ good labels with probability $1 - \epsilon$ if we start from $O((-\log_2 \epsilon)r2^{\sqrt{2\log_2 3n}})$ labels.

**False Positives.** We have seen above that when the functions are not shifted, we have still some probability to fall on $|0^r\rangle$ or $|1^r\rangle$ after the final Hadamard transform. This probability is also independent of $f$ and $g$. The amplitude on the state $|0^r\rangle$ or $|1^r\rangle$ is exactly $\frac{1}{\sqrt{2^r}}$, and for all $f: \| |\delta_{FP}\rangle \|^2 = \frac{2}{2^r} \Rightarrow \epsilon_{FP} = 2^{-(r-1)/2}$.

# 5 THE OFFLINE-DAHS ALGORITHM

In this section, we describe an offline-DAHS algorithm that will help us solve the SLS with classical queries, based on the reversible circuit DAHS.

The algorithm looks for a pair of shifted functions $g(\cdot) = f(\cdot + s)$ over an abelian group, when $g$ is fixed and $f$ goes through a family $(f_i)_{i \in I}$. We will consider a simple version of this problem, in which the group is $\mathbb{Z}_{2^n}$, all functions are injective and admit distinct image sets.

**Problem 5 (Finding a shifted pair, injective case).** Let $g: \mathbb{Z}_{2^n} \to X$ be a function, and $f_i: \mathbb{Z}_{2^n} \to X$ be a family of functions indexed by $I$, such that: • $g$ and all $f_i$ are injective; • there exists a single $i_0 \in I$ and a shift $s$ such that: $\forall x \in \mathbb{Z}_{2^n}, g(x) = f_{i_0}(x + s); \bullet \bigcup_{i \neq i_0} \text{Im}(f_i)$ and $\text{Im}(g)$ are disjoint. Then find $i_0$.

## 5.1 HIGH-LEVEL DESCRIPTION

First of all, we describe offline-DAHS in a generic way, following the layout of the offline-Simon algorithm by Bonnetain et al. [10]. Note that [10] already proposed to combine their algorithm with Kuperberg's, but did not analyze the resulting algorithm nor its time complexity. Originally, the offline-Simon algorithm, which itself
follows Grover-meet-Simon [30], combines a quantum search and a quantum circuit for Simon's algorithm. Roughly speaking, offline-DAHS is obtained by replacing Simon's algorithm by Kuperberg's (which is why we needed to define a quantum circuit for it).

**Description.** We use a quantum search for the right index $i_0 \in I$. Testing a given $i$ means finding whether $f_i$ is a shift of $g$. For this, we use the circuit DAHS. Recall that DAHS takes in input the sample database of $(f_i, g): |\psi_{f_i, g}\rangle^{\otimes t}$ and writes a single output bit. Thus, the naive Grover search would reconstruct the database at each iteration, then compute DAHS, then return the database to $|0\rangle$.

However, due to the asymmetric nature of the problem, the function $g$ in the database remains the same from one iteration to the next. Let us introduce the sample database of $(0, g)$:

$$ |\psi_{0,g}\rangle^{\otimes t} = \left( \sum_x |0\rangle|x\rangle|0\rangle + |1\rangle|x\rangle|g(x)\rangle \right)^{\otimes t} . $$

It contains all the data on $g$ that we need for the successive iterations of quantum search. The algorithm has then two steps:

* Precomputation step: Construct $|\psi_{0,g}\rangle^{\otimes t}$.

* Search step: Run the quantum search for $i_0$. At each search iterate, compute $f_i$ inside the database to obtain the state $|\psi_{f_i, g}\rangle^{\otimes t}$, run the circuit DAHS, then compute $f_i$ again to return to the state $|\psi_{0,g}\rangle^{\otimes t}$. Due to the approximate nature of DAHS, this is a quantum search with an approximate test (Theorem 2).

We have bounded the error of DAHS and given its complexity in Theorem 3. As long as the initial state $|\psi_{0,g}\rangle^{\otimes t}$ can be constructed exactly, this becomes an easy instance of Theorem 2, and we deduce:

**Proposition 1.** Let $\alpha = 2 \log_2 3$. Problem 5 can be solved within a time $\tilde{O}(2^{\sqrt{\alpha n}} \sqrt{I})$ using $\tilde{O}(2^{\sqrt{\alpha n}})$ qubits, with constant probability. There are $\tilde{O}(2^{\sqrt{\alpha n}})$ queries to $g$ and $\tilde{O}(2^{\sqrt{\alpha n}} \sqrt{I})$ queries to $f$ (in superposition for both).

The fact that the queries to $O_g$ are now performed only in the precomputation step is the reason for the offline denomination. Note that the polynomial factors in the $\tilde{O}$ in Proposition 1 are not negligible, and depend on $\log_2 I$ and $n$ together.

## 5.2 APPROXIMATE PROMISE

We now go into technical details specific to offline-DAHS and not discussed in the previous literature.

So far, our analysis has assumed that we could start from an exact sample database $|\psi_{0,g}\rangle^{\otimes t}$ as defined above. But it is not the case in the SLS problem. Here, $g$ will be the secretly shifted Legendre symbol $(\frac{s+1}{p})$. This function is defined on $\mathbb{Z}_p$, but it is queried on an interval of length $M$.

In particular, in order to run the algorithm as expected from Proposition 1, we would need sample states of the form:

$$ |\psi_{0,g}^{\text{exact}}\rangle = \sum_{0 \le x \le M-1} |0\rangle|x\rangle|0\rangle + \sum_{-s \le x \le M-s-1} |1\rangle|x\rangle|g(x)\rangle , $$

which would allow for a total interference between the matching values of $f(x)$ and $g(x)$, when querying the good $f$.

However, since we do not know the value of $s$, such states cannot be created. Instead, we will rely on approximate sample states:

$$ |\psi_{0,g}^{\text{approx}}\rangle = \sum_{0 \le x \le M-1} |0\rangle|x\rangle|0\rangle + \sum_{0 \le x \le M-1} |1\rangle|x\rangle|g(x)\rangle . $$

There is an error vector $|\psi_{0,g}^{\text{err}}\rangle$ such that $|\psi_{0,g}^{\text{approx}}\rangle = |\psi_{0,g}^{\text{exact}}\rangle + |\psi_{0,g}^{\text{err}}\rangle$:

$$ \| |\psi_{0,g}^{\text{err}}\rangle \| = \left\| \sum_{-s \le x \le -1} |1\rangle|x\rangle|g(x)\rangle - \sum_{M-s \le x \le M-1} |1\rangle|x\rangle|g(x)\rangle \right\| \le \sqrt{\frac{2s}{4M}} , $$

and we can bound the distance between the “exact” database of $(0, g)$ and the “approximate” one:

$$ \left\| \left( |\psi_{0,g}^{\text{approx}}\rangle \right)^{\otimes t} - \left( |\psi_{0,g}^{\text{exact}}\rangle \right)^{\otimes t} \right\|^2 \le t \| |\psi_{0,g}^{\text{err}}\rangle \| = \frac{ts}{2M} . $$

This gives a total “starting error” $\nu = \sqrt{\frac{ts}{2M}}$. As we have seen in Theorem 2, we need this error to be constant, thus $s$ needs to be subexponentially smaller than $M$ for the algorithm to work.
## 5.3 APPLICATION TO THE LEGENDRE SYMBOL

Given a sequence of $M = 2^n$ successive outputs ($\frac{s+x}{P}$) of the Legendre PRF, we define a function $g(x) = L_{s+x}$ on $\mathbb{Z}_M$. Next, we choose an integer $n'$ such that $2^{n'} < M$ and we write: $s = s_1 + 2^{n'}s_2$, where $s_1 < 2^{n'}$. For a given $s_2$, we define $f(x) = L_{x+2^{n'}s_2}$. Then there exists a single $s_2$ such that $g(x) = f(x + s_1)$.

Note that we need a subexponential gap between $2^{n'}$, where $n'$ is the number of bits of the secret handled by the DAHS subroutine, and $M = 2^n$, the amount of data given. It is due to the approximation discussed in Section 5.2. The DAHS subroutine still runs with labels of $n = \log_2 M$ bits.

By taking L-sequences of length $\ge 3 \log_2 P$, our Heuristic 1 ensures that the functions are injective, and that they have distinct image sets: two L-sequences cannot collide randomly. Thus, we have an instance of Problem 5 with an approximate promise, and we can apply Theorem 2.

We use the $M$ classical queries to build the approximate sample states $|\psi_{0,g}^{approx}\rangle$, and then, we run a Grover search over the remaining secret $s_2$. Building the sample database from the classical queries is costly ($O(Mm)$ quantum gates for each sample), but done only once in the precomputation step.

Let $\alpha = 2 \log_2 3$. In order to make the starting error $v$ smaller than $\frac{1}{4}$, we must take $t$ labels where $\sqrt{t2^{n'}/(2M)} \le \frac{1}{4} \Rightarrow t \le M/2^{n'+3}$. But since $t = \tilde{O}(2^{\sqrt{\alpha n}})$, this means the circuit DAHS can only recover $n'$ bits of $s$, where $n' + \sqrt{\alpha n} = \log_2 M = n$. Thus $n' = n - \sqrt{\alpha n}$. The remaining $(\log_2 P - n')$ bits must be searched with Grover's algorithm.

**Theorem 4.** Given a sequence of $M$ outputs of the Legendre PRF, we can solve the SLS problem using $\tilde{O}(2^{\sqrt{\alpha \log_2 M}})$ qubits, in quantum time:

$$ \tilde{O}\left(M2^{\sqrt{\alpha \log_2 M}}\right) + \tilde{O}\left(2^{\frac{3}{2}\sqrt{\alpha \log_2 M}}\sqrt{\frac{P}{M}}\right). $$

*Proof.* We use Corollary 1 and Theorem 3. We run a quantum search with an approximate test (the circuit DAHS) and an approximate starting state (the approximate sample states).

The analysis of DAHS assumes an exact ancillary state $|\psi_{0,g}\rangle^{\otimes t}$. Thus, Theorem 2 is crucial here to ensure that the approximate starting state does not disrupt the algorithm. $\square$

The minimum occurs when the two terms are equal, which constrains: $\sqrt{\alpha \log_2 M} + \log_2 M = \frac{3}{2}\sqrt{\alpha \log_2 M} + \frac{1}{2}\log_2 P - \frac{1}{2}\log_2 M \Rightarrow \log_2 M = \frac{1}{3}\sqrt{\alpha \log_2 M} + \frac{1}{3}\log_2 P$, up to the polynomial factors. We get $\sqrt{\log_2 M} = \sqrt{\frac{1}{3}\log_2 P + \frac{\alpha}{36} + \frac{\sqrt{\alpha}}{6}} = \sqrt{\frac{1}{3}\log_2 P} + O(1)$ and $\log_2 M = \frac{1}{3}\log_2 P + \frac{\sqrt{\alpha}}{3\sqrt{3}}\sqrt{\log_2 P} + O(1)$. This gives a time complexity of order: $P^{1/3}2^{\frac{4}{3}\sqrt{\alpha}\sqrt{\log_2 P}}$.

## 6 CONCLUSION

In this paper, we presented two quantum algorithms for solving the Legendre hidden shift problem (SLS) when classical queries are given, and without quantum RAM. The first one (distinguished table-based collisions) allows to reach an advantage against Grover's algorithm when more data is given. The second one is the offline Kuperberg's algorithm. It is an interesting method, notably the only one reaching a time-memory product below $O(\sqrt{P})$. However, some numerical estimations (see Appendix 11) suggest that its subexponential factor renders it impractical so far.

While all algorithms studied in this paper can be applied to the Ethereum challenges, in which a sequence of successive Legendre symbols is given, they do not concern all applications of the Legendre PRF. In the signature scheme LegRoast [5], the adversary learns only the evaluation of the PRF on a few random inputs. In that case, the best classical and quantum attacks are table-based collision searches with small tables, in time $\tilde{O}(P)$ and $\tilde{O}(\sqrt{P})$ respectively.

Although a very efficient algorithm exists when superposition queries are allowed [18], it does not seem amenable to an offline version, which requires to define reduced instances of the problem (e.g., guessing part of the secret and finding the remaining bits by searching for a shift). Nevertheless, the algebraic properties of the Legendre symbol might still find a use in this context, and we leave this as an open question.

## ACKNOWLEDGMENTS.

A.S. would like to thank Xavier Bonnetain for discussions on Kuperberg's algorithm. Both authors would like to thank Jeeun Lee, Changmin Lee and the anonymous reviewers of Mathcrypt for helpful comments. This work has been supported by the European Union's H2020 project No. 714294 (QUASYModo) and by ERC-ADG-ALSTRONGCRYPTO (project 740972).
REFERENCES

[1] Andris Ambainis. "Quantum Walk Algorithm for Element Distinctness". In: *SIAM J. Comput.* 37.1 (2007), pp. 210–239.

[2] Kenneth E. Batcher. "Sorting Networks and Their Applications". In: *AFIPS Spring Joint Computing Conference*. Vol. 32. AFIPS Conference Proceedings. Thomson Book Company, Washington D.C., 1968, pp. 307–314.

[3] Robert Beals et al. "Efficient distributed quantum computing". In: *Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences* 469.2153 (2013), p. 20120686.

[4] Charles H. Bennett et al. "Strengths and Weaknesses of Quantum Computing". In: *SIAM J. Comput.* 26.5 (1997), pp. 1510–1523.

[5] Ward Beullens and Cyprien Delpech de Saint Guilhem. "LegRoast: Efficient Post-quantum Signatures from the Legendre PRF". In: *PQCrypto*. Vol. 12100. Lecture Notes in Computer Science. Springer, 2020, pp. 130–150.

[6] Ward Beullens et al. "Cryptanalysis of the Legendre PRF and Generalizations". In: *IACR Trans. Symmetric Cryptol.* 2020.1 (2020), pp. 313–330.

[7] Xavier Bonnetain. "Improved Low-qubit Hidden Shift Algorithms". In: *CoRR abs/1901.11428* (2019). arXiv: 1901.11428. URL: http://arxiv.org/abs/1901.11428.

[8] Xavier Bonnetain and María Naya-Plasencia. "Hidden Shift Quantum Cryptanalysis and Implications". In: *ASIACRYPT (1)*. Vol. 11272. Lecture Notes in Computer Science. Springer, 2018, pp. 560–592.

[9] Xavier Bonnetain and André Schrottenloher. "Quantum Security Analysis of CSIDH". In: *EUROCRYPT (2)*. Vol. 12106. Lecture Notes in Computer Science. Springer, 2020, pp. 493–522.

[10] Xavier Bonnetain et al. "Quantum Attacks Without Superposition Queries: The Offline Simon's Algorithm". In: *ASIACRYPT (1)*. Vol. 11921. Lecture Notes in Computer Science. Springer, 2019, pp. 552–583.

[11] Gilles Brassard, Peter Høyer, and Alain Tapp. "Quantum Cryptanalysis of Hash and Claw-Free Functions". In: *LATIN*. Vol. 1380. Lecture Notes in Computer Science. Springer, 1998, pp. 163–169.

[12] Gilles Brassard et al. "Quantum amplitude amplification and estimation". In: *Contemporary Mathematics* 305 (2002), pp. 53–74.

[13] Richard P. Brent and Paul Zimmermann. "An $O(M(n) \log n)$ Algorithm for the Jacobi Symbol". In: *ANTS*. Vol. 6197. Lecture Notes in Computer Science. Springer, 2010, pp. 83–95.

[14] André Chailloux, María Naya-Plasencia, and André Schrottenloher. "An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography". In: *ASIACRYPT (2)*. Vol. 10625. Lecture Notes in Computer Science. Springer, 2017, pp. 211–240.

[15] Melissa Chase et al. "Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives". In: *CCS*. ACM, 2017, pp. 1825–1842.

[16] Andrew M. Childs, David Jao, and Vladimir Soukharev. "Constructing elliptic curve isogenies in quantum subexponential time". In: *J. Math. Cryptol.* 8.1 (2014), pp. 1–29.

[17] Steven A Cuccaro et al. "A new quantum ripple-carry addition circuit". In: *arXiv preprint quant-ph/0410184* (2004).

[18] Wim van Dam, Sean Hallgren, and Lawrence Ip. "Quantum Algorithms for Some Hidden Shift Problems". In: *SIAM J. Comput.* 36.3 (2006), pp. 763–778.

[19] Ivan Damgård. "On the Randomness of Legendre and Jacobi Sequences". In: *CRYPTO*. Vol. 403. Lecture Notes in Computer Science. Springer, 1988, pp. 163–172.

[20] Dankrad Feist. *Legendre pseudo-random function*. Accessed: 2021-01-19. 2019. URL: https://legendreprf.org.

[21] Lorenzo Grassi et al. "MPC-Friendly Symmetric Key Primitives". In: *CCS*. ACM, 2016, pp. 430–443.

[22] Lov K. Grover. "A Fast Quantum Mechanical Algorithm for Database Search". In: *STOC*. ACM, 1996, pp. 212–219.

[23] Alexander Helm and Alexander May. "The Power of Few Qubits and Collisions - Subset Sum Below Grover's Bound". In: *PQCrypto*. Vol. 12100. Lecture Notes in Computer Science. Springer, 2020, pp. 445–460.

[24] Samuel Jaques and John M. Schanck. "Quantum Cryptanalysis in the RAM Model: Claw-Finding Attacks on SIKE". In: *CRYPTO (1)*. Vol. 11692. Lecture Notes in Computer Science. Springer, 2019, pp. 32–61.
[25] Novak Kaluderovic, Thorsten Kleinjung, and Dusan Kostic. "Improved key recovery on the Legendre PRF". In: *IACR Cryptol. ePrint Arch.* 2020 (2020), p. 98.

[26] Novak Kaluderović, Thorsten Kleinjung, and Dušan Kostić. "Cryptanalysis of the generalised Legendre pseudorandom function". In: *ANTS*. Vol. 4. Open Book Series 1. Mathematical Sciences Publishers, 2020, pp. 267–282.

[27] Dmitry Khovratovich. "Key recovery attacks on the Legendre PRFs within the birthday bound". In: *IACR Cryptol. ePrint Arch.* 2019 (2019), p. 862.

[28] Greg Kuperberg. "A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem". In: *SIAM J. Comput.* 35.1 (2005), pp. 170–188.

[29] Greg Kuperberg. "Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem". In: *TQC*. Vol. 22. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 20–34.

[30] Gregor Leander and Alexander May. "Grover Meets Simon - Quantumly Attacking the FX-construction". In: *ASIACRYPT (2)*. Vol. 10625. Lecture Notes in Computer Science. Springer, 2017, pp. 161–178.

[31] Michael A Nielsen and Isaac Chuang. *Quantum computation and quantum information*. 2002.

[32] Chris Peikert. "He Gives C-Sieves on the CSIDH". In: *EUROCRYPT (2)*. Vol. 12106. Lecture Notes in Computer Science. Springer, 2020, pp. 463–492.

[33] Oded Regev. "A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space". In: *arXiv preprint quant-ph/0406151* (2004).

[34] Martin Roetteler et al. "Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms". In: *ASIACRYPT (2)*. Vol. 10625. Lecture Notes in Computer Science. Springer, 2017, pp. 241–270.

[35] István András Seres, Máté Horváth, and Péter Burcsi. "The Legendre Pseudorandom Function as a Multi-variate Quadratic Cryptosystem: Security and Applications". In: *IACR Cryptol. ePrint Arch.* 2021 (2021), p. 182. URL: https://eprint.iacr.org/2021/182.

[36] Peter W. Shor. "Algorithms for Quantum Computation: Discrete Logarithms and Factoring". In: *FOCS*. IEEE Computer Society, 1994, pp. 124–134.

# APPENDIX

## 7 DETAILED COMPLEXITIES

We give in Table 2 a detailed version of Table 1.

<table><caption>Table 2: Comparison of classical and quantum algorithms to solve the SLS problem, including previous works and our new results. We note $m = 3 \lfloor \log_2 P \rfloor$, $\alpha = 2 \log_2 3$, $L \le (\log_2 P)^2$ the time to compute a Legendre symbol, and we omit constant factors.</caption><thead><tr><th>Method</th><th>Queries</th><th>Time<br>Classical algorithms</th><th>Memory</th><th>Source</th></tr></thead><tbody><tr><td>Pollard's rho</td><td>√Pm</td><td>L√Pm</td><td>m</td><td>[27]</td></tr><tr><td>Table</td><td>M</td><td>M<sup>2</sup> + Pm<sup>2</sup>/M<sup>2</sup></td><td>M<sup>2</sup>/m</td><td>[6]</td></tr><tr><td>Table</td><td>M</td><td>M<sup>2</sup> + Pm log<sub>2</sub> m/M<sup>2</sup></td><td>M<sup>2</sup></td><td>[25]</td></tr><tr><td colspan="5" style="text-align: center;">Quantum algorithms</td></tr><tr><td>Sup. queries</td><td>2</td><td>poly(m)</td><td>poly(m)</td><td>[18]</td></tr><tr><td>Table (QRACM)</td><td>M</td><td>M<sup>2</sup> + m<sup>2</sup>√P/M<sup>2</sup>L</td><td>M<sup>2</sup> QRACM</td><td>[25]</td></tr><tr><td>Grover search</td><td>m</td><td>log<sub>2</sub> m√PL</td><td>m qubits</td><td>Sec. 3.2</td></tr><tr><td>Distinguished points</td><td>M</td><td>M<sup>2</sup> + <sup>√P</sup>&frasl;<sub>M<sup>1/3</sub></sub>m<sup>11/6</sup> log<sub>2</sub> log<sub>2</sub> M</td><td>M classical<br>+ m qubits</td><td>Sec. 3.3</td></tr><tr><td>Offline-DAHS</td><td>M</td><td>~O(<sup>M2√α log<sub>2</sub> M</sup>&frasl;<sub>2<sup>3/2</sup>√α log<sub>2</sub> M</sub>√P/M)</td><td>~O(2√α log<sub>2</sub> M)<br>qubits</td><td>Sec. 5.3</td></tr></tbody></table>
# 8 PROOF OF THEOREM 2

In this section, we prove Theorem 2.

Let $\mathcal{A}, a, t = \lfloor \frac{\pi}{4\theta_a} \rfloor$ be defined as in Theorem 1. Let $f$ be a boolean function that tests if an output of $\mathcal{A}$ is “good”, and let $O'_f$ be an approximate oracle for $f$ with error $\epsilon$, using an ancillary state $|\psi\rangle$, as per Definition 1. Let $|\psi'\rangle$ be a quantum state such that $\| |\psi\rangle - |\psi'\rangle \| \le \nu$. We run the following algorithm:

$$ ((1 \otimes \mathcal{A})(1 \otimes O_0)(1 \otimes \mathcal{A}^\dagger)O'_f)^t |\psi'\rangle , $$

that is, $t$ iterations of “approximate” quantum search using $O'_f$, where $1$ is the identity operator applied to the ancillary state $|\psi\rangle$. Then measuring the output yields a good result with probability greater than $(1 - t\epsilon - \nu)^2 \max(1 - a, a)$.

*Proof.* The proof uses a “hybrid argument” as in [4] or [1, Lemma 5]. We will consider the “perfect” run of the algorithm, that starts with the initial $|\psi\rangle$ and applies the perfect test $O_f$, and compare it with the “imperfect” one, that starts with $|\psi'\rangle$ and applies the imperfect test $O'_f$.

Let $|\psi'_k\rangle$ be the state after $k$ iterations of the imperfect search, and $|\psi_k\rangle$ after the perfect search. Our goal is to bound $\| |\psi'_k\rangle - |\psi_k\rangle \|$. Let $U = (1 \otimes \mathcal{A})O_0(1 \otimes \mathcal{A}^\dagger)$, then the quantum search iterates are respectively $UO'_f$ and $UO_f$. Before the first iteration, we have:

$$ \| |\psi'_0\rangle - |\psi_0\rangle \| = \nu , $$

by definition of $|\psi'\rangle$. Next, for each $k \ge 0$:

$$ \begin{aligned} \| |\psi'_{k+1}\rangle - |\psi_{k+1}\rangle \| &= \| UO'_f |\psi'_k\rangle - UO_f |\psi_k\rangle \| \\ &= \| O'_f |\psi'_k\rangle - O_f |\psi_k\rangle \| \\ &= \| O'_f (|\psi'_k\rangle - |\psi_k\rangle) + O'_f |\psi_k\rangle - O_f |\psi_k\rangle \| , \end{aligned} $$

and using the triangle inequality:

$$ \begin{aligned} \| |\psi'_{k+1}\rangle - |\psi_{k+1}\rangle \| &\le \| O'_f (|\psi'_k\rangle - |\psi_k\rangle) \| + \| O'_f |\psi_k\rangle - O_f |\psi_k\rangle \| \\ &\le \| |\psi'_k\rangle - |\psi_k\rangle \| + \| O'_f |\psi_k\rangle - O_f |\psi_k\rangle \| . \end{aligned} $$

In order to bound the second term, we use the fact that $O'_f$ induces a uniform error $\epsilon$. More specifically, if $|\psi_k\rangle = \sum_x \alpha_x |x\rangle$, we have: $O'_f |\psi_k\rangle - O_f |\psi_k\rangle = \sum_x \alpha_x |\delta_x\rangle$ where $|\delta_x\rangle$ is the error induced by $O'_f$ on the input state $x$. Then we have

$$ \| O'_f |\psi_k\rangle - O_f |\psi_k\rangle \| = \sum_x \alpha_x^2 \| |\delta_x\rangle \| \le \epsilon^2 \implies \| O'_f |\psi_k\rangle - O_f |\psi_k\rangle \| \le \epsilon , $$

by definition of $\epsilon$. Thus, each iteration adds an error $\epsilon$.

After $t$ iterations, we have $|\psi'_t\rangle = |\psi_t\rangle + |\psi_{err}\rangle$ where $\| |\psi_{err}\rangle \| \le \nu + t\epsilon$. By the Cauchy-Schwarz inequality, we have:

$$ | \langle \psi_t | \psi_{err} \rangle | \le \| |\psi_t\rangle \| \| |\psi_{err}\rangle \| \le \nu + t\epsilon . $$

Measuring $|\psi'_t\rangle$, we project on $|\psi_t\rangle$ with a probability greater than:

$$ (1 - | \langle \psi_t | \psi_{err} \rangle |)^2 \ge (1 - \nu - t\epsilon)^2 $$

and then, by Theorem 1, we have a probability greater than $\max(1 - a, a)$ to measure a “good” element. $\square$

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

It can seem surprising to require a uniform error $\epsilon$. Indeed, in a classical exhaustive search with a single solution, we can afford a constant probability of false negative (not recognizing the solution), and still obtain a constant probability of success, as we expect to look at the solution only once.

Our classical intuition then dictates that the same should be true of a quantum search: we could afford a much higher probability of false negatives than of false positives. We found that this was not the case, due to the stateful nature of the search. Indeed, taking different $\epsilon_{FP}$ and $\epsilon_{FN}$ changes the error term $\epsilon$ added at iteration $k$ to a term:

$$ \sqrt{\sin^2((2k+1)\theta_a)\epsilon_{FN}^2 + \cos^2((2k+1)\theta_a)\epsilon_{FP}^2} . $$
In order to have a constant probability of success in the end, we must measure a state in which a constant proportion of the amplitude is on the solution. That is, $(2k + 1)\theta_a$ must be sufficiently close to $\frac{\pi}{2}$ to have $\sin^2((2k + 1)\theta_a)$ constant. This means that in the last iterations, the error term is close to $\epsilon_{FN}$. (Although in the first iterations, it was close to $\epsilon_{FP}$). Over all the iterations, the solution and the bad elements both capture roughly (up to a constant) the same amount of amplitude, and so both terms $\epsilon_{FN}$ and $\epsilon_{FP}$ will have roughly the same effect.

## 9 QUANTUM CIRCUIT FOR THE LEGENDRE SYMBOL

The prime $P$ is fixed. We detail a quantum circuit that given $x$, computes $(\frac{x}{p})$. We will actually adopt the more general view of computing Jacobi symbols. We recall Algorithm 1 that uses the multiplicativity, the law of quadratic reciprocity and its supplement:

$$ \forall p, q, a, b, \left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}}\frac{q-1}{2}, \quad \left(\frac{q}{p}\right) = \left(\frac{q \mod p}{p}\right), \\ \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}, \quad \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right). $$

The situation is similar to the extended GCD algorithm studied in [34]: in the classical algorithm, the number of steps depends on the input. The corresponding quantum circuit must run for a fixed amount of iterates, thus we take the greatest possible number of iterates and control them depending on whether the algorithm has finished or not. Note that there exists asymptotically more efficient classical algorithms, such as [13], but it is not clear whether they can have an impact on the design of quantum circuits (especially for rather small prime numbers).

<caption>**Algorithm 1** Computation of the Legendre symbol, through the Jacobi symbol.</caption>

1: **function LEGENDRE(q,p)**
2:     **Computes:** $(\frac{q}{p})$ where $p$ is prime and $1 \le q < p$
3:     **while** $q \ne 0$ **do**
4:         **if** $q \bmod 2 = 0$ **then**
5:             $q = q/2$
6:             **if** $p \bmod 8 = 3$ or $p \bmod 8 = 5$ **then**
7:                 $t = -t$
8:             **end if**
9:         **else if** $q < p$ **then**
10:             $q, p = p, q$
11:         **if** $p \bmod 4 = 3$ and $q \bmod 4 = 3$ **then**
12:             $t = -t$
13:         **end if**
14:     $q = q - p$
15:     **else**
16:         $q = q - p$
17:     **end if**
18: **end while**
19: **return** $t$
20: **end function**

Let us analyze briefly Algorithm 1. We can easily prove that if $q$ does not start even, then in the next loop it is. Thus, the current pair $(p, q)$ is reduced by one bit at each two loops, and after at most $2(\lceil \log_2 p \rceil + \lceil \log_2 q \rceil) \le 4\lceil \log_2 p \rceil$ loop iterations, the computation of $(\frac{q}{p})$ terminates.

In order to compute the Legendre symbol modulo $P$, we thus use a circuit of $4\lceil \log_2 P \rceil$ iterations. We keep a “flag” qubit indicating whether the computation has finished, and a “result” qubit containing the value $t$ of Algorithm 1. At each iteration, we look at the “flag”, the values of $p$ and $q$ and find which case applies:

* Case 1: we must divide $q$ by $2$ $(q > 0$ and $q \bmod 2 = 0$)

* Case 2: we must swap $q$ and $p$ $(q > 0, q \le p$ and $q \bmod 2 = 1$)

* Case 3: we must subtract $p$ to $q$ $(q > 0, q > p$ and $q \bmod 2 = 1$)

* Case 4: we must do nothing $(q = 0)$
Two new qubits indicate the case; their computation requires a comparator ($O(\log_2 P)$ gates). Then we apply all the operations controlled on these qubits. The division by 2 is implemented as a rotation of the register (we know that the least significant bit is 0, so we do not need to write a carry). The swap is an easy operation. The subtraction does not need any carry either. Then $t$ is flipped depending on the case (this is also reversible, and costs a constant number of computations).

Since each iteration requires $O(\log_2 P)$ gates and writes $O(1)$ new qubits, the complete circuit requires $O((\log_2 P)^2)$ gates and $O(\log_2 P)$ ancilla qubits.

# 10 COMBINATION CIRCUIT

<figure><img src="image_3.png" /><figcaption>Figure 1: Combination circuit Combine<sub>v</sub> from Section 4.4. Note the “control on 0” which applies the addition only if the qubit $|\phi_{y_2}\rangle$ is 0.</figcaption></figure>

# 11 SIMULATIONS AND COST ESTIMATES

In this section, we give more precise, non-asymptotic (but heuristic) complexity estimates for offline-DAHS applied to the SLS problem. Our goal is to determine for which values of $P$ the algorithm becomes more efficient than the table-based collision search. We expect that for small $P$, its advantage in the exponential term will be defeated by the subexponential factor.

Note that for exhaustive search and table-based collisions, the asymptotic formulas of Table 2 are very close to the non-asymptotic costs (only by a small constant factor).

## 11.1 NUMBER OF LABELS IN DAHS

As we have seen, the number of labels dictates the probability of false positives and false negatives in the DAHS circuit. This is a property of the combination step, independent from the functions $f, g$ that we are actually studying.

We will first fix $r = 200$, meaning that we want the combination step to produce 200 labels equal to $2^{n-1}$. This reduces the probability of false positives to $2^{-(r-1)} = 2^{-199}$.

Next, we will estimate how many initial label states we need to reduce the probability of false negatives below $2^{-199}$ as well. We upper bound this probability by the probability that a given sequence of random labels $y_1, \dots, y_t$, drawn at random, is “bad”, i.e., does not allow to produce 200 labels equal to $2^{n-1}$. Concretely, we choose a value of $t$ and we sample sequences of $t$ initial labels uniformly at random. We then perform the combination step as in the DAHS circuit, i.e., with layers of combination circuits and of sorting.

During this step, we actually simulate the output of DAHS when starting from the sequence of labels $y_1, \dots, y_t$. This is doable because the entire circuit (except the initial QFTs, which produce the labels in the first place) contains only classical reversible operations such as CNOTs and controlled additions. We can then check how many labels equal to $2^{n-1}$ are produced.

Our goal is still to estimate the probability:

$$ \Pr_{y_1, \dots, y_t \leftarrow \Sigma_{2n}} \left( y_1, \dots, y_t \text{ produce } r \text{ labels equal to } 2^{n-1} \right). $$

However, we cannot estimate it experimentally, since we need it to be extremely small.
**Heuristic.** The heuristic assumption that we make is that the number of labels equal to $2^{n-1}$, that the sieve produces, follows a normal distribution. Our experiments allow then to estimate the mean and standard deviation. We estimate the probability to obtain less than 200 labels by integrating the density function on $]-\infty; 200]$.

Since the circuit is better layout with $t = 2^l$, we increase the number of labels in powers of 2, and there is always a clear threshold. At some point, the average number of good labels exceeds 700 and the probability of failure becomes negligibly smaller than $2^{-200}$ (by our estimate).

We display some simulation results in Table 3 for different values of $n$ and $l$. In general, if there are enough labels for a given $n$, then the same circuit should work for $n' < n$. This is not always what we observe (see the column (60, 19)), because having a smaller $n'$ can increase the number of zero-labels produced, to the detriment of good labels. In that case we must take a smaller number of labels, but we can layout the circuit as if there were $2^l$ of them exactly (with dummy labels).

<table><caption>Table 3: Estimates of the number of labels required (in $\log_2$). The numbers are rounded to the nearest integer. We highlight the values of $n, l$ for which we estimate a probability of failure (having less than 200 labels) smaller than $2^{-200}$.</caption><thead><tr><th></th><th>36</th><th><b>36</b></th><th>40</th><th><b>40</b></th><th><b>44</b></th><th><b>48</b></th><th><b>52</b></th><th><b>56</b></th><th>60</th><th><b>64</b></th><th><b>68</b></th><th><b>72</b></th><th><b>76</b></th></tr></thead><tbody><tr><th><i>n</i></th><td>36</td><td><b>36</b></td><td>40</td><td><b>40</b></td><td><b>44</b></td><td><b>48</b></td><td><b>52</b></td><td><b>56</b></td><td>60</td><td><b>64</b></td><td><b>68</b></td><td><b>72</b></td><td><b>76</b></td></tr><tr><th><i>l</i></th><td>16</td><td><b>17</b></td><td>17</td><td><b>18</b></td><td><b>18</b></td><td><b>18</b></td><td><b>18</b></td><td><b>19</b></td><td>19</td><td><b>19</b></td><td><b>20</b></td><td><b>20</b></td><td><b>21</b></td></tr><tr><th>Mean</th><td>361</td><td>1517</td><td>408</td><td>1259</td><td>728</td><td>1374</td><td>933</td><td>1289</td><td>565</td><td>811</td><td>1601</td><td>1199</td><td>2307</td></tr><tr><th>Std.</th><td>17</td><td>36</td><td>19</td><td>33</td><td>28</td><td>37</td><td>26</td><td>38</td><td>21</td><td>26</td><td>38</td><td>29</td><td>45</td></tr></tbody></table>

## 11.2 COMPARISON

Let us take an example of SLS parameters: $\log_2 P = 240$ and $\log_2 M = 80$. The best classical table-based collision reaches a complexity roughly $2^{120}$, as does quantum exhaustive search. The quantum table-based collision will strictly improve on that, but we can leave it aside for now.

We will run the DAHS circuit with labels in $\mathbb{Z}_M$, thus 80 bits. By our estimates in Appendix 11.1, in order to have negligible errors in the DAHS circuit, we can use $t = 2^{21}$ labels for $\log_2 M = 80$. Thus we need $2^{21}$ sample states.

The DAHS circuit will only recover $n'$ bits of the secret, where $n' < 80$ depends on the bound on the error $\nu$, that we need to make smaller than $\frac{1}{4}$. This constrains:

$$ \sqrt{\frac{t2^{n'}}{2M}} \le \frac{1}{4} \Rightarrow n' \le \log_2 M - \log_2 t - 3 = 56. $$

Building a sample state requires roughly $M$ register-wise operations; this makes $2^{101}$ in total for the first step of offline-DAHS. Next, since there remains $\log_2 P - n' = 184$ bits of secret, the quantum search requires $\frac{\pi}{4} 2^{92}$ iterations. But each of them costs at least $80 \times 21^2 \times 2^{21} = 2^{36}$ n-qubit operations, due to the 80 layers of sorting in DAHS. This brings the total complexity above exhaustive search.

Thus, the subexponential factor of Kuperberg's sieve, but also the polynomial factors induced by our reversible circuit, defeat the time speedup for a prime $P$ of 300 bits. With the circuit that we presented, the improvements for larger values of $P$ (400 or 500 bits) will likely remain outperformed by the table-based collision search.

In order to overturn this situation, the circuit DAHS must be made more efficient. There are different possible ways:

* Increasing the resistance of the search to the errors in DAHS. Having to produce a large number of labels is problematic for small parameters.

* Using a more involved variant of Kuperberg's algorithm, for example Kuperberg's collimation sieve [29]. It is currently unclear to us if its asymptotic improvement could also translate into a non-asymptotic improvement of the circuit layout.

* Reducing the overall cost of the sorting and combination layers. It is clear that most of the work in the final layers is useless, since most of the labels have already been consumed. It might be possible to reduce this cost using a refined estimation on the number of remaining labels at each step.