Nu cred. Dacă am putea extinde o astfel de construcție la grupul cutie neagră, ar da a $q^{1/4}$ metoda de rezolvare a logaritmilor discreti din acel grup. De asemenea, rețineți că dacă constrângerea de dimensiune este activată $a$, $b$, $k$ și $k'$ este eliminat, problema nu este bine definită (pot fi mai multe soluții chiar și în cazul constrâns; nu sunt sigur).
Soluții multiple dacă constrângerile de dimensiune sunt ignorate
În mod generic, putem considera această problemă izomorfă la o problemă de algebră liniară în exponenți. Noi scriem $c_1=a+km_1$, $C_i=g^c_i\mod p$ si asa mai departe. Prin înmulțirea termenilor $C_iC_j$ sau termeni exponențiatori $C_i^d$ putem adauga $c_i+c_j$ sau înmulțiți exponenții noștri necunoscuți cu constante $dc_i$, ca să putem găsi $g^x$ Unde $x$ este o combinație liniară arbitrară a acestora $c_i$ (un oracol Diffie-Hellman ne-ar permite să ne formăm $g^y$ Unde $y$ este o expresii polinom arbitrare în $c_i$). Restricționându-ne la astfel de combinații liniare (cum ar fi cazul unui grup cutie neagră), problema devine să găsim o combinație liniară a noastră. $c_i$ care este egal cu $a$ sau $b$.
Avem sistemul
$$\left(\matrix{1&0&m_1&0\ 0&1&0&-m_2\ 1&0&m_3&0\ 0&1&0&-m_4}\right)\left(\matrix{a\ b\ k\ k'}\right)=\left (\matrix{c_1\ c_2\c_3\c_4}\right)\pmod{\phi(p)}$$
dacă scriem $M$ pentru matricea 4x4 și $\mathbf c$ pentru vectorul din dreapta, am putea spera să găsim combinația noastră liniară din $M^{-1}\mathbf c$. Oricum vedem asta
$$\mathrm{det}(M)=m_1m_4-m_2m_3\equiv 0\pmod{\phi(p)}$$
astfel încât matricea noastră să nu fie inversabilă.
Algebra liniară de liceu ne spune acum că fie nu avem soluții, fie că avem multe soluții. Faptul că construcția noastră definește o singură soluție ne spune că există multe soluții. O mică reducere de rând ne spune asta $m_2c_1+m_1c_2-m_3c_3-m_1c_4\equiv 0\pmod{\phi(p)}$. În special atunci dacă de ex. $m_1$ este coprim la $\phi(p)$, putem determina $C_4$ dat $C_1$, $C_2$ și $C_3$ și astfel a patra ecuație nu ne oferă informații suplimentare. În absența unei degenerescențe ulterioare, rezultă că putem, de exemplu, să alegem un arbitrar $g^a$ și apoi găsiți $g^k\equiv(C_1/g^a)^{1/m_1}\pmod p$, $g^b\equiv C_2(g^k)^{m_2}\pmod p$ și $g^{k'}\equiv(C_3/g^a)^{1/m_3}$ care produc $C_1$, $C_2$, $C_3$ și $C_4$ cu care ni se prezintă.Însă $a$, $b$, $k$ și $k'$ asociate cu acestea nu vor îndeplini neapărat constrângerile de dimensiune.
Un no-go în modelul cutie neagră
Acum să presupunem că putem extinde un astfel de rezolvator la un grup multiplicativ cutie neagră. Să presupunem că ni se oferă o problemă de logaritm discret pentru generator $g$ de ordine $q$ și elementul $C_1$ este un astfel de grup. Alegem un arbitrar $m_1$ iar printr-un argument de numărare există o mare probabilitate ca $c_1$ poate fi scris sub forma $c_1\equiv a+km_1\pmod q$ cu $a,k\le q^{1/2}$. Scrie $d=[q^{1/2}]$. Acum sunăm solutorul nostru cu $C_1=C_1$, $C_2=g^d/C_1$, $C_3=C_1g^{m_1}$ și $C_4=g^d/C_3$ și $m_1=m_2=m_3=m_4$ (corespunzător valorilor $b=d-a$ și $k'=k+1$ care satisfac constrângerile de dimensiune). Rezolvatorul nostru va reveni $g^a$ din care ne putem recupera $a$ folosind metoda baby-steps/giant-steps în $O(\rădăcină 4\din q)$ trepte. La fel ne putem recupera $g^k=(C_1/g^a)^{1/m_1}$ și $k$ in alt $O(\rădăcină 4\din q)$ trepte. Acest lucru ne permite să calculăm $c_1$ cu $O(\rădăcină 4\din q)$ operațiuni de grup care nu sunt posibile pentru un grup cutie neagră.
