Pt2520 Unit 1 Algorithm Paper
For the second event Event2, the algorithm C does not abort during the challenge phase if one of d_0 and d_1 is 0. By the definition of H-list Pr[d_b=0]=1/(m!q_T+1) where b∈{0,1} and the two values are independent of one another, we have that both Pr[d_0=d_1=1]=1-1/q_T≥〖(1-1/(q_T+1))〗^2. Hence, the Pr[Event2] is at least 1/q_T. Since A never issues trapdoor queries for target keyword vectors, Event1 and Event2 are independent. Hence, the probability that C does not abort during the entire simulation, that is Pr[Event_1 ∧ Event_2]≥1/(eq_T).
Consequently, if the advantage of A against the proposed scheme is ϵ, the success probability of the algorithm C against the DDH challenge is at least ϵ/(e(m!q_T+1)).
Consequently, if the advantage of A against the proposed scheme is ϵ, the success probability of the algorithm C against the DDH challenge is at least ϵ/(e(m!q_T+1)).