înregistrare Logare
Puncte:1
avatar Crypto

Duritatea unei variante a problemei CDH

drapel us
raisyn

Dat $g$, un generator al unui grup multiplicativ (peste un câmp finit sau o curbă eliptică) și elementele grupului $\left( g^x, g^a, g^b, g^c, g^{x(a+b)}, g^{x(b+c)} \right)$, este posibil să găsiți eficient valoarea lui $g^{x(a+b+c)}$ (fără cunoștințe despre valori $x, a, b, c$)?

Cred că problema în cauză este strâns legată de problema CDH (dată $\stânga (g, g^a, g^b \dreapta)$, găsi $g^{ab}$). Un algoritm eficient al CDH duce imediat la un algoritm eficient pentru problema de mai sus. Deci problema de mai sus este cel puțin nu mai grea decât CDH. Cu toate acestea, nici nu am găsit o modalitate de a folosi informații suplimentare pentru a ajunge la o soluție eficientă și nici nu am putut demonstra că este de fapt la fel de greu ca CDH. Deci orice ajutor este foarte apreciat.

78
0 + 0
Puncte:1
Ievgeni avatar Crypto
drapel cn
Ievgeni

Să presupunem $\mathcal{B}$ știe să calculeze $g^{x(a+b+c)}$, și vreau să rezolv provocarea cdh $(g,X,Y)$, (vom interpreta $X$ la fel de $g^x$ și $Y$ la fel de $g^b$) alegem scalari $d,e$ care corespund $(a+b)$ și $(b+c)$ și calculăm $Z=\mathcal{B}(X, g^d\cdot Y^{-1}, Y, g^e\cdot Y^{-1},X^d, X^e )$.

Ne intoarcem $\frac{X^{d+e}}{Z}$.

Dovada: $DLog \left(\frac{X^{d+e}}{Z}\right) = DLog \left(X^{d+e}\right) - DLog \left(Z\right) = x(d +e)- x\left( d-b + b + e-b\right) = xb$.

0 + 0
drapel us
raisyn
Este trist să văd că problema nu este de fapt mai ușoară decât CDH, altfel ar fi existat niște aplicații frumoase. Mi-a luat ceva timp să lucrez la postarea ta. Fascinant cum ai venit cu asta atât de repede. Mulțumesc mult.
0
Răspunde
Ievgeni avatar
drapel cn
Ievgeni
@raisyn De ce ești trist, dacă această problemă este mai grea, înseamnă că o poți folosi ca ipoteză de duritate pentru aplicațiile tale. Nu?
0
Răspunde
drapel us
raisyn
Ei bine, în aplicația pe care am avut-o în minte (legată de semnăturile agregate) aveam nevoie de ea invers.Dacă ar fi posibil, ar fi existat o modalitate bună de a agrega eficient semnătura într-o anumită setare.
0
Răspunde
Ievgeni avatar
drapel cn
Ievgeni
@raisyn sfătuiesc citirea „The Uber-Assumption Family” (Boyen) să aibă o intuiție de a caracteriza problemele grele într-un context de grup (chiar tu nu găsești nicio reducere la presupunerea standard).
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.