prob]Problem conj]Conjecture

# Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations

Joseph<EMAIL_ADDRESS>
University of Maryland  Alexander Poremba222<EMAIL_ADDRESS>
MIT

###### Abstract

Sponge hashing is a novel class of cryptographic hash algorithms which
underlies the current international hash function standard SHA-3. In a
nutshell, a sponge function takes as input a bit-stream of any length and
processes it via a simple iterative procedure: it repeatedly feeds each block
of the input into a so-called _block function_ , and then produces a short
digest which consists of a subset of the final output bits. While much is
known about the post-quantum security of the sponge construction in the case
when the block function is modeled as a random function or permutation, the
case of _invertible_ permutations, which more accurately models the
construction underlying SHA-3, has so far remained a fundamental open problem.

In this work, we make new progress towards overcoming this barrier and show
several results. First, we prove the “double-sided zero-search” conjecture
proposed by Unruh (eprint’ 2021) and show that finding zero-pairs in a random
$2n$-bit permutation requires at least $\Omega(2^{n/2})$ many queries—and this
is tight due to Grover’s algorithm. At the core of our proof lies a novel
“symmetrization argument” which uses insights from the theory of Young
subgroups. Second, we consider more general variants of the double-sided
search problem and show similar query lower bounds for them. As an
application, we prove the quantum one-wayness of the single-round sponge with
invertible permutations in the quantum random oracle model.

##  1 Introduction

Hash functions are one of the most fundamental objects in cryptography. They
are used in a multitude of applications, such as integrity checks for data
packages (e.g., software updates), password storage on cloud servers, or as
important components in digital signature schemes—whether it is to design
hash-based signatures or simply to construct signatures schemes for variable
input lengths [KL14].

In recent years, the National Institute of Standards and Technology (NIST)
announced a new international hash function standard known as SHA-3. Unlike
its predecessor SHA-2, which was rooted in the Merkle-Damgård construction
[Mer88, Mer90, Dam87], the new hash function standard uses Keccak [Ber+11a]—a
family of cryptographic functions based on the novel idea of _sponge hashing_
[Ber+11]. This particular approach allows for both variable input length and
variable output length, which makes it particularly attractive towards the
design of cryptographic hash functions. The internal state of a sponge
function gets updated through successive applications of a so-called _block
function_ $\varphi:\\{0,1\\}^{r+c}\rightarrow\\{0,1\\}^{r+c}$, where we call
the parameters $r\in\mathbb{N}$ the _rate_ and $c\in\mathbb{N}$ the _capacity_
of the sponge. The evaluation of the sponge function
$\mathsf{Sp}^{\varphi}:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{*}$ takes place in
two phases:

  1. 1.

(Absorption phase:) During each round, a new block consisting of $r$ many bits
of the input gets “fed” into the block function $\varphi$. Following the
sponge metaphor, we say that the sponge function “absorbs” the input. More
formally, suppose that the input consists of $r$-bit blocks
$m_{1},m_{2},\dots,m_{\ell}$. During the first round, we compute
$\varphi(m_{1}||0^{c})=y_{1}||z_{1}$, for some $y_{1}\in\\{0,1\\}^{r}$ and
$z_{1}\in\\{0,1\\}^{c}$. Then, to absorb the next block $m_{2}$, we compute
$\varphi(y_{1}\oplus m_{2}||z_{1})=y_{2}||z_{2}$, and so on.

  2. 2.

(Squeezing phase:) During each round, a new $r$-bit block is produced by
essentially running the absorption phase in reverse. Each $r$-bit digest
becomes a block of the final output of the function $\mathsf{Sp}^{\varphi}$.
Following the sponge metaphor, we say that the sponge function gets “squeezed”
to produce fresh random bits. More formally, suppose the last round of the
absorption phase results in a pair $y_{\ell}||z_{\ell}$. We then let the
digest $y_{\ell}$ serve as the first block of the output. To produce the
second block, we compute $\varphi(y_{\ell}||z_{\ell})=y_{\ell+1}||z_{\ell+1}$,
and output $y_{\ell+1}$, and so on.

Several works have since analyzed the security properties behind the sponge
construction [Ber+08, FGK22, Aks+23]. In particular, in [Ber+08] it was shown
that the sponge hash function enjoys a strong form of security called
_indifferentiability_ in the case when the underlying block function $\varphi$
is modeled as an invertible random permutation. Indifferentiability already
implies many desired properties of cryptographic hash functions, such as
collision-resistance or pseudorandomness.

While much is known about the security of the sponge in a classical world, our
understanding changes significantly once we take the threat of large-scale
quantum computing into account. The good news is that most hash functions are
believed to only be mildly effected, whereas the majority of public-key
cryptography faces serious threats due to Shor’s algorithm (and its variants)
[Sho97, Reg24]. The reason hash functions are believed to be less susceptible
to quantum attacks is due to their inherent lack of structure, which means
that generic quantum attacks tend to achieve at most a square-root speed-up
relative to their classical counterparts. To this day, however, our
understanding of the post-quantum security of the sponge remains somewhat
incomplete. In fact, the post-quantum security of the sponge construction is
only well-understood in the special case when the block function is modeled as
a _non-invertible_ random permutation [Cza+17, Cza+19]. The case of invertible
random permutations, which more accurately models the construction underlying
SHA-3, has so far remained a major open problem.

#### Single-round sponge hashing.

In the special case when there is only a single round of absorption and
squeezing, the sponge function
$\mathsf{Sp}^{\varphi}:\\{0,1\\}^{r}\rightarrow\\{0,1\\}^{r}$ has a simple
form which is illustrated in Figure 1; namely, on input $x\in\\{0,1\\}^{r}$,
the output is given by $y=\mathsf{Sp}^{\varphi}(x)$, where $y$ corresponds to
the first $r$ bits of $\varphi(x||0^{c})$. In other words,
$\mathsf{Sp}^{\varphi}$ is defined as the restriction of $\varphi$ onto the
first $r$ bits of its output.

$\varphi$$x$ $0^{c}$$y$$z$ Figure 1: The single-round sponge.

Despite its simplicity, the single-round sponge already features many of the
technical difficulties that one encounters when analyzing the security of the
(many-round) sponge—especially once we model $\varphi$ as an invertible random
permutation. In the post-quantum setting, this requires us to analyze quantum
algorithms $\mathcal{A}^{\varphi,\varphi^{-1}}$ which are allowed to make
superposition queries to both the “forward oracle” $O_{\varphi}$, as well as
the “backward oracle” $O_{\varphi^{-1}}$. For example, one may ask:

  * •

(One-wayness:) How many queries does a quantum algorithm
$\mathcal{A}^{\varphi,\varphi^{-1}}$ need to invert $\mathsf{Sp}^{\varphi}$ on
a randomly chosen input? In other words, given $y$ which corresponds to the
first $r$ bits of $\varphi(x||0^{c})$, for a random $x\sim\\{0,1\\}^{r}$, how
many queries does $\mathcal{A}$ need to find $x^{\prime}$ such that the first
$r$ many bits of $\varphi(x^{\prime}||0^{c})$ equal $y$?

  * •

(Collision-resistance:) How many queries does a quantum algorithm
$\mathcal{A}^{\varphi,\varphi^{-1}}$ need to find a collision for
$\mathsf{Sp}^{\varphi}$? Here, $\mathcal{A}$ needs to find a colliding pair
$x,x^{\prime}$ such that the first $r$ many bits of $\varphi(x||0^{c})$ and
$\varphi(x^{\prime}||0^{c})$ match.

To the best of our knowledge, there are currently no known query lower bounds
for either of the two above problems—despite the fact that they concern the
seemingly simple variant of single-round sponge hashing. The lack of lower
bounds is mainly due to the fact that all existing proof techniques for the
non-invertible case [Cza+17, Cza+19] seem to break down once the inverse
oracle $O_{\varphi^{-1}}$ enters the picture.

Consider, for example, the basic property of _zero-preimage-resistance_ ; that
is, the hardness of finding a pre-image of the all-zero string. Czajkowski et
al. [Cza+17] showed that if a (non-invertible) $\varphi$ is both collision-
resistant (when restricted to the left and right half of its output) and zero-
preimage-resistant (when restricted to the right half of its output), then the
(many-round) sponge construction is collision-resistant. Unfortunately, this
approach fails immediately if an adversary can submit inverse queries to the
block function $\varphi$. Clearly, the restriction of $\varphi$ to the right
half of its output is no longer the zero-preimage-resistant—an adversary can
simply query $O_{\varphi^{-1}}$ on inputs of the form $y||0^{c}$, for any
input $y\in\\{0,1\\}^{r}$, in order to find a zero-preimage.

Another difficulty in generalizing existing proof techniques lies in the fact
it is currently not known how to construct _compressed permutation oracles_
[Unr21, Unr23]. Zhandry [Zha18] previously introduced compressed oracles as a
tool to prove query lower bounds for problems involving random oracles;
specifically, as a means to “record” quantum queries to a random oracle.
Compressed oracles have proven to be extremely useful in analyzing the post-
quantum security of hash functions in the quantum random oracle model,
particularly in the case of random sponges [Cza+19, Unr21, Unr23]. However,
unlike random functions where all the function outputs are sampled
independently, this is not true for random permutations. This makes it
difficult to construct compressed oracles for permutations, especially for
modelling algorithms that can query the permutation in both directions [Unr21,
Unr23].

#### Double-sided zero-search.

In light of the difficulty in proving the post-quantum security of the sponge
with invertible permutations, Unruh proposed the following simple conjecture
which seems beyond the scope of current techniques.

[Double-sided zero-search, [Unr21, Unr23]] Any quantum algorithm
$\mathcal{A}^{\varphi,\varphi^{-1}}$ which has quantum query-access to a
random permutation $\varphi:\\{0,1\\}^{2n}\rightarrow\\{0,1\\}^{2n}$ and its
inverse $\varphi^{-1}$ must make $\Omega(2^{n/2})$ many queries to find a zero
pair $(x,y)$ such that $\varphi(x||0^{n})=y||0^{n}$ with constant success
probability. Note that the above lower bound is already tight—a simple Grover
search allows one to find a zero-pair using $\Theta(2^{n/2})$ many queries, if
one exists. Notice that there is a slight subtlety that arises in the
statement of Section 1 since not every permutation has a zero pair; for
example, the permutation $\varphi(x||y):=(x||y\oplus 1^{n})$ has no zero pairs
since $\varphi(x||0^{n})=x||1^{n}$, for any $x\in\\{0,1\\}^{n}$, whereas the
identity permutation $\varphi:=\mathrm{id}$ has precisely $2^{n}$ many zero
pairs. However, for a random permutation there is at least one zero pair with
constant probability—a property we show in Lemma 3.5.

While it is not immediately clear how the double-sided zero-search problem
from Section 1 relates to the security of the sponge construction, it was
suggested by Unruh [Unr21] that it may already provide some evidence for its
collision-resistance. The problem has so far also resisted attempts333This was
pointed out by Unruh [Unr21]. at solving it using standard techniques from
quantum query complexity; for example, the adversary method [Amb02] or the
polynomial method [Bea+01]. Therefore, a resolution to Section 1 may already
offer interesting new insights into proving the post-quantum security of the
sponge construction with invertible permutations.

###  1.1 Our contributions

We now give an overview of our contributions in this work.

#### Resolving Unruh’s conjecture.

We prove the double-sided zero-search conjecture (Section 1) due to Unruh
[Unr21, Unr23] and show that finding zero-pairs in a random $2n$-bit
permutation with constant probability requires at least $\Theta(2^{n/2})$ many
queries. Specifically, we show the following in Theorem 4.1.

######  Theorem (Informal).

Any quantum algorithm for Double-Sided Zero-Search that makes $T$ queries to
an invertible permutation succeeds with probability at most $O(T^{2}/2^{n})$.

In other words, any algorithm must make at least $T=\Omega(\sqrt{\epsilon
2^{n}})$ many queries in order to succeed with probability $\epsilon$. As we
observe in Corollary 4.2, this immediately yields a tight lower bound of
$\Theta(2^{n/2})$ for constant success probability due to Grover, or more
generally a tight bound of $\Theta(\sqrt{\epsilon 2^{n}})$ for any success
probability $\epsilon>0$.

Our proof takes place in two steps:

  * •

Reduction from worst-case unstructured search: Our first insight lies in the
fact that we can reduce Unstructured Search with $K$ out of $2^{n}$ marked
elements to a specific instance of Double-Sided Zero-Search without any
overhead; namely, one in which the $2n$-bit permutation $\varphi$ has exactly
$K$ many zero pairs. Suppose we have quantum oracle access to a function

$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}\quad\quad\text{ with
}\quad\quad|f^{-1}(1)|=K.$

We now construct the following permutation
$\varphi:\\{0,1\\}^{2n}\rightarrow\\{0,1\\}^{2n}$ such that, for any inputs
$x,y\in\\{0,1\\}^{n}$, it holds that:

$\varphi(x||y)=\begin{cases}x||y&\text{ if }f(x)=1\\\ x||(y\oplus
1^{n})&\text{ if }f(x)=0\,.\end{cases}$

Notice that $\varphi$ while is not random, it has exactly $K$ many zero pairs
on inputs of the form $x||0^{n}$ whenever $x$ satisfies $f(x)=1$. Furthermore,
$\varphi=\varphi^{-1}$ and so backwards queries are not helpful—thus worst
case hardness follows.

  * •

Worst-case to average-case reduction via symmetrization: Our next insight lies
in the fact that we can re-randomize any worst-case permutation $\varphi$ with
$K$ zero pairs into an average-case permutation $\varphi^{\mathrm{sym}}$ with
$K$ zero pairs:

    1. 1.

Select two $2n$-bit permutations $\sigma,\omega$ such that both preserve the
property of ending in $0^{n}$, but are otherwise independently random.444More
formally, we require that $\sigma$ and $\omega$ map strings of the form
$(x||0^{n})$ to $(y||0^{n})$, for $x,y\in\\{0,1\\}^{n}$.

    2. 2.

Symmetrize $\varphi$ by letting
$\varphi^{\mathrm{sym}}=\omega\circ\varphi\circ\sigma$.

A zero pair of $\varphi$ can be reconstructed from a zero pair of
$\varphi^{\mathrm{sym}}$, but the location of the zero pairs and the
permutation behaviour everywhere else is now randomized. We have inverse
access to $\varphi$, and so we also have inverse access to
$\varphi^{\mathrm{sym}}$. Hardness of the average case is now implied by
hardness of the worst case.

Our symmetrization argument (formally shown in Lemma 3.12) uses insights from
the theory of _Young subroups_. We give an extensive treatment of the subject
in Section 3.

In Section 4.2, we give an alternative proof of Unruh’s double-sided zero-
search conjecture (Section 1) which combines our technique of symmetrization
with a more conventional approach rooted in one-way to hiding [AHU18]. The
advantage of our alternative proof is that it is more direct—it avoids the
two-step template of the previous proof. At a high level, it uses the
superposition oracle framework and introduces a _function register_ which is
outside of the view of the query algorithm, and contains a uniform
superposition over permutations. Note that the superposition oracle formalism
makes it especially easy to analyze quantum query-algorithms which query
permutations both in the forward, as well as in the backward direction.

Once we introduce the function register, we can then “symmetrize it in
superposition”. This framework allows us to directly show that no quantum
algorithm can distinguish whether it is querying a random invertible
permutation with exactly $K$ many zero pairs, or a random invertible
permutation with no zero pairs—unless it makes a large number of queries. We
remark, however, that contrary to the work of Zhandry [Zha18], we do not need
to “compress” the superposition oracles and use inefficient representations
instead.

#### Subset pairs and double-sided search.

Motivated by the sponge construction, we generalize these techniques to handle
search problems which are non-uniform in the sense of (1) different
constraints on preimages vs images and (2) non-uniform distribution on
permutations. In particular, we define a variant of two-sided search in which
one is given query access to an $n$-bit permutation
$\varphi:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}$ and its inverse, for an
integer $n=r+c$, and asked to produce inputs that end in $c$ many zeros and
whose outputs begin in $r$ many zeros. We further consider a class of non-
uniform distributions on permutations that weights permutations according to
their number of solutions. Notably, under this new distribution a solution is
always guaranteed to exist, avoiding a subtlety in the original uniform
problem. We show that these modifications do not make the problem
significantly easier in Theorem 4.7.

######  Theorem (Informal).

Any quantum algorithm for Non-uniform Double-Sided Search that makes at most
$T$ queries to an invertible (non-uniform) random permutation and succeeds
with probability $\epsilon>0$ satisfies $\epsilon=O(T^{2}/2^{\min(r,c)})$.

The argument mirrors that of the uniform case, though with a slightly more
complicated worst-case instance.

#### Quantum one-wayness of the single-round sponge.

As an application of our techniques, we give a reduction from our Non-uniform
Double-Sided Search problem to the one-wayness (formally defined in Definition
5.1) of the single-round sponge. As a corollary of our bound for Non-uniform
Double-Sided Search, in Theorem 5.2 we establish the first post-quantum
security result for sponge hashing in the case when the block function is
modeled as an invertible permutation.

