in paper public key encryption with keyword search i read that attack algorithm has epsilon advantage and make qH hash function and make qT trapdoor queries.
Hi!
You're right about epsilon, which represents the advantage an adversary A has to break the PEK scheme (expect epsilon to be 2^{-80} for 80 bits of security). It is by the way mentionned at the end of your screenshot : ``consequently, epsilon must be a negligible function in the security parameter''
Nevertheless, q_T (respectively q_{H_2}) represents the (integer) number of queries to the trapdoor (resp. to the hash) function. For such an attack, you can expect these number not only to be positive, but also to be of order 2^{40} or even more depending on your security assumptions.
Probability epsilon' = epsilon / (e*q_T*q_{H_2}) is the result of the operations involved in using attacker A (breaking the PEK scheme) to get algorithm B (solving the BDH problem). Read carefully the proof, and you will get to this quotient.
Hope it will help. Bests
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics
- Probability
- Probability Theory