XDH assumption

The XDH assumption holds if there exist certain subgroups of elliptic curves which have useful properties for cryptography.

In certain elliptic curve subgroups, the existence of an efficiently-computable bilinear map (pairing) can allow for practical solutions to the DDH problem.

This notion was first proposed by Scott (2002), and later by Boneh, Boyen and Shacham (2002) as a means to improve the efficiency of a signature scheme.

The assumption was formally defined by Ballard, Green, de Medeiros and Monrose (2005), and full details of a proposed implementation were advanced in that work.

Evidence for the validity of this assumption is the proof by Verheul (2001) and Galbraith and Rotger (2004) of the non-existence of distortion maps in two specific elliptic curve subgroups which possess an efficiently computable pairing.