2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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$ Commented Feb 6, 2019 at 17:39

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.