# Amplifying PRF Advantage

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?

• 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. – kelalaka Feb 6 '19 at 17:39

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.