This is a long due note concerning constructing **quantum-secure
pseudorandom permutations** (QPRP), a problem that has made my
collaborators
(Andrew Childs, Shih-Han Hung, Zhengfeng Ji) and
myself excited as well as disappointed a couple of times over the past
few years. In a way this makes it a perfect fit for the debut post of
this blog.

A while ago, Mark Zhandry observed in a note that
some existing constructions are immediately quantum-secure for simple
reasons, hence confirming the *existence* of QPRPs. This post aims to:

- give another simple observation that shows the
*existence*of QPRP. This is in fact an observation we had a long time ago, but probably only heard by a few colleagues over drinks. - give a plain summary of Zhandry’s observation and discuss its connection to our observation and other thoughts.
- more importantly, depict the current status and the big questions
that remain
**unclear**about QPRP, beyond its mere*existence*. By sharing our (mostly failed) experience so far on approaching these problems, we would love to see more people bringing in new ideas.

The full article may be long and a bit technical. I will start with a dense summary assuming you already know the context. Then I will walk through the whole story, including the basic concepts of PRPs and the challenges of getting quantum-secure PRPs.

# Executive summary (assuming you know the context)

Informally speaking, a pesudorandom permutation is a permutation that
is *indistinguishable* from a truly random permutation, agaisnt any
poly-time algorithm that has oracle-access to the given
permutation. The majority of classically secure constructions plugs a
pseudorandom function into variants of a Feistel
network. They are **quantum-secure** if indistinguishability still
holds against efficient quantum algorithms that can
issue quantum superposition queries to the oracles. This makes
proving quantum security difficult, and some classically-secure
constructions actually get broken (e.g. 3-round
Luby-Rackoff balanced Feistel). Nonetheless, there are sufficient
conditions for quantum security as identified by us and Zhandry, and
as a result, we are safe to say that quantum-secure PRPs do *exist*
(based on proper computational assumptions, e.g., existence of
quantum-secure PRFs).

**Our observation**: basically we may view the Feistel construction as a random walk on the permutation group, and if this walk mixes rapidly, then it implies quantum indistinguishability. Maximally unbalanced Feistel (a.k.a. Thorp Shuffle) is such an instance.**Zhandry’s observation**: the essence of Zhandry’s observation is that if classical indistinguishability holds to the extreme, namely against a distinguisher that queries the entire domain (hence learning the entire permutation), then it remains quantum-secure. This sounds a very stringent condition, but classical cryptographers have actually been quite successful along this line called*full security*. Several examples are known (e.g., Mix-&-Cut and Sometimes-recurse).**What else**? The two observations are both strong conditions that are sufficient for quantum security. We note that the rapid-mixing condition is even stronger (i.e., it implies full security). Although we do not need to worry about the existence of quantum-secure PRPs any more, it is irritating that we are still not sure how to prove quantum security of the famous Luby-Rackoff construction. In fact we do not even know if it is secure at all no matter how many rounds we employ, though personally I’m positive that it must be. More importantly, current existing examples are very inefficient (compared to classical security with just constant rounds). Can we find more efficient quantum-secure PRPs?

Now the full story is at table.

# PRPs and quantum security

If you have heard about DES/AES, or more generally *block ciphers*,
you are already on board with *pesudorandom permutations* (PRP), which
are just theoretical abstractions of secure block ciphers. Before
digging into more specifics, let me just mention that PRPs are a
fundamental primitive in modern cryptography, and likewise block
ciphers are the workhorse in practical cryptosystems.

## What is a PRP?

Roughly speaking, a PRP is a permutation that is *indistinguishable*
from a **truly random permutation** as far as any efficient observers
are concerned when the permutations are given as a *black-box*. More
precisely, let us work with the set \( X = \{0,1\}^{2n}\), and let
\(\Pi = \{\pi \}\) be the collection of permutations on \(X\),
i.e. the symmetric group $S_X$. Then we consider a family of
permutations $\{E_k\} _{k \in \mathcal{K}} \subseteq \Pi $ indexed
by keys in a keyspace $\mathcal{K}$.

At the heart of the definition is a **distinguisher** $A$, which is an
algorithm that is given *oracle*-access to a primitive $f$. It asks
queries to $f$ and output one bit in the end, and is usually denoted
$A^f$. Now consider the difference in the probabilities that a
distinguisher $A$ outputs 1 after making $q$ queries in two cases:

