înregistrare Logare
Puncte:2
avatar Crypto

Distribuția elementelor grupului cu biți aleși și problema durității jurnalului discret

drapel do
Panos

Pentru generator $g$ de ordine $n$ elementele grupului $y=g^x$mod $n$ sunt distribuite uniform datorită operației modulo.

Să presupunem totuși că din spațiul original de ieșire $Y$, luăm în considerare doar acele elemente $y$ care au niște biți „fixați” în reprezentarea lor binară. De exemplu, pentru $y = y_1,y_2...y_m$ (Unde $y_i$ este un pic din reprezentarea m-bit a $y$), luați în considerare spațiul de ieșire $Y'$ unde toate $y \în Y'$ au un pic static $y_i$ într-o poziție $i$ a stabilit. Sunt cei $x$ care sunt valabile astfel încât $g^x \in Y'$ (și, de asemenea, setul de complement $\bar{Y'}$) încă distribuite uniform? Cu alte cuvinte, duritatea problemei logaritmului discret este echivalentă atunci când se consideră un spațiu de ieșire $Y$ și $Y'$? Intuiția mea spune da din cauza operației modulo și a grupului ciclic, dar caut un răspuns mai convingător (cu cazuri $n$ este fie prim, fie puterea lui 2)

Am văzut lucrări care vorbesc despre „securitatea biților” (de ex. https://dl.acm.org/doi/pdf/10.1145/972639.972642 ) dar acestea vorbesc despre fragmentele din $x$, în timp ce mă gândesc la problema „inversa” pentru bucăți de $y$..

176
0 + 0
kelalaka avatar
drapel in
kelalaka
Argumentul simplu, dacă $n$ nu este puterea lui 2 atunci nu!
0
Răspunde
drapel do
Panos
Deci, să distingem între cele 2 cazuri (a) dacă $n$ este prim și (b) dacă $n$ este puterea lui 2. Spuneți în cazul (a) distribuția lui $x$ unde $g^x$ are unele prefixul ales este denaturat?
0
Răspunde
drapel do
Panos
Am reformulat întrebarea dacă ajută
0
Răspunde
Puncte:1
Daniel S avatar Crypto
drapel ru
Daniel S

UPDATE 20220330: Răspuns nou în urma clarificării întrebării; răspunsul vechi reținut pentru a înțelege comentariile.

Cred că ceea ce întrebi este dacă fragmentele din $y$ acționează ca o funcție de bază pe inversul unei funcții unidirecționale (în acest caz, funcția logaritmului discret modulo $n$).Pentru detalii despre funcțiile de bază, consultați, de exemplu, secțiunea 2.4 pentru Bazele criptografiei). Cu toate acestea, dacă inversul unei funcții unidirecționale este ușor de calculat (ceea ce este adevărat în cazul tău, deoarece funcția de exponențiere poate fi calculată în timp polinomial), atunci nu există funcții de bază.

Criptografii nu formulează acest lucru în termeni de distribuție uniformă, ci în termeni de discriminatori care pot fi calculați în timp polinomial și oferă un avantaj netrivial (a se vedea definiția 2.4 din note). Ei spun că un predicat $b(y)$ este hard-core pentru $f$ dacă pentru toți discriminatorii de timp polinomii avem $$\mathbb P(A(f(U_n)),1^n)=b(U_n)<1/2+1/p(n).$$ In cazul tau $f$ este funcția $y=g^x\mod n\mapsto x$ și funcția ta $b$ este $i$al-lea bucată de $y=g^x\mod n$. Totuși, am discriminatorul contra-exemplu $A(z,1^n)$ care este de a calcula $g^z\mod n$ (în timp polinomial) și uită-te la $i$al-lea bit. Acest lucru discriminează răspunsurile cu probabilitatea 1 deoarece cu primul argument $f(y)=x$ se întoarce $b(y)$.

