## preliminaries

### Primitive root modulo m

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

## DH Self

A & B can exchange their keys on unsecured channel.

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

## Computational Diffie–Hellman assumption

${(g, g^a, g^b) \xRightarrow{\textnormal{computationally\ intractable}} g^{ab}}$

## Decisional DH assumption

1. ${g \leftarrow \mathbb{G_q}}$
2. assumption: ${a,b \leftarrow \mathbb{Z_q}}$, the value ${g^{ab}}$ looks like a random element in ${\mathbb{G_q} }$
3. ${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: ${<\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 ${\mathbb{G_1}}$ and ${\mathbb{G_2} }$
2. There exists an efficiently computable bilinear map(pairing): ${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 ${\mathbb{G_1} }$

## q-strong Diffie-Hellman(q-SDH)

paper-On the q-Strong Diffie-Hellman Problem

## Refer

mostly in wiki XDH qSBDH-stack-exchange