On the Indierentiability of Key-Alternating Feistel Ciphers with No Key Derivation⋆

Abstract. Feistel constructions have been shown to be indierentiable from random permutations at STOC 2011. Whereas how to properly mix the keys into an un-keyed Feistel construction without appealing to domain separation technique to obtain a block cipher which is provably secure against known-key and chosen-key attacks (or to obtain an ideal cipher) remains an open problem. We study this, particularly the basic structure of NSA's SIMON family of block ciphers. SIMON family takes a construction which has the subkey xored into a halve of the state at each round. More clearly, at the i-th round, the state is updated according to (xi, xi−1) 7 → (xi−1 ⊕ Fi(xi) ⊕ ki, xi) For such key-alternating Feistel ciphers, we show that 21 rounds are suf-cient to achieve indierentiability from ideal ciphers with 2n-bit blocks and n-bit keys, assuming the n-to-n-bit round functions F1,..., F21 to be random and public and an identical user-provided n-bit key to be applied at each round. This gives an answer to the question mentioned before, which is the rst to our knowledge