A Constant Number of Luby–Rackoff Rounds Is Indistinguishable from a Random Invertible Permutation

Statement: AI-written, not yet formalized. Proof: human draft, not yet independently reviewed, not yet formalized.

View PDF · LaTeX source · Formal statement — not yet formalized

Write $\mathsf{LR}_{f_1,\dots,f_r}$ for the $r$-round Luby–Rackoff (Feistel) construction on $\{0,1\}^{2n}$ built from round functions $f_1, \dots, f_r$.

Conjecture (constant-round Luby–Rackoff). There exists $r \in \mathbb{N}$ such that for every polynomial $p$ there is a negligible $\mu$ with: for all $n$ and every oracle algorithm $A$ making at most $p(n)$ queries,

\[\Bigl|\ \Pr\bigl[A^{U_\Psi, U_{\Psi^{-1}}} \Rightarrow 1 : f_1,\dots,f_r \xleftarrow{\$} \mathrm{Func}_n,\ \Psi := \mathsf{LR}_{f_1,\dots,f_r}\bigr] - \Pr\bigl[A^{U_\pi, U_{\pi^{-1}}} \Rightarrow 1 : \pi \xleftarrow{\$} \mathrm{Perm}(\{0,1\}^{2n})\bigr]\ \Bigr| \le \mu(n).\]

Which version this is. The round functions are drawn uniformly at random from all functions — so the statement is information-theoretic and unconditional, and this page is filed that way. The source’s surrounding discussion is phrased in terms of a strong qPRP built from pseudorandom round functions, which is the cryptographic reading of the same question; the two differ in whether the round functions are random or merely pseudorandom, and a proof of the version above is the natural first step toward the other.

Sources

Unruh. Towards compressed permutation oracles. Cryptology ePrint Archive, Report 2023/770; Advances in Cryptology – ASIACRYPT 2023, pp. 369–400. Read at the single ePrint posting, received 26 May 2023, byte-identical to the harvested copy (SHA-256 prefix e32e1eb4a186bb37, 22 pages). The classical four-round result, the refutation of four rounds quantumly, the remark that five rounds are not excluded, and the report that the published four-round forward-only proof is flawed are all on p. 3; the two-for-one observation about a CPO-based proof is on p. 1. Sole authorship, venue and page range confirmed against DBLP.

The attack refuting four rounds and the flawed four-round proof are cited by the source as its references [20] and [18]. This page has not resolved either to a paper, so neither is named here rather than being named on the strength of a bracket number. [UNVERIFIED: the identity of the four-round quantum attack and of the flawed forward-only proof; both are cited only by reference number in the source read here] Carolan (see Proof, below) separately confirms Hosoyamada–Iwata’s claimed four-round forward-only qPRP proof “was found to contain a bug,” citing a 2024 erratum — so reference [18]’s flaw is independently corroborated, though this page still has not resolved [18] itself to a paper.
Carolan. Compressed Permutation Oracles. Cryptology ePrint Archive, Report 2025/1734; accepted to STOC 2026 (also arXiv:2509.18586). Read at the ePrint PDF. The abstract’s claim to resolve “an open question of (Zhandry, 2012)” and the seven-round result are stated informally on p. 5 and proved as Theorem 6.5, pp. 64–65; the reliance on the paper’s own compressed-permutation-oracle soundness (Theorem 5.19) is explicit in the proof, p. 65 (“By Theorem 5.19…”); the random-vs-pseudorandom round function remark is p. 58.

Resolved for $r = 7$, by a paper this page’s Statement was not transcribed from. Carolan (Compressed Permutation Oracles, ePrint 2025/1734, accepted STOC 2026) proves seven rounds suffice, unconditionally, for random round functions — his abstract states this “resolv[es] an open question of (Zhandry, 2012),” which is the same paper this page cites as first raising the question.

The exact match, checked against the PDF. Carolan’s informal Theorem (p. 5): “No algorithm can distinguish the seven round Feistel construction from a truly random size $N$ permutation unless it makes $\Omega(\sqrt[12]{N})$ bidirectional quantum queries.” His formal Theorem 6.5 (p. 64) bounds the distinguishing advantage of any $q$-query algorithm against seven-round Feistel (built from truly random round functions, matching this page’s information-theoretic framing) by $O(q^3/N^{1/4})$ — negligible for any polynomial $q$, giving exactly this page’s conjecture with $r = 7$.

How the proof works, and its dependency structure. Carolan’s proof of Theorem 6.5 goes: (1) his own compressed permutation oracle cpO is unconditionally sound, by his Theorem 5.19 (see c/0036); (2) seven-round Feistel is shown indistinguishable from cpO, by reusing the masked-Feistel/twirling machinery built for (1) but with the twirl distribution set to two-round Feistel (and its inverse) rather than a uniform permutation — this is the technical content of his Section 6; (3) triangle inequality composes the two. The proof states explicitly, “By Theorem 5.19, we have $\|\rho^{(\mathsf{cpO})} - \rho^{(\mathcal{O})}\|_1 = O(q^3/N^{1/4})$” — so Theorem 6.5 depends on Carolan’s own soundness theorem for his own oracle, not on Unruh’s Conjecture 2 (Unruh’s CPO, built from his CFO-with-free-Flip construction, is a different object — see c/0036). Since Carolan’s Theorem 5.19 is proved outright, this dependency is not a gap: Theorem 6.5 is unconditional.

