No fully-black-box reduction from DDH to IBE

Unconditional · against fully-black-box reductions · PRV12, Zha22

Statement

There is no fully-black-box construction of IBE from a group in which DDH is hard: in the generic group model, every IBE scheme that uses a prime-order generic group only through its group-operation oracle is broken by an attack — PRV12. The generic group model of that proof does not fully capture Shoup’s model, in which schemes also see random labels of group elements; the separation in Shoup’s model is proved in Zha22. The generic group is DDH-hard (GGM ⇒ DDH) — Sho97, so a fully-black-box construction from a DDH-hard group would give a secure generic-group IBE. The result covers DDH and similar group assumptions — PRV12.

Notes

• CDH ⇒ IBE (Döttling–Garg) gets around the barrier: its garbled circuits use the group non-black-box, and DDH hardness implies CDH hardness (DDH ⇒ CDH) — DG17a.
• The pairing-based schemes BDH ⇒ IBE (random oracle model) and DBDH ⇒ IBE (Waters, standard model) are outside the barrier’s scope: they evaluate a bilinear map on the group, an operation beyond the group-operation oracle — BF01, Wat05.