Demonstrarea unei variații a CDH este dificilă

lăsa $(\mathbb{G},q,p)$ fi un grup $\mathbb{G}$ cu ordin primar $q$ si generator $g$. Să presupunem că CDH este greu în raport cu această configurație (și anume, dat $(g,g^a,g^b)$, este greu de găsit $g^{ab}$).

Acum luați în considerare următoarele: pentru un adversar de timp probabilistic-polinom $\mathcal{A}$, și dat $(\mathbb{G},q,p)$, alege aleatoriu $a,b,c\in \mathbb{Z}_q$ și fugi $\mathcal{A}(g,g^a,g^b,g^c)$. $\mathcal{A}$ reușește dacă scoate oricare dintre $g^{ab}, g^{ac}, g^{bc}$.

Trebuie să arăt că și asta este greu. Abordarea oarecum evidentă ar fi reducerea celor trei rezultate posibile care au ca rezultat succesul pentru CDH, de exemplu: $g^{bc}$ este exact CDH dacă intrarea ar fi $(g,g^b,g^c)$. Totuși, în acest caz ni se dă și noi $g^a$ deci aceasta nu este o simulare a CDH. Am încercat și alte abordări, încercând să aleg $c$ astfel încât să mă pot recupera $g^{ab}$ cu mare probabilitate în orice caz. M-am uitat la $g^c=g^{a+b}$ dar apoi nu sunt sigur cum să ajung $g^{ab}$ din $g^{a^2+ab}$.

Orice ajutor este apreciat, aceasta nu este teme.