# 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?

-
Is the subtraction mod 2^n? $\;$ –  Ricky Demer Mar 7 at 5:56
yes, the subtraction mod $2^n$ –  Jenifer Tran Mar 7 at 6:01
@fgrieu: Just a quick thought, and nowhere near a full argument but surely yes? Consider trying to calculate $f(k,x)=F(k,x)+f(k,x-1) \bmod 2^n$ then ask the oracle for $f(k,x-1)$ (for a secure prf releasing this value shouldn't leak f(k,x) so should be fine to do). Then, if F(k,x) was predictable with better probability than ideal we could calculate f(k,x). –  figlesquidge Mar 10 at 14:13
@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 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 at 16:32

## This question has an open bounty worth +500 reputation from fgrieu ending in 3 days.

The question is widely applicable to a large audience. A detailed canonical answer is required to address all the concerns.

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 at 6:08
With $n= 128$, how to prove $F$ indistinguishable from random? –  Jenifer Tran Mar 7 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 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 yesterday
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 yesterday
show 1 more comment

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 2 days ago
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 2 days ago

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-1$ queries and $t-q$ time. Then by the lemma above, if $q\le 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-1,\epsilon)$-secure PRF.

In particular, $F$ is a secure PRF as long as the adversary is restricted to make at most $2^n-1$ queries.

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 9 hours ago
Yes, there seems to be a small mistake in the theorem. I think the condition on f should be 2q queries, and F should be bounded by q<2^n queries. Otherwise, the proof is natural and correct. –  K.G. 48 mins ago

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 yesterday
@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 11 hours ago
@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 2 hours ago

I agree with user12400’s answer. Regarding the two issues you pointed out:

• there are no issues with too many queries; true, the number of queries can not be infinite but this is the way the "game" is played to test whether a PRF is secure, namely the challenger fixes the key $k$ (choosing a single function from the family of functions) and sends to the attacker either an $f(k,.)$ or some random data. The adversary is allowed to send multiple queries $x_1,x_2, … x_n$ for which he receives an answer of $f(k,xi)$ which he uses to judge whether the first message was random data or PRF data; in this case, you only need to test two values to test for insecurity; generally, the maximum number of queries is fixed depending on the intended difficulty of the problem;
• as for your argument regarding $F(k,x) = f(k,x) * f(k,x-1)$, this is true but you have to take into consideration the fact that you are using two random variables (or assumed random variables); there is a theorem that states that the sum of two independent, uniform random variables mod n is also an independent uniform random variable (see slide 5: http://spark-university.s3.amazonaws.com/stanford-crypto/slides/01.5-intro-v2.pdf - Dan Boneh's materials, his page on the Stanford website seems to be down...). This does not apply to their product which, as you have shown, is biased.

In fact, this is the problem with user12400's demonstration: he assumes (correctly) that the difference of the two $f$'s would also look random but he should also explicitly mention that the difference does not change the “random-lookingness”, so to speak. This is the part that the proof would also need to mention.

-
I'm not sure of the difference here... might be too late, though :) That number of queries is huge! Think of the PRP switching lemma which states that the difference between the PRP and PRF advantages is smaller than $\frac{q^2}{2*\left|X\right|}$, a negligable quantity. So the number of queries is a lot smaller than $2^{n/2}$ –  AdrianH Mar 10 at 22:32
Latex is awful for me, has been a pain since school... the main idea is you do not have to go as far as proving security for $2^{n-1}$ queries. As for the number of bits in $k$, I don't think they are very much relevant to the matter of hand... true, a small number of bits can be a problem but you can't actually say anything about m - it can be equal to n (AES - 128/128), smaller (DES - 56/64) or larger (3DES - 168/64). The output of the function still seems random in these three cases. Remember the way the test is made - k is fixed by the challenger and is internal. –  AdrianH Mar 10 at 22:41
Revision 5... we should outsource this to Github :) –  AdrianH Mar 10 at 22:43
So what you're saying is that n is so small that the number of queries q would be practical/polynomial with respect to n? Just saw the new edit. So you would use a 256-bit key to encrypt less than a byte... no points for efficiency there but I believe F would no longer be secure under such conditions. I'll look something up and get back to you in a jiffy –  AdrianH Mar 10 at 22:44
n=8 is still very small for PRF output. 64-bits would be safe (for a couple of years and with a less-determined attacker, at least). I was looking for the part on MACs based on PRF truncation and there, I'll refer you to slide 8 of, again, Dan Boneh's course materials, link, 64-bits is still recommended as a minimum (the NSA would probably laugh at that, though) in order to have a small enough $\frac{1}{2^n}$ –  AdrianH Mar 10 at 23:08