######  Theorem (Informal).

Any $T$-query quantum algorithm that breaks the quantum one-wayness of the
single-round sponge, where the block function is instantiated with an
invertible random permutation, has a success probability of at most
$\epsilon=O(T^{2}/2^{\min(r,c)})$.

By modeling the block function as an invertible random permutation, our
theorem shows the post-quantum security of the single-round sponge in the
quantum random oracle model [Bon+11]. To prove our main theorem, we first
switch to an alternative but equivalent characterization of one-wayness of the
sponge (Lemma 5.3), where the image is chosen uniformly at random before the
actual block function is sampled (in this case, $\varphi$). Note that this
approach, however, results in a non-uniform distribution over $\varphi$. To
complete the proof, we then give a reduction from the Non-Uniform Double-Sided
Search problem (formally defined in Definition 5.1).

#### Combinatorics of subset-pairs.

Along the way, we work out the combinatorics of the expected number of input-
output pairs of any given kind (i.e., for a general _subset-pair_), as well as
strong tail bounds in the case where the expected number is small. We show
that the number of such pairs decays exponentially in this case for both the
uniform distribution in Theorem 3.15 and a certain non-uniform one in Theorem
3.20.

######  Theorem (Informal).

Whenever the average number of subset pairs of a random permutation is a
constant, the probability that there are more than $K$ subset pairs is at most
$\exp(-\Omega(K))$.

In the uniform case, the number of subset pairs of permutations follows a so-
called _hypergeometric distribution_ —a well studied distribution
corresponding to sampling without replacement. We relate our non-uniform
distribution, in which permutations are favored proportional to their number
of subset pairs, to the uniform distribution, and show how to derive strong
tail bounds in this case as well.

###  1.2 Open questions

This work does not address post-quantum security of the many-round sponge,
which is a natural and important next direction. In particular, we do not
address whether the many-round sponge when instantiated with an invertible
random permutation is one-way. However, we believe that our techniques could
potentially open up new directions towards proving the post-quantum security
of the many-round sponge, especially when combined with insights from the non-
invertible case [Cza+17].

Another natural question is whether one can show stronger security properties
of the sponge with invertible permutations, even in the single-round case. For
example, whether the single-round sponge is _collision-resistant_ (or more
generally, _collapsing_) when the block function is instantiated with an
invertible random permutation. This is not addressed by our work. However, in
this case, it is conceivable that there exist direct reductions from
collision-resistance (or collapsing) to natural query problems involving
invertible permutations, similar to our reduction for one-wayness. In such a
case, our techniques would be well suited to analyzing this type of problem.

###  1.3 Related work

Czajkowski, Bruinderink, Hülsing, Schaffner and Unruh [Cza+17] showed that the
many-round sponge is _collapsing_ —a strengthening of collision-resistance—in
the case when the block function is modeled as a random function or a random
(non-invertible) permutation. In the same model, Czajkowski, Majenz, Schaffner
and Zur [Cza+19] proved the quantum indifferentiability of the (many-round)
sponge. However, in contrast with the former work, the latter relies on
Zhandry’s compressed oracle technique [Zha18]. Inspired by Zhandry’s
compressed oracle method, Rosmanis [Ros22] recently also gave tight bounds for
the permutation inversion problem. We remark that the results in the
aforementioned works do not apply in the case where the adversary has access
to an invertible random permutation.

Unruh proposed the notion of _compressed permutation oracles_ [Unr21, Unr23]
which are aimed at dealing with invertible permutations. However, the
soundness of the construction is still unresolved and currently relies on a
conjecture. Unruh also put forward the double-sided zero-search conjecture
[Unr21, Unr23] as a simple and non-trivial query problem in the context of
invertible random permutations which may potentially have implications for
collision-resistance.

Alagic, Bai, Poremba and Shi [Ala+23] showed space-time trade-offs for two-
sided permutation inversion—the task of inverting a random but invertible
permutation on a random input. While the inverter does in fact receive access
to an inverse oracle, it is crucial that such an oracle is _punctured_ at the
challenge input; otherwise, the inversion task would become trivial. Although
this work does not seem to have any immediate implications for the single-
round sponge, it does suggest that permutation inversion remains hard in the
presence of inverse oracles.

#### Acknowledgments.

We thank Gorjan Alagic, Chen Bai, Luke Schaeffer and Kaiyan Shi for many
useful discussions. JC acknowledges funding from the Department of Defense. AP
is supported by the National Science Foundation (NSF) under Grant No.
CCF-1729369.

###  1.4 Organization

In Section 2, we review the fundamentals of quantum computing and quantum
search lower bounds. In Section 3, we review basic group theory—with a
particular focus on the theory of Young subgroups—and state the key group-
theoretic lemma for our symmetrization argument. We also introduce the concept
of a _zero pair_ as well as a _subset pair_ , which constitute the main
objects in the query problems we study. Moreover, we analyze many general
combinatorial properties of these objects.

In Section 4, we prove tight lower bounds for the Double-Sided Zero-Search
problem using a worst-case to average-case reduction, as well as a direct
proof based on the superposition oracle framework. We also define and show
lower bounds for a non-uniform variant of this problem which we call Non-
uniform Double-Sided Search—a problem which we naturally encounter later in
Section 5. In the final section, we give a reduction from Non-uniform Double-
Sided Search to the one-way game of the single-round sponge with invertible
permutations.

##  2 Preliminaries

Let us first introduce some basic notation and relevant background.

#### Notation.

For $N\in\mathbb{N}$, we use $[N]=\\{1,2,\dots,N\\}$ to denote the set of
integers up to $N$. The symmetric group on $[N]$ is denoted by $S_{N}$. In
slight abuse of notation, we oftentimes identify elements $x\in[N]$ with bit
strings $x\in\\{0,1\\}^{n}$ via their binary representation whenever $N=2^{n}$
and $n\in\mathbb{N}$. Similarly, we identify permutations $\pi\in S_{N}$ with
permutations $\pi:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}$ over bit strings of
length $n$.

We write $\operatorname{negl}(\cdot)$ to denote any _negligible_ function,
which is a function $f$ such that, for every constant $c\in\mathbb{N}$, there
exists an integer $N$ such that for all $n>N$, $f(n)<n^{-c}$.

#### Probability theory.

The notation $x\sim X$ describes that an element $x$ is drawn uniformly at
random from the set $X$. Similarly, if $\mathcal{D}$ is a distribution, we let
$x\sim\mathcal{D}$ denote sampling $x$ according to $\mathcal{D}$. We denote
the expectation value of a random variable $X$ by
$\mathbb{E}[X]=\sum_{x}x\Pr[X=x]$. We make use of the following distribution.

######  Definition 2.1 (Hypergeometric distribution).

A hypergeometric distribution describes the number of marked elements found by
drawing $T$ many objects from a total of $N$, of which $K$ are marked. More
formally, for $X\sim\text{Hypergeometric}(N,K,T)$, we have

$\displaystyle\Pr[X=k]=\frac{\binom{K}{k}\binom{N-K}{T-k}}{\binom{N}{T}}.$

We use the following tail bound for the hypergeometric distribution.

######  Lemma 2.2 (Hoeffding’s inequality, [Hoe63, Chv79]).

Let $X\sim\text{Hypergeometric}(N,K,T)$ and define $p=K/N$. Then, for any
$t\in\mathbb{R}$ with $0\leq t<1-p$, it holds that

$\Pr\left[X\geq(p+t)\cdot T\right]\leq\exp\big{(}-T\cdot
D_{\mathrm{KL}}(p+t||p)\big{)}\,,$

where $D_{\mathrm{KL}}(q||p)$ denotes the Kullback-Leibler divergence with

$D_{\mathrm{KL}}(q||p)=q\cdot\ln\left(\frac{q}{p}\right)+(1-q)\cdot\ln\left(\frac{1-q}{1-p}\right).$

#### Quantum computing.

A finite-dimensional complex Hilbert space is denoted by $\mathcal{H}$, and we
use subscripts to distinguish between different systems (or registers); for
example, we let $\mathcal{H}_{A}$ be the Hilbert space corresponding to a
system $A$. The tensor product of two Hilbert spaces $\mathcal{H}_{A}$ and
$\mathcal{H}_{B}$ is another Hilbert space which we denote by
$\mathcal{H}_{AB}=\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. We let
$\mathcal{L}(\mathcal{H})$ denote the set of linear operators over
$\mathcal{H}$. A quantum system over the $2$-dimensional Hilbert space
$\mathcal{H}=\mathbb{C}^{2}$ is called a _qubit_. For $n\in\mathbb{N}$, we
refer to quantum registers over the Hilbert space
$\mathcal{H}=\big{(}\mathbb{C}^{2}\big{)}^{\otimes n}$ as $n$-qubit states. We
use the word _quantum state_ to refer to both pure states (unit vectors
$\ket{\psi}\in\mathcal{H}$) and density matrices
$\rho\in\mathcal{D}(\mathcal{H})$, where we use the notation
$\mathcal{D}(\mathcal{H})$ to refer to the space of positive semidefinite
linear operators of unit trace acting on $\mathcal{H}$.

The _trace distance_ between two density matrices
$\rho,\sigma\in\mathcal{D}(\mathcal{H)}$ is given by

$\mathsf{TD}(\rho,\sigma)=\frac{1}{2}\mathrm{Tr}\left[\sqrt{(\rho-\sigma)^{\dagger}(\rho-\sigma)}\right].$

Note that the trace distance between two pure states
$\ket{\psi},\ket{\phi}\in\big{(}\mathbb{C}^{2}\big{)}^{\otimes n}$ satisfies

$\mathsf{TD}(|\psi\rangle\langle\psi|,|\phi\rangle\langle\phi|)\leq\big{\|}\ket{\psi}-\ket{\phi}\big{\|}\,,$

where $\|\cdot\|$ denotes the Euclidean distance over the vector space
$\big{(}\mathbb{C}^{2}\big{)}^{\otimes n}$.

When the dimensions are clear from context, we use $\mathbb{1}$ to denote the
identity matrix. A _unitary_ $U:\cL(\mathcal{H}_{A})\to\cL(\mathcal{H}_{A})$
is a linear operator such that $U^{\dagger}U=UU^{\dagger}=\mathbb{1}_{A}$. A
_projector_ $\Pi$ is a Hermitian operator such that $\Pi^{2}=\Pi$. Oftentimes,
we use the shorthand notation $\bar{\Pi}=\mathbb{1}-\Pi$.

A quantum algorithm is a uniform family of quantum circuits
$\\{\mathcal{A}_{\lambda}\\}_{\lambda\in\mathbb{N}}$, where each circuit
$\mathcal{A}_{\lambda}$ is described by a sequence of unitary gates and
measurements; moreover, for each $\lambda\in\mathbb{N}$, there exists a
deterministic Turing machine that, on input $1^{\lambda}$, outputs a circuit
description of $\mathcal{A}_{\lambda}$. We say that a quantum algorithm
$\mathcal{A}$ has oracle access to a classical function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{m}$, denoted by $\mathcal{A}^{f}$, if
$\mathcal{A}$ is allowed to use a unitary gate $O^{f}$ at unit cost in time.
The unitary $O^{f}$ acts as follows on the computational basis states of a
Hilbert space $\mathcal{H}_{X}\otimes\mathcal{H}_{Y}$ of $n+m$ qubits:

$O^{f}:\quad\ket{x}_{X}\otimes\ket{y}_{Y}\longrightarrow\ket{x}_{X}\otimes\ket{y\oplus
f(x)}_{Y},$

where the operation $\oplus$ denotes bit-wise addition modulo $2$. Oracles
with quantum query-access have been studied extensively, for example in the
context of quantum complexity theory [Ben+97], as well as in cryptography
[Bon+11, AHU18, Ala+20].

###  2.1 Lower bounds for unstructured search

The quantum query complexity of worst-case Unstructured Search is one of the
most fundamental results in quantum computing [Gro96, Ben+97, Boy+98]. In this
problem, a quantum algorithm is given query access to a function
$f:[N]\rightarrow\\{0,1\\}$ and is tasked with finding an $x\in[N]$ such that
$f(x)=1$. We will consider this problem subject to the promise that there are
exactly $K$ preimages of $1$, i.e., $|f^{-1}(1)|=K$. Note also that only ever
consider the worst-case complexity of this problem, meaning the success
probability is only over the internal randomness of the algorithm.

The exact query complexity of this problem is well-understood [Gro96, Zal99,
DH09]. We use the following lower bound, which is a direct corollary of the
work of Dohotaru and Høyer.

######  Theorem 2.3 ([DH09], Theorem 8).

Any algorithm which solves Unstructured Search with $K$ out of $N$ marked
elements with worst-case success probability $\epsilon>0$ requires at least

$T\geq\frac{\sqrt{N/K}}{2\sqrt{2}}\left(1+\sqrt{\epsilon}-\sqrt{1-\epsilon}-\frac{2}{\sqrt{N/K}}\right)$

many queries.

We can rearrange the expression in Theorem 2.3 to obtain a bound on the worst-
case success probability of a $T$-query quantum algorithm.

######  Corollary 2.4.

Any algorithm which solves Unstructured Search with $K$ marked elements out of
$N$ with worst-case success probability $\epsilon>0$, satisfies the inequality

$\epsilon\leq\frac{8(T+1)^{2}K}{N}.$

###### Proof.

We have

$\displaystyle T\geq$
$\displaystyle\frac{\sqrt{N/K}}{2\sqrt{2}}\left(1+\sqrt{\epsilon}-\sqrt{1-\epsilon}-\frac{2}{\sqrt{N/K}}\right)$
(Theorem 2.3) $\displaystyle\geq$
$\displaystyle\frac{\sqrt{N/K}}{2\sqrt{2}}\left(\sqrt{\epsilon}-\frac{2}{\sqrt{N/K}}\right).$

This implies that $T+1\geq\sqrt{N\epsilon/K}/\sqrt{8}$, which yields the
desired inequality. ∎

This bound is no longer exact, but will suffice for our purposes.

##  3 Subset Pairs and the Symmetric Group

In this section, we recall some basic facts from the theory of Young
subgroups. Due to the nature of the query problems in Section 4, we oftentimes
encounter subgroups of the symmetric group $S_{N}$ consisting of permutations
that fix certain subsets of $[N]$; for example, zero pairs in the case of
Double-Sided Zero-Search in Section 4.1. This forces us to analyze certain
subgroups of $S_{N}$—called Young subgroups—which are direct products of
subgroups on fewer elements that form a partition of $[N]$.

We use the machinery of Young subgroups to prove a key lemma which shows our
symmetrization procedure is sound, and to offer an algebraic characterization
of the input/output pairs of a permutation satisfying certain constraints.

###  3.1 Group Theory

We first define relevant notions in group theory, and recall known results
about the symmetric group $S_{N}$ on $N$ elements. For a more complete
overview of the subject, we refer the reader to the work of James [Jam84].

Let $S_{N}$ denote the symmetric group consisting of permutations which act on
the set $[N]:=\\{1,...,N\\}$. For a subset $A\subset[N]$, let $S_{A}$ denote
the maximal subgroup of $S_{N}$ which fixes every element in the complement of
$A$, i.e. $[N]\setminus A$. Now let $A_{1},...,A_{l}$ be a partition of $[N]$
such that the disjoint union satisfies $\bigsqcup_{i\in[\ell]}A_{i}=[N]$.

######  Definition 3.1 (Young subgroup).

A subgroup $H$ of the symmetric group $S_{N}$ is a Young subgroup if it can be
expressed as $H=S_{A_{1}}\times...\times S_{A_{l}}$, where $\times$ denotes
the internal direct product and the collection of subsets
$\\{A_{i}\\}_{i\in[\ell]}$ forms a partition of $[N]$.

The concept of a double coset, which we review below, will also be relevant.

######  Definition 3.2 (Double cosets).

Let $H,K$ be subgroups of a group $G$. The double cosets of $G$ under $(H,K)$,
which we denote by $H\diagdown G\diagup K$, are the set of sets of elements
which are invariant under left multiplication by $H$ and right multiplication
by $K$. Formally,

$H\diagdown G\diagup K=\big{\\{}\\{hxk\,:\,h\in H,k\in K\\}\,:\,x\in
G\big{\\}}.$

It is well-known that $G$ is the disjoint union of its double cosets for any
subgroups $H,K\leq G$. We focus on the double cosets of the symmetric group
$S_{N}$, specifically those generated by Young subgroups. These subgroups
admit the following characterization, adapted from Jones [Jon96] and James
[Jam84].

######  Theorem 3.3 ([Jon96], Theorem 2.2).

Let $H,K$ be Young subgroups of $S_{N}$, with corresponding partitions
$A_{1},...,A_{l}$ (for $H$) and $B_{1},...,B_{m}$ (for $K$). Let $\pi\in
S_{N}$ and $C=H\pi K$ be the corresponding double coset. Any other permutation
$\pi^{\prime}\in S_{N}$ is in $C$ if and only if for all $i\leq l,j\leq m$ we
have $|A_{i}\cap\pi^{\prime}B_{j}|=|A_{i}\cap\pi B_{j}|$.

