0
$\begingroup$

I'm reading a paper Code-Based Game-Playing Proofs and the Security of Triple Encryption , which indicates an error on the standard proof of the PRP/PRF switching lemma using the conditional probability in its chapter 2.

In the standard proof, it defines COLL and DIST events, which COLL means the adversary A asks distinct queries to the oracle and gets the same return, DIST is the complementary event. which makes $ Pr[A^{\pi}\Rightarrow 1]=Pr[A^{\rho }\Rightarrow 1|DIST]$.

Then the author constructed an counterexample of this equality, which event DIST is true for $(\rho(0),\rho(1))=(0,0),(0,1),(1,0)$, but I can't understand why the event $(0,0)$ are DIST. Is the adversary A asks distinct queries to the oracle and gets the same return, means a COLL?

Here is an excerpt from the relevant part of the paper below.

enter image description here enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

but I can't understand why the event $(\rho(0),\rho(1))=(0,0)$ is DIST

Because the adversary queries its oracle at 0, gets the answer $\rho(0)=0$, and halts. It does not query its oracle at input 1, therefore it never observes a repeated oracle output.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much $\endgroup$
    – Ji Li
    Commented Sep 4 at 6:04

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.