Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / iterated random permutation problem, block cipher, pseudorandom permutation, cascade encryption

Original Publication (with minor differences): IACR-CRYPTO-2015

Date: received 26 May 2015

Contact author: brice minaud at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150527:094243 (All versions of this report)

Short URL: ia.cr/2015/504

Discussion forum: Show discussion | Start new discussion