XDH Assumption
Encyclopedia
The external Diffie–Hellman (XDH) assumption is a mathematic assumption used in elliptic curve cryptography
. The XDH assumption holds that there exist certain subgroup
s of elliptic curves which have useful properties for cryptography. Specifically, XDH implies the existence of two distinct groups
with the following properties:
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
.
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.
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
. The XDH assumption holds that there exist certain subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
s of elliptic curves which have useful properties for cryptography. Specifically, XDH implies the existence of two distinct groups
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
with the following properties:- The discrete logarithm problem (DLP), the computational Diffie–Hellman problem (CDH), and the computational co-Diffie–Hellman problem are all intractable in
and 
. - There exists an efficiently computable bilinear map (pairing)
. - The decisional Diffie–Hellman problem (DDH) is intractable in
.
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
.The XDH assumption is used in some pairing-based
Pairing-based cryptography
Pairing-based cryptography is the use of a pairing between elements of two cryptographic groups to a third group to construct cryptographic systems. If the same group is used for the first two groups, the pairing is called symmetric and is a mapping from two elements of one group to an element from...
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
Key exchange
Key exchange is any method in cryptography by which cryptographic keys are exchanged between users, allowing use of a cryptographic algorithm....
, 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
ElGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...
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
Dan Boneh
Dan Boneh is a Professor of Computer Science and Electrical Engineering atStanford University. He is a well-known researcher in the areas of applied cryptographyand computer security.-Education:...
, 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.