Măcinarea în euristica Fiat-Shamir

Ce îl evită pe doveditor să-și macine mesajele pentru a putea falsifica o dovadă falsă?

Am putea pune exact aceeași întrebare și cu privire la un oracol aleatoriu! Ce îl împiedică pe doveditor să-și macine mesajele până când poate falsifica o dovadă falsă? Ceea ce sugerezi se poate face în totalitate cu un RO.

Și răspunsul este: ar trebui să existe un număr foarte mic de mesaje $\alpha_1$ astfel încât $\beta_1 = H(\alpha_1)$ lasă dovatorul să aibă un avantaj. Într-un mod tipic $\Sigma$-protocol, de exemplu, atunci când afirmația nu este în limbă (deci probatorul înșală), există în medie unu $\alpha_1$ care permite doveditorului să trișeze. (Exercițiu: arătați că acesta este cazul pentru $\Sigma$-protocol pentru tuplurile DDH, unde este cuvântul $(X,Y)$ iar martorul este $x\in\mathbb{Z}_p$ astfel încât $X = g^x$ și $Y = h^x$). Prin urmare, dacă există $2^c$ valori posibile $\beta_1$ (acesta este spațiul provocării), probatorul rău intenționat va trebui să calculeze $O(2^c)$ hashes pentru a falsifica o dovadă falsă. Acum fa $c$ suficient de mare și obțineți securitate computațională.

Rețineți că atacul de măcinare este încă un aspect important: $\Sigma$-protocoalele au securitate necondiționată, dar imediat ce le compilați în ROM-ul cu Fiat-Shamir, au doar de calcul soliditatea. Aceasta înseamnă că parametrul de securitate pentru soliditate (spațiul de provocare) trebuie ajustat în consecință: un spațiu de provocare de 40 de biți este bine pentru un $\Sigma$-protocol (deoarece oferă un doveditor rău intenționat a $2^{-40}$ probabilitatea statistică de a încălca cu succes soliditatea, care poate fi acceptabilă în practică), dar ruptă pentru Fiat-Shamir (deoarece încălcarea protocolului compilat necesită $2^{40}$ operațiuni, care este banal de efectuat). De obicei, vom folosi un spațiu de provocare despre $2^{128}$ când utilizați Fiat-Shamir.