înregistrare Logare
Puncte:1
James avatar Crypto

Sunt zk-STARK-urile cu adevărat rezistente la cuantum?

drapel br
James

Văd o mulțime de mențiuni că dovezile zk-STARK care sunt dezvoltate în special pentru a fi utilizate în rețelele blockchain sunt etichetate ca „rezistente cuantice”. Multe articole și rapoarte care afirmă acest lucru, susțin acest lucru pe baza ideii că zk-STARK se bazează pe hashuri rezistente la coliziuni. Înțeleg însă că nu poate exista niciodată un hash perfect rezistent la coliziuni - și că ar fi banal ca un computer cuantic să încerce să găsească o coliziune în orice hash. Există o parte pe care nu o înțeleg care face ca zk-STARK să fie rezistent la cuantum?

274
1 + 0
Geoffroy Couteau avatar
drapel cn
Geoffroy Couteau
Întrebare înrudită: [Funcțiile hash criptografice cuantice sunt sigure?](https://crypto.stackexchange.com/questions/44386/are-cryptographic-hash-functions-quantum-secure/44390#44390)
1
Răspunde
Puncte:1
Mark avatar Crypto
drapel ng
Mark

Pentru multe funcții hash, se bazează cele mai cunoscute atacuri cuantice Căutare Grover. Acest lucru accelerează o $O(N)$ operațiune la $O(\sqrt{N})$, la fel și o accelerare, dar numai printr-un factor „polinom” (nu accelerează un $O(2^N)$ operațiune la $O(N)$, sau ceva de genul ăsta).

Înțeleg însă că nu poate exista niciodată un hash perfect rezistent la coliziuni - și că ar fi banal ca un computer cuantic să încerce să găsească o coliziune în orice hash.

Partea pe care nu o înțelegi este a doua afirmație. Dacă aveți în minte un anumit atac (care depășește lucrurile bazate pe căutarea Grover), ar trebui să încercați să rezolvați detaliile, deoarece ar fi un rezultat destul de frumos.

0 + 5
poncho avatar
drapel my
poncho
@James: rețineți că căutarea lui Grover se poate dovedi într-un factor constant (nu departe de 1) al valorii optime dovedit, dacă vedeți funcția hash ca un obiect opac. Prin urmare, orice rezultat pe care îl puteți obține semnificativ mai bun decât cel al lui Grover va depinde de elementele interne ale funcției hash în sine.
0
Răspunde
James avatar
drapel br
James
Deoarece computerele clasice pot găsi o coliziune aleatorie pentru o funcție hash în $O(\sqrt{N})$, înseamnă asta că atât computerele clasice, cât și cele cuantice parcurg aproximativ același număr de pași pentru a efectua acest lucru? Sau căutarea lui Grover ar dura $O(\sqrt{\sqrt{N}})$ pași în schimb pentru a găsi o coliziune aleatorie?
0
Răspunde
James avatar
drapel br
James
De asemenea, am avut impresia că computerele cuantice sunt capabile să verifice mai multe ieșiri posibile pe pas, în funcție de numărul de qubiți - deși cunoștințele mele exacte despre această zonă sunt puțin neclare.
0
Răspunde
Mark avatar
drapel ng
Mark
@James [Aceste note](https://www.scottaaronson.com/qclec/24.pdf) fac să pară că răspunsul este $O(N^{1/3})$. Indiferent de exponentul precis, calculul cuantic nu este cunoscut pentru a obține o îmbunătățire super-polinom aici. Și a doua ta impresie este o neînțelegere comună a calculatoarelor cuantice. Vezi, de exemplu, [mitul 2 al acestui articol](https://cacm.acm.org/magazines/2019/4/235578-cyber-security-in-the-quantum-era/fulltext), care este (aproximativ) ceea ce la care faci aluzie.
0
Răspunde
poncho avatar
drapel my
poncho
@Mark: pentru o căutare de coliziune, se știe că răspunsul este între $O(N^{1/3})$ și $O(N^{1/2})$. Dacă numărați doar interogările Oracle, atunci limita inferioară este cunoscută ca fiind realizabilă; totuși, acest lucru vine cu un cost al circuitelor destul de ridicat (atât de mare încât pentru funcții hash practice, ar fi mai ieftin să paralelizezi cu un algoritm $O(N^{1/2})$). Nu se știe dacă există un algoritm mai puțin costisitor care atinge (sau se apropie) de limita inferioară.
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.