CDH ⇒ NIKE (Diffie–Hellman with a hard-core bit)

Fully-black-box reduction · standard model · DH76, GL89 · security loss: polynomial: the Goldreich–Levin decoder turns a key distinguisher with advantage ε into a CDH solver with success probability Ω(ε²) and running time poly(L, 1/ε)

Statement

If CDH is hard for $\mathsf{GrGen}$, let party $A$ publish $(g^a,s_A)$ and party $B$ publish $(g^b,s_B)$ for uniform exponents and uniform $s_A,s_B\in \{0,1{\}}^L$, where $L$ is the encoding length of group elements, and let both take the key $⟨g^{ab},s_A\oplus s_B⟩$, the inner product of the encoding of $g^{ab}$ with $s_A\oplus s_B$ over ${\mathbb{F}}_2$ — DH76. The key is pseudorandom given both public keys, since the inner product with a uniform string is a hard-core predicate of any value that is hard to compute from public data — GL89. This is a NIKE with one-bit keys.

Sketch

A distinguisher between the key and a uniform bit predicts $⟨g^{ab},s⟩$ from $(g,g^a,g^b,s)$ with advantage $\epsilon$, and the Goldreich–Levin decoder, querying it on many $s$, lists candidates for $g^{ab}$ containing the right one with probability $\Omega ({\epsilon }^2)$ — GL89.

Notes

• Inner products with $\Theta (\log \lambda )$ independent strings are simultaneously hard-core, so the key can have $\Theta (\log \lambda )$ bits; DDH makes $g^{ab}$ itself pseudorandom in the group (DDH ⇒ NIKE) — standard.
• With NIKE ⇒ PKE this gives IND-CPA bit encryption from CDH — folklore.