Paper 2013/255

How to Construct an Ideal Cipher from a Small Set of Public Permutations

Rodolphe Lampe and Yannick Seurin

Abstract

We show how to construct an ideal cipher with $n$-bit blocks and $n$-bit keys (\emph{i.e.} a set of $2^n$ public $n$-bit permutations) from a small constant number of $n$-bit random public permutations. The construction that we consider is the \emph{single-key iterated Even-Mansour cipher}, which encrypts a plaintext $x\in\{0,1\}^n$ under a key $k\in\{0,1\}^n$ by alternatively xoring the key $k$ and applying independent random public $n$-bit permutations $P_1,\ldots, P_r$ (this construction is also named a \emph{key-alternating cipher}). We analyze this construction in the plain indifferentiability framework of Maurer, Renner, and Holenstein (TCC 2004), and show that twelve rounds are sufficient to achieve indifferentiability from an ideal cipher. We also show that four rounds are necessary by exhibiting attacks for three rounds or less.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
block cipherideal cipheriterated Even-Mansour cipherkey-alternating cipherindifferentiability
Contact author(s)
yannick seurin @ m4x org
History
2013-05-08: received
Short URL
https://ia.cr/2013/255
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/255,
      author = {Rodolphe Lampe and Yannick Seurin},
      title = {How to Construct an Ideal Cipher from a Small Set of Public Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2013/255},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/255}},
      url = {https://eprint.iacr.org/2013/255}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.