Cryptology ePrint Archive: Report 2012/035
Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations
Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Francois-Xavier Standaert, John Steinberger, Elmar Tischhauser
Abstract: This paper considers---for the first time---the concept of
key-alternating ciphers in a provable security setting.
Key-alternating ciphers can be seen as a generalization of a
construction proposed by Even and Mansour in 1991. This
construction builds a block cipher $PX$ from an $n$-bit permutation $P$
and two $n$-bit keys $k_0$ and $k_1$, setting $PX_{k_0,k_1}(x)=k_1\oplus P(x\oplus k_0)$.
Here we consider a (natural) extension of the Even-Mansour construction
with $t$ permutations $P_1,\ldots,P_t$ and $t+1$ keys, $k_0,\ldots,
k_t$. We demonstrate in a formal model that such a cipher is secure in the
sense that an attacker needs to make at least $2^{2n/3}$ queries to
the underlying permutations to be able to distinguish the construction
from random. We argue further that the bound is tight for $t=2$ but
there is a gap in the bounds for $t>2$, which is left as an open and
interesting problem. Additionally, in terms of statistical attacks, we show that the distribution of Fourier
coefficients for the cipher over all keys is close to ideal.
Lastly, we define a practical instance of the construction with $t=2$
using AES referred to as AES$^2$. Any attack on AES$^2$ with complexity below $2^{85}$ will have to make use of AES with a fixed known key in a non-black box manner. However, we conjecture its security is $2^{128}$.
Category / Keywords: secret-key cryptography / Block ciphers, provable security, Even-Mansour construction, AES
Publication Info: extended abstract to appear at Eurocrypt 2012, this is the full version
Date: received 22 Jan 2012, last revised 30 Jan 2012
Contact author: g leander at mat dtu dk
Available format(s): PDF | BibTeX Citation
Version: 20120130:091633 (All versions of this report)
Short URL: ia.cr/2012/035
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]