Singura primitivă criptografică necesară pentru un zk-STARK este o funcție hash sigură criptografic, pe care o vom desemna $H$. Formele vulnerabile cuantice cunoscute de criptografie depind toate de alte primitive criptografice.
Pentru a preveni generarea de dovezi invalide, funcția hash $H$ trebuie să fie rezistent la pre-imagine, adică pentru o ieșire țintă $y$ ar trebui să fie greu de găsit o intrare $x$ astfel încât $H(x)=y$. Acum, dacă nu știm nimic despre funcție $H$ dincolo de rezultatele pe care le produce, acesta este un exemplu de problemă de căutare nestructurată care poate fi rezolvată prin Algoritmul lui Grover pe un computer cuantic suficient de mare și stabil în timp, aproximativ proporțional cu rădăcina pătrată a spațiului imaginii. Într-adevăr, știm că algoritmul lui Grover este în esență cea mai bună abordare posibilă pentru astfel de probleme. Cu toate acestea, algoritmul lui Grover este extrem de neparalelizabil (pentru a efectua căutarea în 1/10 din timp, trebuie să folosim computere cuantice de 100x) și se susține că căutarea de soluții pentru spațiile de imagine de 256 de biți nu va fi posibilă pentru orice proiecție rezonabilă a capacității de calcul cuantic.
În practică, o funcție hash, cum ar fi SHA256, este utilizată în zk-STARK pentru care cunoaștem detaliile de calcul complete. Cu toate acestea, nimeni nu a reușit să demonstreze vreo structură în cadrul SHA256 care să conducă la o abordare superioară abordării Grover. Credința în puterea lui SHA256 este de așa natură încât este folosit ca unul dintre punctele de referință în procesul de criptografie post-cuantică NIST (securitatea de nivel 2 este definită ca fiind nevoie de nu mai puține resurse pentru a sparge decât găsirea unei coliziuni SHA256; vezi cererea de propuneri secțiunea 4.A.5).
Chiar dacă SHA256 a afișat dovezi ale structurii care permite atacuri superioare lui Grover, există multe alte funcții hash care ar putea fi integrate cu ușurință în cadrul zk-STARK. Din toate aceste motive, există o mare încredere în siguranța cuantică a cadrului zk-STARK.
