Pseudorandom Permutations

Block-cipher-style constructions analyzed as permutations that should be indistinguishable from a uniformly random one.

Status	Statement	Tags
	192-Round AES Pairwise Independence Theorem 7 proves the bound for 192-round censored AES – real AES S-boxes and mixing layer, but a subset of the mixing layers removed. The source conjectures the same round count suffices for AES itself, and calls proving it an outstanding open problem. The best proved bound for actual AES is Liu, Tessaro and Vaikuntanathan’s, which needs more than 9000 rounds. 4 open	Block Ciphers Limited Independence Pseudorandom Permutations T Wise Independencetight-bound
	Constant-round Luby–Rackoff, quantum Resolved for r=7. Carolan (Compressed Permutation Oracles, ePrint 2025/1734, STOC 2026) proves seven-round Luby-Rackoff with truly random round functions is indistinguishable from a random invertible permutation against Omega(N^{1/12}) bidirectional quantum queries (his Theorem 6.5), exactly this page’s conjecture with r=7 – and states, without full proof here, that the result lifts to pseudorandom round functions (the strong qPRP form) by a standard hybrid argument. The paper’s own abstract calls this ‘resolving an open question of (Zhandry, 2012).’	Feistel Networks Pseudorandom Permutations Quantum Query Complexityotherequivalenceresearch-solved
	6-round Feistel indifferentiability Whether 6-round Feistel is fully indifferentiable from a random permutation is open, bridging the proven r=5 attack and the proven r>=8 construction. 2 open	Feistel Networks Indifferentiability Pseudorandom Permutationsothertight-bound
	Generalized mirror theory The fully generalized Mirror Theory bound for arbitrary cycle-consistent multi-graphs up to the information-theoretic limit is open; current techniques only reach component size O(N^{1/4}). 2 open	Block Ciphers Mirror Theory Pseudorandom Permutationslower-bound
	Logarithmic independence implies PRP Open at independence order log n. The same implication is refuted at order 4 and at every constant order by an explicit construction; the logarithmic-order form is untouched, and no unconditional proof of it can be expected. 5 open	Limited Independence Pseudorandom Permutationscharacterization
	Compressed permutation oracle soundness Still open as formalized, but the underlying research question – can the compressed-oracle technique be extended to permutations at all – is now resolved in the affirmative by a different construction. Carolan (Compressed Permutation Oracles, ePrint 2025/1734, STOC 2026) proves his own compressed permutation oracle unconditionally sound. That oracle is, in his own words, ‘similar to that of Unruh [Unr23], though we explicitly and unitarily maintain injectivity of the database’ – a change that goes beyond resolving Unruh’s own left-open choice of how the flipping operator acts on non-injective inputs. Whether Unruh’s original construction (for an arbitrary such choice) is itself sound remains, on the reading defended here, unestablished.	Compressed Oracle Pseudorandom Permutations Quantum Query Complexityotherequivalence
	Censoring can only hurt Open. The censored side is proved at essentially optimal round count with matching lower bounds; what is missing is the transfer of any such bound to uncensored AES at the same round count. 5 open	Block Ciphers Pseudorandom Permutationslower-bound
	AES t-Wise Independence, t > 2 Named by the source as the first of the two outstanding open problems that come of its work. It proves almost pairwise independence (t = 2) for multi-round AES with independent round keys, and an existential t-wise result for key-alternating ciphers with most permutations, but nothing for concrete AES beyond t = 2. Its Appendix B attacks 4-wise independence in the width-1 case with the same S-box. 4 open	Block Ciphers Limited Independence Pseudorandom Permutations T Wise Independencecharacterizationbarrier (ai)