XDH assumption

The external Diffie–Hellman (XDH) assumption is a computational hardness assumption used in elliptic curve cryptography. The XDH assumption holds that there exist certain subgroups of elliptic curves which have useful properties for cryptography. Specifically, XDH implies the existence of two distinct groups $\langle{\mathbb G}_1, {\mathbb G}_2\rangle$ with the following properties:

1. The discrete logarithm problem (DLP), the computational Diffie–Hellman problem (CDH), and the computational co-Diffie–Hellman problem are all intractable in ${\mathbb G}_1$ and ${\mathbb G}_2$.
2. There exists an efficiently computable bilinear map (pairing) $e(\cdot, \cdot) : {\mathbb G}_1 \times {\mathbb G}_2 \rightarrow {\mathbb G}_T$.
3. The decisional Diffie–Hellman problem (DDH) is intractable in ${\mathbb G}_1$.

The above formulation is referred to as asymmetric XDH. A stronger version of the assumption (symmetric XDH, or SXDH) holds if DDH is also intractable in ${\mathbb G}_2$.

The XDH assumption is used in some pairing-based cryptographic protocols. In certain elliptic curve subgroups, the existence of an efficiently-computable bilinear map (pairing) can allow for practical solutions to the DDH problem. These groups, referred to as gap Diffie–Hellman (GDH) groups, facilitate a variety of novel cryptographic protocols, including tri-partite key exchange, identity based encryption, and secret handshakes (to name a few). However, the ease of computing DDH within a GDH group can also be an obstacle when constructing cryptosystems; for example, it is not possible to use DDH-based cryptosystems such as ElGamal within a GDH group. Because the DDH assumption holds within at least one of a pair of XDH groups, these groups can be used to construct pairing-based protocols which allow for ElGamal-style encryption and other novel cryptographic techniques.

In practice, it is believed that the XDH assumption may hold in certain subgroups of MNT elliptic curves. 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. As pairings and distortion maps are currently the only known means to solve the DDH problem in elliptic curve groups, it is believed that the DDH assumption therefore holds in these subgroups, while pairings are still feasible between elements in distinct groups.

References

1. Mike Scott. Authenticated ID-based exchange and remote log-in with simple token and PIN. E-print archive (2002/164), 2002. (pdf file)
2. Dan Boneh, Xavier Boyen, Hovav Shacham. Short Group Signatures. CRYPTO 2004. (pdf file)
3. Lucas Ballard, Matthew Green, Breno de Medeiros, Fabian Monrose. Correlation-Resistant Storage via Keyword-Searchable Encryption. E-print archive (2005/417), 2005. (pdf file)
4. Steven D Galbraith, Victor Rotger. Easy Decision Diffie–Hellman Groups. LMS Journal of Computation and Mathematics, August 2004. ()
5. E.R. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems, in B. Pfitzmann (ed.) EUROCRYPT 2001, Springer LNCS 2045 (2001) 195–210.