How can you efficiently create a pseudorandom permutation with a large domain given a PRP with a small domain? Meaning: given an $n$-bit PRP, how can I create an $n k$-bit PRP?

I'm only interested in security up to $C 2^{\frac{n}{2}}$ messages, when $C$ is a reasonably-sized constant. For a power-of-2 $k$, the Luby-Rackoff construction essentially achieves this, although it requires $k^2$ calls to the PRF.


The cascade construction extends a PRF (in particular, a PRP) with fixed input length to a PRF with an arbitrarily large input length. If you want a PRP with large input length, you can use the Luby-Rackoff/Feistel transformation on the large-input PRF obtained from the cascade.

The cascade construction is analogous to the Merkle-Damgard paradigm for extending a fixed-input-length compression function to a hash function with arbitrary input length, except that cascade uses a secret-key primitive (the given PRP) in place of the compression function. The secret keys for the small- and large-input PRFs are exactly the same size, and the number of invocations of the small-input PRF is the ratio of the input lengths (large divided by small). Both of these efficiency measures are about the best one could hope for.

Let $F \colon \{0,1\}^k \times \{0,1\}^\ell \to \{0,1\}^k$ be the given PRF, where the first input denotes the "key," and denote $F_y(\cdot) = F(y,\cdot)$. Note that the PRF output and key lengths must be equal. If $F$ is a PRP, then $\ell=k$.

For a secret key $y \in \{0,1\}^k$ and an input $x = x_1 x_2 \cdots x_n$ where each $x_i$ is a block of length $k$ (the input length of the original PRF $F$), we compute the cascade iteratively as: $y_0 = y$, and $y_i = F_{y_{i-1}}(x_i)$ for $i=1,\ldots,n$; the final output is $y_n$. In words, the output on block $x_i$ becomes the key for the next invocation, on $x_{i+1}$.

Bellare, Canetti, and Krawczyk analyzed the cascade construction in http://cseweb.ucsd.edu/~mihir/papers/cascade.html . They proved that as long as the large inputs $x$ are encoded in a prefix-free manner (in particular, if all inputs have the same length), then the cascade construction yields a secure PRF. Concrete bounds may be found in the paper.


There are generic constructions along the lines of a PRP is a PRF, which can be extended to have larger input and output, which can then be used in the Luby-Rackoff Feistel construction.

You can also use more specific block cipher modes like EME. I would expect these to be more efficient than more generic constructions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.