Lăsa $\mathbb G$ cu generator $g$, este comanda principală de 256 de biți $q$, și primul de 128 de biți $p$ fi cunoscut și fixat.
Să presupunem că obținem un algoritm $\mathcal A$ care la intrare $(h_1,h_2)\in\mathbb G^2$, cu $h_1=g^{a_1}$, $h_2=g^{a_2}$ pentru aleatoriu $a_1,a_2\in\mathbb Z_q$, iesiri $h_3=g^{a_1+a_2\bmod p}$ cu probabilitate nedisparatoare, ca în întrebare.
Definiți algoritmul $\mathcal A'$ că la intrare $h\in\mathbb G$ încercări de ieșire $y$ cu $g^y=h$, iar spre aceasta:
- remiză $u$ aleatoriu în $\mathbb Z_q$, calculează $h_1=g^u\;h$, care acum este aleatoriu în $\mathbb G$; există astfel un unic (încă necunoscut, aleatoriu) $a_1\in\mathbb Z_q$ cu $g^{a_1}=h_1$
- remiză $a_2$ aleatoriu în $\mathbb Z_q$, calculează $h_2=g^{a_2}$
- aleargă $\mathcal A$ cu intrare $(h_1,h_2)$, devine $h_3$ presupus a fi (cu probabilitate care nu dispare) $g^{a_1+a_2\bmod p}$
- găsește $x\in\mathbb Z_q$ cu $0\le x<p<2^{128}$ astfel încât $g^x=h_3$, care necesită în ordinea lui $2^{66}$ operațiuni de grup folosind rho lui Polard cu puncte distinse, memorie posibilă mică și este ușor de distribuit
- calculează $r=x-a_2\bmod p$; tine $a_1\equiv r\bmod p$, și $0\le a_1<q$; lăsați (sd încă necunoscut) $s\în\stânga[0,\stânga\lfloor q/p\right\rfloor\right]$ fie astfel încât $a_1=r+s\,p$, prin urmare $g^{r+s\,p}=h_1$, prin urmare $g^{s\,p}=h_1\,g^{q-r}$, prin urmare $g^s=(h_1\,g^{q-r})^{p^{-1}\bmod q}$
- calculează $h_4=(h_1\,g^{q-r})^{p^{-1}\bmod q}$; tine $g^s=h_4$ și $s<2^{129}$
- găsește $s$ prin aceeași metodă ca și $x$
- calculează $a_1=r+s\,p$, care este astfel încât $g^{a_1}=h_1$
- calculează și ieșire $y=a_1-u\bmod q$, care este astfel încât $g^y=h$.
Algoritmul nostru $\mathcal A'$ este astfel capabil să calculeze logaritmul discret $y$ la baza $g$ a oricărui element dat $h$ în $\mathbb G$ cu o probabilitate nedisparatoare și puține lucrări fezabile. Acest lucru se presupune că este imposibil. De aici presupunem că $\mathcal A$ există este fals.
Răspundem astfel la întrebare negativ.
