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.