13
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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.) $\endgroup$
    – user991
    Commented Nov 21, 2012 at 10:31
  • $\begingroup$ @Ricky Demer: I amended the definition to allow that. I'm eager to see how that makes a difference. $\endgroup$
    – fgrieu ♦
    Commented Nov 21, 2012 at 11:35
  • $\begingroup$ Just curious, what is your distinguisher for your first proposal ? $\endgroup$
    – Alexandre Yamajako
    Commented Nov 21, 2012 at 13:35
  • $\begingroup$ @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$. $\endgroup$
    – fgrieu ♦
    Commented Nov 22, 2012 at 6:51

3 Answers 3

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Interestingly, none of these constructions beat the birthday bound while using a single key and working over the same domain. $\endgroup$
    – David Cash
    Commented Nov 21, 2012 at 20:58
11
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Nov 21, 2012 at 18:55
  • $\begingroup$ 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. $\endgroup$
    – Thomas
    Commented Nov 21, 2012 at 19:19
  • $\begingroup$ 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). $\endgroup$
    – fgrieu ♦
    Commented Nov 21, 2012 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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