DDH ⇒ Non-interactive key exchange (NIKE)

Fully-black-box reduction · standard model · DH76 · security loss: tight for one honest pair: the DDH instance is forwarded unchanged

Statement

In the Diffie–Hellman NIKE of DH76, over $(\mathbb{G},g,p)\leftarrow \mathsf{GrGen}(1^{\lambda })$ party $i$ samples $x_i\stackrel{\$}{\leftarrow }[p]$ and publishes ${\mathsf{pk}}_i=g^{x_i}$, and parties $i$ and $j$ each compute $k_{ij}={\mathsf{pk}}_j^{x_i}={\mathsf{pk}}_i^{x_j}=g^{x_i{x}_j}$. If DDH is hard for $\mathsf{GrGen}$, then for honestly generated keys $k_{ij}$ is indistinguishable from a uniform element of $\mathbb{G}$ given $({\mathsf{pk}}_i,{\mathsf{pk}}_j)$ — folklore.

Sketch

The reduction sets $({\mathsf{pk}}_i,{\mathsf{pk}}_j,k_{ij}):=(X,Y,Z)$ from its DDH challenge: $Z=g^{xy}$ gives the real key and $Z=g^z$ a uniform one, so a distinguisher for $k_{ij}$ is a DDH distinguisher with the same advantage.

Notes

• DH76 predates the DDH assumption: the protocol is DH76’s, and its security under DDH is immediate from the definition — folklore.
• The statement covers one pair of honestly generated keys; NIKE security models with adversarially registered public keys are formalized in FHKP13.