How to construct a good PRF from a block cipher?

We want to explicitly construct a good (as tentatively defined below) Pseudo-Random Function $F$ with $b$-bit input and output, from (preferably just) one Pseudo-Random Permutation $E$ of $b$-bit, as instantiated in practice by TDEA for $b=64$ or AES-256 for $b=128$, and one fixed random secret key.

I tentatively define a good PRF to be one indistinguishable (with small constant advantage) from a random function, assuming $2^{b(1-\epsilon)}$ queries to an oracle implementing our construction of $F$ from $E$, and delegating invocations of $E$ (edit: and in addition of $E^{-1}$ if that helps) to a random oracle for that. Fix this definition as necessary (Update: I'm told by the answers that for $\epsilon<1/2$, this is roughly what's called a PRF with beyond the birthday bound security).

Are there simple constructions of $F$ from $E$ with a security argument?

$F(x)=E(x)$ is squarely unfit: it can be distinguished from a random function by detecting collisions after $2^{b/2}$ distinct queries, which happens with sizable probability for a random function but not for a random permutation. That can even be done with constant memory, using Floyd's cycle finding. A distinguisher can also be built against $F(x)=E(x)\oplus x$.

Right now I fail to find a distinguisher for $F(x)=E(E(x)\oplus x)$, but that's not even a weak security argument. Update: If the security of that is unprovable, I'm still interested by a distinguishing attack, in order to get a feeling of how insecure in practice that could be.

-
Is the construction of $F$ allowed to use $E^{-1}$? $\:$ (I can't think of a way to do it in either case, but that might help.) – Ricky Demer Nov 21 '12 at 10:31
@Ricky Demer: I amended the definition to allow that. I'm eager to see how that makes a difference. – fgrieu Nov 21 '12 at 11:35
Just curious, what is your distinguisher for your first proposal ? – Alexandre Yamajako Nov 21 '12 at 13:35
@Alexandre Yamajako: (fixed) for $F(x)=E(x)$, in the game of distinguishing $F$ from a random function: set $x=y=0$; repeat $⌊2^{b/2}/3⌋$ times: set $x=F(F(x))$, if $x=y$ say "random" and stop, else set $y=F(y)$, if $x=y$ say "random" and stop; say "non-random" with odds 51%, else say "random". For $F(x)=E(x)⊕x$, apply the same distinguisher to $G$ defined by $G(x)=F(x)⊕x$ instead of $F$. – fgrieu Nov 22 '12 at 6:51

What you're looking for is often called a construction of a PRF with "beyond the birthday bound security," and you can probably find some constructions by searching on variants of that term.

For concreteness, this paper by Iwata (alternate link) almost gives a solution to your problem: The only deficiencies are that the resulting $F$ has inputs one bit narrower than $E$, and it does not achieve your definition of security for every $\varepsilon > 0$. Specializing that construction down to your setting, and using your notation, it defines $F(x)$ for $x\in\{0,1\}^{b-1}$ as $$F(x) = E(x\|0)\oplus E(x\|1),$$ where $\|$ denotes concatenation. Its proof applies for a number queries well beyond $2^{b/2}$, which is obviously non-trivially better than the direct $F(x) = E(x)$ construction.

-

I agree with David Cash that what you are looking for is a construction of a PRF with "beyond the birthday bound" security. There has been a variety of work on this topic.

Stefan Lucks analyzes several simple constructions:

• SUM$^2$: Here $F_{K,K'}(x) = E_K(x) \oplus E_{K'}(x)$. This has security for up to about $2^{2b/3}$ queries, which is better than the trivial construction.

• SUM$^d$: This is the obvious generalization: $F_{K_1,\dots,K_d}(x) = E_{K_1}(x) \oplus \dots \oplus E_{K_d}(x)$. This has security up to about $2^{db/(d+1)}$ queries.

• TWIN$^2$: Here $F_K(x) = E_K(x||0) \oplus E_K(x||1)$ (the same construction as David Cash mentions). This has security for up to about $2^{2b/3}$ queries.

• TWIN$^d$: Here $F_K(x) = E_K(dx+0) \oplus E_K(dx+1) \oplus \dots \oplus E_K(dx+d-1)$, where we consider $0 \le x <2^b/d$. This has security up to about $2^{db/(d+1)}$ queries.

Here is the paper:

I think there is still more work out there on this topic.

-
Interestingly, none of these constructions beat the birthday bound while using a single key and working over the same domain. – David Cash Nov 21 '12 at 20:58

I think this paper may help:

M. Bellare, T. Krovetz and P. Rogaway (1998), "Luby-Rackoff backwards: Increasing security by making block ciphers non-invertible", Advances in Cryptology - EUROCRYPT '98, Lecture Notes in Computer Science, Vol. 1403.

"Abstract: We argue that the invertibility of a block cipher can reduce the security of schemes that use it, and a better starting point for scheme design is the non-invertible analog of a block cipher, that is, a pseudorandom function (PRF). Since a block cipher may be viewed as a pseudorandom permutation, we are led to investigate the reverse of the problem studied by Luby and Rackoff, and ask, how can one transform a PRP into a PRF in as security-preserving a way as possible? The solution we propose is "data-dependent re-keying." As an illustrative special case, let $E: \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ be the block cipher. Then we can construct the PRF $F$ from the PRP $E$ by setting $F(k,x) = E(E(k,x),x)$. We generalize this to allow for arbitrary block and key lengths, and to improve efficiency. We prove strong quantitative bounds on the value of data-dependent re-keying in the Shannon model of an ideal cipher, and take some initial steps towards an analysis in the standard model."

A PDF of the paper is available here. (The PDF link on the abstract page is wrong, it leads to the PS version.)

-
I'm not sure why this got downvoted. It looks like the sort of thing that fgrieu is looking for: it is a construction of a PRF with "beyond the birthday bound" security, out of a block cipher. Its main limitation is that they can only prove good security in the ideal cipher model (which is a much stronger model than assuming that the block cipher is a PRP), but still, it's relevant and a result. – D.W. Nov 21 '12 at 18:55
Perhaps the answer should contain more than just a link, i.e. shortly summarizing the results given by the paper? I didn't downvote though. – Thomas Nov 21 '12 at 19:19
I upvoted, as the construct fits the goal in the title. But it does not fit the more detailed statement, which requires that F is built from one E (in a block-cipher context: no re-keying). – fgrieu Nov 21 '12 at 20:39