$$\epsilon(q,\lambda) :=| \Pr_{k\gets \mathcal{K}} [A^{E_k, E_k^{-1} }() = 1] - \Pr_{\pi \gets \Pi} [A^{\pi,\pi^{-1} }() = 1] | \, .$$

- $A$ has access to $E_k$ and its inverse $E_k^{-1}$ for a random key $k\gets \mathcal{K}$.
- $A$ has access to $\pi$ and its inverse $\pi^{-1}$ for a
*truly random permutation*$\pi \gets \Pi$.

This difference $\epsilon(q,n)$ is usually dubbed the distinguishing
**advantage**. Then a PRP is family $\{E_k\}$ so that the advantage
$\epsilon(q,n)$ is tiny (i.e., decreases faster than any inverse
polynomial in $n$) for any $A$ making $q = poly(n)$ queries (and
running in $poly(n)$ time). This is sometimes called a *strong* PRP in
the sense that both the permutation and its inverse is available to a
distinguisher. If only the forward permutation is allowed, we call the
resulting family a standard PRP. In this post, a PRP means a strong
one unless otherwise specified.

If we consider more generally function families rather than just
permutations, we obtain a similar notion called *pseudorandom
functions* (PRFs), which are a family of keyed-functions that are
indistinguishable from a *truly random function*.

## How to construct PRPs?

Both theoretical and practical constructions are based on the idea of
*iteration*, where a basic module is iterated with fresh randomness or
different sub-keys. The famous construction in theory is due
to Luby&Rackoff based on the elegant design of
the Feistel network. $\Xi_f$ converts a function $f:
\{0,1\}^{n} \to \{0,1\}^{n}$ into a permutation on
$\{0,1\}^{2n}$ by the simple rule:

$$\Xi_f(x_L,x_R) = (y_L,y_R): y_L = x_R, y_R = x_L\oplus f(x_R)\, . $$

If we iterate the basic unit $r$ times, we get the $r$-round Feistel
network $\Xi_{f_1,\ldots,f_r}$, and each $f_i$ is called a *round*
function. Luby and Rackoff proved that 3-round Feistel is a standard
PRP, and 4-round is a (strong) PRP, when each of the round function is
a PRP with independent random keys. Then by a beautiful series of
results, we know the existence of **one-way functions**, functions
that are easy to compute but hard to invert **on-average**, would
imply pseudorandom generators (PRGs), which suffice for PRFs, and
ultimately give rise to PRPs.

one-way functions –[HILL]–> PRGs –[GMM]–> PRFs –[LubyRackoff]–> PPRs

The gist of Luby&Rackoff’s proof, which is inherent in all most all analyses, goes in two steps

1) Substituting independently truly random functions for PRFs in every round. This is legit by a straightforward hybrid argument.

2) Proving **information-theoretically** that the resulting network is
indistinguishable from a truly random permutaion. For example, the
4-round Feistel is shown to be secure up to $\sim \sqrt{2^{2n}}$ queries
against any, possibly **computationally** unbounded, distinguishers.

There are various followups and modern constructions (e.g., this and this). Essentially all analysis proceeds in this way, and a lot of efforts have been on improving the information-theoretical bound in step 2).

## What about quantum security?

Everything sounds sweat so far. But the new player
of quantum computers will totally change the landscape. You may
have heard about Shor’s ground breaking poly-time quantum algorithm
for factorization, which will smash down almost the entire
security infrastructure on the Internet. In current setting, the issue
comes from the unique feature of quantum **superposition**. For a
**quantum** distinguisher, we need to consider “superposed” queries:

$$\sum_{x\in X}\alpha_x |x,0\rangle \stackrel{f}{\mapsto} \sum_{x \in X} \alpha_x |x, f(x)\rangle \, .$$

We call a PRP **quantum-secure** (QPRP), if it remains
indistinguishable against any efficient quantum distinguishers that
are equipped with quantum superposition access to the given
permutations.

To be clear, although it seems that in one quantum query, all function
values of $f$ is “contained” in the response state, the only way that
$A$ can read them out is by a quantum measurement, which will reveal
one $f(x)$ and then collapse the state. Therefore, it is not that a
quantum distinguisher can effortlessly learn $f$ entirely. Rather, the
real difficult is that the proof and analysis we had for classical
distinguishers may not **make sense** anymore. More specifically, if
we look at the two-step proof of Luby&Rackoff:

