preliminaries

Primitive root modulo m

  1. ad1(mod m),dm1{a^d \equiv 1 (mod \ m), d \leqslant m-1}
  2. def δm(a)={agcd(a,m)=1,dmin{ad1(mod m)}}{def\ \delta_m(a) = \{a|gcd(a, m) = 1, d\leftarrow min\{ a^d \equiv 1 (mod\ m)\}\}} and of course δm(a)φ(m){\delta_m(a) \leqslant \varphi(m)}
  3. Got Primitive root modulo m a if δm(a)=φ(m){\delta_m(a)=\varphi(m)}

DH Self

A & B can exchange their keys on unsecured channel.

  1. p{p} prime, g{g} primitive root of n;
  2. a {\leftarrow} Alice, b {\leftarrow} Bob;
  3. Common channel transfer: ga mod m{g^a\ mod\ m} and gb mod m{g^b\ mod\ m};
  4. Alice calculate: gabmod m{g^{ab} mod\ m} and Bob cal: gbamod m{g^{ba} mod\ m} and definitely gabgba{g^{ab} \equiv g^{ba}};
  5. But, Eavesdropper Eve: gab(ga,gb) mod m{g^{ab}\nLeftarrow (g^a, g^b)\ mod\ m}; the math base: Discrete Logarithm problem(DLP)

Computational Diffie–Hellman assumption

(g,ga,gb)computationally  intractablegab{(g, g^a, g^b) \xRightarrow{\textnormal{computationally\ intractable}} g^{ab}}

Decisional DH assumption

  1. gGq{g \leftarrow \mathbb{G_q}}
  2. assumption: a,bZq{a,b \leftarrow \mathbb{Z_q}}, the value gab{g^{ab}} looks like a random element in Gq{\mathbb{G_q} }
  3. a,b,c,Zq, Pr[g,ga,gb,gab]=?indistinguishablePr[g,ga,gb,gc]{a,b,c, \leftarrow \mathbb{Z_q},\ \Pr[g,g^a,g^b,g^{ab}] \xlongequal[?]{\textnormal{indistinguishable}}\Pr[g,g^a,g^b,g^c]}

External DH assumption(XDH)

two group: <G1,G2>{<\mathbb{G_1},\mathbb{G_2} >} XDH 前置条件如下:

  1. The discrete logarithm problem (DLP), the computational Diffie–Hellman problem (CDH), and the computational co-Diffie–Hellman problem are all intractable in G1{\mathbb{G_1}} and G2{\mathbb{G_2} }
  2. There exists an efficiently computable bilinear map(pairing): e(,):G1×G2GT{e(\cdot, \cdot): \mathbb{G_1} \times \mathbb{G_2} \to \mathbb{G_\textnormal{T}} }
  3. The decisional Diffie–Hellman problem (DDH) is intractable in G1{\mathbb{G_1} }

q-strong Diffie-Hellman(q-SDH)

paper-On the q-Strong Diffie-Hellman Problem

q-strong bilinear Diffie-Hellman(q-SBDH)

Refer

mostly in wiki XDH qSBDH-stack-exchange