Question about the definition of a secure PRF

Question

I'm taking a cryptography introduction course, and we're covering the definition of a secure PRF.

I understand the test goes as follows: A challenger picks a function $f$ such that

$f \leftarrow \left\{ \begin{array}{lr} b=1: k\leftarrow K, f\leftarrow \left(k,\cdot \right ) \\ b=0: Funs \left(X,Y \right ) \end{array} \right.$

Where $Funs(X,Y)$ is the set of all possible PRFs, The entire experiment is defined as $EXP\left(b \right )$, such that the output is the adversary's guess as to whether or not the challenger chose a function at random. A secure PRF is then defined as the conditions where

$\left | Pr\left[EXP\left(0 \right ) =1\right ] - Pr\left[EXP\left(1 \right ) = 1\right ] \right |$ is negligible. Or in other words, when the probability that the attacker's result is zero minus the probability that the attacker's result is one is negligible.

However, what if the adversary's detection method always returns one? This would imply that the cipher is not secure, but that can't be true.

What am I missing here?

Answer 1

You have the math right, but you seem to have mis-interpreted the formulas. So, let me try to walk you through it.

The "advantage" of an attack is the difference $|\Pr[Exp(0)=1] - \Pr[Exp(1)=1]|$. The advantage is a measure of how effective the attack is. If the advantage is large (significantly greater than 0), the attack is successful (and the function is not a secure PRF). If the advantage is negligible, the attack is ineffective.

You suggested we look at an attacker whose algorithm always returns one. In this case it turns out that the advantage is 0: in particular, $\Pr[Exp(0)=1] = \Pr[Exp(1)=1] = 1$, so $|\Pr[Exp(0)=1] - \Pr[Exp(1)=1]| = 0$. Since the advantage is 0, this attack strategy is ineffective -- exactly as you'd expect.