Cu alte cuvinte, există o lipsă de uniformitate verificabilă din punct de vedere computațional, deoarece pot testa rapid $x$ valori pentru a vedea dacă produc sau nu rezultate care se află în $Y'$.

Vechi răspuns.

Da. Lăsa $|Y'|=M$ si lasa $z$ fi orice element al $Y'$ atunci teorema lui Bayes ne spune că $$\mathbb P(g^x\mod n=z|g^x\mod n\in Y')=\frac{\mathbb P(g^x\mod n=z)\mathbb P(g^x \mod n\in Y'|g^c\mod n=z)}{\mathbb P(g^x\mod n\in Y')}.$$ Acum notăm că $\mathbb P(g^x\mod n=z)=1/\phi(n)$ (prin uniformitatea observată în întrebare), $\mathbb P(g^x\mod n\in Y'|g^c\mod n=z)=1$ și asta $\mathbb P(g^x\mod n\in Y')=M/\phi(n)$ (din nou prin uniformitatea în întrebare). Prin urmare $$\mathbb P(g^x\mod n=z|g^x\mod n\in Y')=1/M$$ pentru toți $z\în Y'$ care descrie o distribuţie uniformă.

0 + 0
drapel do
Panos
Mulțumesc, dar abordarea Bayes captează cu adevărat distribuția $x$? i.e. acele $x$ care sunt „valide” astfel încât $g^x \in Y'$ ar putea fi denaturate în ceea ce privește întregul spațiu $Y$? De exemplu. poate pentru „repararea” unui bit $y_b$, acei $x$ ar putea avea probabilitatea ca unul dintre biții săi să fie egal cu 0 să fie mai mare de 1/2?
0
Răspunde
Daniel S avatar
drapel ru
Daniel S
Nu sunt sigur că vă urmăresc comentariul.Dacă întrebați „Este posibil să construim o distribuție de probabilitate condiționată în care teorema lui Bayes nu se aplică?” Atunci răspunsul este „Nu”. De asemenea, rețineți că, deși valorile lui $g^x$ sunt distribuite uniform, biții nu sunt de ex. pentru un $B$-bit $p$, MSB este 0 cu probabilitatea $(2^{B-1}-1)/(p-1)$ și 1 cu probabilitatea $(p-2^{B-1} )/2$.
0
Răspunde
drapel do
Panos
Deci întreb despre distribuția $x$, nu $g^x$. Și întrebarea mea este dacă distribuția lui $x$ (adică probabilitatea ca un bit al lui $x$ să fie 0 sau 1) se schimbă cumva dacă „repar” un anumit bit în reprezentarea lui $y = g^x$. Nu văd cum faptul că P = $1/M$ pentru toți $z \în Y'$ arată că $x$ sunt încă distribuite uniform în spațiul de ieșire *original* $Y$..
0
Răspunde
Daniel S avatar
drapel ru
Daniel S
Cred că acum am înțeles întrebarea dvs. și mi-am modificat răspunsul.
0
Răspunde
drapel do
Panos
Deci întrebarea este dacă un anumit bit de ieșire $y$ dezvăluie unele informații despre orice bit de preimagine $x$. Prin urmare, cred că funcția $b$ ar trebui să fie *orice* bit de $x$ (**nu** $y$), iar dacă discriminatorul cu acel bit de $y$ setat, poate prezice cu o probabilitate mai mare de 1 /2 orice bit de $x$ (recompensă acordată deoarece expiră)
0
Răspunde
Daniel S avatar
drapel ru
Daniel S
Dacă ne limităm la aproximații liniare pe un singur bit așa cum le descrieți, atunci orice informație reciprocă între un singur bit de $y$ și un singur bit de $x$ funcționează în ambele sensuri, ambele predicate fiind ușor de calculat. În afară de polarizarea biților din cauza modulului, orice informație suplimentară ar fi un predicat dur asupra biților logaritmului discret despre care nu credem că există.
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.