The Iterated Random Permutation Problem with Applications to Cascade Encryption

Abstract

We introduce and study the iterated random permutation problem, which asks how hard it is to distinguish, in a black-box way, the r-th power of a random permutation from a uniformly random permutation of a set of size N. We show that this requires $\varOmega (N)$ queries (even for a two-sided, adaptive adversary). As a direct application of this result, we show that cascading a block cipher with the same key cannot degrade its security (as a pseudorandom permutation) more than negligibly.

1 Introduction

A Simple Question. Assume that, as a cautious and slightly paranoid cryptographer, you are not at ease with using $\mathsf {AES}$ (say, with 256-bit keys) as is. Instead, you define the block cipher $\mathsf {myAES}$ as

$$\begin{aligned} \mathsf {myAES}(k,x) \mathrel {\mathop =^\mathrm{def}}\mathsf {AES}(k,\mathsf {AES}(k,x)), \end{aligned}$$

that is, you encipher the plaintext x twice with the same key k, hoping that this will increase security. After all, this seems like a cheap, “black-box” way of doubling the number of rounds of $\mathsf {AES}$-256, and it is heuristically well established that increasing the number of rounds of a cipher improves its resistance to various attacks. Another motivation is some contexts could be to slow down brute force attacks.¹ How can you be sure that the security of your new custom block cipher does not suddenly collapse, becoming much worse than the security of $\mathsf {AES}$-256? This seems quite implausible, but can we hope to formally prove that this cannot happen?

Cascade Encryption. This question is obviously related to what is called cascade encryption (or multiple encryption), i.e., self-composition of a block cipher. Given a block cipher E, the cascade of length r associated with E encrypts a message x as

$$\begin{aligned} E'_{k_1,\ldots ,k_r}(x)\mathrel {\mathop =^\mathrm{def}}(E_{k_r} \circ \cdots \circ E_{k_1})(x). \end{aligned}$$

Cascade encryption has been extensively studied in the setting where the keys $(k_1,\ldots ,k_r)$ for the r calls to the underlying block cipher E are independent: there are results in the computational setting [LR86, Mye99, MT09, Tes11], in the information-theoretic setting (where only computationally unbounded adversaries are considered) [Vau98, Vau99, Vau03, MP04, MPR07, CPS14], and in the ideal cipher model (in the context of key-length extension) [ABCV98, BR06, GM09, Lee13, DLMS14]. In particular, it is known that cascading a given block cipher with independent keys is security-amplifying: if E is a $(q,t,\varepsilon )$-pseudorandom permutation² (PRP), then the r-fold cascade with independent keys for the r calls to E is a $(q',t',r\varepsilon ^r)$-PRP [Tes11], with $q'\simeq q$ and $t'\simeq t$. In the information-theoretic setting, the following slightly weaker result has been shown: if E is a $(q,\varepsilon )$-PRP, then the r-fold cascade of E with independent keys is a $(q,2^{r-1}\varepsilon ^r)$-PRP [Vau98, Vau99].

On the other hand, virtually nothing is known regarding the security of cascade encryption when the keys used for each call to the underlying block cipher are not independent.³ Not only is it not known whether this might amplify security (and indeed, proving even a tiny security amplification result for cascade encryption without increasing the total key-length would be a major breakthrough), but there is absolutely no guarantee that this might not in some cases dramatically deteriorate security.

Our Result. In this short paper, we prove that cascading a block cipher with the same key cannot degrade its security beyond negligible. By security, we mean the standard notion of (strong) pseudorandomness, defined as follows.

Definition 1

(Strong Pseudorandom Permutation (SPRP)). Let E be a block cipher with key space K and message space S, and $\mathsf {Perm}(S)$ be the set of all permutations of S. Let $\mathcal {D}$ be a distinguisher with oracle access to a permutation and its inverse, and returning a single bit. The SPRP-advantage of $\mathcal {D}$ against E is defined as

$$\begin{aligned} \mathbf{Adv }^{\mathrm {sprp}}_E(\mathcal {D})&=\Big |\Pr \left[ {P\leftarrow _{\$}\mathsf {Perm}(S): \mathcal {D}^{P,P^{-1}}=1}\right] \\&\quad - \Pr \left[ {k\leftarrow _{\$}K: \mathcal {D}^{E_k,(E_k)^{-1}}=1}\right] \Big |. \end{aligned}$$

For integers q and t, the SPRP-advantage of E is defined as

$$\begin{aligned} \mathbf{Adv }^{\mathrm {sprp}}_E(q,t)=\max _{\mathcal {D}} \mathbf{Adv }^{\mathrm {sprp}}_E(\mathcal {D}), \end{aligned}$$

where the maximum is taken over all distinguishers making at most q oracle queries and running in time at most t. E is a $(q,t,\varepsilon )$-SPRP if $\mathbf{Adv }^{\mathrm {sprp}}_E(q,t)\le \varepsilon$.

A block cipher is deemed secure if its SPRP-advantage is “small” for all “reasonable” parameters q and t. We show the following.

Theorem 1

Let E be a block cipher with message space of size N, and $r>0$ be an integer. Let $E^r$ be the block cipher obtained by r-fold self-composition of E with the same key. (Note that E and $E^r$ have the same message and key spaces.) Then

