I am trying to solve this question and I have no idea how to find the value for $q$. I know that I am supposed to find the probability of $q>3q/512$ in terms of the equation $q$, but not sure how?

Any help is appreciated.

Alice has a function $$F: \{0, 1\}^k × \{0, 1\}^n \to \{0, 1\}^n$$ that she intends to use as a PRF. However, this $F$ has a serious weakness: for any fixed key $K$, if we pick a random message $$x \leftarrow \{0, 1\}^n$$, then the first byte of FK(x) will be $0^8$ with probability $1/128$, instead of the desired probability $1/256$.

Adversary Eve wants to break the PRF security of F., Of course, it’s trivial to have advantage 1/128−1/256 =1/256 using just a single random query. However, being greedy, Eve aims for more. She makes q random queries x1, . . . , xq to the oracle Fn to receive answers C1, . . . , Cq.

Let T be the number of ciphertexts Ci whose first byte is 0^8 . Note that in the real world, E[T] = q/128, whereas in the ideal world, E[T]is much smaller, q/256. Based on that observation, Eve will output 1 if T ≥1/2[q/128 +q/256] =3q/512, and output 0 otherwise. How big should q be so that Eve’s advantage is at least 0.99?

  • 2
    $\begingroup$ Welcome to Cryptography. I've edited some part of your question, firstly, please check that part is ok, secondly continue to transfer your dumped question with Latex/MathJax. $\endgroup$
    – kelalaka
    Commented Feb 6, 2019 at 17:39

1 Answer 1


The general question is, "what is the probability that $T$ is significantly far from its mean?" This is a question about the "tail" of a distribution.

Your random variable $T$ can be written as a sum of indicator variables, $T = \sum_{i=1}^q T_i$, where $T_i=1$ if the $i$th query begins with 8 zeroes. Hence, $T$ follows a binomial distribution $B(q,1/256)$ in the ideal world and $B(q,1/128)$ in the real world.

The standard way to estimate tail probabilities for binomial distributions is through the Chernoff bound. For example, in the ideal world, $T$ has mean $q/256$: \begin{align*} \Pr[ T > 3q/512 ] &= \Pr[ T > (1+0.5) q/256] \end{align*} So you can use the multiplicative Chernoff bound with $\delta=0.5$ to get: \begin{align*} \Pr[ T > 3q/512 ] &\le \left( \frac{ e^{0.5} }{ 1.5^{1.5} } \right)^{q/256} \approx (0.999577)^q \end{align*}

You can do a similar computation to get a bound on $\Pr[ T < 3q/512 ]$ in the real world, and from that get a lower bound on the advantage.


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.