Computational Diffie-Hellman assumption

Computational Diffie-Hellman assumption

The computational Diffie-Hellman (CDH) assumption is the assumption that a certain computational problem within a cyclic group is hard.

Consider a cyclic group {mathbb G} of order q. The CDH assumption states that, given

:(g,g^a,g^b)

for a randomly-chosen generator g and random

:a,b in {0, ldots, q-1},

it is computationally intractable to compute the value

:g^{ab}.

The security of many cryptosystems is based on the CDH assumption, including notably the Diffie-Hellman key agreement scheme. Also, the confidentiality of ElGamal encryption is equivalent to the CDH assumption (though the semantic security of the scheme is based on the decisional Diffie-Hellman assumption).

The CDH assumption is related to the discrete logarithm assumption, which holds that computing the discrete logarithm of a value base a generator g is hard. If taking discrete logs in {mathbb G} were easy, then the CDH assumption would be false: given

:(g,g^a,g^b),

one could efficiently compute g^{ab} in the following way:
* compute a by taking the discrete log of g^a to base g;
* compute g^{ab} by exponentiation: g^{ab} = (g^b)^a;

It is an open problem to determine whether the discrete log assumption is equivalent to CDH, though in certain special cases this can be shown to be the case.

The CDH assumption is also related to the decisional Diffie-Hellman assumption (DDH), which holds that it is hard to distinguish tuples of the form (g,g^a,g^b,g^{ab}) from random tuples. If computing g^{ab} from (g,g^a,g^b) were easy, then one could detect DDH tuples trivially. It is believed that CDH is a weaker assumption than DDH: there are groups for which detecting DDH tuples is easy, but solving CDH problems is believed to be hard.

ee also

* Diffie-Hellman problem
* Diffie-Hellman key exchange

References

#Variations of the Diffie-Hellman Problem ( [http://www.i2r.a-star.edu.sg/icsd/publications/Baofeng_2003_Variations%20of%20Diffie%20Hellman%20problems.pdf pdf file] )
#Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms ( [http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C94/271.PDF pdf file] )


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Computational Diffie–Hellman assumption — The computational Diffie–Hellman (CDH assumption) is the assumption that a certain computational problem within a cyclic group is hard. Consider a cyclic group G of order q. The CDH assumption states that, given for a randomly chosen… …   Wikipedia

  • Decisional Diffie–Hellman assumption — The decisional Diffie–Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most… …   Wikipedia

  • Decisional Diffie-Hellman assumption — The decisional Diffie Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most… …   Wikipedia

  • Diffie–Hellman problem — Cryptography portal The Diffie–Hellman problem (DHP) is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography. The motivation for this problem is that many security systems use mathematical… …   Wikipedia

  • Diffie-Hellman problem — The Diffie Hellman problem (DHP) is the name of a specific problem in cryptography which was first proposed by Whitfield Diffie and Martin Hellman. The DHP is a problem that is assumed to be difficult to do, hence the security of many… …   Wikipedia

  • Computational — may refer to: Computer Computational algebra Computational Aeroacoustics Computational and Information Systems Laboratory Computational and Systems Neuroscience Computational archaeology Computational auditory scene analysis Computational biology …   Wikipedia

  • Computational hardness assumption — In cryptography, a major goal is to create cryptographic primitives with provable security. In some cases cryptographic protocols are found to have information theoretic security, the one time pad is a common example. In many cases, information… …   Wikipedia

  • XDH assumption — The External Diffie Hellman (XDH) assumption is a mathematic assumption used in elliptic curve cryptography. The XDH assumption holds that there exist certain subgroups of elliptic curves which have useful properties for cryptography.… …   Wikipedia

  • Decision Linear assumption — The Decision Linear (DLIN) assumption is a mathematical assumption used in elliptic curve cryptography. In particular, the DLIN assumption is useful in settings where the decisional Diffie–Hellman assumption does not hold (as is often the case in …   Wikipedia

  • 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 agreement. It was described by Taher Elgamal in 1984 [Taher ElGamal, A Public Key… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”