Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
You're missing the massive difference between the actual expression and your other words. $\hspace{.6 in}$ – Ricky Demer Apr 7 '13 at 6:03
up vote 7 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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