Intuitively, the above characterization says that the double cosets defined by
Young subgroups $(H,K)$ correspond to sets of permutations which look the same
if one only considers how they distribute the elements of each $B_{j}$ among
the different $A_{i}$’s. Two permutations $\pi,\pi^{\prime}$ are in the same
double coset if and only if for every $A_{i},B_{j}$ both $\pi$ and
$\pi^{\prime}$ send the same number of elements from $B_{j}$ to $A_{i}$. This
characterization will prove useful when showing the random self-reducibility
of two-sided search problems. The following lemma and proof is a key component
of this reduction, and is based heavily on the approach of Wildon [Wil],
Theorem 4.4.

######  Lemma 3.4.

For any subgroups $H,K$ of a (finite) group $G$ with $x,g\in G$ both in the
same $(H,K)$ double coset, there are exactly $|x^{-1}Hx\cap K|$ ways of
choosing $h\in H$ and $k\in K$ such that $g=hxk$.

###### Proof.

Fix some $x\in G$, and consider any $g\in G$ in the same double coset as $x$.
Then, there exist elements $h\in H$, $k\in K$ such that

$\displaystyle g=$ $\displaystyle hxk$ $\displaystyle=$ $\displaystyle
x(x^{-1}hx)k.$

Any alternative $k^{\prime}\in K$ can be written as $k^{\prime}=u_{k}k$ for
$u_{k}\in K$, and an alternative $h^{\prime}\in H$ can be written as
$x^{-1}h^{\prime}x=(x^{-1}hx)u_{h}$ for $u_{h}\in x^{-1}Hx$. These new
elements satisfy

$\displaystyle g^{\prime}=$ $\displaystyle h^{\prime}xk^{\prime}$
$\displaystyle=$ $\displaystyle x(x^{-1}hx)u_{h}u_{k}k$

It is apparent that $g^{\prime}=g$ holds if and only if $u_{h}=u_{k}^{-1}$.
This implies that

$u_{k},u_{h}\in K\cap x^{-1}Hx.$

Thus, there are $|x^{-1}Hx\cap K|$ alternative ways to choose a satisfying
$h\in H$ and $k\in K$.

∎

###  3.2 Subset Pairs

In this section, we introduce the notion of a subset pair, which will be the
main object of study. Specifically, we are interested in the complexity of
finding input/output pairs of a permutation which lie within certain pairs of
subsets.

#### Zero pairs.

Before giving the general definition of a subset pair, we first define a zero
pair as a specific and relevant example of a subset pair.

######  Example 3.1 (Zero pair).

Let $Z\subset[2^{2n}]$ be the subset consisting of all $z\in[2^{2n}]$ with
binary decomposition $(z_{1},z_{2},\dots,z_{2n})\in\\{0,1\\}^{2n}$ such that

$\displaystyle z_{n+1}=z_{n+2}=\ldots=z_{2n}=0.$

Then, $Z$ is a subset of size $2^{n}$ and, when identifying $S_{2^{2n}}$ with
permutations over $2n$-bit strings, $(x||0^{n})$ and $(y||0^{n})$ form a
$Z$-pair for a permutation $\pi:\\{0,1\\}^{2n}\rightarrow\\{0,1\\}^{2n}$, if
$\pi(x||0^{n})=y||0^{n}$. For brevity, we sometimes call $(x,y)$ a zero pair
of the permutation $\pi$. We show the following concerning zero pairs in
random permutations.

######  Lemma 3.5.

A random permutation $\pi\sim S_{2^{2n}}$ contains at least one zero pair with
probability

$\underset{\pi\sim S_{2^{2n}}}{\Pr}[|Z_{\pi}|\geq 1]=1-1/e+o(1).$

Here, $|Z_{\pi}|$ denotes the random variable for the number of zero pairs of
the permutation $\pi$.

###### Proof.

Let $N=2^{2n}$ and let $Z\subset[N]$ be the subset from Example 3.1, where
$|Z|=\sqrt{N}$. It suffices the estimate the probability that a random
permutation $\pi\sim S_{N}$ has no zero pairs. The total number of
permutations over $[N]$ which have no zero pairs is

$\frac{(N-\sqrt{N})!}{(N-2\sqrt{N})!}\cdot(N-\sqrt{N})!\,\,.$

This is because we need to match all $\sqrt{N}$ elements in the subset $Z$
exclusively with elements outside of $Z$. Therefore, we get

$\displaystyle\underset{\pi\sim S_{N}}{\Pr}[|Z_{\pi}|\geq 1]$
$\displaystyle=1-\underset{\pi\sim S_{N}}{\Pr}[|Z_{\pi}|=0]$
$\displaystyle=1-\frac{(N-\sqrt{N})!\cdot(N-\sqrt{N})!}{N!\cdot(N-2\sqrt{N})!}$
$\displaystyle=1-\binom{N-\sqrt{N}}{\sqrt{N}}/\binom{N}{\sqrt{N}}.$

Therefore, the claim follows from the fact that
$\binom{N-\sqrt{N}}{\sqrt{N}}/\binom{N}{\sqrt{N}}$ is a monotonically
increasing sequence which approaches the limit $1/e$ as $N\rightarrow\infty$.
∎

We will use the notation $G_{Z}$ to denote the subgroup $G_{Z}\leq S_{2^{2n}}$
of permutations which preserve membership in $Z$.

######  Definition 3.6 (Subgroup $G_{Z}$).

A permutation $\pi$ is a member of the subgroup $G_{Z}\leq S_{2^{2n}}$ if and
only if $\pi$ fixes the subset $Z$ such that $\pi(Z)=Z$. In other words, for
every $x\in\\{0,1\\}^{n}$, there exists $y\in\\{0,1\\}^{n}$ such that
$\pi(x||0^{n})=y||0^{n}$.

Note that the subgroup $G_{Z}$ decomposes as $G_{Z}\simeq S_{Z}\times
S_{[N]\setminus Z}$. The algebraic structure of the double cosets induced by
$G_{Z}\times G_{Z}$ will be central in proving the hardness of Double-Sided
Zero-Search in Section 4.1.

#### General statements.

We now turn to defining a subset pair in full generality, and prove a key
“symmetrization lemma” using the theory of Young subgroups.

######  Definition 3.7 (Subset pair).

Let $N\in\mathbb{N}$, let $X_{1},X_{2}\subseteq[N]$ be subsets and
$X=(X_{1},X_{2})$. We say that a pair $(i,j)$ is an $X$-pair for a permutation
$\pi\in S_{N}$ if $i\in X_{1},j\in X_{2}$ and $\pi(i)=j$. We denote the set of
all $X$-pairs of a permutation $\pi\in S_{N}$ by

$X_{\pi}=\\{(i,j)\,|\,i\in X_{1},j\in X_{2}\,\text{ and }\,\pi(i)=j\\}.$

######  Remark 3.8.

Whenever $X=(X_{1},X_{2})$ is a pair of identical subsets with
$X_{1}=X_{2}=Z$, for some $Z\subseteq[N]$, we sometimes refer to the pairs
$(i,j)$ in Definition 3.7 as $Z$-pairs instead. This is the case for the zero
pair subsets from Example 3.1.

For an $X=(X_{1},X_{2})$, define the subgroups $G_{1}\leq S_{N}$ and
$G_{2}\leq S_{N}$ with

$\displaystyle G_{1}:=$ $\displaystyle\\{\pi\in S_{N}\,:\,\pi(X_{1})=X_{1}\\}$
$\displaystyle G_{2}:=$ $\displaystyle\\{\pi\in
S_{N}\,:\,\pi(X_{2})=X_{2}\\}.$

In other words, $G_{i}$ consists of all permutations in $S_{N}$ that fix
$X_{i}$. Moreover, it follows from Definition 3.2 that $G_{1}$ and $G_{2}$ are
Young subgroups of $S_{N}$.

######  Fact 3.9.

The Young subgroups $G_{1}\leq S_{N}$ and $G_{2}\leq S_{N}$ decompose as

$G_{i}\simeq S_{X_{i}}\times S_{[N]\setminus X_{i}},\quad\quad\text{ for
}i\in\\{1,2\\}.$

We introduce the following notation for the double cosets of $S_{N}$ under
$(G_{1},G_{2})$.

######  Definition 3.10.

For $\kappa\in\mathbb{N}\cup\\{0\\}$, and $X=(X_{1},X_{2})$ with
$X_{1},X_{2}\subset[N]$, define the subset

$\displaystyle S_{N}^{\kappa,X}:=\\{\pi\in S_{N}\,:\,\text{$\pi$ has exactly
$\kappa$-many $X$-pairs}\\}.$

We oftentimes omit the superscript $X$ when it is clear from context. Note
that $S_{N}=\bigsqcup_{\kappa=0}^{|X_{1}|}S_{N}^{\kappa}$, i.e., $S_{N}$ is
the disjoint union over all the $S_{N}^{\kappa}$. Note, however, that whenever
we have $\kappa>|X_{1}|$ or $\kappa>|X_{2}|$, it must be that
$S_{N}^{\kappa}=\emptyset$. The following corollary is immediate from the
characterization in Theorem 3.3, since $G_{1}$ and $G_{2}$ are both Young
subgroups.

######  Corollary 3.11.

The sets $\\{S_{N}^{\kappa}\\}$ are the double cosets of $S_{N}$ under
$(G_{1},G_{2})$; formally,

$\displaystyle G_{1}\diagdown S_{N}\diagup
G_{2}=\\{S_{N}^{\kappa}\,|\,\kappa\in\\{0,1,\dots,|X_{1}|\\}\\}.$

We are now ready to prove the main tool for analyzing random double-sided
search problems, such as Double-Sided Zero-Search in Section 4.1.

######  Lemma 3.12 (Symmetrization lemma).

Consider any fixed permutation $\pi\in S_{N}^{\kappa}$, for some
$\kappa\in\mathbb{N}\cup\\{0\\}$, and suppose that $\omega\sim
G_{1},\sigma\sim G_{2}$ are sampled independently and uniformly at random.
Then, $\omega\circ\pi\circ\sigma$ is a uniformly random element of
$S_{N}^{\kappa}$.

###### Proof.

From Lemma 3.4, it follows that for any fixed $\pi\in S_{N}^{\kappa}$ and some
$\varphi\in S_{N}^{\kappa}$ the number of $\omega,\sigma$ pairs with
$\omega\in G_{1},\sigma\in G_{2}$ such that
$\varphi=\omega\circ\pi\circ\sigma$ is $|\pi G_{1}\pi^{-1}\cap G_{2}|$, which
notably is independent of $\varphi$. In particular, we have

$\displaystyle\Pr_{\omega\sim G_{1},\sigma\sim
G_{2}}[\omega\circ\pi\circ\sigma=\varphi]=\frac{|\pi G_{1}\pi^{-1}\cap
G_{2}|}{\sum_{\varphi^{\prime}\in S_{N}^{k}}|\pi G_{1}\pi^{-1}\cap
G_{2}|}=\frac{1}{|S_{N}^{\kappa}|}.$

The probability is the same for all elements $\varphi\in S_{N}^{\kappa}$, and
so the element $\omega\circ\pi\circ\sigma$ is uniformly random among elements
of $S_{N}^{\kappa}$. ∎

###  3.3 Combinatorics of Subset Pairs

In this section, we work out the combinatorics behind the expected number of
subset pairs (on average over the choice of permutation), as well derive
strong tail bounds in the case where the expected number is small. We show
that the number of subset pairs decays exponentially for the uniform
distribution (see Theorem 3.15), as well as for a particular choice of non-
uniform distribution (see Theorem 3.20).

#### Uniform case.

We begin by considering the case of uniformly random $\pi\sim S_{N}$ and
derive the expected number of $X$-pairs as well as tail bounds. We show the
following:

######  Theorem 3.13.

Let $N\in\mathbb{N}$ and let $X_{1},X_{2}\subseteq[N]$ be subsets with
$X=(X_{1},X_{2})$. Then, on average over the uniform choice of $\pi\sim
S_{N}$, the expected number of $X$-pairs equals

$\underset{\pi\sim S_{N}}{\mathbb{E}}[|X_{\pi}|]=\frac{|X_{1}||X_{2}|}{N}.$

###### Proof.

For a uniform random $\pi\sim S_{N}$, we let $I_{x}$ denote the indicator
variable which equals $1$, if $\pi(x)\in X_{1}$, and $0$ otherwise. Thus, we
have

$\displaystyle\mathbb{E}[I_{x}]=$ $\displaystyle\frac{|X_{2}|}{N},$
$\displaystyle|X_{\pi}|=$ $\displaystyle\sum_{x\in X_{1}}I_{x}\,.$

From the above, it then follows that

$\displaystyle\underset{\pi\sim S_{N}}{\mathbb{E}}[|X_{\pi}|]=$
$\displaystyle\sum_{x\in X_{1}}\mathbb{E}[I_{x}]$ (Linearity of Expectation)
$\displaystyle=$ $\displaystyle\frac{|X_{1}||X_{2}|}{N}.$

∎

A simple corollary of this bound is an alternative characterization of the
total number of subset pairs over all permutations.

######  Corollary 3.14.

Let $N\in\mathbb{N}$ and fix arbitrary subsets $X_{1},X_{2}\subseteq[N]$ with
$X=(X_{1},X_{2})$. Then, there exist precisely

$\sum_{\pi\in S_{N}}|X_{\pi}|=\frac{|X_{1}||X_{2}|}{N}\cdot N!$

many $X$-pairs over all permutations $\pi\in S_{N}$.

###### Proof.

This is easily verified as follows:

$\displaystyle\sum_{\pi\in S_{N}}|X_{\pi}|=$ $\displaystyle\underset{\pi\sim
S_{N}}{\mathbb{E}}[|X_{\pi}|]\cdot|S_{N}|$ $\displaystyle=$
$\displaystyle\frac{|X_{1}||X_{2}|}{N}\cdot N!\,.$ (Theorem 3.13)

∎

We now state and prove tail bounds, which will be sufficiently tight for the
case where the expected number of subset pairs is small.

######  Theorem 3.15.

Let $N\in\mathbb{N}$ and $X_{1},X_{2}\subseteq[N]$ be subsets with
$X=(X_{1},X_{2})$. Then, for any real number $u\geq 6\,\mathbb{E}_{\sigma\sim
S_{N}}[|X_{\sigma}|]$, it holds that

$\displaystyle\underset{\pi\sim
S_{N}}{\Pr}\Big{[}|X_{\pi}|\geq\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|]+u\Big{]}\leq\exp\left(-\frac{3}{4}u\right).$

###### Proof.

The number of permutations having $\kappa$ many $X$-pairs for
$0\leq\kappa\leq|X_{1}|,|X_{2}|$ is hypergeometrically distributed (see
Definition 2.1). In other words,

$\displaystyle\Pr_{\pi\sim S_{N}}[|X_{\pi}|=\kappa]=$
$\displaystyle\frac{\binom{|X_{2}|}{\kappa}\binom{N-|X_{2}|}{|X_{1}|-\kappa}}{\binom{N}{|X_{1}|}}.$

This is because each image of $X_{1}$ can be assigned without replacement by a
random permutation to one of $N$ images. Next, we want to count how many
images there are in $X_{2}$, which we interpret as a “success”. Let us
consider the hypergeometric distribution $\text{Hypergeometric}(N,K,T)$ with
the following parameters:

$\displaystyle N:=$ $\displaystyle N$ (Total Objects) $\displaystyle K:=$
$\displaystyle|X_{2}|$ (Success Objects) $\displaystyle T:=$
$\displaystyle|X_{1}|$ (Trials)

Let $p=|X_{2}|/N$ denote the probability that the first draw is a success.
Applying Hoeffding’s inequality (see Lemma 2.2), we get

$\displaystyle\Pr_{\pi\sim S_{N}}\Big{[}|X_{\pi}|\geq(p+t)|X_{1}|\Big{]}\leq$
$\displaystyle\exp\left(-|X_{1}|D_{\mathrm{KL}}(p+t||p)\right)$
$\displaystyle\leq$ $\displaystyle\exp\left(-\frac{3}{4}|X_{1}|t\right)$
$\displaystyle\text{(From
\lx@cref{creftypecap~refnum}{lem:KLDivergenceBound})}.$

By substituting $u=|X_{1}|t$ and applying Theorem 3.13, we obtain

$\displaystyle\underset{\pi\sim
S_{N}}{\Pr}\Big{[}|X_{\pi}|\geq\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|]+u\Big{]}\leq\exp\left(-\frac{3}{4}u\right)$
$\displaystyle\text{(When $u\geq 6\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|]$)}.$

∎

We use the following technical lemma.

######  Lemma 3.16.

Let $p,t\in(0,1)$ such that $t\geq 6p$ and $p+t<1$. Then, we can lower bound
the Kullback-Leibler divergence as follows:

