înregistrare Logare
Puncte:2
fgrieu avatar Crypto

Găsirea $k$ șiruri $M_i$ astfel încât XOR al hashurilor $k$ $H(i,M_i)$ este zero

drapel ng
fgrieu

Lăsa $k\ge2$ fie o constantă moderată dată și $H:[0,k)\times\{0,1\}^*\la\{0,1\}^b$ fi a $b$-bit dată funcție hash asimilată unui oracol aleatoriu. De exemplu $H(i,M)=\operatorname{SHAKE256}((\subliniați i\mathbin\|M),b)$ Unde $\subliniați i$ este $i$ codificat conform ASN.1 DER.

Cât de greu este de găsit din punct de vedere computațional $k$ siruri de caractere $M_i$ astfel XOR-ul $k$ hashuri $H(i,M_i)$ cu $0\le i<k$ este zero?

Motivația este evaluarea costului unui atac asupra acest protocol.

Văd că pentru $k=2$ probabil că vom reuși $2^{b/2+2}$ hashes și rho lui Pollard distribuit cu puncte distinse. Și că un adversar puternic arbitrar cu acces oracol la hash ar putea face cu mult mai puține interogări hash când $k$ devine mare, dar îmi este greu să cuantific munca de calcul.

55
1 + 1
kodlu avatar
drapel sa
kodlu
Întrebare și răspuns înrudit (aproape același?): https://crypto.stackexchange.com/questions/72596/is-it-feasible-to-find-n-hashes-that-sum-up-to-a-given -hash/72606#72606
2
Răspunde
Puncte:2
avatar Crypto
drapel us
Mikero

Dacă calculezi $2^{b/k}$ valorile formei $H(i,\cdot)$, pentru fiecare $i$, atunci cu mare probabilitate va exista niste set de reprezentanți care XOR la ​​zero. Intuitiv, va exista $(2^{b/k})^k$ modalități de a alege un reprezentant pentru fiecare $i$, deci una dintre aceste moduri este probabil să XOR la ​​zero. Provocarea este găsirea eficientă a unei astfel de soluții.

Această problemă este studiată de Wagner în O problemă generalizată a zilei de naștere. El arată un algoritm care rulează în timp $O(k \cdot 2^{b/(1+\log k)})$. Într-adevăr, algoritmul nu se îmbunătățește foarte mult ca $k$ crește, deși pentru $k=4$ primim deja $O(2^{b/3})$ care este un salt mare de la $k=2$ caz.

am gasit o lucrare de continuare de Brakerski, Stephens-Davidowitz & Vaikuntanathan, ceea ce demonstrează că un algoritm mai rapid este puțin probabil.

De asemenea, rețineți că atunci când $k \ge b$, soluțiile pot fi găsite în timp polinomial prin algebră liniară simplă. Vezi Anexa A din această hârtie.

0 + 2
kodlu avatar
drapel sa
kodlu
vezi și https://crypto.stackexchange.com/questions/72596/is-it-feasible-to-find-n-hashes-that-sum-up-to-a-given-hash/72606#72606
1
Răspunde
drapel ph
bmm6o
Aceste rezultate sunt toate despre sume întregi. Se aplică rezultatele pentru $Z_2^b$?
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.