Paper 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.

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

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in TCC 2015
Keywords
block cipherideal cipherindifferentiabilitykey-alternating cipherFeistel cipher.
Contact author(s)
guochun @ iie ac cn
History
2015-05-07: last of 8 revisions
2014-10-07: received
See all versions
Short URL
https://ia.cr/2014/786
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/786,
      author = {Chun Guo and Dongdai Lin},
      title = {On the Indifferentiability of Key-Alternating Feistel Ciphers with No Key Derivation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/786},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/786}},
      url = {https://eprint.iacr.org/2014/786}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.