DBDH ⇒ Three-party NIKE (Joux)

Fully-black-box reduction · standard model · Jou04 · security loss: none: the transcript and key are a DBDH tuple

Statement

In Joux’s protocol over a symmetric pairing group $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$, three parties publish $g^a$, $g^b$ and $g^c$ for their secrets $a,b,c\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$ and each derives $K=e(g,g{)}^{abc}$, the first as $e(g^b,g^c{)}^a$ — Jou04. If decisional BDH holds, $K$ is pseudorandom given the three messages, so this is a three-party NIKE — standard.

Sketch

Given a decisional BDH challenge $(g^a,g^b,g^c,T)$, the reduction publishes $g^a,g^b,g^c$ as the three messages and offers $T$ as the key. $T=e(g,g{)}^{abc}$ is the real key and a uniform $T$ a random one, so a key distinguisher is a decisional BDH distinguisher with the same advantage — standard.

Notes

• Without pairings, one-round key exchange among three or more parties is known from iO and one-way functions, for any polynomial number of parties — BZ14.
• The two-party case is Diffie–Hellman — DH76.
• Efficiency: in a symmetric pairing group each party sends one group element and computes one pairing and one exponentiation in ${\mathbb{G}}_T$ — standard.