CDH ⇒ IBE (Döttling–Garg)

Free reduction · standard model · DG17a · security loss: polynomial

Statement

If CDH is hard for some group generator $\mathsf{GrGen}$ (no pairing is needed), there is an IND-ID-CPA-secure (adaptive) IBE scheme in the standard model — DG17a. The construction builds chameleon encryption from CDH and combines it with one garbled circuit per level of an implicit binary tree over the identity bits; the garbled circuits use chameleon encryption non-black-box — DG17a.

Notes

• The same paper obtains IBE from factoring by the same route, and a selectively secure HIBE from either assumption — DG17a.
• In the generic group model, every IBE scheme that uses the group only through the group-operation oracle is broken (No fully-black-box reduction from DDH to IBE) — PRV12. The non-black-box use of the group inside garbled circuits is what gets around it — DG17a.
• Earlier IBE schemes from Diffie–Hellman-type assumptions need a bilinear pairing: BDH ⇒ IBE (random oracle model) — BF01; DBDH ⇒ IBE (Waters, standard model) — Wat05.