$$\begin{aligned} \mathbf{Adv }^{\mathrm {sprp}}_{E^r}(q,t)\le \mathbf{Adv }^{\mathrm {sprp}}_{E}(rq,t') + \frac{(2r+1)q}{N}, \end{aligned}$$

with $t'=\mathcal {O}(t)$.

Hence, cascade encryption with the same key does not hurt security beyond negligible, or, to phrase it more positively, it can only improve the security of a given PRP. Theorem 1 follows straightforwardly from a purely information-theoretic result that we now expose in details.

The Iterated Random Permutation Problem. Let S be a set of size $N>0$, and let $\mathsf {Perm}(S)$ be the group of all permutations of S. For a permutation $P\in \mathsf {Perm}(S)$ and an integer $r\ge 1$, we denote $P^r$ the r-fold self-composition of P. Consider an adversary (later called distinguisher) $\mathcal {D}$ having two-sided oracle access to an element $P\in \mathsf {Perm}(S)$: it can either query P(x) and receive the corresponding image y, or query $P^{-1}(y)$ and receive the corresponding antecedent x. We assume that $\mathcal {D}$ makes at most q (adaptive queries) before outputting a bit b. The iterated random permutation problem asks how many queries q needs $\mathcal {D}$ to distinguish with a noticeable probability the following two situations:

• 1. a permutation P is drawn at random from $\mathsf {Perm}(S)$, and $\mathcal {D}$ is given oracle access to P and $P^{-1}$;

• 2. a permutation P is drawn at random from $\mathsf {Perm}(S)$, and $\mathcal {D}$ is given oracle access to $P^r$ and $(P^r)^{-1}$.

In other words, defining the advantage of $\mathcal {D}$ for the iterated random permutation problem as

$$\begin{aligned} \mathbf{Adv }_{P,P^r}(\mathcal {D})&=\Big |\Pr \left[ {P\leftarrow _{\$}\mathsf {Perm}(S):\mathcal {D}^{P,P^{-1}}=1}\right] \\&\quad - \Pr \left[ {P\leftarrow _{\$}\mathsf {Perm}(S):\mathcal {D}^{P^r,(P^r)^{-1}}=1}\right] \Big |, \end{aligned}$$

and the best advantage at q queries as

$$\begin{aligned} \mathbf{Adv }_{P,P^r}(q)=\max _{\mathcal {D}} \mathbf{Adv }_{P,P^r}(\mathcal {D}), \end{aligned}$$

where the maximum is taken over all distinguishers making at most q queries, we ask how q must grow with N for $\mathbf{Adv }_{P,P^r}(q)$ to be constant, say $\mathbf{Adv }_{P,P^r}(q)\ge 1/2$. We show that this requires $q=\varOmega (N/r)$. More precisely, we have the following theorem.

Theorem 2

For any integer q, one has

$$\begin{aligned} \mathbf{Adv }_{P,P^r}(q)\le \frac{(2r+1)q}{N}. \end{aligned}$$

This theorem is proved in Sect. 2. Theorem 1 follows from Theorem 2 by a simple hybrid argument that we give for completeness.

Proof

of Theorem  1. Let $\mathcal {D}$ be a distinguisher against the strong pseudorandomness of $E^r$ making at most q oracle queries and running in time at most t. By definition,

$$\begin{aligned} \mathbf{Adv }^{\mathrm {sprp}}_{E^r}(\mathcal {D})&=\Big | \Pr \left[ {P\leftarrow _{\$}\mathsf {Perm}(S): \mathcal {D}^{P,P^{-1}}=1}\right] \\&\quad - \Pr \left[ {k\leftarrow _{\$}K: \mathcal {D}^{(E_k)^r,((E_k)^r)^{-1}}=1}\right] \Big |\\&\le \mathbf{Adv }_{P,P^r}(\mathcal {D})+ \mathbf{Adv }_{P^r,E^r}(\mathcal {D})\\&\le \frac{(2r+1)q}{N}+ \mathbf{Adv }_{P^r,E^r}(\mathcal {D}), \end{aligned}$$

where the last inequality follows from Theorem 2 and where

$$\begin{aligned} \mathbf{Adv }_{P^r,E^r}(\mathcal {D})&=\Big | \Pr \left[ {P\leftarrow _{\$}\mathsf {Perm}(S): \mathcal {D}^{P^r,(P^r)^{-1}}=1}\right] \\&\quad - \Pr \left[ {k\leftarrow _{\$}K: \mathcal {D}^{(E_k)^r,((E_k)^r)^{-1}}=1}\right] \Big |. \end{aligned}$$

Consider the following distinguisher $\mathcal {D}'$ against the strong pseudorandomness of E. It has oracle access to some permutation oracle O (which is either a random permutation P or $E_k$ for a random key k) and works as follows: it runs $\mathcal {D}$, answering each oracle query of $\mathcal {D}$ by querying its own oracle r times to return $O^r(x)$ for a direct query or $(O^r)^{-1}(y)$ for an inverse query, and outputting the same decision as $\mathcal {D}$. Clearly, the SPRP-advantage of $\mathcal {D}'$ against E is exactly $\mathbf{Adv }_{P^r,E^r}(\mathcal {D})$, and $\mathcal {D}'$ makes at most rq queries and runs in time $t'=\mathcal {O}(t)$. Hence

$$\begin{aligned} \mathbf{Adv }_{P^r,E^r}(\mathcal {D})\le \mathbf{Adv }^{\mathrm {sprp}}_{E}(rq,t'), \end{aligned}$$

which concludes the proof.   $\square$

Remark 1

It can be noted in the proof above that even when $\mathcal {D}$ is non-adaptive (i.e., $\mathcal {D}$ chooses all its queries at the beginning of the security experiment and issues them all at once), $\mathcal {D}'$ seems to inherently have to query its oracle adaptively. And indeed, Theorem 1 does not extend to the non-adaptive variant of (strong) pseudorandomness. This can be seen from the following simple example: Consider a (single-key) Even-Mansour cipher [EM97], defined by $E_k(x)=k\oplus P(k\oplus x)$, where P is a public (efficiently computable and invertible) permutation. Assume that P is an involution (i.e., $P^2$ is the identity). Then, the block cipher $E^2$ obtained by composing E twice with the same key is highly insecure (even against non-adaptive adversaries making one single query) since it is equal to the identity for any key. On the other hand, modeling P as a public random involution oracle, it can be shown [DKS12] that E is secure against non-adaptive distinguishers making at most $q=2^{n/2}$ encryption/decryption queries and evaluating P on at most $t=2^{n/2}$ values.⁴ This shows that, unlike what Theorem 1 ensures for adaptive security, cascading with the same key can completely ruin security against non-adaptive distinguishers.

We also exhibit a distinguisher whose advantage matches the upper bound of Theorem 2 (up to some constant term which depends on r), establishing the following lower bound.

Theorem 3

For $q\le N/r$, one has

$$\begin{aligned} \mathbf{Adv }_{P,P^r}(q) \ge \frac{q}{2N}-\frac{r}{N}. \end{aligned}$$

The adversary that we use to arrive at Theorem 3 simply picks a random message $x\in S$ and travels along the cycle on which this point lies, hoping to cycle back to x. Details of the analysis can be found in Sect. 3. A different attack, based on the search of a fixed point, has been analyzed by Courtois et al. [BAC12].

Perspectives. A natural question is whether it is possible to prove any kind of security amplification for cascade encryption with non-independent keys, which in its full generality would take the form

$$\begin{aligned} E'_k(x)=(E_{f_r(k)}\circ \cdots \circ E_{f_1(k)})(x), \end{aligned}$$

where the $f_i$’s are permutations of the key space of E.⁵ However, in the particular scenario where the same key is reused (i.e., all $f_i$’s are equal to the identity), this clearly requires additional assumptions on the underlying block cipher E, as indicated (again) by the simple example of a single-key Even-Mansour cipher $E_k(x)=k\oplus P(k\oplus x)$, where P is a public (efficiently computable and invertible) permutation. There is a generic⁶ attack on any block cipher of this class requiring $q=2^{n/2}$ queries to the encryption/decryption oracle and $t=2^{n/2}$ evaluations of the inner permutation P [Dae91, DKS12]. Note that for any $r>1$, the r-fold cascade with the same key $E^r$ is again a one-round single-key Even-Mansour cipher, with inner permutation $P^r$, so that it can be generically attacked with $q=2^{n/2}$ queries to the encryption/decryption oracle and $t=r2^{n/2}$ evaluations of P. Hence, under the assumption that P is such that the best attack against E is the generic one, composition with the same key does not amplify the security of such a block cipher. The same argument applies if the $f_i$’s are of the form $f_i(k) = k\oplus c_i$ for public constants $c_i$. Indeed, this yields again a one-round single-key Even-Mansour cipher with inner permutation

$$\begin{aligned} P'(x)=c_r\oplus P(c_r\oplus c_{r-1}\oplus P(c_{r-1}\oplus \cdots \oplus c_1 \oplus P(c_1\oplus x)\cdots )). \end{aligned}$$

Besides, slide attacks [BW99] show that iterating a truly weak cipher cannot make it arbitrarily strong, independently of the number of iterations. For instance, in the information-theoretic setting, if E is so weak that it can be distinguished from random using a single plaintext/ciphertext pair with advantage $1-2^{n/2}$, then $E^{r}$ can be distinguished from random using $2^{n/2}$ queries with constant probability of success, regardless of the value of r.⁷

We leave open the problem whether it is possible to find assumptions on the block cipher E (e.g. resistance to related-key attacks, resistance to key-dependent messages attacks, etc.) sufficient to prove that cascading with non-independent keys is security amplifying.

2 Proof of the Main Result

In this section, we prove Theorem 2. We rely on the game-playing framework, and we assume some familiarity of the reader with this technique (see [Sho04, BR06] for more details).

In all the following, given a non-empty set S, we denote $\mathrm{Card}(S)$ the number of elements in S. Let $\mathsf {Cycl}(S)$ denote the set of cyclic permutations of S, i.e., the subset of $\mathsf {Perm}(S)$ consisting of permutations with a single cycle. Overall, we will consider the following four games:

• $\mathsf {G_P^{}}$, which gives access to P and $P^{-1}$ for $P\leftarrow _{\$}\mathsf {Perm}(S)$;

• $\mathsf {G_{P^r}^{}}$, which gives access to $P^{r}$ and $(P^{r})^{-1}$ for $P\leftarrow _{\$}\mathsf {Perm}(S)$;

• $\mathsf {G_C^{}}$, which gives access to C and $C^{-1}$ for $C\leftarrow _{\$}\mathsf {Cycl}(S)$;

• $\mathsf {G_{C^r}^{}}$, which gives access to $C^{r}$ and $(C^{r})^{-1}$ for $C\leftarrow _{\$}\mathsf {Cycl}(S)$.

Each game provides two interfaces to the distinguisher, denoted $\mathsf {Q}$ and $\mathsf {Q}^{-1}$, for querying the underlying permutation respectively in the direct and inverse direction. For example, the formal definition of $\mathsf {G_P^{}}$ is:

For any games $\mathsf {G}$, $\mathsf {H}$, we write $\mathbf{Adv }_{\mathsf {G},\mathsf {H}}(q)$ to denote the maximal advantage attainable by distinguishers between $\mathsf {G}$ and $\mathsf {H}$ within q queries. We say that two games $\mathsf {G}$ and $\mathsf {H}$ are equivalent (within q queries) if $\mathbf{Adv }_{\mathsf {G},\mathsf {H}}(q)=0$. Our goal is to bound $\mathbf{Adv }_{\mathsf {G_P^{}},\mathsf {G_{P^r}^{}}}(q)$. The layout of the proof is summarized by the following picture:

Lemma 1

$$\begin{aligned} \mathbf{Adv }_{\mathsf {G_P^{}},\mathsf {G_C^{}}}(q) \le \frac{q}{N}. \end{aligned}$$

Proof

We start with some useful definitions. A partial permutation graph (V, E) of size N is a directed graph (with loops allowed) with set of vertices V of size N and set of edges $E\subset V^2$, where each vertex has out- and in-degree 0 or 1. Given a partial permutation graph (V, E) containing no cycles and a vertex $z\in V$, the source of z, denoted $\mathsf {So}(z)$, is the unique $x\in V$ with in-degree 0 such that there is a path from x to z (with the convention that $\mathsf {So}(z)=z$ if z has in-degree 0), and the sink of z, denoted $\mathsf {Si}(z)$, is the unique $y\in V$ with out-degree 0 such that there is a path from z to y (with the convention that $\mathsf {Si}(z)=z$ if z has out-degree 0). The existence and uniqueness of $\mathsf {So}(z)$ and $\mathsf {Si}(z)$ when (V, E) is acyclic are straightforward to prove.

We consider lazily sampled versions of $\mathsf {G_P^{}}$ and $\mathsf {G_C^{}}$. To describe the lazy sampling procedure, we assume that $\mathsf {G_P^{}}$ internally maintains a partial permutation graph over $V=S$ (with initially no edge). This graph represents the current state of the sampling process. We let $E\subset S^2$ denote the (time-dependent) set of edges of the graph. We also let X be the set of vertices with out-degree 1 and Y be the set of vertices with in-degree 1, these two sets being time-dependent as well. Slightly abusing notation, for $x\in X$, we denote E(x) the unique $y\in S$ such that $(x,y)\in E$, and for $y\in Y$, we denote $E^{-1}(y)$ the unique $x\in S$ such that $(x,y)\in E$. The lazy sampled version of $\mathsf {G_P^{}}$ is as follows:

Claim

$\mathsf {G_P^{}}$ and $\mathsf {G_P^{lazy}}$ are equivalent (for any number q of queries).

Proof

This is a folklore result (see e.g. [BR06, Sect. 7.4]). Proving it amounts to showing, with the previous notation, that if $P\leftarrow _{\$}\mathsf {Perm}(S)$ agrees with a partial permutation graph (S, E), for $x\in S \setminus X$, then P(x) is uniformly distributed over $S\setminus Y$. Equivalently, for any $x, x_1, \dots , x_n$ pairwise distinct in S, and $y_A, y_B, y_1, \dots , y_n$ pairwise distinct in S, we have

$$\begin{aligned}&\mathrm{Card}\{P \in \mathsf {Perm}(S) : P(x) = y_A, P(x_{1}) = y_{1}, \dots , P(x_{n}) = y_{n}\} \\ =\,&\mathrm{Card}\{P \in \mathsf {Perm}(S) : P(x) = y_B, P(x_{1}) = y_{1}, \dots , P(x_{n}) = y_{n}\}. \end{aligned}$$

To see this, observe that left-hand side composition with transposition $(y_A\;y_B)$ is a bijection between the two sets. The reasoning for an inverse query is similar.    $\blacksquare$

Similarly, the lazy version of $\mathsf {G_C^{}}$ is:

Claim

$\mathsf {G_C^{}}$ and $\mathsf {G_C^{lazy}}$ are equivalent (for any number q of queries).

Proof

Here, we must show that for any partial permutation graph (S, E) containing no cycle, with the previous notation and letting $X = \{x_1,\dots ,x_n\}$, $Y= \{y_1,\dots ,y_n\}$, $x \in S\setminus X$ and $y_A, y_B \in S\setminus (Y \cup \{\mathsf {So}(x)\})$, we have

$$\begin{aligned}&\mathrm{Card}\{C \in \mathsf {Cycl}(S) : C(x) = y_A, C(x_{1}) = y_{1}, \dots , C(x_{n}) = y_{n}\} \\ =\,&\mathrm{Card}\{C \in \mathsf {Cycl}(S) : C(x) = y_B, C(x_{1}) = y_{1}, \dots , C(x_{n}) = y_{n}\}. \end{aligned}$$

Once again, we prove this equality by building a bijection between the two sets. This bijection is: $C \mapsto (y_A\,y_B) \circ C \circ (\mathsf {Si}(y_A)\;\mathsf {Si}(y_B))$, where $(a\;b)$ denotes the transposition swapping a and b. If C is seen as a cyclic graph, this bijection swaps the position of the longest chain starting from $y_A$ in E with the longest chain starting from $y_B$. Thus it preserves the cyclic structure and is an involutive bijection between the two sets considered. The reasoning for an inverse query is similar.    $\blacksquare$

From the lazy sampling versions of the games, it becomes apparent that $\mathsf {G_C^{lazy}}$ and $\mathsf {G_P^{lazy}}$ are identical, unless the event $[\mathsf {Q}(x) = \mathsf {So}(x) \text { or } \mathsf {Q}^{-1}(y) = \mathsf {Si}(y)]$ happens for some query in $\mathsf {G_P^{lazy}}$. More precisely, we can rewrite $\mathsf {G_C^{lazy}}$ using a flag $\mathsf {bad}$ as follows:

Clearly, $\mathsf {G_C^{lazy}}$ and $\mathsf {G_C^{lazy2}}$ are equivalent (this technique is called resampling, see [BR06, Sect. 7.2]). Moreover, $\mathsf {G_P^{lazy}}$ and $\mathsf {G_C^{lazy2}}$ are syntactically identical unless $\mathsf {bad}$ is set to true. By the fundamental lemma of game-playing (see [BR06, Lemma 2]), one has

$$\begin{aligned} \mathbf{Adv }_{\mathsf {G_P^{lazy}},\mathsf {G_C^{lazy2}}}(q) \le \max _{\mathcal {D}}\Pr \left[ {\mathcal {D}\text { sets } \mathsf {bad}\text { to }\mathbf{true}\text { in } \mathsf {G_C^{lazy2}}}\right] , \end{aligned}$$

where the maximum is taken over all distinguishers making at most q queries.

For any distinguisher $\mathcal {D}$, the probability that $\mathsf {bad}$ is set to true at the i-th query of $\mathcal {D}$ in $\mathsf {G_C^{lazy2}}$ is exactly $1/(N-i)$. Hence, we finally obtain

$$\begin{aligned} \mathbf{Adv }_{\mathsf {G_P^{}},\mathsf {G_C^{}}}(q)= \mathbf{Adv }_{\mathsf {G_P^{lazy}},\mathsf {G_C^{lazy2}}}(q)\le 1 - \prod _{i=0}^{q-1} \left( 1 - \frac{1}{N - i}\right) = \frac{q}{N}. \end{aligned}$$

   $\square$

Lemma 2

$$\begin{aligned} \mathbf{Adv }_{\mathsf {G_{P^r}^{}},\mathsf {G_{C^r}^{}}}(q) \le \frac{rq}{N}. \end{aligned}$$

Proof

Any distinguisher between $P^r$ and $C^r$ can be used to distinguish between P and C at the cost of multiplying the number of queries by r. More formally, given a distinguisher $\mathcal {D}$ between $P^r$ and $C^r$ making at most q queries, consider the distinguisher $\mathcal {D}'$ with oracle access to some permutation oracle O (which is either P or C) working as follows: it runs $\mathcal {D}$, answering each oracle query of $\mathcal {D}$ by querying its own oracle r times to return $O^r(x)$ for a direct query or $(O^r)^{-1}(y)$ for an inverse query, and outputting the same decision as $\mathcal {D}$. Clearly, the advantage of $\mathcal {D}'$ in distinguishing $\mathsf {G_P^{}}$ and $\mathsf {G_C^{}}$ is equal to the advantage of $\mathcal {D}$ in distinguishing $\mathsf {G_{P^r}^{}}$ and $\mathsf {G_{C^r}^{}}$, and $\mathcal {D}'$ makes at most rq queries if $\mathcal {D}$ makes at most q queries. Hence, by Lemma 1,

$$\begin{aligned} \mathbf{Adv }_{\mathsf {G_{P^r}^{}},\mathsf {G_{C^r}^{}}}(q) \le \mathbf{Adv }_{\mathsf {G_P^{}},\mathsf {G_C^{}}}(rq) \le \frac{rq}{N}. \end{aligned}$$

   $\square$

Lemma 3

$$\begin{aligned} \mathbf{Adv }_{\mathsf {G_C^{}},\mathsf {G_{C^r}^{}}}(q) \le \frac{rq}{N}. \end{aligned}$$

Proof

Let $d = \gcd (N,r)$. The key observation is that $\mathsf {G_{C^r}^{}}$ is equivalent to querying a random permutation with d cycles of equal length.⁸ This follows from the fact that the mapping $C\mapsto C^r$ sends $\mathsf {Cycl}(S)$ onto the set of permutations with exactly d cycles of the same length, and that each such permutation has the same number of preimages in $\mathsf {Cycl}(S)$ under this mapping (the interested reader can refer to Appendix A where we prove this claim). In particular, if $d = 1$ (when N and r are coprime), the games $\mathsf {G_C^{}}$ and $\mathsf {G_{C^r}^{}}$ are identical and we are done. If $d>1$, we need to upper bound the advantage of an adversary distinguishing between a random permutation with a single cycle, and a random permutation with d cycles of equal length.

We now describe a new game $\mathsf {G_{C^r}^{*}}$, which we claim is an equivalent description of $\mathsf {G_{C^r}^{}}$.

Intuitively, $\mathsf {G_{C^r}^{*}}$ may be pictured as shown on Fig. 1.

We show in Appendix A that the sampling process underlying game $\mathsf {G_{C^r}^{*}}$ is also equivalent to sampling a random permutation with d cycles of equal length. Meanwhile, we define the game $\mathsf {G_C^{*}}$ as being identical to $\mathsf {G_{C^r}^{*}}$, except queries $\mathsf {Q}(x)$ (resp. $\mathsf {Q}^{-1}(y)$) simply return C(x) (resp. $C^{-1}(y)$): the $s_{i}$’s play no special role. This corresponds to step 2 in the picture above. The point is that $\mathsf {G_C^{*}}$ is clearly an equivalent description of $\mathsf {G_C^{}}$ (since procedures $\mathsf {Q}$ and $\mathsf {Q}^{-1}$ are syntactically the same in both games), while $\mathsf {G_{C^r}^{*}}$ is an equivalent description of $\mathsf {G_{C^r}^{}}$ (indeed, by the two claims proved in Appendix A, they are both equivalent to querying a random permutation with d cycles of length N / d).

Thus $\mathbf{Adv }_{\mathsf {G_C^{}},\mathsf {G_{C^r}^{}}}(q) = \mathbf{Adv }_{\mathsf {G_C^{*}},\mathsf {G_{C^r}^{*}}}(q)$. The following claim completes the proof.

Claim

$$\begin{aligned} \mathbf{Adv }_{\mathsf {G_C^{*}},\mathsf {G_{C^r}^{*}}}(q) \le \frac{dq}{N}. \end{aligned}$$

Proof

The only difference between $\mathsf {G_C^{*}}$ and $\mathsf {G_{C^r}^{*}}$ occurs when $\mathsf {Q}(s_{i})$ is queried for some i (or $\mathsf {Q}^{-1}(C(s_{i}))$ for backward queries). So $\mathbf{Adv }_{\mathsf {G_C^{}},\mathsf {G_{C^r}^{}}}(q)$ is upper bounded by the advantage of an adversary playing the following game: she queries $\mathsf {G_C^{*}}$, and wins iff one of the queries is an $s_{i}$ (or $C(s_{i})$ for a backward query). We now prove that the advantage of such an adversary is at most dq / N.

Fig. 1.

Representation of the game $\mathsf {G_{C^r}^{*}}$.

To show this, we give extra information to the adversary: we grant her full knowledge of the cycle C before queries begin. Clearly this can only increase her advantage. The point is that queries no longer provide any new information. Thus the game becomes equivalent to the adversary simply trying to guess one of the $s_{i}$’s within q tries.

Notice that the position of the $s_{i}$’s in the cycle C is essentially defined modulo $a = N/d$. Guessing the position of one of the $s_{i}$’s in the cycle amounts to guessing a value modulo a. Thus the game is equivalent to guessing a value among a possibilities, within q tries. The advantage of an adversary in this game is:

$$\begin{aligned} 1-\prod _{i=0}^{q-1}\left( 1 - \frac{1}{a-i}\right) = 1- \frac{a-q}{a} = 1 - \frac{N-dq}{N} = \frac{dq}{N}. \end{aligned}$$

By the previous reasoning, this is an upper bound for $\mathbf{Adv }_{\mathsf {G_C^{*}},\mathsf {G_{C^r}^{*}}}(q)$.    $\blacksquare$

Thus, we have

$$\begin{aligned} \mathbf{Adv }_{\mathsf {G_C^{}},\mathsf {G_{C^r}^{}}}(q) = \mathbf{Adv }_{\mathsf {G_C^{*}},\mathsf {G_{C^r}^{*}}}(q) \le \frac{dq}{N} \le \frac{rq}{N}. \end{aligned}$$

   $\square$

The proof of Theorem 2 is now complete. Combining Lemmas 1, 2, and 3, we obtain

$$\begin{aligned} \mathbf{Adv }_{\mathsf {G_P^{}},\mathsf {G_{P^r}^{}}}(q) \le \mathbf{Adv }_{\mathsf {G_P^{}},\mathsf {G_C^{}}}(q) + \mathbf{Adv }_{\mathsf {G_C^{}},\mathsf {G_{C^r}^{}}}(q) + \mathbf{Adv }_{\mathsf {G_{C^r}^{}},\mathsf {G_{P^r}^{}}}(q) \le \frac{(2r+1)q}{N}. \end{aligned}$$

3 A Matching Attack

In this section, we describe a simple attack matching the bound in Theorem 2 within a constant factor, when the number of iterations r is constant. Our attack uses the following distinguisher $\mathcal {D}_{\text {cycle}}$ between $\mathsf {G_P^{}}$ and $\mathsf {G_{P^r}^{}}$. It makes q queries to the interface $\mathsf {Q}$ (corresponding to P in $\mathsf {G_P^{}}$ and $P^{r}$ in $\mathsf {G_{P^r}^{}}$), ignoring $\mathsf {Q^{-1}}$.

Thus, $\mathcal {D}_{\text {cycle}}^{\mathsf {Q}}$ returns 1 iff the point $s_{0} \leftarrow _{\$}S$ belongs to a cycle of length at most q. We have the following result (from which Theorem 3 is a direct application).

Lemma 4

Assume $q \le N/r$. Then

$$\begin{aligned} C(r)\frac{q}{N} - \frac{r}{N} \le \mathbf{Adv }_{\mathsf {G_P^{}},\mathsf {G_{P^r}^{}}}(\mathcal {D}_{\text {cycle}}) \le C(r)\frac{q}{N} + \frac{r}{N} \quad \text { with } C(r) = \sum _{d | r} \frac{\phi (d)}{d} - 1 \end{aligned}$$

where d | r denotes “d divides r”, and $\phi$ is Euler’s totient function. Moreover $C(r) \ge 1/2$ for $r \ge 2$.

Proof

By definition:

$$\begin{aligned} \mathbf{Adv }_{\mathsf {G_P^{}},\mathsf {G_{P^r}^{}}}(\mathcal {D}_{\text {cycle}})&= \Big |\Pr \left[ {P\leftarrow _{\$}\mathsf {Perm}(S):\mathcal {D}_{\text {cycle}}^{P^{r}}=1}\right] \\&\quad - \Pr \left[ {P\leftarrow _{\$}\mathsf {Perm}(S):\mathcal {D}_{\text {cycle}}^{P}=1}\right] \Big |. \end{aligned}$$

We now set out to compute these two probabilities.

If we pick a random point in a random permutation on N points, and look at the length of the cycle it belongs to, all lengths $1 \le k \le N$ are equally probable. This is a standard result. It can be shown, for instance, using $\mathsf {G_P^{lazy}}$: if we choose $s_{0} \leftarrow _{\$}S$ and query q times along a chain, and assume the first i queries do not create a cycle, then the probability that the next query does is exactly $1/(N-i)$. Thus, the probability that $s_{0}$ belongs to a cycle of length k is precisely

$$\begin{aligned} \prod _{i=0}^{k-1}\left( 1-\frac{1}{N-i}\right) \cdot \frac{1}{N-k} = \frac{1}{N}. \end{aligned}$$

As a consequence, one has

$$\begin{aligned} \Pr \left[ {P\leftarrow _{\$}\mathsf {Perm}(S):\mathcal {D}_{\text {cycle}}^{P}(q)=1}\right] = \frac{q}{N}. \end{aligned}$$

We now turn to the case where $\mathcal {D}_{\text {cycle}}$ interacts with $P^{r}$ instead of P. We let

$$\begin{aligned} p\mathrel {\mathop =^\mathrm{def}}\Pr [P\leftarrow _{\$}\mathsf {Perm}(S):\mathcal {D}_{\text {cycle}}^{P^{r}}(q)=1]. \end{aligned}$$

First, we recall two classic equalities regarding the totient function:

$$ \sum _{d|n}\phi (d) = n \quad (1)\qquad \phi (n) = n\prod _{p|n,p\in \mathbb {P}}\left( 1-\frac{1}{p}\right) \quad (2) $$

where $\mathbb {P}$ is the set of prime numbers. Now let k be the length of the cycle containing $s_{0}$. In $P^{r}$ this cycle is broken up into $d = \gcd (k,r)$ cycles of length k / d. Hence $\mathcal {D}_{\text {cycle}}(q)$ detects a cycle iff $q \ge k/d$. Since all lengths k are equally probable, we have

$$\begin{aligned} p&=\frac{1}{N}\mathrm{Card}\left\{ k \le N : q \ge \frac{k}{\gcd (k,r)}\right\} \\&=\frac{1}{N}\mathrm{Card}\{k \le N : \exists d | r, \gcd (k,r) = d \text { and } k \le dq\}\\&=\frac{1}{N}\mathrm{Card}\{k : \exists d | r, \gcd (k,r/d) = 1 \text { and } k \le \min (q,N/d)\} \qquad \text {with }k \leftarrow k/d\\&=\frac{1}{N}\mathrm{Card}\{k : \exists d | r, \gcd (k,r/d) = 1 \text { and } k \le q\} \qquad \text {using } q\le N/r\\&=\frac{1}{N}\sum _{d|r}\mathrm{Card}\{k : \gcd (k,d) = 1 \text { and } k \le q\} \ \text {since } d\mapsto r/d \text { is 1-to-1 over }d|r\\&\ge \frac{1}{N}\sum _{d|r}\mathrm{Card}\left\{ k : \gcd (k,d) = 1 \text { and } k \le d\left\lfloor \frac{q}{d}\right\rfloor \right\} \\&=\frac{1}{N}\sum _{d|r} \phi (d)\left\lfloor \frac{q}{d}\right\rfloor \\&\ge \frac{1}{N}\sum _{d|r}\phi (d)\left( \frac{q}{d}-1\right) \\&=\frac{q}{N}\sum _{d|r}\frac{\phi (d)}{d} - \frac{r}{N} \qquad \text {by (1).} \end{aligned}$$

One can upper bound p in a very similar manner, and we obtain the main inequality.

Finally, we show that $C(r) \ge 1/2$ for $r\ge 2$. In fact it holds that for all r, $C(r) \ge 1 - 1/r$. To see this, observe that if $r>2$ is not prime, we have:

$$\begin{aligned} C(r)&= \sum _{d|r}\frac{\phi (d)}{d} - 1\\&= \frac{\phi (1)}{1} + \sum _{d|r,1<d<r} \frac{\phi (d)}{d} + \prod _{p|r,p\in \mathbb {P}}\bigg (1-\frac{1}{p}\bigg ) - 1 \quad \text { by (2)}\\&\ge \sum _{d|r,1<d<r} \frac{\phi (d)}{d} + \bigg (1 - \sum _{p|r,p\in \mathbb {P}}\frac{1}{p}\bigg ) \quad \text { by the union bound}\\&\ge 1 \quad \text { since }\{p\in \mathbb {P} : p|r\} \subseteq \{1<d<r: d|r\}. \end{aligned}$$

On the other hand, if r is prime then $C(r) = 1 - 1/r$, hence this is the lower bound.    $\square$

Corollary 1

For constant r, the best distinguisher between $\mathsf {G_P^{}}$ and $\mathsf {G_{P^r}^{}}$ has advantage $\varTheta (q/N)$ as $N \rightarrow \infty$ and $q \le N$ is any function of N.

Proof

Theorem 2 shows that the advantage is $\mathcal {O}(q/N)$. Theorem 3 shows that it is $\varOmega (q/N)$ if $q \le N/r$. On the other hand if $q>N/r$, as the advantage can only increase with q, it is at least $C(r)\frac{N/r}{N} + o(1) \ge \frac{1}{2r} + o(1) = \varOmega (1) = \varOmega (q/N)$. Hence overall the advantage is $\varTheta (q/N)$.    $\square$

For concreteness, if $r=2$, Theorem 3 exhibits a distinguisher with advantage 0.5q / N (under the assumption $q<N/2$), while the main theorem upper bounds the advantage of any such distinguisher by 5q / N. Note that if r is not constant, the behavior is more complex; informally, only cycles whose length is not coprime with r are affected by the transformation $P \mapsto P^{r}$. In particular, if r is prime and $r > N$, $P \mapsto P^{r}$ is a permutation of $\mathsf {Perm}(S)$ and $\mathsf {G_P^{}}$ is indistinguishable from $\mathsf {G_{P^r}^{}}$.

The problem of finding a tight bound for variable r is interesting from a purely theoretical standpoint, although we do not know of a situation where such a result would be applicable.

A Omitted Proofs

We prove here two claims that we used in the proof of Lemma 3. We denote $\mathsf {Cycl}_d(S)$ the set of permutations of S with exactly d cycles of length N / d (note that $\mathsf {Cycl}(S)=\mathsf {Cycl}_1(S)$).

Claim

Let S be a set of size N, $r\ge 1$ be an integer, and $d=\gcd (N,r)$. Let $\phi$ be the mapping

$$\begin{aligned} \phi :\;&\mathsf {Cycl}(S) \rightarrow \mathsf {Perm}(S)\\&P \mapsto P^r. \end{aligned}$$

Then $\phi (\mathsf {Cycl}(S))=\mathsf {Cycl}_d(S)$ and all permutations in $\mathsf {Cycl}_d(S)$ have exactly the same number of preimages by $\phi$.

Proof

First, we show that for any $C\in \mathsf {Cycl}(S)$, $\phi (C)\in \mathsf {Cycl}_d(S)$. Let $a=N/d$. Denote

$$\begin{aligned} C= (x_1 \ x_2 \ \cdots \ x_N). \end{aligned}$$

Then it is easy to see that $C^r$ is the product of d disjoint cycles $C_i$, $1\le i\le d$, with

$$\begin{aligned} C_i=(x_i \ x_{(i+r) \text { mod } N} \ x_{(i+2r) \text { mod } N} \cdots \ x_{(i+(a-1)r) \text { mod } N}). \end{aligned}$$

For $A\in \mathsf {Cycl}_d(S)$, we denote $\phi ^{-1}(A)$ the set of preimages of A by $\phi$. We now show that for any $A,B\in \mathsf {Cycl}_d(S)$, $|\phi ^{-1}(A)|=|\phi ^{-1}(B)|$. For $P\in \mathsf {Perm}(S)$, we denote $f_P$ the conjugation by P, namely $f_P(Q)=P\circ Q \circ P^{-1}$. Since A and B have the same cycle structure, they belong to the same conjugacy class, i.e., there exists a permutation P such that $f_P(A)=B$. Hence, for any $C\in \phi ^{-1}(A)$, $f_P(C)\in \mathsf {Cycl}(S)$ since conjugation preserves the cycle structure, and one has

$$\begin{aligned} f_P(C)^r =(P\circ C \circ P^{-1})^r=P \circ C^r \circ P^{-1}=P\circ A \circ P^{-1} =B. \end{aligned}$$

This implies that $f_P(\phi ^{-1}(A))\subseteq \phi ^{-1}(B)$, and hence $|\phi ^{-1}(A)|\le |\phi ^{-1}(B)|$ since $f_P$ is one-to-one. By symmetry, $|\phi ^{-1}(A)|=|\phi ^{-1}(B)|$.    $\blacksquare$

Claim

Let $\psi$ denote the mapping which sends a pair $(C,s_0)\in \mathsf {Cycl}(S)\times S$ to the permutation defined by game $\mathsf {G_{C^r}^{*}}$. Then $\psi (\mathsf {Cycl}(S)\times S) = \mathsf {Cycl}_d(S)$ and all permutations in $\mathsf {Cycl}_d(S)$ have exactly the same number of preimages by $\psi$.

Proof

The fact that $\psi (C,s_0)\in \mathsf {Cycl}_d(S)$ for any $(C,s_0)\in \mathsf {Cycl}(S)\times S$ is clear. We now show that for any $A,B\in \mathsf {Cycl}_d(S)$, $|\psi ^{-1}(A)|=|\psi ^{-1}(B)|$. As in the previous claim, there exists a permutation P such that $f_P(A)=B$. We show that for any $(C,s_0)\in \psi ^{-1}(A)$, $(f_P(C),P(s_0))\in \psi ^{-1}(B)$. First, $f_P(C)\in \mathsf {Cycl}(S)$ since conjugation preserves the cycle structure. For $i<d$, let $s_i=C^{iN/d}(s_0)$. By definition of $\psi$, $A(s_i)=C(s_{(i-1) \text { mod } d})$ and $A(x)=C(x)$ for $x\notin \{s_0,\ldots ,s_{d-1}\}$. Let $s'_0=P(s_0)$ and for $i<d$, $s'_i=f_P(C)^{iN/d}(s'_0)=P(s_i)$. Then

$$\begin{aligned} \psi (f_P(C),P(s_0))(s'_i)&=f_P(C)(s'_{(i-1)\text { mod } d})\\&=P\circ C(s_{(i-1)\text { mod } d})=P\circ A (s_i)=f_P(A)(s'_i)=B(s'_i), \end{aligned}$$

and for $x\notin \{s'_0,\ldots ,s'_{d-1}\}$, since $P^{-1}(x)\notin \{s_0,\ldots ,s_{d-1}\}$, one has

$$\begin{aligned} \psi (f_P(C),P(s_0))(x)=f_P(C)(x)=P\circ C \circ P^{-1}(x)=P\circ A \circ P^{-1}(x)=B(x), \end{aligned}$$

which shows that $\psi (f_P(C),P(s_0))=B$. Hence, the image of $\psi ^{-1}(A)$ by the one-to-one mapping $(C,s_0)\mapsto (f_P(C),P(s_0))$ is a subset of $\psi ^{-1}(B)$, thus $|\psi ^{-1}(A)|\le |\psi ^{-1}(B)|$. By symmetry, $|\psi ^{-1}(A)|=|\psi ^{-1}(B)|$.    $\blacksquare$