International Association
for Cryptologic Research

Feistel constructions have been shown to be indifferentiable

from random permutations (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 resists known-key and chosen-key attacks remains

an open problem. We study this. NSA\'s SIMON family of block

ciphers 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

$$(x_i,x_{i-1})\\mapsto(x_{i-1}\\oplus F_i(x_i)\\oplus k_i,x_i)$$

For such key-alternating Feistel ciphers, we show that 21

rounds are sufficient to achieve indifferentiability from ideal

ciphers with $2n$-bit blocks and $n$-bit keys, assuming the

$n$-to-$n$-bit round functions $F_1,\\ldots,F_{21}$ to be random

and public and an identical user-provided $n$-bit key to be

applied at each round. This gives a solution to the problem

mentioned before, and is the first to study the

indifferentiability of key-alternating Feistel ciphers to our

knowledge.