$\displaystyle D_{\mathrm{KL}}(p+t||p)>3t/4.$

###### Proof.

Recall that the Kullback-Leibler divergence $D_{\mathrm{KL}}(p+t||p)$ is
defined as

$\displaystyle D_{\mathrm{KL}}(p+t||p)=$
$\displaystyle\underbrace{(p+t)\ln\left(\frac{p+t}{p}\right)}_{=D_{1}}+\underbrace{(1-p-t)\ln\left(\frac{1-p-t}{1-p}\right)}_{=D_{2}}.$

We now bound $D_{1}$ and $D_{2}$ separately. Beginning with the first term, we
get

$\displaystyle
D_{1}>t\ln\left(\frac{p+t}{p}\right)>t\ln\left(\frac{t}{p}\right)\geq
t\ln(6)\,,$

where we used that $t\geq 6p$. We now continue with the second term. First, we
consider the following first-order derivatives with respect to $t$:

$\displaystyle\frac{\partial}{\partial t}\left(D_{2}\right)=$
$\displaystyle-\ln\left(\frac{p+t-1}{p-1}\right)-1$
$\displaystyle\frac{\partial}{\partial t}\left(D_{2}\right)\big{|}_{t=0}=$
$\displaystyle-1\,.$

Calculating the second-order derivatives, we also find that

$\displaystyle\frac{\partial^{2}}{\partial t^{2}}\left(D_{2}\right)=$
$\displaystyle-\frac{1}{p+t-1}$ $\displaystyle\frac{\partial^{2}}{\partial
t^{2}}\left(D_{2}\right)>$ $\displaystyle\,0\,.$ $\displaystyle\text{(From
$p+t<1$)}.$

It follows that $D_{2}$ is concave upwards in the relevant regime, and the
derivative at $t=0$ is $-1$. We further have $D_{2}|_{t=0}=0$, so when $p+t<1$
and $t\geq 0$ we have $D_{2}>-t$. Combining these results, we obtain the
desired inequality:

$D(p+t||p)>t\ln(6)-t>3t/4.$

∎

#### Non-uniform case.

In this section, we work out the combinatorics for the number of subset pairs
with respect to a particular _non-uniform_ distribution which assigns more
weight to permutations that have a large amount of $X$-pairs.

######  Definition 3.17.

Let $N\in\mathbb{N}$. The non-uniform distribution $\mathcal{D}_{X}$ over
permutations in $S_{N}$ is parameterized by a pair of subsets
$X=(X_{1},X_{2})$, and is defined as follows:

$\underset{\Phi\sim\mathcal{D}_{X}}{\Pr}[\Phi=\varphi]=\frac{|X_{\varphi}|}{\sum_{\,\sigma\in
S_{N}}|X_{\sigma}|}\,\,,\,\quad\text{ for }\,\varphi\in S_{N}.$

We begin by bounding the average number of $X$-pairs.

######  Theorem 3.18.

Let $N\in\mathbb{N}$ and $X_{1},X_{2}\subset[N]$ be non-empty subsets. Let
$|X_{\pi}|$ denote the number of $X$-pairs with respect to $\pi\in S_{N}$.
Then, the average number of $X$-pairs over the choice of permutation from
$\pi\sim\mathcal{D}_{X}$ satisfies

$1\,\leq\,\underset{\pi\sim\mathcal{D}_{X}}{\mathbb{E}}[|X_{\pi}|]\,\leq\,1+\frac{|X_{1}||X_{2}|}{N}.$

###### Proof.

Recall that the subsets $\\{S_{N}^{\kappa}\\}$ form a partition
$S_{N}=\bigsqcup_{\kappa=0}^{|X_{1}|}S_{N}^{\kappa}$, i.e., $S_{N}$ is the
disjoint union over all the $S_{N}^{\kappa}$, we have
$N!=\sum_{\kappa=0}^{|X_{1}|}|S_{N}^{\kappa}|$, and thus

$\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|]=\sum_{\kappa=0}^{|X_{1}|}\kappa\cdot\Pr_{\sigma\sim
S_{N}}[\sigma\in
S_{N}^{\kappa}]=\sum_{\kappa=0}^{|X_{1}|}\kappa\cdot\frac{|S_{N}^{\kappa}|}{N!}.$

Therefore, we obtain the following identity,

$\displaystyle\sum_{\,\sigma\in
S_{N}}|X_{\sigma}|=\sum_{\kappa=0}^{|X_{1}|}\sum_{\sigma\in
S_{N}^{\kappa}}|X_{\sigma}|=\sum_{\kappa=0}^{|X_{1}|}\kappa\cdot|S_{N}^{\kappa}|=N!\cdot\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|].$ (1)

We can now write the average number of $X$-pairs as follows:

$\displaystyle\underset{\pi\sim\mathcal{D}_{X}}{\mathbb{E}}[|X_{\pi}|]$
$\displaystyle=\sum_{\kappa=0}^{|X_{1}|}\kappa\cdot\Pr_{\pi\sim\mathcal{D}_{X}}[\pi\in
S_{N}^{\kappa}]$
$\displaystyle=\sum_{\kappa=0}^{|X_{1}|}\kappa\cdot\sum_{\pi\in
S_{N}^{\kappa}}\Pr_{\Pi\sim\mathcal{D}_{X}}[\Pi=\pi]$
$\displaystyle=\sum_{\kappa=0}^{|X_{1}|}\kappa\cdot\frac{\sum_{\pi\in
S_{N}^{\kappa}}|X_{\pi}|}{\sum_{\sigma\in S_{N}}|X_{\sigma}|}$
$\displaystyle=\sum_{\kappa=0}^{|X_{1}|}\kappa\cdot\frac{\kappa\cdot|S_{N}^{\kappa}|}{\sum_{\sigma\in
S_{N}}|X_{\sigma}|}$ $\displaystyle=\left(\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|]\right)^{-1}\sum_{\kappa=0}^{|X_{1}|}\kappa^{2}\cdot\frac{|S_{N}^{\kappa}|}{N!}$
(By LABEL:{eq:identity-sum-Z}) $\displaystyle=\frac{\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|^{2}]}{\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|]}.$ (2)

In other words, the average number of zero pairs in the non-uniform case is
the ratio between the second moment and the first moment in the uniform case.
We also have

$\displaystyle\frac{|X_{1}||X_{2}|}{N}\leq\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|^{2}]\leq$
$\displaystyle\frac{|X_{1}||X_{2}|}{N}+\frac{|X_{1}|^{2}|X_{2}|^{2}}{N^{2}}$
(Lemma 3.19) $\displaystyle\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|]=$ $\displaystyle\frac{|X_{1}||X_{2}|}{N}.$
(Theorem 3.13)

Putting everything together, we find that

$\displaystyle 1\leq\underset{\pi\sim\mathcal{D}}{\mathbb{E}}[|X_{\pi}|]\leq
1+\frac{|X_{1}||X_{2}|}{N}.$

∎

Recall that the previous lemma relied on the following fact:

######  Lemma 3.19.

Let $N\in\mathbb{N}$ and $X_{1},X_{2}\subset[N]$ be non-empty subsets. Let
$|X_{\pi}|$ denote the random variable for the number of $X$-pairs for $\pi\in
S_{N}$. Then, the second moment satisfies

$\left(\frac{|X_{1}||X_{2}|}{N}\right)\leq\underset{\pi\sim
S_{N}}{\mathbb{E}}[|X_{\pi}|^{2}]\leq\left(\frac{|X_{1}||X_{2}|}{N}+\frac{|X_{1}|^{2}|X_{2}|^{2}}{N^{2}}\right).$

###### Proof.

For a uniform random $\pi\sim S_{N}$ and some $x\in[N]$, we let $I_{x}$ be the
indicator variable which equals $1$, if $\pi(x)\in X_{2}$, and $0$ otherwise.
Then, we find that

$\displaystyle\mathbb{E}[I_{x}]=$ $\displaystyle\frac{|X_{2}|}{N},$
$\displaystyle|X_{\pi}|^{2}=$ $\displaystyle\left(\sum_{x\in
X_{1}}I_{x}\right)^{2}$

Therefore, we can express the second moment as follows:

$\displaystyle\underset{\pi\sim S_{N}}{\mathbb{E}}[|X_{\pi}|^{2}]=$
$\displaystyle\sum_{x,y\in X}\mathbb{E}[I_{x}I_{y}]$ (Linearity of
Expectation) $\displaystyle=$ $\displaystyle\sum_{x\in
X_{1}}\mathbb{E}[I_{x}]+\sum_{x\neq y\in X_{1}}\mathbb{E}[I_{x}I_{y}].$

Note that the the first term is equal to

$\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|]=\frac{|X_{1}||X_{2}|}{N}.$

The second term is obviously positive, hence the lower bound. The second term
has less than $|X_{1}|^{2}$ summands, and each summand can be bounded above
via

$\frac{|X_{2}|(|X_{2}|-1)}{N(N-1)}<\frac{|X_{2}|^{2}}{N^{2}}.$

Multiplying this through, we can upper bound the term as
$\frac{|X_{1}|^{2}|X_{2}|^{2}}{N^{2}}$. This gives the desired inequality. ∎

We can now give a tail bound for the number of $X$-pairs in the non-uniform
case. Our bound is tailored to the case where $|X_{1}|\cdot|X_{2}|=N$.

######  Theorem 3.20.

Let $N\in\mathbb{N}$ and let $X=(X_{1},X_{2})$ be a pair of subsets
$X_{1},X_{2}\subseteq[N]$ such that $|X_{1}|\cdot|X_{2}|=N$. Then, for any
real number $u\geq 6\underset{\sigma\sim S_{N}}{\mathbb{E}}[|X_{\sigma}|]$, it
holds that

$\displaystyle\underset{\pi\sim
S_{N}}{\Pr}\Big{[}|X_{\pi}|\geq\underset{\sigma\sim
S_{N}}{\mathbb{E}}[|X_{\sigma}|]+u\Big{]}\leq 3\exp\left(-4u/9\right).$

###### Proof.

Note that because $|X_{1}|\cdot|X_{2}|=N$ we can write $\mathcal{D}_{X}$ as

$\displaystyle\underset{\Phi\sim\mathcal{D}_{X}}{\Pr}[\Phi=\varphi]=$
$\displaystyle\frac{|X_{\varphi}|}{\sum_{\,\sigma\in S_{N}}|X_{\sigma}|}$
$\displaystyle=$ $\displaystyle\frac{|X_{\varphi}|}{N!}$ (Corollary 3.14)

Using the above equation, we can now write the probability distribution on
$X$-pairs as follows:

$\displaystyle\Pr_{\pi\sim\mathcal{D}}[|X_{\pi}|=\kappa]=$
$\displaystyle\kappa\cdot\Pr_{\sigma\sim S_{N}}[|X_{\sigma}|=\kappa],$

for any $\kappa\in\\{0,1,\dots,|X_{1}|\\}$. In particular, for $\kappa>6$, we
have the bound

$\displaystyle\Pr_{\pi\sim S_{N}}[|X_{\pi}|\geq\kappa]\leq$
$\displaystyle\exp(-3\kappa/4).$ (Theorem 3.15)

Therefore, we obtain

$\displaystyle\Pr_{\pi\sim\mathcal{D}_{X}}[|X_{\pi}|=\kappa]\leq$
$\displaystyle\kappa\cdot\exp(-3\kappa/4)$ $\displaystyle\leq$
$\displaystyle\exp\left(-\left(\frac{9-2\ln(6)}{12}\right)\kappa\right).$
$\displaystyle\text{(From $\kappa\geq 6$)}.$

Putting everything together and bounding the geometric series, we get that

$\displaystyle\Pr_{\pi\sim\mathcal{D}_{X}}[|X_{\pi}|\geq\kappa]=$
$\displaystyle\sum_{i=\kappa}^{|X_{1}|}\Pr_{\pi\sim\mathcal{D}}[|X_{\pi}|=i]$
$\displaystyle\leq$
$\displaystyle\sum_{i=\kappa}^{\infty}\exp\left(-\left(\frac{9-2\ln(6)}{12}\right)i\right)$
$\displaystyle\leq$
$\displaystyle\left(1-\exp\Big{(}-\frac{9-2\ln(6)}{12}\Big{)}\right)^{-1}\exp\left(-\left(\frac{9-2\ln(6)}{12}\right)\kappa\right)$
$\displaystyle\leq$ $\displaystyle 3\exp\left(\frac{-4\kappa}{9}\right).$

∎

##  4 Query Problem Lower Bounds

Unruh [Unr21, Unr23] proposed the task of “double-sided zero-search”—a simple
query problem dealing with invertible permutations which seems to go beyond
the scope of current techniques, and may potentially offer new insights into
the post-quantum security of the sponge construction. Unruh conjectured that
it requires at least $\Omega(2^{n/2})$ many queries to solve the problem with
constant success probability—and this is tight due to Grover’s algorithm.

In this section, we prove query-lower bounds for Unruh’s original double-sided
zero-search problem, as well as a non-uniform variant that will be useful in
proving the one-wayness of the single-round sponge with invertible
permutations. We remark that our lower bounds on double-sided zero-search are
tight up to a constant factor, and therefore resolve Unruh’s original
conjecture.

###  4.1 Double-Sided Zero-Search

In light of the difficulty in proving the post-quantum security of the sponge
with invertible permutations, Unruh [Unr21, Unr23] proposed the following
simple query problem which seems beyond the scope of current techniques.

[Double-Sided Zero-Search] Given quantum query-access to a uniformly random
permutation $\varphi:\\{0,1\\}^{2n}\rightarrow\\{0,1\\}^{2n}$ as well as its
inverse $\varphi^{-1}$, output a pair of strings $x,y\in\\{0,1\\}^{n}$ such
that $\varphi(x||0^{n})=y||0^{n}$. Recall that we call $x,y\in\\{0,1\\}^{n}$
which satisfy $\varphi(x||0^{n})=y||0^{n}$ a _zero pair_ of $\varphi$.

We prove that any algorithm must make at least $T=\Omega(\sqrt{\epsilon
2^{n}})$ many queries in order to find a zero pair for a random $2n$-bit
permutation with probability $\epsilon$. At a high level, the first step of
the proof is showing that there is some worst case instances on which the
problem is hard for any fixed number of zero pairs, in Lemma 4.3. Then we give
a worst to average case reduction to show hardness for a random permutation
with a fixed number of zero pairs in Lemma 4.4. Finally, we give a bound for
the general problem using the aforementioned bounds as well as tail bounds on
the number of zero pairs.

######  Theorem 4.1.

Any quantum algorithm for Double-Sided Zero-Search that makes $T$ queries to a
random $2n$-bit permutation or its inverse and succeeds with probability
$\epsilon>0$ satisfies

$\epsilon\leq\frac{50(T+1)^{2}}{2^{n}}.$

###### Proof.

Let $\varphi$ be a uniformly random $2n$-bit permutation and
$K=|Z_{\varphi}|\in\\{0,1,\dots,2^{n}\\}$ be the random variable corresponding
to the number of zero pairs in $\varphi$. By the law of total probability, we
can write the success probability $\epsilon$ of a $T$-query algorithm as

$\displaystyle\epsilon=$
$\displaystyle\sum_{\kappa=0}^{2^{n}}\Pr[K=\kappa]\cdot\Pr[success|K=\kappa]$
$\displaystyle=$
$\displaystyle\underbrace{\sum_{\kappa=1}^{6}\Pr[K=\kappa]\cdot\Pr[success|K=\kappa]}_{=P_{1}}+\underbrace{\sum_{\kappa=7}^{2^{n}}\Pr[K=\kappa]\cdot\Pr[success|K=\kappa]}_{=P_{2}}.$

We bound each term separately. Beginning with the first, we get

$\displaystyle P_{1}\leq$
$\displaystyle\max_{\kappa\in[6]}\left\\{\Pr[success|K=\kappa]\right\\}$ (By
Convexity) $\displaystyle\leq$ $\displaystyle\frac{48(T+1)^{2}}{2^{n}}.$ (By
Lemma 4.4)

Continuing with the second, we find that

$\displaystyle P_{2}\leq$
$\displaystyle\sum_{\kappa=7}^{2^{n}}\Pr[success|K=\kappa]\cdot\exp(-3\kappa/4)$
(By Theorem 3.15) $\displaystyle\leq$
$\displaystyle\sum_{\kappa=7}^{2^{n}}\frac{8(T+1)^{2}\kappa}{2^{n}}\cdot\exp(-3\kappa/4)$
(By Lemma 4.4) $\displaystyle\leq$ $\displaystyle\frac{2(T+1)^{2}}{2^{n}}.$
(Arithmetico-geometric series)

Therefore, we obtain the following bound on total success probability:

$\displaystyle\epsilon\leq\frac{50(T+1)^{2}}{2^{n}}$

∎

We observe that this bound is tight up to constant factors for any $\epsilon$,
as there is at least single zero pair with $\Omega(1)$ probability (Lemma
3.5), which can be found using Grover’s algorithm [Gro96] with probability
$\Theta(T^{2}/2^{n})$ after $T$ queries. In particular, we have the following
corollary.

