Cryptology ePrint Archive: Report 2014/786

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