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

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

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]

View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized

Open for every $r$, and both nearby data points cut against easy progress.

Four rounds are refuted. A known quantum chosen-ciphertext attack on Feistel ciphers rules them out: “We know that four rounds are not sufficient.” So any proof must start at five, and the source says plainly that “nothing excludes that, e.g., five-round Luby-Rackoff could be a strong qPRP.”

The one published proof of the weaker claim is reported flawed. There is a published proof that four-round Luby–Rackoff is a (forward-only) qPRP, and the source reports it contains a flaw. That matters for anyone planning to extend it: the literature does not currently offer a working technique for even the weaker statement, so the first step may be re-deriving a claim rather than generalising one.

Why it is stuck, and why this paper mentions it. The obstruction is the one that motivates the whole compressed-permutation-oracle programme — no existing method reaches superposition access to an invertible permutation. The source’s observation is a two-for-one: “If we use the compressed permutation oracle methodology to show that some construction (e.g., Luby-Rackoff) implements a random permutation (or strong qPRP), then” the argument would additionally establish the oracle’s soundness for free. So a CPO-based proof of this conjecture would also settle c/0036.

The source proves nothing about Luby–Rackoff itself. This page records a question it poses and motivates.

The classical picture is settled and clean: four rounds give a strong PRP from a non-invertible pseudorandom round function. That is a textbook result. The quantum picture is that four rounds are broken, five are unknown, and no round count has a proof — which is a fair measure of how much less is provable once the adversary may query in superposition and invert.

This entry is the third from one 22-page note, alongside c/0036 and c/0037, and the three sit in a sensible order: c/0037 is the simplest question nobody can answer, c/0036 is the tool proposed for such questions, and this is the headline application the tool is aimed at. None of the three is proved.

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.

Prove the conjecture for some constant $r \ge 5$, or extend the four-round attack to all constant round counts.
Re-derive or repair the published four-round forward-only proof the source reports as flawed, so the weaker statement has a sound reference.
Settle the five-round case specifically, which the source singles out as not excluded.
Establish the pseudorandom-round-function version (strong qPRP) once the random-function version is known, and record whether the step is routine.
Check the claimed two-for-one: verify that a CPO-based proof really would establish c/0036, which the source asserts without proving.
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.