How many Feistel rounds suffice against a quantum adversary?
Four are broken, five are unknown, and no round count has a proof
Motivation
Classically this is a textbook result: four rounds of Luby–Rackoff turn a non-invertible pseudorandom function into a strong pseudorandom permutation. The construction is the Feistel network, and the analysis is standard.
Quantumly, almost none of that survives. A quantum chosen-ciphertext attack rules out four rounds outright. Five rounds are not excluded by anything known — and no round count, at any value, has a proof. That gap is one of the sharper illustrations of how much less is provable once the adversary may query in superposition and invert.
Provenance and history
The question as recorded here is from Unruh, Towards compressed permutation oracles, ePrint 2023/770, ASIACRYPT 2023, pp. 369–400, which poses and motivates it without proving anything about Luby–Rackoff itself. Tracked as c/0038.
Two facts from that source shape the state of play, and both are discouraging for anyone hoping to extend existing work:
- Four rounds are refuted. “We know that four rounds are not sufficient”, by a known quantum chosen-ciphertext attack on Feistel ciphers.
- The published proof of the weaker forward-only four-round claim is reported flawed. So the literature offers no working technique even for the weaker statement — a would-be prover may have to re-derive a claim before generalising it.
The source names both by reference number only, and this archive has not resolved either to a paper; c/0038 marks that gap rather than guessing.
Two versions of the question
| version | round functions | status |
|---|---|---|
| indistinguishable from a random invertible permutation | drawn uniformly at random — information-theoretic | open for every \(r\); this is what c/0038 states |
| strong qPRP | pseudorandom | open; the source’s own framing, and the cryptographically useful form |
The first is the natural first step toward the second, and keeping them apart matters because only the first is unconditional.
Why it is stuck
The obstruction is not specific to Feistel. No existing technique reaches superposition access to an invertible permutation — which is exactly the gap the compressed permutation oracle is built to fill, and why this question appears in a paper about that tool rather than in a paper about block ciphers.
The source adds a two-for-one observation worth checking: a proof of this conjecture via the compressed permutation oracle would additionally establish the oracle’s soundness for free, settling c/0036. That claim is asserted rather than proved, and verifying it is listed as an obligation on c/0038.
A companion question, from the other end of this archive
c/0001 — the oldest statement on this site — asks for exact full indifferentiability of 6-round Feistel from a random permutation, classically. Same construction, same shape of question, different security notion and different adversary. Neither implies the other.
Read together they make a point worth stating plainly: “how many Feistel rounds are enough” has no single answer. It has one answer per security notion, and for the quantum notion here there is not yet any answer at all.