The claimed “two-for-one” did not happen the way Unruh’s paper anticipated. Unruh’s own remark was that proving some construction (e.g. Luby–Rackoff) secure via CPO methodology would establish CPO’s soundness “for free,” as a byproduct. Carolan’s paper runs the opposite direction: he proves his oracle’s soundness first, directly, and Feistel security follows as an application of it, reusing the same proof technique rather than deriving the oracle’s soundness from the Feistel result. The obligation this page previously recorded — “check the claimed two-for-one” — is therefore moot in the form Unruh posed it, though the underlying question of whether the two proofs are as tightly linked as Unruh imagined is not directly addressed by Carolan’s paper.

The pseudorandom round-function (strong qPRP) form. This page’s Statement is deliberately the information-theoretic, random-round-function version; Carolan’s own framing of the general Feistel distribution notes in passing, without elaborating a proof here, that “$\mathsf{Feist}^{(m)}$… is query-indistinguishable from the case where the round functions are pseudorandom” (p. 58) — i.e., the stronger cryptographic reading (true strong qPRP, matching the source’s abstract framing) is asserted to follow by a standard hybrid argument, which this page has not independently checked.

What has and hasn’t been checked here. Confirmed directly from the PDF: the abstract’s Zhandry-2012 claim, the informal and formal statements of Theorem 6.5, and the explicit invocation of Theorem 5.19 in its proof. Not independently re-derived here: the twirling/cromulence argument of Section 6.1 that establishes seven-round Feistel is indistinguishable from cpO, or the proof of Theorem 5.19 itself. This is a human-written, published (STOC 2026-accepted) proof, matched against this page’s formalisation by AI review rather than an independent human cryptographer or a machine-checked formalization — see Open obligations.

The classical picture was settled and clean: four rounds give a strong PRP from a non-invertible pseudorandom round function. The quantum picture, as of Unruh’s 2023 note, was that four rounds are broken, five were unknown, and no round count had a proof. Carolan’s 2025 paper changes the last part decisively: seven rounds now have a proof, with an explicit (if loose — $\Omega(N^{1/12})$, “exponential in the size of an input to the permutation,” in the paper’s own words) query lower bound.

This entry, c/0036, and c/0037 all trace to one 22-page Unruh note, which for a long time offered one conjectural tool (c/0036) and two motivating applications (c/0037 and this page). That picture is now out of date in a specific way: this page and c/0037 are both fully resolved by Carolan’s 2025 paper, and resolved unconditionally — via Carolan’s own, directly-proved compressed permutation oracle, not via Unruh’s original conjecture, which c/0036 explains is not the same object and is judged to remain open in its own right.

The five-round and six-round cases (between the refuted four and the now-proved seven) remain genuinely open; Carolan’s paper does not address them, and nothing here suggests seven is optimal rather than merely what the author’s technique reaches.

It also pairs with this archive’s oldest entry. c/0001 asks for exact full indifferentiability of 6-round Feistel from a random permutation, classically. Same construction, same shape of question — how many rounds suffice — and a different security notion in a different model. Neither implies the other, and reading them together is a good way to see that “how many Feistel rounds are enough” has no single answer, only one per notion — this page’s notion now has an answer (seven suffices), c/0001’s does not yet.

Resolved by a 2025 follow-up

Joseph Carolan’s Compressed Permutation Oracles (Cryptology ePrint Archive 2025/1734, accepted STOC 2026, also arXiv:2509.18586) states in its own abstract: “We then apply this framework to show that the Feistel construction with seven rounds is a strong quantum PRP, resolving an open question of (Zhandry, 2012).” The technique — a redesigned compressed permutation oracle, proved sound, with the twirling machinery reused for Feistel specifically — is described in the Proof tab above.

No independent human or machine-checked review of Carolan’s proof yet. This page’s Proof tab confirms Theorem 6.5’s statement and its explicit dependence on Theorem 5.19, checked directly against the paper’s PDF. It does not independently re-derive the twirling/cromulence argument of Section 6, or the proof of Theorem 5.19. proof_review is graded ai for exactly this reason.
Not yet formalized. Neither this page’s statement nor Carolan’s proof has a Lean formalization; statement_formal, statement_match, and proof_formal all remain open.
The five- and six-round cases remain open. Carolan’s paper proves seven rounds suffice but says nothing about whether fewer (above the refuted four) also do. Settling five or six rounds, or showing seven is tight, is untouched by this resolution.
Independently check the pseudorandom-round-function lift. Carolan’s paper asserts, without full proof in the portion read here, that the random-round-function result is “query-indistinguishable from the case where the round functions are pseudorandom” — a reviewer should verify this hybrid argument rather than take the remark at face value, since it is what connects this page’s information-theoretic statement to the “strong quantum PRP” form in the paper’s abstract.
Re-derive or repair the published four-round forward-only proof this page’s Statement reports as flawed (Hosoyamada–Iwata), so the weaker statement has a sound reference — Carolan’s paper corroborates the existence of a bug and cites a 2024 erratum, but this page has not resolved either the original claim or the erratum to a specific, named paper.
Formalize the statement in Lean. Quantum oracle access with an inverse oracle needs writing down first, as it does for c/0036 and c/0037.