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&gt;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?
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 &gt; 3q/512 ] &amp;= \Pr[ T &gt; (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 &gt; 3q/512 ] &amp;\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 &lt; 3q/512 ]$ in the real world, and from that get a lower bound on the advantage.