**On the Indifferentiability of Key-Alternating Feistel Ciphers with No Key Derivation**

*Chun Guo and Dongdai Lin*

**Abstract: **Feistel constructions have been shown to be indifferentiable 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
$$(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 an answer to the question mentioned before, which is the first to our knowledge.

**Category / Keywords: **block cipher, ideal cipher, indifferentiability, key-alternating cipher, Feistel cipher.

**Original Publication**** (with minor differences): **IACR-TCC-2015

**Date: **received 3 Oct 2014, last revised 7 May 2015

**Contact author: **guochun at iie ac cn

**Available format(s): **PDF | BibTeX Citation

**Note: **Change the references. Also revise an error due to presentation.

**Version: **20150507:080221 (All versions of this report)

**Short URL: **ia.cr/2014/786

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]