The Iterated Random Permutation Problem with Applications to Cascade Encryption

Brice Minaud; Yannick Seurin

Paper 2015/504

The Iterated Random Permutation Problem with Applications to Cascade Encryption

Brice Minaud and 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: A minor revision of an IACR publication in CRYPTO 2015
Keywords: iterated random permutation problem block cipher pseudorandom permutation cascade encryption
Contact author(s): brice minaud @ gmail com
History: 2015-05-27: received
Short URL: https://ia.cr/2015/504
License: CC BY

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}
}