We want to explicitly construct a _good_ (as tentatively defined below) Pseudo-Random Function $F$ with $b$-bit input and output, from _one_ Pseudo-Random Permutation $E$ of $b$-bit, as instantiated in practice by TDEA for $b=64$ or AES-256 for $b=128$, and a 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.

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][1]. 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 the weakest kind of security argument.

  [1]: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare