# Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)

I have a question about Pseudo Random Functions.

Let $f:\{0,1\}^m \times \{0,1\}^n → \{0,1\}^n$ be a secure PRF.

Define $F(k,x) = f(k,x) - f(k, x-1 \bmod 2^{n}) \bmod 2^{n}$.

Is $F$ is a secure PRF?

-
@figlesquidge et al: A definition of a secure Pseudo-Random Function family $\{0,1\}^m×\{0,1\}^n→\{0,1\}^n$ (with first parameter the key, $m$ unbounded, $n$ fixed) secure for $q$ queries could be on the tune of: for any fixed $\epsilon>0$; if some algorithm succeeds with odds at least $1/2+\epsilon$ in a game where the objective is to guess, from $q$ queries, the choice of a referee (choosing by fair coin toss) between A) the function being tested with a fixed random key and B) a random function $\{0,1\}^n→\{0,1\}^n$; then the algorithm has cost more than polynomial in $m$. –  fgrieu Mar 10 '14 at 16:09
re-revised: I'll assign the bounty at the end of the bounty period to the best answer according to the following criteria: 1) Includes a correct proof. 2) Uses a standard, or stated and consistent definition of a Pseudo-Random Function family. 3) Gives proof that $F$ is secure for the maximum number of queries $q$ given a small fixed $n$, for some consistent definition of that [see previous comment for an example of definition]. 4) Elegance. 5) Was first [date is that of the revision with essentially the argument in the final version]. –  fgrieu Mar 10 '14 at 16:32
@figlesquidge: DW transformed the question into what formerly was the extension that I suggested. It is easy to turn the answer to that new question into the answer to the original question [with $f:\{0,1\}^n×\{0,1\}^n→\{0,1\}^n$ ], as the condition at most $2^{n-1}$ queries is met by any polynomial adversary in the original question. –  fgrieu Mar 14 '14 at 17:07

Not if the attacker is given enough time to ask for the values $F(k,x)$ for all $2^n$ values of $x$. We have

$\Sigma_x F(k,x) = 0$

which is distinguishable from random.

-
... unless $f$ can be distinguished from random faster than that, in which case $F$ could still be "secuer", depending on whether that is supposed to mean "secure" or "securer". $\;$ –  Ricky Demer Mar 7 '14 at 6:08
With $n= 128$, how to prove $F$ indistinguishable from random? –  Jenifer Tran Mar 7 '14 at 6:41
@Jenifer Tran: as in any exercise of this kind, you would succeed if you could turn any hypothetical distinguisher for $F$ with advantage $\epsilon$ after $q$ queries, into a distinguisher for $f$ with advantage $\epsilon'$ after $q'$ queries, with $q'/q$ and $\epsilon/\epsilon'$ less than some bounds independent of the problem size $n$. –  fgrieu Mar 7 '14 at 8:05
@tylo: I believe that the proof can be summarized as "if you are limited to no more than $2^n-1$ queries, then if $f(x)$ is a random function, then $f(x)-f(x-1)$ is a random function", and then "if $f(x)-f(x-1)$ can be distinguished from a random function, then $f(x)$ is distinguished from a random function" –  poncho Mar 12 '14 at 17:23
That's one way to prove it. But you could also go argue that additions and subtractions are just circular shifts over the domain, and uniform distributions are invariant to circular shifts of this kind. In the end it comes down to: If you cant check the entire domain for the sum, you don't know if you deal with the function or just with the differences between two function values. Even if you query $2^n-1$ elements, the remaining element tells you whether it adds up to a specific sum or is drawn from uniform again –  tylo Mar 12 '14 at 17:39

Theorem. (Barring any errors, which are certainly possible): Let $A$ be any adversary attacking $F$. As long as $A$ makes fewer than $2^n$ queries, there is an adversary $B[A]$ attacking $f$, making at most twice the queries of $A$ and running in (roughly) the same time such that $\mathsf{Adv}^{\mathsf{prf}}_F(A) = \mathsf{Adv}^{\mathsf{prf}}_{f}(B[A]).$

That is, $F$ is as secure as $f$.

Intuition. First an informal overview. View F_k and f_k as tables. The adversary is filling in a table for F as he makes queries, and is trying to figure out if the values he's getting are random, or are based off the (unknown, randomly chosen) table f.

Here's a picture:

