Exact Full Indifferentiability of 6-Round Feistel Networks

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

Abstract

The Feistel construction is a standard mechanism for converting public random functions into public pseudorandom permutations. While 5-round Feistel is provably non-indifferentiable from a random permutation (Coron, Patarin & Seurin, CRYPTO 2008), and 8-round Feistel is fully indifferentiable (Dai & Steinberger, CRYPTO 2016), the exact full indifferentiability status of 6-round Feistel remains one of the longest-standing open problems in symmetric-key theoretical cryptography.

Formal Setup

Let $\mathcal{F}_n = \{F : \{0,1\}^n \to \{0,1\}^n\}$ denote the set of all $n$-bit to $n$-bit functions, and let $\mathcal{P}_{2n} = \mathrm{Perm}(\{0,1\}^{2n})$ denote the set of all $2n$-bit permutations.

Definition (Feistel Network)

Given $r$ round functions $\mathbf{F} = (F_1, \dots, F_r) \in (\mathcal{F}_n)^r$, the $r$-round Feistel construction $\Psi^r[\mathbf{F}] : \{0,1\}^{2n} \to \{0,1\}^{2n}$ maps $(L_0, R_0) \mapsto (L_r, R_r)$ via the iterative update rule for $i = 1, \dots, r$:

\[ L_i = R_{i-1}, \qquad R_i = L_{i-1} \oplus F_i(R_{i-1}). \]

Definition (Indifferentiability Framework, Maurer, Renner & Holenstein, TCC 2004)

A construction $C^{\mathbf{F}}$ using oracle access to ideal components $\mathbf{F}$ is indifferentiable from an ideal primitive $\mathcal{P}$ if there exists a stateful PPT simulator $\mathcal{S}$ with oracle access to $\mathcal{P}$ such that for every PPT distinguisher $\mathcal{D}$:

\[ \mathbf{Adv}_{C, \mathcal{S}}^{\mathrm{indiff}}(\mathcal{D}) := \left| \Pr\left[ \mathcal{D}^{C^{\mathbf{F}}, \mathbf{F}}(1^n) = 1 \right] - \Pr\left[ \mathcal{D}^{\mathcal{P}, \mathcal{S}^\mathcal{P}}(1^n) = 1 \right] \right| \le \epsilon(n), \]

where $\epsilon(n)$ is negligible in the security parameter $n$. (See Maurer, Renner & Holenstein, TCC 2004.)

The 6-Round Open Conjecture

Conjecture (Full Indifferentiability of 6-Round Feistel)

Let $\mathbf{F} = (F_1, \dots, F_6) \stackrel{\$}{\leftarrow} (\mathcal{F}_n)^6$ be independent random functions, and let $\mathcal{P} \stackrel{\$}{\leftarrow} \mathcal{P}_{2n}$ be a uniform random permutation.

There exists an efficient simulator $\mathcal{S}^{\mathcal{P}}$ making at most $\mathrm{poly}(q)$ queries to $\mathcal{P}$ such that for any distinguisher $\mathcal{D}$ making at most $q$ total queries to its oracles:

\[ \mathbf{Adv}_{\Psi^6, \mathcal{S}}^{\mathrm{indiff}}(\mathcal{D}) \le O\left( \frac{q^k}{2^n} \right), \]

for some universal polynomial degree $k \ge 2$.

Current Bounds and Theoretical Barrier

Indifferentiability status of $r$-round Feistel networks.
Rounds ($r$)	Status	Security Bound	Reference
$r \le 4$	Attackable	Non-Indifferentiable	folklore, a fortiori from the $r=5$ attack below
$r = 5$	Attackable	Non-Indifferentiable	Coron, Patarin & Seurin (2008)
$r = 6$	OPEN	Public / Sequential Indiff. Only	Mandal, Patarin & Seurin (2012)
$r \ge 8$	Proven	$O(q^8/2^n)$	Dai & Steinberger (2016)

Key open question: can a simulator construct consistent responses for queries $F_1, \dots, F_6$ without incurring exponential blowup in query history when handling middle-round path completions ($F_3, F_4$), or does a non-trivial distinguishing attack exist for $r=6$?

This conjecture is open — no proof exists yet.

Once (an attempt at) a proof exists, add its own .tex source and compiled PDF (e.g. latex/proof.tex / pdf/proof.pdf) and link them here, following the same convention as the statement.

Formal artifact.

Lean statement — autoformalized by Claude Sonnet 5; not yet checked by a human against the tex statement above.

Only the conjecture’s statement has been formalized so far (as a Lean theorem ending in sorry — see lean/Statement.lean), not a proof. Once a proof exists, set status.proof_informal/status.proof_review/status.proof_formal accordingly and regenerate the badge with scripts/status_badge.py.

The interest is entirely in the gap. Five rounds are attackable and eight are provably indifferentiable, so the open question is where between them full indifferentiability begins, and six is the first round count nobody can place. What is known at six is weaker than what this statement asks: public and sequential indifferentiability rather than full. So a resolution either way moves a boundary rather than adding a data point.

Nothing beyond this has been written here; the parameter lattice for the problem, and what the neighbouring round counts settle, is on the problem page.

Formalize the indifferentiability framework itself (simulator, distinguisher advantage) in Lean; only the bare conjecture statement has been formalized so far.
Either construct a simulator witnessing full indifferentiability at $r=6$, or exhibit a distinguishing attack.

Coron, Patarin and Seurin. The Random Oracle Model and the Ideal Cipher Model are Equivalent (CRYPTO 2008). The paper carrying the 5-round attack that fixes the lower end of the gap.
Mandal, Patarin and Seurin. On the Public Indifferentiability and Correlation Intractability of the 6-Round Feistel Construction (2012). What is known at six rounds, and it is weaker than what this statement asks.
Dai and Steinberger. Indifferentiability of 8-Round Feistel Networks (CRYPTO 2016). The upper end of the gap.
Maurer, Renner and Holenstein. Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology (TCC 2004). The framework the statement is posed in.