1’) OK, if we use **quantum-secure** PRFs, which exist assuming
**quantum-secure** one-way functions as shown
by Zhandry12.

2’) The classical *information-theoretical* analysis becomes
completely inapplicable. In essence, the analysis goes by defining
“bad events” in the probability space, which captures the possibility
of seeing a difference in the case of the Feistel construction or a
truly random permutation. Bounding the probability of these “bad
events” thus bounds the distinguishing advantage too. However, there
is no (or rather we do not know) sensible counterpart of such “bad
events” when dealing with quantum distinguishers. This is where the
challenge goes wild, mainly due to our lacking of tools in reasoning
about quantum attackers.

### 3-round Feistel broken

To make things worse, it was shown that 3-round Feistel is
**broken** by quantum distinguishers using Simon’s algorithm, the
inspiration of Shor’s algorithm. While this attack does not seem to
generalize to 4 rounds, we did not know if 4-round Feistel is
quantum-secure (even in the standard sense i.e., without inverse
permutations), or how many rounds will make it quantum-secure if any
at all. In fact, whether there exists a QPRP, by any possible
construction under reasonable assumptions, was in doubt.

# Existence of QPRPs

That was the status when we (Andrew Childs, Zhengfeng Ji
and myself, all at IQC then) started thinking about this
problem. We were optimistic and decided to salvage the Luby-Rackoff
proof against quantum attacks. Out of various attempts, one approach
based on rapid mixing of random walks seemed promising and left with
us an observation that shows the *existence* of QPRP, which we thought
insignificant back then (early 2014). None of us had imagined that it
was till last summer (2016) that we resumed on this hanging problem,
with a fresh mind joining force - Shih-Han Hung, Andrew’s Ph.D
student at UMD. We realized a few months later that the mixing
approach would very likely fail on Balanced Feistel based on a
counting argument. Let me come back to this later, and let good news
come first.

## Our observation: quantum PRPs exist based on Rapid Mixing

What we observed in early 2014 was that at least *existence* of QPRPs
should not bother us anymore. Basically one can view any iterated
construction (e.g. $\Xi_{f_1,\ldots, f_r}$) as an $r$-step random
walk on the symmetric group $S_X$. Namely we start from the identity
permutation, and then the random choice of round function $f_i$
determines the transition at each step. Suppose that the walk has
uniform stationary distribution and it converges up to
statistical error $\delta$ within $r$ steps. This will imply that the
resulting permutation $\Xi_{f_1,\ldots, f_r}$ is the *same* as
drawing a truly random permutation, except with error at most
$\delta$. Therefore, **information-theoretically**, no adversary
(classical nor quantum) can tell a difference regardless of the number
of queries and how much time s/he spends on it. This still holds if
both $\pi$ and $\pi^{-1}$ are given to the adversary. This would
justify step 2) against quantum distinguishers. Everything here can be
made formal. This idea is not new at all (e.g., Morris08).

By László Németh - CC0, Link

Next, as said earlier, one can replace truly random functions by
quantum-secure PRFs in step 1), and this results in permutations that
are indistinguishable from a truly random permutation against
*poly-time* quantum adversaries making *poly*-many queries.

The question then becomes, do we have constructions that mix over
$S_X$ rapidly? Luckily a variation on LubyRackoff construction called
the **maximally-unbalanced** Feistel (Max-UBF), which corresponds
to Thorp shuffle in the study of card shuffling, has been
shown to **mix rapidly to uniform**. Instead of evenly divide the
input string into two halves in the Luby-Rackoff construction, which we
may call **Balanced Feistel** (BF) hereafter, Max-UBF applies random
round function $f_i:\{0,1\}^{2n-1} \to \{0,1\}$ on all but the
first bit and XOR the one-bit output to the first bit of input. Namely
one-round Max-UBF goes as follows:

$$ (x_1,x_{2,\ldots,2n}) \mapsto (x_{2,\ldots, 2n}, f(x_{2,\ldots, 2n})\oplus x_1) \, . $$

Therefore, we have

Theorem. Assuming existence of quantum-secure one-way functions, there exist quantum-secure pseudorandom permutations.

This is all too easy, isn’t it? We thought so too back then, and were reluctant to write it up. What we wanted to answer is:

