Computational cryptography › Public-key encryption and key exchange › Classical number theory › Pairing groups: BLS12-381, BN254
Hardness assumptionKE: gives key exchangeTD: gives trapdoor functions

Bilinear DH family

In plain words

Diffie-Hellman-style puzzles adapted to pairing curves: work out a combined secret from pieces you can see but can't take apart.

The idea: With a pairing you can check a Diffie-Hellman relationship that you can't compute. Given g^a and h^a, a pairing confirms they share the same hidden a, but producing h^a yourself, from h and without a, is believed hard. That asymmetry is a signature scheme: a is the private key, h is the hash of a message, and h^a is the signature, which anyone can check with a pairing.

Why it matters: The basis of short BLS signatures and identity-based encryption.

The details

On the map: co-CDH, BDH, SXDH

Diffie-Hellman-style assumptions adapted to pairing groups:

They underlie BLS signatures and identity-based encryption, and they give key exchange (Joux's one-round three-party key exchange, 2000)[3], hence the KE tag.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

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, Ben Lynn and Hovav Shacham. Short Signatures from the Weil Pairing. Journal of Cryptology, 2004. doi:10.1007/s00145-004-0314-9
  2. Dan Boneh and Matt Franklin. Identity-Based Encryption from the Weil Pairing. Advances in Cryptology — CRYPTO 2001. doi:10.1007/3-540-44647-8_13
  3. Antoine Joux. A One Round Protocol for Tripartite Diffie–Hellman. Algorithmic Number Theory, 2000. doi:10.1007/10722028_23