Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
How can we construct a (pseudo) random permutation from a (pseudo) random function ?
I've seen a method from Luby-Rackoff which allows to construct a PRP of length $2N$ from a PRF of input/output length $N$. Is there a method to keep the same length $N$ ?
I'm looking for a method that has better security bounds than truncating the output of a $N$-bits output pseudorandom function to obtain an output of $N/2$-bits and using the Luby-Rackoff construction.
There are so many possible solutions here. Without giving your requirements more carefully, it's just not possible to tell what would count as a valid solution. Here are a bunch of schemes that offer better security than simply truncating to $N/2$ bits and applying 4 rounds of Luby-Rackoff:
For instance, one approach is to truncate the random function to $N/2$ bits, then use 6 or more rounds of the Luby-Rackoff construction. Paterin has a paper at FSE 1998 that apparently proves that 6 rounds gives security for up to $O(2^{3N/8})$ chosen plaintext/ciphertext queries. He also has a later paper at Crypto 2003 that apparently proves that 10 rounds is enough for security for up to $O(2^{N(1-\epsilon)/2})$ chosen plaintext/ciphertext queries. Don't ask me to explain the proofs; I don't understand them. I am not aware of any concrete-security versions of these results, so it's hard to know exactly how much security this gives you in practice.
Another approach is to truncate the random function to 1 bit of output (and $N-1$ input bits), then build a maximally unbalanced Feistel network that uses $4N$ rounds. Naor and Reingold showed (Journal of Cryptology, Jan 1999) that this will give security for up to $O(2^{N/2})$ chosen plaintext/ciphertext queries. (Technically speaking, their result assumed that you used a pairwise-independent permutation, then $2N$ rounds of unbalanced Feistel, than another pairwise-independent permutation, so if you really care about provable security, you could use that: but I suspect their results would likely apply to $4N$ rounds of unbalanced Feistel as well.)
Even better yet, if you do enough rounds of maximally unbalanced Feistel network, you can get arbitrarily close to $O(2^N)$ security. Truncate the random function to one that takes $N-1$ input bits and has 1 output bit, and use it in an unbalanced Feistel network. Morris, Rogaway, and Stegers proved at Crypto 2009 that, if you do $4RN$ rounds of this, you get security up to $O(2^{N(1-1/R)})$ chosen plaintext/ciphertext queries. For instance, if you do $40N$ rounds, you get security up to something like $O(2^{0.9N})$ chosen plaintext/ciphertext queries. That's a very impressive result. If maximizing security is your goal, this might be your best bet.
Another approach is to truncate the random function to one on $N/2$ bits, then apply a suitable Benes network construction. Aiello and Venkatesan proved in Eurocrypt 1996 that, with four rounds, this gives you security for up to $O(2^{N/2})$ chosen plaintext/ciphertext queries.
One keyword that may help you find still more results is "Luby-Rackoff beyond the birthday bound".
There is a generic construction called Permutator, which can turn a seekable stream of random bits into a permutation. A "seekable stream" is obtained from a PRF by applying the PRF on an input index.
This construction works with any target space (it generates a permutation of a space of size $n$ where $n$ is not necessarily a power of 2). Also it is "perfect", meaning that every possible permutation of the space of size $n$ can be selected, with probability exactly $1/n!$, contrary to, for instance, Feistel schemes which necessarily implement even permutations only. This can have some some importance when targeting a permutation in a small domain (e.g. a permutation of all sequences of 8 decimal digits).
Unfortunately, implementing Permutator, as described in the article, implies doing some computations in arbitrary precision arithmetics, which is doable but very slow. This is a consequence of the sampling method (based on rejection) for the hypergeometric distribution, that we used: that method is unbiased but expensive.
There is a recent paper by Hoang, Morris & Rogaway which proposes an alternative construction of PRPs from PRFs.
Viet Tung Hoang, Ben Morris, Phillip Rogaway, An Enciphering Scheme Based on a Card Shuffle, CRYPTO 2012
The construction has a few nice features. First, the domain of the PRF is preserved, which is one of your requirements. Second, it provides security beyond the birthday bound. The construction is still quite simple, but the tradeoff compared to Luby-Rackoff is an increase in the number of rounds (logarithmic).
You can see the slides & video of the associated talk at the CRYPTO 2012 program page.
edit: Hm, actually this construction uses a one-bit PRF to build a PRP. Still, you could think of an $n$-bit PRF as $n$ distinct 1-bit PRFs, and use a different bit for each round of this construction. Certainly $n$ rounds would be plenty. Also, you have $n$ distinct 1-bit PRFs that are all keyed by the same key. So your key size would not increase going from PRF to PRP (as it does in Luby-Rackoff -- you need independent keys for each round of the Feistel network).
