The Iterated Random Permutation Problem with Applications to Cascade Encryption

Brice Minaud; Yannick Seurin

Paper 2015/504 Original: eprint.iacr.org/2015/504 ↗

The Iterated Random Permutation Problem with Applications to Cascade Encryption

Brice Minaud

Yannick Seurin

Abstract

We introduce and study the iterated random permutation problem, which asks how hard it is to distinguish, in a black-box way, the r-th power of a random permutation from a uniformly random permutation of a set of size N. We show that this requires Omega(N) queries (even for a two-sided, adaptive adversary). As a direct application of this result, we show that cascading a block cipher with the same key cannot degrade its security (as a pseudorandom permutation) more than negligibly.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
History: 2015-05-27: last updated; 2015-05-27: published
Short URL: https://ia.cr/2015/504
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2015/504,
      author = {Brice Minaud and Yannick Seurin},
      title = {The Iterated Random Permutation Problem with Applications to Cascade Encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/504},
      year = {2015},
      url = {https://eprint.iacr.org/2015/504}
}