does LubyRackoff construction (Balanced Feistel) also mix rapidly?

Searching its answer ended up in the negative message found by Shih-Han. But again, let me defer it till later.

### A word of caution

The idea of random walk is very natural, so natural as we sometimes fail to recognize what “walk” we are indeed taking. We stress that we are considering a random walk over the permutations (each node is a permutation and the edge connects nodes that are achievable by composing one-round Feistel with some round function $f$).

In contrast, one may also consider a walk over the **strings**
$\{0,1\}^{2n}$. Namely take an input string $x$, it will get
permuted to a new string $ x^{\prime}$ after sending it through the
Feistel network. We can analyze how fast, if it does, the string
becomes **uniformly** distributed. In cryptographic terms, this shows
(standard, w.o. inverse permutation) indistinguishability against a
single-query, **non-adaptive** (i.e., query $x$ determined in advance)
distinguisher. We can generalize this idea to analyze how a $q$-tuple
$(x_1,\ldots,x_q)$ evolves, and this would establish $q$-query,
non-adaptive security. Indeed, this is the approach many of the
classical works on PRPs take, and this walk on strings is sometimes
called *projective* walks. It is often easier to analyze than the walk
on the symmetric group. Classical cryptographers are also blessed that
non-adaptive security can be easily amplified by various
forms of composition to achieve stronger security (e.g., adaptive,
strong PRP).

That said, the $q$-*projective* walk on strings is not totally
unrelated to the walk on the symmetric group. Note that when $q$ is as
big as the entire domain size, these two walks will indeed
coincide. This is not super helpful though, since classical results
are not ususally so strong. But they do exist, and this is exactly
leading us to Zhandry’s observation.

## Zhandry’s observation: fully-secure PRPs are quantum-secure

In a recent note by Zhandry, he noticed another
**sufficient** condition that can make a classically secure PRP also
quantum-secure. He called the constructions satisfying this property a
*full-domain Function-to-Permutation Converter* (FD-FPC). He then
observed that some classical constructions are indeed FD-FPCs
(e.g., Mix-&-Cut and Sometimes-recurse shuffles in the
design of format-preserving encryption). Then similarly once the
random functions in FD-FPCs are replaced by quantum-secure PRFs, one
gets quantum-secure PRPs.

The formal definition and analysis in Zhandry’s note are somehow
technical and not so easy to grasp. But the key idea is extremely
simple. FD-FPC is essentially a notion called *full security* in the
study of format-preserving encryption. Basically it requires that even
if the distinguisher queires the **entire domain** of a given oracle
$\sigma$ drawn according to some distribution, a distinguisher still
cannot tell it apart from a truly random permutation. Clearly such a
distinguisher can completely reconstruct the permutation $\sigma$, and
hence quantum superposition queries do not add any power. Therefore
quantum-secure follows trivially.

## Reflection on the existence of QPRPs

Well, both observations indicate that *existence* of QPRPs is in fact
easy to attain, given the hard work in the literature. Let’s
reflect on them a bit, before we ask what’s next.

### How about *almost* FD-FPCs?

Zhandry’s FD-FPC (i.e., full security) is very stringent and in some
sense captures **perfectly** indistinguishability. Is it possible to
loose it slightly? For instance, consider an notion of
$\epsilon$-**almost** FD-FPC where we require that after querying a
construction $\sigma$ on all but $N^\epsilon$ elements of the domain
of size $N$, it is still difficult for the distinguisher to tell it
from a truly random permutation. It is likely that, by direct statistical
analysis or some standard techniques in quantum query complexity
(e.g., BBBV hybrid method), this notion also implies quantum
security. In fact, Zhandry’s definition FD-FPC may already entails
almost FD-FPC when very small $\epsilon$ is concerned.

### Rapid mixing implies (almost) full security

An immediate application about the almost FD-FPC is that rapid mixing
implies almost FD-FPC. This is because rapid mixing means that if one
draws a permutation from some construction $\Xi$ or uniformly random,
they get literally the **same** permutation with the same probability
except with some negligible error. Of course learning the entire truth
table does not tell anything, because the distinguisher is looking at
the same permutation!

In other words, FD-FPC was considering a special family of distinguishers who query (almost) the entire domain and make a decision, whereas rapid mixing ensures security for any distinguishers.

