Cum să găsiți extractorul în ipoteza cunoașterii exponentului?

De la Mihir Bellare hârtie

Lăsa $q$ fi un prim astfel încât $2q +1$ este, de asemenea, prim, și lasă $g$ fi un generator al ordinii $q$ subgrup de ${Z^â}_{2q+1}$. Să presupunem că ni se oferă intrare $q$, $g$, $g^a$ și doriți să scoateți o pereche $(C, Y)$ astfel încât $Y = C^a$. O modalitate de a face acest lucru este să alegeți câteva $c \in Z_q$, lăsa $C = g^c$, si lasa $Y = (g^a)^c$. Intuitiv, KEA1 poate fi privit ca spunând că aceasta este „singura” modalitate de a produce o astfel de pereche. Ipoteza surprinde acest lucru spunând că orice adversar care scoate o astfel de pereche trebuie să „știe” un exponent $c$ astfel încât $g^c = C$. Formalizarea cere să existe un „extractor” care să se poată întoarce $c$.

Am înțeles cum să găsesc o pereche $(C, Y)$ astfel încât $Y = C^a$ prin alegerea oricarei $c \in Z_q$

Cu toate acestea, sunt confuz despre ce înseamnă „extractor” aici. Înseamnă dată perechea $(C, Y)$ unul trebuie să găsească $c$ care a fost folosit pentru a calcula $C$? Dacă da, cum găsim $c$ dat tocmai $(C, Y)$?

Sau înseamnă altceva?

Dacă ne uităm la referințe lucrarea 11, totul va fi mai clar și așa citim lucrările; privind referințele.

Abrevieri

• DHA: Ipoteza Diffie-Hellman
• SDHA-1: Presupunerea puternică Diffie-Hellman -1

Ipotezele 8 sunt despre ceea ce vorbește KEA1; (SDHA-1). Cu propoziția 9 se arată că sub SDHA-1, DHA este valabil ( SDHA-1 $\implică $ DHA). KEA-1 este o reformulare a acestei propuneri;

KEA1: Pentru orice adversar $A$ care necesită intrare $q, g, g^a$ si se intoarce $(C, Y )$ cu $Y = C^a$ există un âextractorâ $\bar{A}$ , care a dat aceleași intrări ca $A$ se intoarce $c$ astfel încât $g^c = C$. i.e. astfel de $\bar{A}$ se numeste extractor.

Adică cuvinte, dacă adversar $A$ rezolvă SDHA-1 atunci $\bar{A}$ (numit extractor) poate rezolva DHA.