######  Corollary 4.2.

Given quantum oracle-access to a random $2n$-bit permutation and its inverse,
the query complexity of outputting a zero pair with probability $\epsilon$ is
$\Theta(\sqrt{\epsilon 2^{n}})$.

#### Reduction from worst-case unstructured search.

In the following lemma, we prove a query-lower bound for a worst-case variant
of Double-Sided Zero-Search in Section 4.1, where we are given the promise
that the underlying permutation has exactly $K$-many zero pairs. We show the
following.

######  Lemma 4.3.

Any $T$-query quantum algorithm for the Double-Sided Zero-Search problem with
respect to a $2n$-bit worst-case permutation with exactly $K>0$ zero and which
succeeds with probability $\epsilon>0$ must satisfy the inequality

$\epsilon\leq\frac{8(T+1)^{2}K}{2^{n}}.$

###### Proof.

We reduce the worst-case Unstructured Search problem with $K$ out of $2^{n}$
marked elements to a specific instance of Double-Sided Zero-Search for a
$2n$-bit permutation $\varphi$ with exactly $K$ many zero pairs without any
query overhead.

Suppose we are given quantum query access to a function

$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$

such that $|f^{-1}(1)|=K$. We now construct a permutation
$\varphi:\\{0,1\\}^{2n}\rightarrow\\{0,1\\}^{2n}$, where $\varphi$ is defined
as follows for any pair of strings $x,y\in\\{0,1\\}^{n}$:

$\varphi(x||y)=\begin{cases}x||y&\text{ if }f(x)=1\\\ x||(y\oplus
1^{n})&\text{ if }f(x)=0.\end{cases}$

It is apparent that we can implement a query to $\varphi$ using a single query
to $f$. Further, we have $\varphi=\varphi^{-1}$ since $\varphi$ is a
composition of $1$ and $2$-cycles; hence, we can also implement queries to
$\varphi^{-1}$. Now let $x||0^{n}$ be a zero pair of $\varphi$. It follows
that $f(x)=1$, as otherwise $\varphi(x||0^{n})=x||1^{n}$. Similarly, if, for
any $x^{\prime}$, we have $f(x^{\prime})=1$, then $x^{\prime}||0^{n}$ is a
zero pair of $\varphi$. There are therefore $K$ zero pairs in $\varphi$ and,
given a zero pair of $\varphi$, it is straight forward to find a preimage of
$1$ under $f$, which can be used to solve Unstructured Search. The claim now
follows from Corollary 2.4. ∎

#### Worst-case to average-case reduction.

In the following lemma, we prove a query-lower bound for an average-case
variant of Double-Sided Zero-Search in Section 4.1, where we are given the
promise that the underlying permutation has exactly $K$-many zero pairs. In
this case, average refers to a uniform random permutation over all that have
exactly $K$-many zero pairs. We show the following.

######  Lemma 4.4.

Any quantum algorithm for Double-Sided Zero-Search on a uniform random
permutation $\varphi$, subject to the constraint that $\varphi$ has exactly
$K>0$ zero pairs, making $T$ queries to $\varphi,\varphi^{-1}$ and succeeding
with probability $\epsilon>0$ satisfies the inequality

$\epsilon\leq\frac{8(T+1)^{2}K}{2^{n}}$

###### Proof.

Let $N=2^{2n}$ and let $Z\subset[N]$ denote the set of elements whose binary
decomposition ends in $0^{n}$. Let $G_{Z}\leq S_{N}$ be the subgroup of
permutations that fix $Z$, i.e.,

$G_{Z}\simeq S_{Z}\times S_{[N]\setminus Z}.$

We can re-randomize any worst-case permutation
$\varphi:\\{0,1\\}^{2n}\rightarrow\\{0,1\\}^{2n}$ with $K$ zero pairs into an
average-case permutation $\varphi^{\mathrm{sym}}$ with $K$ zero pairs as
follows.

  1. 1.

Randomly and independently sample permutations $\omega,\sigma\sim G_{Z}$.

  2. 2.

Define the symmetrized permutation
$\varphi^{\mathrm{sym}}=\omega\circ\varphi\circ\sigma$.

It follows from Lemma 3.12 that $\varphi^{\mathrm{sym}}$ is uniform random
among permutations with $K$ zero pairs. Let $x,y\in Z$ be a zero pair of
$\varphi^{\mathrm{sym}}$ such that $\varphi^{\mathrm{sym}}(x)=y$. We have that

$\displaystyle x^{\prime}=$ $\displaystyle\,\sigma(x),$ $\displaystyle
y^{\prime}=\omega^{-1}(y)$ (3)

satisfy $x^{\prime},y^{\prime}\in Z$ and $\varphi(x^{\prime})=y^{\prime}$,
hence a zero pair of $\varphi$ can be constructed for free from a zero pair of
$\varphi^{\mathrm{sym}}$. We can simulate queries to $\varphi^{\mathrm{sym}}$
as well as its inverse with a single query to $\varphi,\varphi^{-1}$
respectively, so the reduction incurs no overhead. Therefore, the claim
follows from Lemma 4.3. ∎

###  4.2 Alternative proof in the superposition-oracle framework

In this section, we give an alternative proof for Lemma 4.4, i.e., the query
lower bound for Double-Sided Zero-Search. Because this lemma is a key
component of Theorem 4.1, it presents an alternative approach for resolving
Section 1.

We work with two-way accessible superposition oracles for invertible
permutations. The superposition oracle framework is a powerful tool which has
been used to prove query lower bounds in a variety of settings, e.g., [Amb+11,
Zha18, Ros22, Ala+22]. Zhandry [Zha18] also introduced the notion of
compressed oracles as a means to “record” quantum queries to a random oracle.
However, contrary to the work of Zhandry [Zha18], we do not need to “compress”
the oracles and use inefficient representations instead. First, we introduce
some relevant notation.

#### Superposition oracles.

Let $\mathcal{F}_{n}=\\{f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}\\}$ be the
family of $n$-bit functions. The _function register_ for $f\in\mathcal{F}_{n}$
is a collection $F=\\{F_{x}\\}_{x\in\\{0,1\\}^{n}}$ with

$\ket{f}_{F}=\bigotimes_{x\in\\{0,1\\}^{n}}\ket{f(x)}_{F_{x}}.$

A query to $f$ in the superposition oracle framework amounts to the operation
$O$ with

$O_{XYF}\ket{x}_{X}\ket{y}_{Y}\ket{f}_{F}=\mathsf{CNOT}_{F_{x}:Y}\ket{x}_{X}\ket{y}_{Y}\ket{f}_{F}=\ket{x}_{X}\ket{y\oplus
f(x)}_{Y}\ket{f}_{F}.$

We can also model inverse queries in the superposition oracle framework. This
amounts to the operation $O^{-1}$ which is defined as the unitary

$O_{XYF}^{-1}\ket{x}_{X}\ket{y}_{Y}\ket{f}_{F}=\ket{x\oplus(\oplus_{x^{\prime}:f(x^{\prime})=y}\,x^{\prime})}_{X}\ket{y}_{Y}\ket{f}_{F}.$

For example, if $f$ is a permutation, the inverse oracle amounts to the
operation

$O_{XYF}^{-1}\ket{x}_{X}\ket{y}_{Y}\ket{f}_{F}=\ket{x\oplus
f^{-1}(y)}_{X}\ket{y}_{Y}\ket{f}_{F}.$

#### Symmetrization.

Let $N=2^{2n}$ and consider a random permutation $\varphi\in S_{N}^{\kappa}$
which has exactly $\kappa$ many zero pairs. In the superposition oracle
framework, we can model queries to such a permutation using a function
register of the form

$\displaystyle\ket{\Phi_{\kappa}}_{F}=|S_{N}^{\kappa}|^{-\frac{1}{2}}\sum_{\varphi\in
S_{N}^{\kappa}}\ket{\varphi}_{F}.$ (4)

We now switch to an alternative characterization of the function registers
which uses our technique of symmetrization via subset pairs of the symmetric
group. Let $Z\subset[N]$ denote the set of strings whose binary decomposition
ends in $0^{n}$ many zeroes. Let $G_{Z}\leq S_{N}$ be the subgroup of
permutations in $S_{N}$ that fix $Z$, i.e.,

$G_{Z}\simeq S_{Z}\times S_{[N]\setminus Z}.$

Define the product group $G=G_{Z}\times G_{Z}$, where $G$ consists of pairs of
permutations $(\sigma,\omega)$ such that each permutation fixes $Z$, i.e.,
$\sigma(Z)=Z=\omega(Z)$. Define the unitary representation
$U:G\rightarrow\mathrm{GL}(\mathbb{C}^{\mathcal{F}})$ with
$(\sigma,\omega)\mapsto U_{\sigma,\omega}$ and

$U_{\sigma,\omega}\ket{f}_{F}=\ket{\omega\circ f\circ\sigma}_{F},\quad\text{
for }f\in\mathcal{F}_{2n}.$

Using symmetrization, we can now equivalently instantiate the function
register $F$ in Equation 4 via the extension

$\ket{\Phi_{\kappa}}_{F}\mapsto\ket{\pi_{\kappa}^{\mathrm{sym}}}_{\Sigma\Omega
F}=\frac{1}{\sqrt{|G|}}\sum_{(\sigma,\omega)\in
G}\ket{\sigma}_{\Sigma}\ket{\omega}_{\Omega}U_{\sigma,\omega}\ket{\pi_{\kappa}}_{F},$

where $\pi_{\kappa}$ is an _arbitrary_ fixed permutation in $S_{N}^{\kappa}$
with exactly $\kappa$ many zero pairs. To see why this is a valid
purification, we can use our symmetrization argument in Lemma 3.12 to argue
that—once we trace out registers $\Sigma\Omega$—the reduced state equals

$\frac{1}{|G|}\sum_{(\sigma,\omega)\in
G}U_{\sigma,\omega}|\pi_{\kappa}\rangle\langle\pi_{\kappa}|_{F}U_{\sigma,\omega}^{\dagger}=\frac{1}{|S_{N}^{\kappa}|}\sum_{\varphi\in
S_{N}^{\kappa}}|\varphi\rangle\langle\varphi|_{F}.$

#### Double-sided zero-search revisited.

To give an alternative proof for Lemma 4.4 in the superposition oracle
framework, we first prove a lower bound for the decision problem. We show that
no quantum algorithm can distinguish whether it is querying a random
invertible permutation with exactly $\kappa$ many zero pairs, or a random
invertible permutation with no zero pairs—unless it makes a large number of
queries. Our proof is rooted in one-way to hiding [AHU18] and allows the query
algorithm to query two oracles: one in the forward direction and one in the
backward direction.

######  Theorem 4.5.

Let $N=2^{2n}$ and let $\kappa\in\\{0,1,\dots,\sqrt{N}\\}$. Then, for any
quantum algorithm $\mathcal{D}$ which makes at most $T$ many queries, it holds
that

$\Big{|}\Pr_{\varphi\sim
S_{N}^{\kappa}}[\mathcal{D}^{\varphi,\varphi^{-1}}(1^{n})=1]-\Pr_{\varphi\sim
S_{N}^{0}}[\mathcal{D}^{\varphi,\varphi^{-1}}(1^{n})=1]\Big{|}\,\leq\,2T\sqrt{\frac{\kappa}{2^{n}}}.$

###### Proof.

Suppose that a distinguisher $\mathcal{D}$ makes a total amount of $T$ oracle
queries. In the superposition oracle framework, we can model the
adversary/oracle interaction by introducing a function register $F$ which is
outside of the view of $\mathcal{D}$. Suppose the register $F$ is initially in
the state $\ket{\Phi^{0}}_{F}$. Using symmetrization, we can now equivalently
instantiate the register $F$ as the uniform superposition

$\ket{\Phi^{0}}_{F}\mapsto\ket{\pi_{0}^{\mathrm{sym}}}_{\Sigma\Omega
F}=\frac{1}{\sqrt{|G|}}\sum_{(\sigma,\omega)\in
G}\ket{\sigma}_{\Sigma}\ket{\omega}_{\Omega}U_{\sigma,\omega}\ket{\pi_{0}}_{F},$

where $\pi_{0}(x_{1}||x_{2})=(x_{1}||x_{2}\oplus 1^{n})$ is a fixed
permutation in $S_{N}^{0}$ with no zero pairs.

For the remainder of the proof, we will analyze the effect of swapping out the
symmetrization of $\pi_{0}\in S_{N}^{0}$ with symmetrization of a different
permutation which comes from $S_{N}^{\kappa}$. Specifically, we will choose a
particular permutation $\pi_{K}$ which is generated as follows: first sample a
random subset $K\subset\\{0,1\\}^{n}$ (independently of everything else) of
size $|K|=\kappa$, and then let $\pi_{K}$ be the permutation

$\pi_{K}(x_{1}||x_{2})=\begin{cases}x_{1}||x_{2}&\text{ if }x_{1}\in K;\\\
x_{1}||x_{2}\oplus 1^{n}&\text{ otherwise. }\end{cases}$

Note that $\pi_{K}$ differs from $\pi_{0}$ on exactly $\kappa\cdot 2^{n}$ many
inputs of the form $(x_{1}||x_{2})$, where $x_{1}\in K$ and $x_{2}$ is
arbitrary. Moreover, $\pi_{K}$ has exactly $\kappa$ many zero pairs of the
form $(x_{1}||0^{n})$ whenever $x_{1}\in K$. Thus, $\pi_{K}\in
S_{N}^{\kappa}$. Notice that we can map between the symmetrizations
$\ket{\pi_{0}^{\mathrm{sym}}}$ and $\ket{\pi_{K}^{\mathrm{sym}}}$ via the
following unitary

$\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F}=U_{\Sigma\Omega:F}(\mathbb{1}_{\Sigma\Omega}\otimes
W^{K}_{F})U_{\Sigma\Omega:F}^{\dagger}\,,$

where $U_{\Sigma\Omega:F}$ is a controlled unitary of the form

$U\ket{\sigma}_{\Sigma}\ket{\omega}_{\Omega}\ket{f}_{F}=\ket{\sigma}_{\Sigma}\ket{\omega}_{\Omega}U_{\sigma,\omega}\ket{f}_{F},\quad\text{
for }f\in\mathcal{F}_{2n},$

and where $W^{K}$ is the unitary which flips between $\ket{\pi_{K}}$ and
$\ket{\pi_{0}}$. 555$W^{K}$ has a well-defined extension to all $\ket{f}_{F}$
since we just need to $XOR$ the string $(0^{n}||1^{n})$ into the function
output whenever the input is of the form $(x_{1}||y)$, for $x_{1}\in K$ and
$y\in\\{0,1\\}^{n}$ Therefore,

$\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F}\ket{\pi_{0}^{\mathrm{sym}}}_{\Sigma\Omega
F}=\ket{\pi_{K}^{\mathrm{sym}}}_{\Sigma\Omega F}.$

Our goal is to show the following property: on average over the choice of $K$,
the query magnitude on symmetrized oracle calls that involve $\pi_{0}$ on
$(x_{1}||x_{2})$ with $x_{1}\in K$ and arbitrary $x_{2}$ will be small. We
will prove this through a sequence of intermediate steps. Note that oracle
calls to $\ket{\omega\circ\pi_{0}\circ\sigma}_{F}$, where the permutations
$\sigma,\omega$ come from registers $\Sigma$ and $\Omega$) only involve $K$ in
one of two ways:

  * •

a forward query in the $X$ register is made on $\sigma^{-1}(x_{1}||x_{2})$
with $x_{1}\in K$; or

  * •

a backward query in the $Y$ register is made on $\omega(x_{1}||x_{2})$ with
$x_{1}\in K$.

Define the following projectors that exclude each of the two cases:

$\displaystyle\Pi_{X\Sigma}^{K}$
$\displaystyle=\sum_{x^{\prime}\in\\{0,1\\}^{2n}}|x^{\prime}\rangle\langle
x^{\prime}|_{X}\otimes\bigotimes_{\begin{subarray}{c}x_{1}\in K\\\
x_{2}\in\\{0,1\\}^{n}\end{subarray}}\big{(}\mathbb{1}-|x_{1}||x_{2}\rangle\langle
x_{1}||x_{2}|\big{)}_{\Sigma_{x^{\prime}}}$ (5)
$\displaystyle\Xi_{Y\Omega}^{K}$
$\displaystyle=\sum_{y^{\prime}\in\\{0,1\\}^{2n}}|y^{\prime}\rangle\langle
y^{\prime}|_{Y}\otimes\bigotimes_{\begin{subarray}{c}x_{1}\in K\\\
x_{2}\in\\{0,1\\}^{n}\end{subarray}}\big{(}\mathbb{1}-|y^{\prime}\rangle\langle
y^{\prime}|\big{)}_{\Omega_{x_{1}||x_{2}}}\,.$ (6)

