1
$\begingroup$

According to Wikipedia, PRF is an abbreviation for Pseudorandom function family. But this answer says that PRF means Pseudorandom Function. Does that mean that a Pseudorandom Function is the same as a Pseudorandom function family? Or is the abbreviation PRF used inconsistently?

$\endgroup$
1

2 Answers 2

2
$\begingroup$

The word "family" can mean various things. For instance, you have the SHA-2 family of hash functions. In this case the algorithms are part of a family because they are based on the same hash construction.

However, in this case the "family" simply means that you have a PRF construction, say HMAC-SHA256. In that case the "family" is actually the set of all the possible HMAC-SHA256 functions that can be selected using the key.

In other words, say that you have a family of keyed hash functions called $H$ and a key $k_0$ consisting of $\{0\}^{256}$, then $H_{k_0}$ is the function chosen by $k_0$ from the family.

$\endgroup$
2
  • $\begingroup$ Would $H$ and $H_{k_0}$ then both be called a PRF? Or only $H$? $\endgroup$
    – Riemann
    Oct 25, 2023 at 9:18
  • 1
    $\begingroup$ I guess both, it depends on context. HMAC is a PRF construct(ion) and when keyed a function. To make it more complex, in API's you'd could HMAC a function as well as the key is then considered a parameter. Language is a fickle thing, but generally we know what is meant by "a PRF" and the distinction is clear or doesn't matter. For me the bigger problem is that "a PRF" can be too generic in the sense that a lot of constructions can be called a PRF or made into a PRF - for instance a KDF and a MAC construction both are (related) PRF's. $\endgroup$
    – Maarten Bodewes
    Oct 25, 2023 at 10:58
2
$\begingroup$

PRF is short for PseudoRandom Function. A single function $F:\{0,1\}^n\rightarrow \{0,1\}^n$ cannot be pseudorandom. Pseudorandomness asks that it is not feasible to distinguish an oracle for $F$ from an oracle for a truly random function $f:\{0,1\}^n\rightarrow \{0,1\}^n$ (meaning that $f(x)$ is uniformly distributed for every $x\in\{0,1\}$). This is very easy to distinguish for a single $F$: send $x$ to an oracle and check if the output is equal to $F(x)$. Since $f(x)$ is uniform, $f(x)=F(x)$ only with probability $2^{-n}$.

So whenever we speak of pseudorandom functions, we actually mean function families $\{F_k\}_{k\in\{0,1\}^\lambda}$. In the pseudorandom distinguishing game, the distinguisher is given an oracle to $F_k$ for a random unknown $k$. Since $F_k$ is now one of exponentially many functions, the "attack" outlined above for a single function does not work.

$\endgroup$
3
  • $\begingroup$ What do you mean by '$f(x)$ is uniformly distributed' ? If $f(x)$ is a number, I would think that it is fixed, and thus not 'distributed'. $\endgroup$
    – Riemann
    Oct 25, 2023 at 15:28
  • $\begingroup$ That would be short for all $y$ where $y = f(x)$ where both $x$ and $y$ are in $\{0, 1\}^n$ as made clear in the function definition. $\endgroup$
    – Maarten Bodewes
    Oct 25, 2023 at 17:50
  • $\begingroup$ The function $f$ is itself selected at random from the set of functions mapping $\{0,1\}^n$ to $\{0,1\}^n$, so if you look at one $x\in \{0,1\}^n$ then the maginal distribution of $f(x)$ is uniform over $\{0,1\}^n$. $\endgroup$
    – lamontap
    Oct 25, 2023 at 19:48

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.