### How was full security proven?

You may have been wondering, after all, one still needs some technique
to prove full security. How did people do it? Roughly speaking,
Ristenpart and Yilek in their mix-&-cut paper introduced the
*icicle* technique, which recursively applies an “already-good-enough”
inner PRP $\sigma$ on shorter inputs. This can be viewed as amplifying
the security of $\sigma$ to full security. What does
“already-good-enough” mean? It is basically almost FD-FPC that we just
discussed. How to construct and prove a “already-good-enough” inner
PRP? It turns out, not surprisingly, *rapid mixing of random walks* is
the hero again. This was demonstrated in the Swap-or-Not
construction, which is the inner PRP used in both FD-FPCs Zhandry
identified (Mix-&-cut and Sometimes-recurse). Beware that the random
walk studied in Swap-or-Not is the walk on *strings* rather than
*permutations*.

# What now?

Well, maybe we just need to be happy now. But we (maybe just me) are so annoyed that no quantum security has been said about the original LubyRackoff’s Balanced Feistel (BF) construction.

how many round are enough, if any, to make the LubyRackoff Balanced Feistel quantum-secure?

Let’s start with the rapid mixing approach? Restating the question we mentioned earlier

does LubyRackoff construction (Balanced Feistel) also mix rapidly?

We were very hopeful. First thing to notice is that balanced Feistel
networks only produce *even* permutations, i.e., they generate the
alternating group $A_{X}$ as shown by Evan&Goldreich several
decades ago. But this is not a problem, since we can show that a
uniformly random *even* permutation is indistinguishable from a
uniformly random permutation. So it suffices to have BF mix well in
$A_X$. We tried several techniques (spectral analysis, coupling
argument as Morris used to show the mixing
of Max-Unbalanced Feistel), but were not successful.

Then came the embarrassing moment. Shih-Han pointed out that there is
just not enough **randomness** or freedom to produce all even
permutations by BF in poly-many rounds. A simple criterion that
somehow sneaked out of our eyes. Think about how many possible
permutations one round BF is able to generate – the number of
possible round functions, which is $a = 2^{n2^n}$. So $r$-round
iteration at most gives you $(2^{n2^n})^r = 2^{r n \cdot 2^n}$ many
permutations. But what is the size of alternating group of $2n$-bit
strings? It is $2^{2n}! /2 \approx 2^{2n\cdot 2^{2n}}$. Clearly $r$
needs to be at least $\Omega(2^n)$ to make ends meet.

As a sanity check, the Max-Unbalanced Feistel does not suffer from this, because there are $2^{2^{2n-1}}$ possible functions each round, and roughly $2n$ rounds will generate the entire symmetric group. Indeed Morris showed $O(n^3)$ mixing time.

Is this approach totally doomed? One may identify a subgroup in $A_X$ so that BF mixes rapidly on it and meanwhile a random element there remains indistinguishable from being truly random. But we do not see a clear route at present.

Finally note that Zhandry’s FD-FPC approach does not help here,
because BF is **NOT** FD-FPC, not even close to almost FD-FPC. Recall
that Balanced Feistel only generates even permutations, whereas a
truly random permutation is eaually liketly to be even or odd. A
distinguisher querying the entire domain can of course reconstrut the
permutation and determine if it is even or odd (with enough
time). Similarly, we could imagine tweaking the definition of FD-FPC
so that we just need the construction to be indistinguishable from a
random even permutation. It still seems unlikely that poly-many rounds
of BF is able to realize this slightly weaker notion of FD-FPC.

## Open question: efficient QPRPs

I am still optimistic about finding a **proof** of its quantum
security (yeah, I do believe it is quantum-secure with not too-many
rounds). As discussed before, we can say so much strong security
classically, and maybe we are just missing a suitable *bridge*, i.e.,
a sufficient condition for quantum security, which in the meantime
follows from classical security results.

Maybe we (I) should not be too obsessed by balanced Feistel. The more significant question is probably how to get more efficient QPRPs. The QPRPs identified so far (e.g., Max-UBF, Mix-Cut Shuffle) need linear or polynomially many round in $n$. This may be acceptable on small domain (e.g., constant $n$), but clearly too expensive for large domains.

can we construct more efficient QPRPs? e.g., constant number of iterations and calls of PRFs?

Any ideas? Comments welcome.