If we apply the projectors $\Pi_{X\Sigma}^{K}$ and $\Xi_{Y\Omega}^{K}$ to each
forward/backward query just before the oracle is applied, then swapping from
$\pi_{0}$ to $\pi_{K}$ before the oracle evaluation has no effect. Formally,
we have the commutation relations666For two linear operators $A$ and $B$, the
commutator is defined as $[A,B]:=AB-BA$.

$\displaystyle\left[\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F},O_{XYF}\,\Pi_{X\Sigma}^{K}\right]$ $\displaystyle=0$ (7)
$\displaystyle\left[\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F},O_{XYF}^{-1}\,\Xi_{Y\Omega}^{K}\right]$ $\displaystyle=0.$ (8)

For $i\in[T]$, we now define the ensemble of projectors
$\\{P_{i}^{K}\\}_{i\in[T]}$, where

$\displaystyle P_{i}^{K}=\begin{cases}\Pi^{K},&\text{ if }O_{i}=O;\\\
\Xi^{K},&\text{ if }O_{i}=O^{-1}.\end{cases}$ (9)

Suppose $F$ is initially in the state $\ket{\Phi^{0}}_{F}$ and $\mathcal{D}$
starts out with some normalized pure state $\ket{\eta_{0}}$ on registers
$XYE$. We can model the interaction between $\mathcal{D}$ and the oracle as
sequence of oracle queries and unitaries such that for $i\in[T]$,

$\displaystyle\ket{\psi_{i}}_{XYE\Sigma\Omega
F}=U_{i}O_{i}U_{i-1}O_{i-1}\cdots U_{1}O_{1}\ket{\psi_{0}}\,.$ (10)

Here, the unitaries $O_{i}\in\\{O,O^{-1}\\}$ represent a call to the
forward/backward oracles acting on registers $XYF$, the $U_{i}$ represent
intermediate unitaries performed by $\mathcal{D}$ which act on $XYE$, for some
workspace register $E$, and where $\ket{\psi_{0}}$ is the state

$\ket{\psi_{0}}_{XYE\Sigma\Omega
F}=\ket{\eta_{0}}_{XYE}\otimes\ket{\pi_{0}^{\mathrm{sym}}}_{\Sigma\Omega
F}\,.$

To study the effects of swapping between symmetrizations of $\pi_{0}\in
S_{N}^{0}$ and $\pi_{K}\in S_{N}^{\kappa}$, we now define $i$-th intermediate
state as

$\ket{\psi_{i}^{K}}_{XYE\Sigma\Omega F}=U_{i}O_{i}U_{i-1}O_{i-1}\cdots
U_{1}O_{1}\ket{\psi_{0}^{K}}\,,$

where $\ket{\psi_{0}}$ is the initial state corresponding to a symmetrization
of $\pi_{K}$, i.e.,

$\ket{\psi_{0}^{K}}_{XYE\Sigma\Omega
F}=\ket{\eta_{0}}_{XYE}\otimes\ket{\pi_{K}^{\mathrm{sym}}}_{\Sigma\Omega
F}\,.$

We now introduce the $K$-dependent oracle unitaries
$\\{O^{K}_{i}\\}_{i\in[T]}$ where

$O^{K}_{i}=\left(\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F}\right)^{\dagger}(O_{i})_{XYF}\,\,\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F}$

acts on registers $XY\Sigma\Omega F$. This yields the following equivalent
characterization

$\displaystyle\ket{\psi_{i}^{K}}_{XYE\Sigma\Omega
F}=U_{i}O_{i}^{K}U_{i-1}O_{i-1}^{K}\cdots U_{1}O_{1}^{K}\ket{\psi_{0}}\,.$
(11)

By unitarity, we can now bound the distance between the $i$-th hybrid states
as

$\displaystyle\left\|\ket{\psi_{i}}-\ket{\psi_{i}^{K}}\right\|^{2}$
$\displaystyle=\left\|U_{i}O_{i}\ket{\psi_{i-1}}-U_{i}O_{i}^{K}\ket{\psi_{i-1}^{K}}\right\|^{2}$
$\displaystyle=\left\|O_{i}\ket{\psi_{i-1}}-O_{i}^{K}\ket{\psi_{i-1}^{K}}\right\|^{2}$
$\displaystyle=\left\|O_{i}\ket{\psi_{i-1}}-O_{i}^{K}\ket{\psi_{i-1}}+O_{i}^{K}\ket{\psi_{i-1}}-O_{i}^{K}\ket{\psi_{i-1}^{K}}\right\|^{2}$
$\displaystyle\leq\left\|O_{i}\ket{\psi_{i-1}}-O_{i}^{K}\ket{\psi_{i-1}}\right\|^{2}+\left\|O_{i}^{K}\ket{\psi_{i-1}}-O_{i}^{K}\ket{\psi_{i-1}^{K}}\right\|^{2}$
$\displaystyle\quad\quad+2\cdot\left\|O_{i}\ket{\psi_{i-1}}-O_{i}^{K}\ket{\psi_{i-1}}\right\|\cdot\left\|O_{i}^{K}(\ket{\psi_{i-1}}-\ket{\psi_{i-1}})\right\|$
$\displaystyle=\left\|(O_{i}-O_{i}^{K})\ket{\psi_{i-1}}\right\|^{2}+\left\|\ket{\psi_{i-1}}-\ket{\psi_{i-1}^{K}}\right\|^{2}$
$\displaystyle\quad\quad+2\cdot\left\|(O_{i}-O_{i}^{K})\ket{\psi_{i-1}}\right\|\cdot\left\|\ket{\psi_{i-1}}-\ket{\psi_{i-1}^{K}}\right\|,$
(12)

where the inequality follows from Cauchy-Schwarz. We now observe that

$\displaystyle\left\|(O_{i}-O_{i}^{K})\ket{\psi_{i-1}}\right\|$
$\displaystyle=\left\|(O_{i}-O_{i}^{K})\bar{P}_{i}^{K}\ket{\psi_{i-1}}+(O_{i}-O_{i}^{K})P_{i}^{K}\ket{\psi_{i-1}}\right\|$
$\displaystyle\leq\left\|(O_{i}-O_{i}^{K})\bar{P}_{i}^{K}\ket{\psi_{i-1}}\right\|+\left\|(O_{i}-O_{i}^{K})P_{i}^{K}\ket{\psi_{i-1}}\right\|$
$\displaystyle\leq
2\cdot\left\|\bar{P}_{i}^{K}\ket{\psi_{i-1}}\right\|+\left\|(O_{i}-O_{i}^{K})P_{i}^{K}\ket{\psi_{i-1}}\right\|$
$\displaystyle=2\cdot\left\|\bar{P}_{i}^{K}\ket{\psi_{i-1}}\right\|.$ (13)

Here, the second to last line uses that $(O_{i}-O_{i}^{K})$ has operator norm
at most $2$. For the last line, we first invoke the fact that
$\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega F}$ and $P_{i}^{K}$ commute,
and then use the commutation relations from Equations 7 and 8 so that

$\displaystyle\left\|(O_{i}-O_{i}^{K})P_{i}^{K}\ket{\psi_{i-1}}\right\|$
$\displaystyle=\left\|\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F}(O_{i}-O_{i}^{K})P_{i}^{K}\ket{\psi_{i-1}}\right\|\quad\quad\text{(By
unitarity)}$
$\displaystyle=\left\|(\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F}\,O_{i}\,P_{i}^{K}-O_{i}\,\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F}\,P_{i}^{K})\ket{\psi_{i-1}}\right\|$
$\displaystyle=\left\|(\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F}\,O_{i}\,P_{i}^{K}-O_{i}\,P_{i}^{K}\,\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F})\ket{\psi_{i-1}}\right\|$
$\displaystyle=\left\|\left[\mathsf{SWAP}^{\pi_{K},\pi_{0}}_{\Sigma\Omega
F},\,O_{i}\,P_{i}^{K}\right]\ket{\psi_{i-1}}\right\|=0.$

By combining Equation 12 and Equation 13, we get that

$\displaystyle\left\|\ket{\psi_{i}}-\ket{\psi_{i}^{K}}\right\|^{2}$
$\displaystyle\leq
4\cdot\left\|\bar{P}_{i}^{K}\ket{\psi_{i-1}}\right\|^{2}+\left\|\ket{\psi_{i-1}}-\ket{\psi_{i-1}^{K}}\right\|^{2}$
$\displaystyle\quad\quad+4\cdot\left\|\bar{P}_{i}^{K}\ket{\psi_{i-1}}\right\|\cdot\left\|\ket{\psi_{i-1}}-\ket{\psi_{i-1}^{K}}\right\|$
$\displaystyle=\left(\left\|\ket{\psi_{i-1}}-\ket{\psi_{i-1}^{K}}\right\|+2\cdot\left\|\bar{P}_{i}^{K}\ket{\psi_{i-1}}\right\|\right)^{2},$
(14)

and thus

$\displaystyle\left\|\ket{\psi_{T}}-\ket{\psi_{T}^{K}}\right\|\leq
2\cdot\sum_{i=1}^{T}\left\|\bar{P}_{i}^{K}\ket{\psi_{i}}\right\|.$ (15)

Therefore, we can bound the average distance as follows:

$\displaystyle\mathsf{TD}\Big{(}|\psi_{T}\rangle\langle\psi_{T}|,\underset{\begin{subarray}{c}K\subset\\{0,1\\}^{n}\\\
|K|=\kappa\end{subarray}}{\mathbb{E}}|\psi_{T}^{K}\rangle\langle\psi_{T}^{K}|\Big{)}$
$\displaystyle\quad\leq\underset{\begin{subarray}{c}K\subset\\{0,1\\}^{n}\\\
|K|=\kappa\end{subarray}}{\mathbb{E}}\mathsf{TD}\Big{(}|\psi_{T}\rangle\langle\psi_{T}|,|\psi_{T}^{K}\rangle\langle\psi_{T}^{K}|\Big{)}$
(By convexity)
$\displaystyle\quad\leq\underset{\begin{subarray}{c}K\subset\\{0,1\\}^{n}\\\
|K|=\kappa\end{subarray}}{\mathbb{E}}\left\|\ket{\psi_{T}}-\ket{\psi_{T}^{K}}\right\|$
(Norm inequality)
$\displaystyle\quad\leq\underset{\begin{subarray}{c}K\subset\\{0,1\\}^{n}\\\
|K|=\kappa\end{subarray}}{\mathbb{E}}2\cdot\sum_{i=1}^{T}\left\|\bar{P}_{i}^{K}\ket{\psi_{i}}\right\|$
(By Equation 15)
$\displaystyle\quad=2T\underset{i\sim[T]}{\mathbb{E}}\,\,\underset{\begin{subarray}{c}K\subset\\{0,1\\}^{n}\\\
|K|=\kappa\end{subarray}}{\mathbb{E}}\left\|\bar{P}_{i}^{K}\ket{\psi_{i}}\right\|$
$\displaystyle\quad\leq
2T\sqrt{\underset{i\sim[T]}{\mathbb{E}}\,\,\underset{\begin{subarray}{c}K\subset\\{0,1\\}^{n}\\\
|K|=\kappa\end{subarray}}{\mathbb{E}}\left\|\bar{P}_{i}^{K}\ket{\psi_{i}}\right\|^{2}}.$
$\displaystyle\text{(Jensen's inequality)}.$

To complete the proof, it suffices to bound the expectation. By the definition
of $\\{P_{i}^{K}\\}_{i\in[T]}$ in Equation 9, we have to consider two cases
for each $i\in[T]$. First, suppose that the $i$-th query is a forward query
with $O_{i}=O$. Then,

$\displaystyle\underset{\begin{subarray}{c}K\subset\\{0,1\\}^{n}\\\
|K|=\kappa\end{subarray}}{\mathbb{E}}\left\|\bar{P}_{i}^{K}\ket{\psi_{i}}\right\|^{2}=\underset{\begin{subarray}{c}K\subset\\{0,1\\}^{n}\\\
|K|=\kappa\end{subarray}}{\mathbb{E}}\left[\left\|(\mathbb{1}-\Pi^{K})_{X\Sigma}\ket{\psi_{i}}_{XY\Sigma\Omega
E}\right\|_{2}^{2}\right]\leq\frac{\kappa}{2^{n}}.$ (16)

Next, suppose that the $i$-th query is to the inverse oracle $O_{i}=O^{-1}$.
Then, we have

$\displaystyle\underset{\begin{subarray}{c}K\subset\\{0,1\\}^{n}\\\
|K|=\kappa\end{subarray}}{\mathbb{E}}\left\|\bar{P}_{i}^{K}\ket{\psi_{i}}\right\|^{2}=\underset{\begin{subarray}{c}K\subset\\{0,1\\}^{n}\\\
|K|=\kappa\end{subarray}}{\mathbb{E}}\left[\left\|(\mathbb{1}-\Xi^{K})_{Y\Omega}\ket{\psi_{i}}_{XY\Sigma\Omega
E}\right\|_{2}^{2}\right]\leq\frac{\kappa}{2^{n}}.$ (17)

Putting everything together and using Equation 16 and Equation 17, we arrive
that

$\mathsf{TD}\Big{(}|\psi_{T}\rangle\langle\psi_{T}|,\underset{\begin{subarray}{c}K\subset\\{0,1\\}^{n}\\\
|K|=\kappa\end{subarray}}{\mathbb{E}}|\psi_{T}^{K}\rangle\langle\psi_{T}^{K}|\Big{)}\leq
2T\cdot\sqrt{\frac{\kappa}{2^{n}}}.$

This proves the claim. ∎

#### Alternative to resolving Unruh’s conjecture.

We can use Theorem 4.5 to prove an alternative version of Lemma 4.4, which in
turn is the key component of Theorem 4.1, and thus in resolving Section 1.

######  Lemma 4.6 (Alternative to Lemma 4.4).

Any quantum $T$-query algorithm for the Double-Sided Zero-Search problem with
respect to a random $2n$-bit invertible permutation with exactly $\kappa>0$
zero pairs, $\pi\sim S_{2^{2n}}^{\kappa}$, that succeeds with probability
$\epsilon>0$ satisfies the inequality

$\epsilon\leq 2(T+1)\sqrt{\frac{\kappa}{2^{n}}}.$

Before proceeding with the proof, we observe a difference between Lemma 4.6
and Lemma 4.4. While both are tight up to constant factors for a constant
success probability (and thus sufficient to resolve Section 1), the bound in
Lemma 4.6 is of the form $\epsilon=O(T\sqrt{\kappa/2^{n}})$ whereas in Lemma
4.4 the bound derived is of the form $\epsilon=O(T^{2}\kappa/2^{n})$. The
latter bound is quadratically tighter for small $\epsilon\ll 1$, and so we
state our main theorem in these terms. We leave tightening the analysis in the
superposition-oracle framework as an interesting open problem

###### Proof.

Suppose that $\mathcal{A}^{\varphi,\varphi^{-1}}$ finds a zero pair with
probability $\epsilon>0$ whenever $\varphi$ is random $2n$-bit permutation
with exactly $\kappa$ many zero pairs. We can transform such an $\mathcal{A}$
into a distinguisher between permutations with $\kappa$ zero pairs and no zero
pairs by running it on a given permutation, and guessing that $\varphi$ has
$\kappa$ zero pairs if and only if $\mathcal{A}$ finds a zero pair. Formally,
given a permutation $\varphi,\varphi^{-1}$ the distinguisher
$\mathcal{D}^{\varphi,\varphi^{-1}}$ proceeds as follows:

  1. 1.

Run $\mathcal{A}^{\varphi,\varphi^{-1}}(1^{n})$ to obtain777If the output is
not of this form, simply output $0$ (guess $\varphi$ has no zero pairs). a
pair $(x||0^{n},y||0^{n})$.

  2. 2.

If $\varphi(x||0^{n})=y||0^{n}$, then output $1$ (guess that $\varphi$ has
$\kappa$ zero pairs)

  3. 3.

Otherwise, output $0$ (guess that $\varphi$ has no zero pairs)

If $\mathcal{A}$ makes $T$ queries then $\mathcal{D}$ makes $T+1$ queries, and
the distinguishing advantage of $\mathcal{D}$ is the probability that
$\mathcal{A}$ succeeds given that $\varphi$ has $\kappa$ zero pairs. We have

$\displaystyle\Big{|}\Pr_{\varphi\sim
S_{N}^{\kappa}}[\mathcal{D}^{\varphi,\varphi^{-1}}(1^{n})=1]-\Pr_{\varphi\sim
S_{N}^{0}}[\mathcal{D}^{\varphi,\varphi^{-1}}(1^{n})=1]\Big{|}\,=\,\Pr_{\varphi\sim
S_{N}^{\kappa}}[\mathcal{A}^{\varphi,\varphi^{-1}}(1^{n})].$

Now applying Theorem 4.5, we obtain

$\displaystyle\Pr_{\varphi\sim
S_{N}^{\kappa}}[\mathcal{A}^{\varphi,\varphi^{-1}}(1^{n})]\,\leq\,2(T+1)\sqrt{\frac{\kappa}{2^{n}}}.$

∎

###  4.3 Non-Uniform Double-Sided Search

In this section we define a new variant of Unruh’s original double-sided zero-
search problem [Unr21, Unr23]. Namely, we consider the Double-Sided Search
problem in which the distribution on permutations is _non-uniform_ , and the
constraints on preimages versus images are more flexible. This problem will be
useful for proving the one-wayness of the single-round sponge, which is our
motivation for studying it.

#### Notation.

For the remainder of this section, we fix the following notation:

  * •

$N=2^{n}$ and $r,c>0$ are integers such that $r+c=n$.

  * •

$X=(X_{1},X_{2})$ is a pair of subsets, where $X_{1}\subset\\{0,1\\}^{n}$ is
the set of bitstrings ending in $0^{c}$, $X_{2}\subset\\{0,1\\}^{n}$ is the
set of bitstrings beginning in $0^{r}$.

  * •

$|X_{\varphi}|$ denotes the number of $X$-pairs with respect to a permutation
$\varphi\in S_{N}$.

  * •

$G_{1}$ is the subgroup of $S_{N}$ consisting of permutations which preserve
membership in $X_{1}$, whereas $G_{2}$ is the subgroup of $S_{N}$ which
preserves membership in $X_{2}$

Note that $|X_{1}|\cdot|X_{2}|=N$, and $G_{1},G_{2}$ are both Young subgroups.
In this section, we consider the distribution $\mathcal{D}_{X}$ from
Definition 3.17 which assigns more weight to permutations $\varphi\in S_{N}$
that have a large amount of $X$-pairs. We will occasionally omit the subscript
which specifies $X=(X_{1},X_{2})$, for the pair of subsets $X_{1},X_{2}$, when
it is clear from context.

[Non-uniform Double-Sided Search] Given quantum query access to a permutation
$\varphi:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}$ as well as its inverse
$\varphi^{-1}$, where $\varphi$ is sampled according to the non-uniform
distribution $\mathcal{D}_{X}$ from Definition 3.17, output a pair of strings
$x\in X_{1},y\in X_{2}$ such that $\varphi(x)=y$.

In the remainder of this section, we prove that any algorithm must make at
least $T=\Omega(\sqrt{\epsilon 2^{\min(r,c)}})$ many queries in order to find
an $X$-pair for an $n$-bit permutation sampled from $\mathcal{D}_{X}$ with
probability $\epsilon$. At a high level, the first step of the proof is
showing that there exist worst-case instances on which the problem is hard for
any fixed number of $X$-pairs (see Lemma 4.9). Then, we give a worst-case to
average-case reduction to show hardness for a random permutation with a fixed
number of $X$-pairs in Lemma 4.10. In the below theorem we give a bound for
the general problem using the aforementioned results, as well as tail bounds
on the number of subset pairs derived in Section 3.3.

######  Theorem 4.7.

Any quantum algorithm for Non-uniform Double-Sided Search that makes $T$
queries to an invertible permutation and succeeds with probability
$\epsilon>0$ satisfies

$\epsilon\leq\frac{80(T+1)^{2}}{2^{\min(r,c)}}.$

###### Proof.

Let $\varphi\sim\mathcal{D}_{X}$ be a permutation sampled according to the
distribution $\mathcal{D}_{X}$ from Definition 3.17 and let
$K=|X_{\varphi}|\in\\{0,1,\dots,2^{\min(r,c)}\\}$ be the random variable
corresponding to the number of $X$-pairs in $\varphi$. By the law of total
probability, we can write the success probability of any $T$-query algorithm
as the sum

$\displaystyle\epsilon=$
$\displaystyle\sum_{\kappa=0}^{2^{\min(r,c)}}\Pr[K=\kappa]\cdot\Pr[success|K=\kappa]$
$\displaystyle=$
$\displaystyle\underbrace{\sum_{\kappa=1}^{6}\Pr[K=\kappa]\cdot\Pr[success|K=\kappa]}_{=P_{1}}+\underbrace{\sum_{\kappa=7}^{2^{\min(r,c)}}\Pr[K=\kappa]\cdot\Pr[success|K=\kappa]}_{=P_{2}}.$

We bound each term separately. Beginning with the first, we find

$\displaystyle P_{1}\leq$
$\displaystyle\max_{\kappa\in[6]}\left\\{\Pr[success|K=\kappa]\right\\}$ (By
Convexity) $\displaystyle\leq$
$\displaystyle\frac{48(T+1)^{2}}{2^{\min(r,c)}}.$ (By Lemma 4.10)

Next, continuing with the second term, we get

$\displaystyle P_{2}\leq$
$\displaystyle\sum_{\kappa=7}^{2^{\min(r,c)}}\Pr[success|K=\kappa]\cdot
3\exp(-4\kappa/9)$ (By Theorem 3.20) $\displaystyle\leq$
$\displaystyle\sum_{\kappa=7}^{2^{\min(r,c)}}\frac{24(T+1)^{2}\kappa}{2^{\min(r,c)}}\cdot\exp(-4\kappa/9)$
(By Lemma 4.10) $\displaystyle\leq$
$\displaystyle\frac{32(T+1)^{2}}{2^{\min(r,c)}}.$ (Arithmetico-geometric
series)

This concludes the proof, as we can bound the success probability as

$\displaystyle\epsilon\leq\frac{80(T+1)^{2}}{2^{\min(r,c)}}.$

∎

This bound is tight up to constant factors for any $\epsilon$, as there is at
least a single $X$-pair with $\Omega(1)$ probability (Lemma 3.5), which can be
found using Grover’s algorithm [Gro96] with probability
$\Theta(T^{2}/2^{\min(r,c)})$ after $T$ queries. In particular, we have the
following corollary.

######  Corollary 4.8.

Given quantum oracle-access to an $n$-bit permutation chosen from
$\mathcal{D}_{X}$, the query complexity of outputting an $X$-pair with
probability $\epsilon$ is $\Theta(\sqrt{\epsilon 2^{\min(r,c)}})$.

#### Reduction from worst-case unstructured search.

In the following lemma, we prove a query-lower bound for a worst-case variant
of Non-uniform Double-Sided Search in Section 4.3, where we are given the
promise that the underlying permutation has exactly $K$-many $X$-pairs. We
show the following.

######  Lemma 4.9.

Any $T$-query quantum algorithm for Non-Uniform Double-Sided Search on a
worst-case permutation with exactly $K>0$ many $X$-pairs that succeeds with
probability $\epsilon>0$ must satisfy the inequality

$\epsilon\leq\frac{8(T+1)^{2}K}{2^{\min(r,c)}}.$

###### Proof.

We can reduce Unstructured Search with $K$ out of $2^{\min(r,c)}$ marked
elements to a specific instance of Non-Uniform Double-Sided Search with
respect to a permutation $\varphi$ on $N=2^{n}$ elements and $K$ many $X$
pairs. Moreover, as we will show, our reduction does not incur any query
overhead.

Suppose we are given query access to a function

$f:\\{0,1\\}^{{\min(r,c)}}\rightarrow\\{0,1\\}$

such that $|f^{-1}(1)|=K$. We can construct a permutation
$\varphi:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}$ for
$x\in\\{0,1\\}^{\min(r,c)},y\in\\{0,1\\}^{\max(r,c)}$ as follows, where
$s^{R}$ denotes the reverse of string $s$:

