BDH ⇒ PEKS (random oracle model)

Fully-black-box reduction · random oracle model · BDOP04, ABC+05

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.

Notes

  • The scheme is a variant of the Boneh–Franklin IBE (BDH ⇒ IBE), with the keyword as identity and as key extraction — BDOP04.