On Linear Systems of Equations with Distinct Variables and Small Block Size: Proof of a Combinatorial Conjecture with Applications to Random Feistel Schemes

摘要

In this paper we will prove the Conjecture 8.1. of [7]. We call it "Conjecture P_i ⊕ P_j". It is a purely combinatorial conjecture that has however some cryptographic consequence. For example, from this result we can improve the proven security bounds on random Feistel schemes with 5 rounds: we will prove that no adaptive chosen plaintext/chosen ciphertext attack can exist on 5 rounds Random Feistel Schemes when m 2~n. This result reach the optimal bound of security against an adversary with unlimited computing power (but limited by m queries) with the minimum number of rounds. It solves the last case of a famous open problem (cf [8]). An extended version of this paper is available from the author.