$\varphi(x||y)=\begin{cases}(x||y)^{R}&\text{ if }f(x)=1\\\ (x||y)^{R}\oplus
1^{r}||0^{c}&\text{ if }f(x)=0.\end{cases}$

It is apparent that we can implement a query to $\varphi$ using a single query
to $f$. Moreover, the image $\varphi(x||y)$ always contains $x^{R}$ in the
last $\min(r,c)$ bits, which suffices to determine $f(x)$, and thus to
determine $x||y$ by inverting whichever case was applied. Hence, we can
implement $\varphi^{-1}$ with a single query to $f$. Now let
$x\in\\{0,1\\}^{\min(r,c)},y\in\\{0,1\\}^{\max(r,c)}$ such that $y$ ends in
$0^{c}$ and $\varphi(x||y)$ begins with $0^{r}$. It follows that $f(x)=1$ and
$y=0^{\max(r,c)}$, as otherwise either $y$ does not end in $0^{c}$ or
$\varphi(x||y)$ does not begin with $0^{r}$. Similarly, if for any
$x^{\prime}$ we have $f(x^{\prime})=1$ then $x^{\prime}||0^{\max(r,c)}$ is an
$X$-pair of $\varphi$. Therefore, there are $K$-many $X$-pairs in $\varphi$,
and given an $X$-pair of $\varphi$ it is straight forward to find a preimage
of $1$ under $f$, which can be used to solve Unstructured Search. The claim
now follows from Corollary 2.4. ∎

#### Worst-case to average-case reduction.

In the following lemma, we prove a query-lower bound for an average-case
variant of Non-uniform Double-Sided Search in Section 4.3, where we are given
the promise that the underlying permutation has exactly $K$-many $X$-pairs. In
this case, average refers to a uniform random permutation subject to this
promise. We show the following.

######  Lemma 4.10.

Any $T$-query algorithm for Non-Uniform Double-Sided Search on a random
permutation which has exactly $K>0$ many $X$-pairs that succeeds with
probability $\epsilon>0$ must satisfy the inequality

$\epsilon\leq\frac{8(T+1)^{2}K}{2^{\min(r,c)}}.$

###### Proof.

We can re-randomize any worst-case permutation $\varphi$ with $K$ many
$X$-pairs toward an average-case permutation $\varphi^{\mathrm{sym}}$ with $K$
many $X$-pairs as follows.

  1. 1.

Randomly and independently sample $\omega\sim G_{1},\sigma\sim G_{2}$, where
$\omega$ preserves membership in $X_{1}$ and $\sigma$ preserves membership in
$X_{2}$.

  2. 2.

Define the symmetrized permutation
$\varphi^{\mathrm{sym}}=\omega\circ\varphi\circ\sigma$.

It follows from Lemma 3.12 that $\varphi^{\mathrm{sym}}$ is random among
permutations with $K$ many $X$-pairs. Let $(x,y)\in X_{1}\times X_{2}$ be an
$X$-pair of $\varphi^{\mathrm{sym}}$ such that $\varphi^{\mathrm{sym}}(x)=y$.
Then,

$\displaystyle x^{\prime}=$ $\displaystyle\,\sigma(x),$ $\displaystyle
y^{\prime}=\omega^{-1}(y)$ (18)

which satisfy $x^{\prime}\in X_{1},y^{\prime}\in X_{2}$ and
$\varphi(x^{\prime})=y^{\prime}$. Hence, an $X$-pair of $\varphi$ can be
constructed for free from an $X$-pair of $\varphi^{\mathrm{sym}}$. We can
simulate queries to $\varphi^{\mathrm{sym}}$ as well as its inverse with a
single query to $\varphi,\varphi^{-1}$ respectively, so the reduction incurs
no overhead. Lemma 2.4 now implies the claim. ∎

##  5 One-Wayness of the Sponge Construction

In this section, we prove our main result; namely, the quantum one-wayness of
the single-round sponge when instantiated with invertible random permutations.

#### The sponge construction.

Recall that the sponge construction [Ber+11] uses two main parameters which we
call the _rate_ $r$ and the _capacity_ $c$ of the sponge. The internal state
of the sponge function gets updated through successive applications of a
_block function_ $\varphi:\\{0,1\\}^{r+c}\rightarrow\\{0,1\\}^{r+c}$. Let
$\sigma^{(0)}=(0^{r}||\mathsf{IV})$ denote the initial state of the sponge,
where $\mathsf{IV}\in\\{0,1\\}^{c}$ is some initialization vector; for
simplicity, we consider the choice $\mathsf{IV}=0^{c}$. In the following, we
use the notation $x_{r}\in\\{0,1\\}^{r}$ and $x_{c}\in\\{0,1\\}^{c}$ to denote
the first $r$ bits as well as the last $c$ bits of $x\in\\{0,1\\}^{r+c}$,
respectively.

The sponge hash function
$\mathsf{Sp}^{\varphi}:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{r}$ is evaluated as
follows on a sequence of $r$-bit blocks $m=(m_{1},\dots,m_{\ell})$:

  * •

(Absorption phase) for $i\in[\ell]$, update the state by computing

$\sigma^{(i)}=\varphi\big{(}(\sigma^{(i-1)}_{r}\oplus
m_{i})||\sigma^{(i-1)}_{c}\big{)}.$

  * •

(Squeezing phase) parse the final state $\sigma^{(\ell)}$ as
$(\sigma_{r}^{(\ell)},\sigma_{c}^{(\ell)})\in\\{0,1\\}^{r}\times\\{0,1\\}^{c}$,
and output the digest
$\mathsf{Sp}^{\varphi}(m_{1},\dots,m_{\ell})=\sigma_{r}^{(\ell)}$ consisting
of the first $r$ bits of $\sigma^{(\ell)}$.

We remark that the sponge construction also allows for variable-length output
by essentially running the absorption phase in reverse [Ber+11]; we choose to
ignore this option for simplicity as we only focus on single-round sponge
hashing.

#### One-wayness of the single-round sponge.

Recall that, in the special case when there is only a single round of
absorption, the sponge function
$\mathsf{Sp}^{\varphi}:\\{0,1\\}^{r}\rightarrow\\{0,1\\}^{r}$ takes on a
simple form; namely, on input $x\in\\{0,1\\}^{r}$, the output is given by the
string $y=\mathsf{Sp}^{\varphi}(x)$, where $y$ corresponds to the first $r$
bits of $\varphi(x||0^{c})$.

We now answer the following question on the one-wayness of the single-round
sponge; namely, how many queries does a quantum algorithm
$\mathcal{A}^{\varphi,\varphi^{-1}}$ need to invert $\mathsf{Sp}^{\varphi}$ on
a randomly chosen input, when $\varphi$ is an invertible random permutation?

Let us first define the one-wayness experiment in full generality. Note that
the sponge function $\mathsf{Sp}^{\varphi}$ depends on $\varphi$, which in
turn is modeled as a uniformly random permutation which we have oracle access
to. Therefore, we need to consider a variant of one-wayness which is
parameterized by an ensemble of oracle functions.

######  Definition 5.1 (One-wayness).

Let $\lambda\in\mathbb{N}$ be the security parameter and let
$\mathcal{O}=\\{\mathcal{O}_{\lambda}\\}$ be an ensemble of oracle functions.
A function family

$\mathcal{H}^{\mathcal{O}}=\Big{\\{}\\{h^{O}:\\{0,1\\}^{m(\lambda)}\rightarrow\\{0,1\\}^{n(\lambda)}\\}_{O\in\mathcal{O}_{\lambda}}\Big{\\}}_{\lambda\in\mathbb{N}}$

is called one-way if $(i)$ there exists a polynomial-time algorithm
$\mathcal{M}^{O}(1^{\lambda})$ that efficiently computes $h^{O}$ with oracle
access to $O$ and $(ii)$, for any efficient quantum algorithm $\mathcal{A}$,
it holds

$\underset{\begin{subarray}{c}x\sim\\{0,1\\}^{m}\\\
O\sim\mathcal{O}_{\lambda}\end{subarray}}{\Pr}\Big{[}h^{O}(x)=h^{O}(x^{\prime})\,:\,x^{\prime}\leftarrow\mathcal{A}^{O}(1^{\lambda},h^{O}(x))\Big{]}\leq\operatorname{negl}(\lambda).$

We now prove a lower bound for single-round sponge hashing, where $\ell=1$ and
the block function $\varphi:\\{0,1\\}^{r+c}\rightarrow\\{0,1\\}^{r+c}$ is an
invertible random permutation. Specifically, we show that any algorithm must
make at least $T=\Omega(\sqrt{\epsilon 2^{\min(r,c)}})$ many queries in order
to find a pre-image of a randomly chosen image with probability $\epsilon$.

######  Theorem 5.2.

Let $n=r+c$ and $N=2^{n}$. Suppose that a quantum algorithm $\mathcal{A}$
breaks the one-wayness of the single-round Sponge
$\mathsf{Sp}^{\varphi}:\\{0,1\\}^{r}\rightarrow\\{0,1\\}^{r}$ with probability

$\underset{\begin{subarray}{c}x\sim\\{0,1\\}^{r}\\\ \varphi\sim
S_{N}\end{subarray}}{\Pr}\Big{[}\mathsf{Sp}^{\varphi}(x)=\mathsf{Sp}^{\varphi}(x^{\prime})\,:\,x^{\prime}\leftarrow\mathcal{A}^{\varphi,\varphi^{-1}}(1^{n},\mathsf{Sp}^{\varphi}(x))\Big{]}=\epsilon.$

Then, if $\mathcal{A}$ makes a total amount of $T$ quantum queries to
$\varphi,\varphi^{-1}$, it satisfies the inequality

$\epsilon\leq\frac{80(T+1)^{2}}{2^{\min(r,c)}}.$

###### Proof.

