Skip to main content
Cryptography

Return to Question

Partly Latex
Source Link
kelalaka
kelalaka
  • 50k
  • 12
  • 125
  • 214

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

Any help is appreciated.

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

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 → {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 ←$ {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?

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?

Source Link
apurvakatti
apurvakatti
  • 21
  • 2

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 → {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 ←$ {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?