BDH ⇒ PEKS (random oracle model)
Statement
Let be a pairing on groups of prime order with generator , and let and be hash functions. The scheme
- : sample , output and ;
- : sample , output ;
- ;
is an IND-CKA-secure PEKS if the computational BDH assumption holds and are modelled as random oracles — BDOP04. In the random oracle model it is also computationally consistent — ABC+05.
Sketch
Correctness holds since . Given a BDH instance , the reduction sets and the challenge’s first component to , embeds in the values of a guessed set of keywords, and sets every other value to with known , so that it answers trapdoor queries on those keywords as . An adversary with non-negligible advantage must query at a value from which the reduction computes ; it picks that value from its list of queries — BDOP04.