Computational cryptography › Public-key encryption and key exchange › Classical number theory › Elliptic-curve discrete log
Hardness assumptionKE: gives key exchangeTD: gives trapdoor functions

Decisional DH

In plain words

A stronger version: you can't even tell the real shared secret apart from a random point.

The idea: CDH says an eavesdropper can't compute the shared secret. DDH says something stronger: shown a candidate, they can't even tell whether it's the real shared secret or a random point. That matters when the shared secret is used as a mask: if any pattern showed through, an attacker could learn part of the message, such as whether a vote was yes or no.

Why it matters: Needed for encryption that hides every last bit of the message.

The details

On the map: on the curve

Given aP, bP and a point R, decide whether R = abP or a random point. A CDH solver also solves this, so it is a stronger assumption[1].

It is what makes ElGamal encryption hide everything about the message[2], and it underlies DDH-based oblivious transfer[3].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (3 boxes)

About the tags

KE
This assumption gives key exchange on its own, so it needs more than one-way functions and falls if public-key encryption is impossible.
TD
This assumption gives trapdoor functions on its own (computable by anyone, invertible only with a secret), so it falls if trapdoor functions don't exist. Schemes built on it need not use a trapdoor: ElGamal doesn't.

References

  1. Dan Boneh. The Decision Diffie-Hellman problem. Algorithmic Number Theory, 1998. doi:10.1007/bfb0054851
  2. Taher ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. Advances in Cryptology, 1985. doi:10.1007/3-540-39568-7_2
  3. Mihir Bellare and Silvio Micali. Non-Interactive Oblivious Transfer and Applications. Advances in Cryptology — CRYPTO’ 89 Proceedings, 1989. doi:10.1007/0-387-34805-0_48