Construcția algoritmului de rezolvare CDH

Presupune $C_k: (g, g^a, g^b) \mapsto g^{ab}$ este solutorul tău CDH, care îl rezolvă cu probabilitate $1 - \frac{1}{2^k}$ iar simbolul special altfel. Să le construim din $C_1$ recursiv.

Construcție de $C_{k+1}$:

1. calculati $C_k(g, g^a, g^b)$. Dacă se întoarce $g^{ab}$, scoateți-l (probabilitatea ca aceasta este $1 - \frac{1}{2^k}$). În caz contrar, treceți la pasul al doilea.
2. Generați două numere aleatoare independente $x$ și $y$ distribuit uniform de la 1 la $p-1$.
3. calculati $g^{ax}$ și $g^{de}$. Rețineți că sunt independente de $g^a$ și $g^b$.
4. calculati $C_1(g, g^{ax}, g^{de})$. Dacă returnează simbolul special, scoateți-l (probabilitatea ca acesta este $\frac{1}{2^{k+1}}$). Altfel s-a calculat $g^{abxy}$. Treci la pasul al cincilea.
5. Utilizați algoritmul euclidian extins pentru a găsi $z$, astfel încât $xyz \equiv 1 (\mod p-1)$.
6. calculati $g^{abxyz} = g^{ab}$ și scoateți-l (probabilitatea ca acesta este $\frac{1}{2^{k+1}}$).

Nu este greu de văzut, că probabilitatea totală de ieșire $g^{ab}$ este $1 - \frac{1}{2^k}$ acum.