XDH assumption (original) (raw)
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 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 .
| Property | Value |
|---|---|
| dbo:abstract | 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 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 and . 2. * There exists an efficiently computable bilinear map (pairing) . 3. * 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 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 (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 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 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. (en) |
| dbo:wikiPageExternalLink | http://eprint.iacr.org/2002/164.pdf http://eprint.iacr.org/2005/417.pdf http://crypto.stanford.edu/~dabo/papers/groupsigs.pdf http://portal.acm.org/citation.cfm%3Fid=647086.715689 http://www.lms.ac.uk/jcm/7/lms2004-010/ |
| dbo:wikiPageID | 1937517 (xsd:integer) |
| dbo:wikiPageLength | 4562 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 948071354 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Decisional_Diffie–Hellman_assumption dbr:Elliptic_curve_cryptography dbc:Computational_hardness_assumptions dbr:Computational_Diffie–Hellman_assumption dbr:Computational_hardness_assumption dbr:Key_exchange dbr:Personal_identification_number dbr:Subgroup dbr:Dan_Boneh dbr:Group_(mathematics) dbr:Bilinear_map dbc:Elliptic_curve_cryptography dbr:ElGamal_encryption dbc:Pairing-based_cryptography dbr:Pairing-based_cryptography dbr:Secret_handshakes dbr:Discrete_logarithm_problem dbr:Identity_based_encryption dbr:Distortion_map dbr:Gap_Diffie–Hellman dbr:MNT_curve |
| dbp:wikiPageUsesTemplate | dbt:Computational_hardness_assumptions |
| dct:subject | dbc:Computational_hardness_assumptions dbc:Elliptic_curve_cryptography dbc:Pairing-based_cryptography |
| rdf:type | yago:WikicatComputationalHardnessAssumptions yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Postulate106753299 yago:Premise106753800 yago:Proposition106750804 yago:Statement106722453 |
| rdfs:comment | 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 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 . (en) |
| rdfs:label | XDH assumption (en) |
| owl:sameAs | freebase:XDH assumption yago-res:XDH assumption wikidata:XDH assumption https://global.dbpedia.org/id/4xktL |
| prov:wasDerivedFrom | wikipedia-en:XDH_assumption?oldid=948071354&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:XDH_assumption |
| is dbo:wikiPageRedirects of | dbr:XDH_Assumption dbr:External_Diffie-Hellman_assumption |
| is dbo:wikiPageWikiLink of | dbr:Decisional_Diffie–Hellman_assumption dbr:Index_of_cryptography_articles dbr:Indistinguishability_obfuscation dbr:XDH_Assumption dbr:Non-interactive_zero-knowledge_proof dbr:External_Diffie-Hellman_assumption |
| is foaf:primaryTopic of | wikipedia-en:XDH_assumption |