Suppose that a quantum algorithm $\mathcal{A}$ breaks the one-wayness of the
single-round sponge hash function
$\mathsf{Sp}^{\varphi}:\\{0,1\\}^{r}\rightarrow\\{0,1\\}^{r}$ with probability
$\epsilon>0$. We reduce from the problem of Non-uniform Double-Sided Search in
Section 4.3. Let $X=(X_{1},X_{2})$ be a pair of subsets, where
$X_{1}\subset\\{0,1\\}^{n}$ denotes the set of bitstrings ending in $0^{c}$
and $X_{2}\subset\\{0,1\\}^{n}$ denotes the set of bitstrings beginning in
$0^{r}$.

Consider the following reduction $\mathcal{B}^{\pi,\pi^{-1}}(1^{n})$ which
receives quantum query access to a random permutation
$\pi:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}$ chosen from $\mathcal{D}_{X}$
(Definition 3.17) as well as its inverse $\pi^{-1}$.

  1. 1.

$\mathcal{B}$ samples a random $y\sim\\{0,1\\}^{r}$.

  2. 2.

$\mathcal{B}$ runs $\mathcal{A}^{\varphi,\varphi^{-1}}(1^{n},y)$ to get
$x^{\prime}\in\\{0,1\\}^{r}$; whenever $\mathcal{A}$ makes a query to either
$\varphi$ or $\varphi^{-1}$, the reduction $\mathcal{B}$ answers with either
$O_{\varphi}$ or $O_{\varphi^{-1}}$, where $\varphi$ is the permutation

$\varphi:=\mathsf{XOR}_{y||0^{c}}\circ\pi$

with $\mathsf{XOR}_{(y||0^{c})}(a||b)=(a\oplus y)||b$ for $a\in\\{0,1\\}^{r}$
and $b\in\\{0,1\\}^{c}$.

  3. 3.

$\mathcal{B}$ computes
$\varphi(x^{\prime}||0^{c})=y_{x^{\prime}}||z_{x^{\prime}}$ using a single
query to $O_{\pi}$, and outputs the pair $(x^{\prime}||0^{c})$ and
$(0^{r}||z_{x^{\prime}})$.

By Lemma 5.3, we know $\mathcal{A}$ sees an instance $(\varphi,y)$ drawn from
the proper one-way game distribution. Note that whenever
$\mathcal{A}^{\varphi,\varphi^{-1}}(1^{n},y)$ succeeds at breaking one-wayness
with respect to $\mathsf{Sp}^{\varphi}$, it holds that $y_{x^{\prime}}=y$, and
thus $\varphi(x^{\prime}||0^{c})=y||z_{x^{\prime}}$. But then the output
$(x^{\prime}||0^{c})$ and $(0^{r}||z_{x^{\prime}})$ of the reduction
$\mathcal{B}$ forms an $X$-pair of $\pi$, since

$\displaystyle\pi(x^{\prime}||0^{c})$
$\displaystyle=\mathsf{XOR}_{(y||0^{c})}(\varphi(x^{\prime}||0^{c}))$
$\displaystyle=\mathsf{XOR}_{(y||0^{c})}(y||z_{x^{\prime}})$
$\displaystyle=0^{r}||z_{x^{\prime}}.$

The lower bound now follows from Theorem 4.7. ∎

Next, we prove the following technical lemma which we require for our main
result. Here, we denote by $\mathcal{D}_{X}$ the non-uniform distribution from
Definition 3.17.

######  Lemma 5.3.

Let $n=r+c$ for $r,c\in\mathbb{N}$ and $N=2^{r+c}$. Let $X=(X_{1},X_{2})$,
where $X_{1}\subset\\{0,1\\}^{n}$ denotes the set of bitstrings ending in
$0^{c}$ and $X_{2}\subset\\{0,1\\}^{n}$ denotes the set of bitstrings
beginning in $0^{r}$. Consider the following two distributions:

$\displaystyle\underline{\text{Distribution $\mathcal{D}_{1}$}:}$
$\displaystyle\underline{\text{Distribution $\mathcal{D}_{2}$}:}$
$\displaystyle 1.\,\,\text{Sample $\varphi\sim S_{N}$;}$ $\displaystyle
1.\,\text{Sample $y\sim\\{0,1\\}^{r}$;}$ $\displaystyle 2.\,\,\text{Sample
$x\sim\\{0,1\\}^{r}$;}$ $\displaystyle 2.\,\text{Sample
$\pi\sim\mathcal{D}_{X}$ with}$ $\displaystyle 3.\,\,\text{Let
$y=\mathsf{Sp}^{\varphi}(x)$;}$
$\displaystyle\quad\underset{\Pi\sim\mathcal{D}_{X}}{\Pr}[\Pi=\pi]=|X_{\pi}|/\sum_{\,\sigma\in
S_{N}}|X_{\sigma}|\,;$ $\displaystyle 4.\,\,\text{Output $(\varphi,y)$.}$
$\displaystyle 3.\,\,\text{Output $(\varphi,y)$ with
$\varphi=\mathsf{XOR}_{(y||0^{c})}\circ\pi$.}$

Then, the distributions $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ are identical.

###### Proof.

To show that the distributions $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ are
identical, it suffices to show that each pair $(\varphi,y)\in
S_{N}\times\\{0,1\\}^{r}$ is equally likely to occur under both
$\mathcal{D}_{1}$ and $\mathcal{D}_{2}$.

First, we consider the probability that $(\varphi,y)$ occur under
$\mathcal{D}_{1}$. Thus,

$\displaystyle\Pr_{(\Phi,Y)\sim\mathcal{D}_{1}}[(\Phi,Y)=(\varphi,y)]=$
$\displaystyle\Pr[\Phi=\varphi]\cdot\Pr[Y=y|\Phi=\varphi]$ $\displaystyle=$
$\displaystyle\frac{1}{N!}\cdot\frac{|\\{x\in\\{0,1\\}^{r}\,:\,\mathsf{Sp}^{\varphi}(x)=y\\}|}{2^{c}}.$

Next, we consider the probability that $(\varphi,y)$ occurs under
$\mathcal{D}_{2}$. We find that

$\displaystyle\Pr_{(\Phi,Y)\sim\mathcal{D}_{2}}[(\Phi,Y)=(\varphi,y)]=\Pr[Y=y]\cdot\Pr[\Phi=\varphi|Y=y]$
$\displaystyle=\frac{1}{2^{c}}\cdot\frac{|\\{x\in\\{0,1\\}^{r}\,:\,\mathsf{Sp}^{\pi}(x)=0^{r}\text{
and }\varphi=\mathsf{XOR}_{(y||0^{c})}\circ\pi,\,\text{ for }\,\pi\in
S_{N}\\}|}{\sum_{\sigma\in
S_{N}}|\\{x\in\\{0,1\\}^{r}\,:\,\mathsf{Sp}^{\sigma}(x)=0^{r},\,\text{ for
}\,\sigma\in S_{N}\\}|}.$

Note that since $|X_{1}|\cdot|X_{2}|=N$, we can invoke Theorem 3.13 to show
that there is precisely one $X$-pair on average over the uniform choice over
$S_{N}$. But since there are $N!$ such permutations the total number of $X$
pairs must be $N!$. Thus,

$N!=\sum_{\sigma\in
S_{N}}|\\{x\in\\{0,1\\}^{r}\,:\,\mathsf{Sp}^{\sigma}(x)=0^{r},\,\text{ for
}\,\sigma\in S_{N}\\}|.$

Moreover, because the permutation $\pi$ is uniquely defined by the permutation
$\varphi$ and the image $y$, it is also easy to see that

$\displaystyle|\\{x\in\\{0,1\\}^{r}\,:\,\mathsf{Sp}^{\pi}(x)=0^{r}\text{ and
}\varphi=\mathsf{XOR}_{(y||0^{c})}\circ\pi,\,\text{ for }\,\pi\in S_{N}\\}|$
$\displaystyle=|\\{x\in\\{0,1\\}^{r}\,:\,\mathsf{Sp}^{\varphi}(x)=y\\}|.$

Putting everything together, it follows that

$\displaystyle\Pr_{(\Phi,Y)\sim\mathcal{D}_{2}}[(\Phi,Y)=(\varphi,y)]=\frac{1}{N!}\cdot\frac{|\\{x\in\\{0,1\\}^{r}\,:\,\mathsf{Sp}^{\varphi}(x)=y\\}|}{2^{c}}.$

This completes the proof. ∎

## References

  * [Hoe63] Wassily Hoeffding  “Probability Inequalities for Sums of Bounded Random Variables”  In _Journal of the American Statistical Association_ 58.301 [American Statistical Association, Taylor & Francis, Ltd.], 1963, pp. 13–30  URL: http://www.jstor.org/stable/2282952
  * [Chv79] V. Chvatal  “The tail of the hypergeometric distribution”  In _Discrete Mathematics_ 25.3, 1979, pp. 285–287  DOI: https://doi.org/10.1016/0012-365X(79)90084-0
  * [Jam84] James  “The Representation Theory of the Symmetric Group”, Encyclopedia of Mathematics and its Applications  Cambridge University Press, 1984
  * [Dam87] Ivan Damgård  “Collision Free Hash Functions and Public Key Signature Schemes”  In _Advances in Cryptology - EUROCRYPT ’87, Workshop on the Theory and Application of of Cryptographic Techniques, Amsterdam, The Netherlands, April 13-15, 1987, Proceedings_ 304, Lecture Notes in Computer Science  Springer, 1987, pp. 203–216  DOI: 10.1007/3-540-39118-5_19
  * [Mer88] Ralph C. Merkle  “A Digital Signature Based on a Conventional Encryption Function”  In _Advances in Cryptology — CRYPTO ’87_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1988, pp. 369–378
  * [Mer90] Ralph C. Merkle  “A Certified Digital Signature”  In _Advances in Cryptology — CRYPTO’ 89 Proceedings_ New York, NY: Springer New York, 1990, pp. 218–238
  * [Gro96] Lov K. Grover  “A fast quantum mechanical algorithm for database search”  In _Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’96  Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, pp. 212–219  DOI: 10.1145/237814.237866
  * [Jon96] Andrew R. Jones  “A Combinatorial Approach to the Double Cosets of the Symmetric Group with respect to Young Subgroups”  In _European Journal of Combinatorics_ 17.7, 1996, pp. 647–655  DOI: https://doi.org/10.1006/eujc.1996.0056
  * [Ben+97] Charles H. Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani  “Strengths and Weaknesses of Quantum Computing”  In _SIAM Journal on Computing_ 26.5 Society for Industrial & Applied Mathematics (SIAM), 1997, pp. 1510–1523  DOI: 10.1137/s0097539796300933
  * [Sho97] Peter W. Shor  “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”  In _SIAM Journal on Computing_ 26.5 Society for Industrial & Applied Mathematics (SIAM), 1997, pp. 1484–1509  DOI: 10.1137/s0097539795293172
  * [Boy+98] Michel Boyer, Gilles Brassard, Peter Høyer and Alain Tapp  “Tight Bounds on Quantum Searching”  In _Fortschritte der Physik_ 46.4–5 Wiley, 1998, pp. 493–505  DOI: 10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p
  * [Zal99] Christof Zalka  “Grover’s quantum searching algorithm is optimal”  In _Phys. Rev. A_ 60 American Physical Society, 1999, pp. 2746–2751  DOI: 10.1103/PhysRevA.60.2746
  * [Bea+01] Robert Beals et al.  “Quantum lower bounds by polynomials”  In _J. ACM_ 48.4 New York, NY, USA: Association for Computing Machinery, 2001, pp. 778–797  DOI: 10.1145/502090.502097
  * [Amb02] Andris Ambainis  “Quantum Lower Bounds by Quantum Arguments”  In _Journal of Computer and System Sciences_ 64.4, 2002, pp. 750–767  DOI: https://doi.org/10.1006/jcss.2002.1826
  * [Ber+08] Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche  “On the Indifferentiability of the Sponge Construction”  In _Advances in Cryptology – EUROCRYPT 2008_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 181–197
  * [DH09] Cătălin Dohotaru and Peter Høyer  “Exact Quantum Lower Bound for Grover’s Problem”  In _Quantum Info. Comput._ 9.5 Paramus, NJ: Rinton Press, Incorporated, 2009, pp. 533–540
  * [Amb+11] Andris Ambainis, Loïck Magnin, Martin Roetteler and Jeremie Roland  “Symmetry-Assisted Adversaries for Quantum State Generation”  In _2011 IEEE 26th Annual Conference on Computational Complexity_ IEEE, 2011  DOI: 10.1109/ccc.2011.24
  * [Ber+11] G. Bertoni, J. Daemen, M. Peeters and G. Assche  “Cryptographic sponge functions”, Submission to NIST (Round 3), 2011  URL: http://sponge.noekeon.org/CSF-0.1.pdf
  * [Ber+11a] G. Bertoni, J. Daemen, M. Peeters and G. Assche  “The Keccak SHA-3 submission”, Submission to NIST (Round 3), 2011  URL: http://keccak.noekeon.org/Keccak-submission-3.pdf
  * [Bon+11] Dan Boneh et al.  “Random Oracles in a Quantum World”  In _Advances in Cryptology – ASIACRYPT 2011_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 41–69
  * [KL14] Jonathan Katz and Yehuda Lindell  “Introduction to Modern Cryptography, Second Edition”  Chapman & Hall/CRC, 2014
  * [Cza+17] Jan Czajkowski et al.  “Post-quantum security of the sponge construction” https://eprint.iacr.org/2017/771, Cryptology ePrint Archive, Paper 2017/771, 2017  URL: https://eprint.iacr.org/2017/771
  * [AHU18] Andris Ambainis, Mike Hamburg and Dominique Unruh  “Quantum security proofs using semi-classical oracles” https://eprint.iacr.org/2018/904, Cryptology ePrint Archive, Paper 2018/904, 2018  URL: https://eprint.iacr.org/2018/904
  * [Zha18] Mark Zhandry  “How to Record Quantum Queries, and Applications to Quantum Indifferentiability” https://eprint.iacr.org/2018/276, Cryptology ePrint Archive, Paper 2018/276, 2018  URL: https://eprint.iacr.org/2018/276
  * [Cza+19] Jan Czajkowski, Christian Majenz, Christian Schaffner and Sebastian Zur  “Quantum Lazy Sampling and Game-Playing Proofs for Quantum Indifferentiability” https://eprint.iacr.org/2019/428, Cryptology ePrint Archive, Paper 2019/428, 2019  URL: https://eprint.iacr.org/2019/428
  * [Ala+20] Gorjan Alagic, Stacey Jeffery, Maris Ozols and Alexander Poremba  “On Quantum Chosen-Ciphertext Attacks and Learning with Errors”  In _Cryptography_ 4.1, 2020  DOI: 10.3390/cryptography4010010
  * [Unr21] Dominique Unruh  “Compressed Permutation Oracles (And the Collision-Resistance of Sponge/SHA3)” https://eprint.iacr.org/2021/062, Cryptology ePrint Archive, Paper 2021/062, 2021  URL: https://eprint.iacr.org/2021/062
  * [Ala+22] Gorjan Alagic, Chen Bai, Jonathan Katz and Christian Majenz  “Post-Quantum Security of the Even-Mansour Cipher”  In _Advances in Cryptology – EUROCRYPT 2022_ Cham: Springer International Publishing, 2022, pp. 458–487
  * [FGK22] Cody Freitag, Ashrujit Ghoshal and Ilan Komargodski  “Time-Space Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions”  In _Advances in Cryptology – CRYPTO 2022_ Cham: Springer Nature Switzerland, 2022, pp. 131–160
  * [Ros22] Ansis Rosmanis  “Tight Bounds for Inverting Permutations via Compressed Oracle Arguments”, 2022  arXiv:2103.08975 [quant-ph]
  * [Aks+23] Akshima, Xiaoqi Duan, Siyao Guo and Qipeng Liu  “On Time-Space Lower Bounds for Finding Short Collisions in Sponge Hash Functions”  In _Theory of Cryptography: 21st International Conference, TCC 2023, Taipei, Taiwan, November 29–December 2, 2023, Proceedings, Part III_ Taipei, Taiwan: Springer-Verlag, 2023, pp. 237–270  DOI: 10.1007/978-3-031-48621-0_9
  * [Ala+23] Gorjan Alagic, Chen Bai, Alexander Poremba and Kaiyan Shi  “On the Two-sided Permutation Inversion Problem”, 2023  arXiv:2306.13729 [quant-ph]
  * [Unr23] Dominique Unruh  “Towards Compressed Permutation Oracles”  In _Advances in Cryptology – ASIACRYPT 2023: 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4–8, 2023, Proceedings, Part IV_ Guangzhou, China: Springer-Verlag, 2023, pp. 369–400  DOI: 10.1007/978-981-99-8730-6_12
  * [Reg24] Oded Regev  “An Efficient Quantum Factoring Algorithm”, 2024  arXiv:2308.06572 [quant-ph]
  * [Wil] Mark Wildon  “A Model for the Double Cosets of Young Subgroups”, Royal Holloway, University of London  URL: https://www.ma.rhul.ac.uk/~uvah099/Maths/doubleRevised2.pdf