The adversary's next query is for F(4). If his oracle is really based on f (i.e., F is not a random function), then we have F(4) = f(4) - f(3). But the adversary already may have learned something about f(4) when he asked for F(5) = f(5) - f(4), and he may have learned something about f(3) when he asked for F(3) = f(3) - f(2), and he may have learned something about f(2) when he asked for F(2) = f(2) - f(1)...

...and...

And, crucially, that's where it stops. The fact that this chain eventually stops, which is implied by the fact that the number of queries is less than $2^n$, is vital to the argument.

Basically, the only points of f that

2. have some statistical dependence on whatever F(4) is (from the adversary's perspective)

...are those points shaded in light green. This is easy to see if one views f as being defined through "lazy sampling", with its outputs generated on-the-fly as needed.

If we're dealing with $2^n = 128$, then there will be 128^2 ways to fill out the green part of the table that are consistent with the adversary's knowledge of F, each of these ways is equally likely, and exactly 128 of them will result in F(4) = 17 (for example). Therefore the probability that F(4) = 17 (if F is based on f) is exactly 1/128. But this is the same probability that we'd have F(4) = 17 if F were a random function!

And that's the gist of the proof.

Proof.

We wish to bound the PRF security of $F$:

$\mathsf{Adv}^{\mathsf{prf}}_F(A) = \mathsf{Pr}(A^{F_k} = 1) - \mathsf{Pr}(A^{\rho} = 1)$,

where the probabilities are evaluated over the random choice of $k$ and random function $\rho : \lbrace 0, 1 \rbrace^n \rightarrow \lbrace 0, 1 \rbrace^n$

Let's start with a standard reduction to the information-theoretic setting. Given a function $g \lbrace 0, 1 \rbrace^n \rightarrow \lbrace 0, 1 \rbrace^n$, define $F[g](x) = g(x) - g(x - 1)$. (Subtraction and addition are understood to be modulo $2^n$ for the standard bit-encoding of the natural numbers.)

Let $\rho'$ be a random function. Then for any adversary $A$ making $q$ queries and running in time $t$:

\begin{align*} \mathsf{Adv}^{\mathsf{prf}}_F(A) &= \mathsf{Pr}(A^{F_k} = 1) - \mathsf{Pr}(A^{F[\rho']} = 1) + \mathsf{Pr}(A^{F[\rho']} = 1) - \mathsf{Pr}(A^{\rho} = 1)\\ & = \mathsf{Adv}^{\mathsf{prf}}_{f}(B[A]) + \mathsf{Pr}(A^{F[\rho']} = 1) - \mathsf{Pr}(A^{\rho} = 1) \end{align*}

where $B[A]$ is the adversary that makes at most $2q$ queries, runs in time $O(t)$, and simulates ${F_k}$ for $A$ to attack $f_k$.

Now consider a point in the execution of of $A^{F[\rho']}$. Suppose $A$ has made $r < 2^n$ queries $X_1, X_2, \ldots, X_r$ and received responses $Y_1, Y_2, \ldots, Y_r$.

Claim: Suppose $r < 2^n$, and we fix $X_r = x_r$ and any predicate $T$ of the form:

$T = (X_1, Y_1) = (x_1, y_1) \land \cdots \land (X_{r-1}, Y_{r-1}) = (x_{r-1}, y_{r-1}) \land X_r = x_r.$

Then for any $c \in \lbrace 0, 1, \rbrace^n$, $\mathsf{Pr}(Y_r = c \; | \; T) = 2^{-n}$. That is, each oracle response is iid from the uniform distribution, even when we condition on the transcript of previous queries.

Proof of claim: Let $D = \lbrace x_1, x_2, \ldots, x_{r-1}\rbrace$. By our assumption that $r < 2^n$, there exists some minimal positive integer $\Delta$ such that $x_r - \Delta \not \in D$, and some minimal positive integer $\delta$ such that $x_r + \delta \not \in D$. (Recall that we are defining subtraction and addition modulo $2^n$.)

By construction of $F$, our claim reduces to the assertion that $Y_r = \rho'(x_r) - \rho'(x_r - 1)$ is uniform and statistically independent of $\lbrace \rho'(x_r - i) - \rho'(x_r - i - 1) \; | \; -\delta < i < \Delta, i \neq 0 \rbrace$. (The remaining values in $D$ and their corresponding $Y_j$ values do not depend on $\rho'(x_r - \Delta + 1), \cdots, \rho'(x_r + \delta - 1)$; one can show this by defining $\rho'$ through lazy sampling.)

Therefore, let $g = \rho'$, but with the domain restricted to $\lbrace x_r - \delta, x_r + \Delta - 1\rbrace$. The purpose of introducing $g$ is to remove some of the clutter from the coming counting arguments.

So $\mathsf{Pr}_\rho(Y_r = c \;|\; T) = \mathsf{Pr}_g(Y_r = c \;|\; T)$

For arbitrary $c$, there are 2^n functions $g$ consistent with $T$ and $Y_r = c$. This can be seen by choosing $g(X_r)$ arbitrarily, and then enforcing the condition $x_r = g(x_r) - g(x_r - 1)$.

More explicitly, the relation

$Y_r = c = F(x_r) = \rho'(x_r) - \rho'(x_r - \delta) - \sum_{i=1}^{\delta - 1} F(x_r - i)$

means that fixing $c$ establishes a bijection between the 2^n possible values for $\rho'(x_r)$ and 2^n possible values for $\rho'(x_r - \delta)$.

For example, in the above image, $x_r = 4$, $\delta = 3$, $\Delta = 2$. Choose an arbitrary value for $F(4)$, and now $f(x_r - \delta) = f(1)$ uniquely determines $f(4)$, along with all the values in the shaded box (and this shaded box in turn determines $g$).

So $\mathsf{Pr}_g(Y_r = c \land T) = 2^n/N$, where $N$ is the size of the set from which $g$ is (uniformly) sampled.

Since there are $2^n$ possible values for $Y_r$, each of which permits a $2^n$ choices for $g$ consistent with $T$, $\mathsf{Pr}_g(T) = (2^n \cdot 2^n) / N = 2^{2n}/N$.

Therefore $\mathsf{Pr}_g(Y_r = c \;|\; T) = (2^n / N) / (2^{2n}/ N) = 1/2^n$, as desired.

This proves the claim.

Therefore as long as the criteria $r < 2^n$ is met, the behavior of $F[\rho']$ is statistically identical to $\rho$, a random function. Hence,

\begin{align*} \mathsf{Adv}^{\mathsf{prf}}_F(A) &= \mathsf{Pr}(A^{F_k} = 1) - \mathsf{Pr}(A^{F[\rho']} = 1) + \mathsf{Pr}(A^{F[\rho']} = 1) - \mathsf{Pr}(A^{\rho} = 1)\\ & = \mathsf{Adv}^{\mathsf{prf}}_{f}(B[A]) \end{align*}

-
I managed to convince myself late last night that this proof was incorrect, "fixed" it, and then realized today that there's a reason one should never do math while tired. I apologize for the numerous edits. Hopefully everything is fine now. I made one of the arguments more explicit to reduce the probability that I made another mistake. –  Seth Mar 11 '14 at 20:41
I really appreciate the effort. As pointed in my new comment about the other proof sketch, the simple argument made there must be incorrect, for it works unchanged with a simple counterexample. –  fgrieu Mar 12 '14 at 6:24

Yes, it is a secure PRF, as long as the attacker can make at most $2^n-1$ queries. The key lemma is purely information-theoretic in nature. From this lemma, you can prove your result using standard methods.

Lemma. Let $x=(x_1,\dots,x_q),y=(y_1,\dots,y_q)$ are any sequence of $q$ $n$-bit values, where $q<2^n$ and the $x_i$'s are all distinct. Then there are exactly $(2^n)^{2^n-q}$ functions $f$ such that $F(x_i)=y_i$ for all $i$, where $F$ is defined by $F(x) = f(x)-f(x-1)$.

Proof. I will show how to enumerate all such $f$. Define the set $X=\{x_1,x_2,\dots,x_q\}$ and $S = \{0,1\}^n \setminus X$. Now $|S|=2^n-q$. Since $q<2^n$, $S$ is non-empty. Now for each $s \in S$, we can freely choose $f(s)$ to be any $n$-bit value, and all of these choices can be made independently. Once we've made those choices, we can extend this to a full definition of $f$ by the formula

$$f(x) = f(s) + F(s+1) + F(s+2) + F(s+3) + \dots + F(x),$$

where $s$ is the largest $n$-bit value such that $s \le x$ and $s+1,s+2,s+3,\dots,x \in X$ (where of course $\le$ and addition wrap around modulo $2^n$). Here we are using the obvious notation: since $s+1 \in X$, there exists $i$ such that $x_i=s+1$, so by $F(s+1)$ we mean the value $y_i$.

It is easy to verify that, by construction, this choice of $f$ meets all the conditions, i.e., the derived function $F$ satisfies $F(x_i)=y_i$ for all $i$. Also, it is easy to verify that every valid $f$ is counted in this enumeration.

We made $2^n-q$ choices, and each choice had $2^n$ possibilities, and all the choices were independent, so by the product rule, there are $(2^n)^{2^n-q}$ functions $f$ that satisfy the desired conditions. $\Box$

Corollary. Let $U$ be a uniformly random function on $\{0,1\}^n \to \{0,1\}^n$. Also let $r$ be a uniformly random on $\{0,1\}^n\to \{0,1\}^n$ and define $R$ by $R(x)=r(x)-r(x-1)$. For any oracle algorithm $A$ that makes at most $2^n-1$ queries to its oracle, the distribution of $A^U$ is the same as the distribution of $A^R$.

Proof. Follows directly from the lemma. Just consider the transcript of queries to $A$'s oracle; the probability of each possible transcript is the same regardless whether $A$'s oracle is $R$ or $U$.

Given the above lemma, we can prove that if $f$ is a PRF, then so is $F$, where $F_k(x)=f_k(x)-f_k(x-1)$.

In particular, let $r$ be a uniformly random function on $\{0,1\}^n \to \{0,1\}^n$, let $R$ be the derived function, i.e., $R(x) = r(x)-r(x-1)$, and let $U$ be another independent uniformly random function on $\{0,1\}^n \to \{0,1\}^n$. Suppose we had a distinguisher $D$ that could distinguish $F_k$ from $U$ in $q/2$ queries and $t-q$ time. Then by the lemma above, if $q/2 < 2^n$, it can also distinguish $F_k$ from $R$ in $q-1$ queries and $t-q$ time, since by the lemma above, if $q-1<2^n$, then $D^R$ has the same distribution as $D^U$. This means we can use $D$ to help us distinguish $f_k$ from $r$, as follows: whenever $D$ queries its oracle on input $x$, we query our oracle on inputs $x$ and $x-1$, get back values $y_1,y_2$, and return $y_1-y_2$ to $D$. Then, we output whatever $D$ did. If $D$ distinguishes $R$ from $F_k$ with advantage $\epsilon$, then this algorithm will distinguish $r$ from $f_k$ with advantage $\epsilon$. This algorithm distinguishes $r$ from $f_k$ with $q$ queries and $t$ time.

This proves the following result:

Theorem. If $f$ is a $(t,q,\epsilon)$-secure PRF for $q \le 2^n$, then $F$ is a $(t-q,q/2,\epsilon)$-secure PRF.

In particular, if $f$ is a $(t,2^n,\epsilon)$-secure PRF, then $F$ will be a secure PRF as long as the adversary is restricted to make at most $2^{n-1}$ queries. In fact, if $f$ is secure for $2^n$ queries, you can show that $F$ is a secure PRF as long as the adversary is restricted to make at most $2^n-1$ queries (just count the number of distinct queries made by the algorithm above in this case; repeated queries can be avoided by using a hashtable).

Conversely, if the adversary can make $2^n$ queries, the adversary can distinguish $F$ from random simply by summing all of the outputs of $F$: we will have $\sum_x F_k(x)=0$ but for a uniformly random function $\sum_k U(x)$ is zero with probability $1/2^n$.

-
I think there may be a (minor) error in the reduction to f, which is queried twice as often as F. Set n = 2, and consider the function family index by keys $(a_1, a_2, a_3) \in (\lbrace 0, 1 \rbrace^n)^3$, where $f = f_{(a_1, a_2, a_3)}$ is defined by $f(i) = a_i$ (for i = 1, 2, 3) and $f(4) = a_2 - a_1 + a_3$. Then because - and + are group operators, any three values of f are statistically independent over the choice of key. So f is $(\infty, 3, 0)$-secure PRF. However, for every key, $F(4) = F(2) = a_2 - a_1$. Therefore $F$ is not $(\infty, 2, 0)$ secure. –  Seth Mar 14 '14 at 0:27
@Seth, thank you! I have fixed the error you pointed out. (I had miscounted the number of queries made by my distinguishing algorithm. I've revised my answer; should be fixed now.) –  D.W. Mar 14 '14 at 15:28
After hesitations, I chose this for the bounty, rather than the excellent and more intuitive other candidate proof, because D.W.'s answers centers on a simple and robust lemma, and I found it less difficult to try to verify the proof (I'm at least confident that if I missed something, it must be minor and repairable locally). –  fgrieu Mar 17 '14 at 20:40

Yes. Assume there is an adversary A that breaks $F$. We will construct an adversary $A'$ that breaks $f$. $A'$ runs $A$ in its head, and whenever $A$ makes a query $x$, $A'$ queries its oracle $R$ on $R(x)$ and $R(x-1)$, and replies with $R(x)-R(x-1)$ to $A'$.

If $R$ is an oracle for a pseudo random function $f$, then $R(x)=f(k,x)$ and $R(x-1)=f(k,x-1)$, which is consistent with $F(k,x)$.

Otherwise, if $R$ is a random function, then the output looks random. Hence, $A'$ breaks the security of $f$.

-
The proof in this question is incorrect even for the standard definition of security using domain $\{0,1\}^n×\{0,1\}^n→\{0,1\}^n$. We could apply it to either of$$F'\big(k,x\big)=\Big(f\big(k,x\big)⋅f\big(k,(x-1)\bmod2^{n}\big)\Big) \bmod2^n$$ $$F''\big(k,x\big)=\Big(f\big(k,x\big)-f\big(k,(x+7)\bmod8+⌊x/8⌋⋅8\big)\Big) \bmod2^n\text{ for }n\ge3$$and it would lead to the wrong conclusion that $F'$ and $F''$ are PRF if $f$ is. In fact there are distinguishers, based on the facts that the low bit of $F′$ is $0$ with odds $3/4$; and that$$\forall k,2^n\text{ divides }\sum_{x=0}^7 F''(k,x)$$ –  fgrieu Mar 13 '14 at 6:58
@fgrieu I don't see how the same argument would work for your examples. If we assume an analogous simulation of the oracle for $F'$, it is easy to see that the simulation of the random case simply fails. That is, in both cases (PRF and random function) the simulated oracle exhibits the bias you mention. The hard part in proving such PRF constructions secure is always to argue why the simulation does not fail in the random case. Here, such an argument can be made for the original function, but not for your examples. –  Maeher Mar 13 '14 at 22:03
@Maeher: My point with $F'$ is that " the output looks random " is not justified, and no rationale is given why it is true for $R(x)-R(x−1)\bmod2^n$ but not $R(x)\cdot R(x−1)\bmod2^n$ when $R$ is random. That can be fixed relatively easily. But the proof needs profound change so that it won't transform the working distinguisher I give for $F''$ into one for $f$, specifically a distinguisher based on$$0\equiv\Big(\sum_{x=0}^7 f\big(k,x)-f(k,(x+7)\bmod8\big)\Big)\pmod{2^n}$$which won't work: this expression is true for any function $f$, random or not. –  fgrieu Mar 14 '14 at 6:57
@fgrieu Yes, the proof sketch is missing the argument, why it is that the reduction perfectly simulates a random function in the case that it itself is given access to a random function. But my point is that the proof does NOT need " profound change" besides that. The reduction trivially fails for the examples you give, because the distribution of outputs is incorrect for the random case. In particular your distinguisher would always output the same bit when run as a subroutine of the reduction, because the condition you check would hold in both cases. –  Maeher Mar 14 '14 at 9:53
@Maeher: The proof must contain something to discriminate between $F$ (which is a PRF) and $F''$ (which is not). It currently does not contain this, and I prove it ad absurdum by applying the reasoning in the proof to a working distinguisher for $F''$ $$0\equiv\sum_{x=0}^7 F''(k,x)\pmod{2^n}$$yielding an alleged distinguisher for $f$ $$0\equiv\sum_{x=0}^7 f\big(k,x)-f(k,x+7\bmod8\big)\pmod{2^n}$$The reasoning in the proof concludes this new distinguisher would work, but in fact it does not. I fail to see any simple fix of the proof, or how your comment hints at one. –  fgrieu Mar 14 '14 at 10:27