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 major differences): IACR-TCC-2015
Date: received 3 Oct 2014, last revised 10 Jan 2015
Contact author: guochun at iie ac cn
Available format(s): PDF | BibTeX Citation
Note: The revised full version.
Version: 20150111:062404 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]