Nguyên hàm mật mã duy nhất được yêu cầu cho zk-STARK là hàm băm bảo mật bằng mật mã, mà chúng ta sẽ biểu thị $H$. Tất cả các dạng mật mã dễ bị tổn thương lượng tử đã biết đều phụ thuộc vào một số nguyên thủy mật mã khác.
Để ngăn chặn việc tạo ra các bằng chứng không hợp lệ, hàm băm $H$ cần phải có khả năng chống hình ảnh trước, tức là đối với đầu ra mục tiêu $y$ thật khó để tìm thấy một đầu vào $x$ như vậy mà $H(x)=y$. Bây giờ, nếu chúng ta không biết gì về chức năng $H$ ngoài các đầu ra mà nó tạo ra, đây là một ví dụ về vấn đề tìm kiếm phi cấu trúc có thể được giải quyết bằng Thuật toán Grover trên một máy tính lượng tử đủ lớn và ổn định trong thời gian gần như tỷ lệ với căn bậc hai của không gian hình ảnh. Thật vậy, chúng ta biết rằng thuật toán Grover về cơ bản là cách tiếp cận tốt nhất có thể cho những vấn đề như vậy. Tuy nhiên, thuật toán của Grover rất không thể song song (để thực hiện tìm kiếm trong 1/10 thời gian chúng ta phải sử dụng máy tính lượng tử 100x) và người ta lập luận rằng việc tìm kiếm giải pháp cho không gian hình ảnh 256-bit sẽ không khả thi đối với bất kỳ dự báo hợp lý nào về khả năng tính toán lượng tử.
Trên thực tế, một hàm băm như SHA256 được sử dụng trong zk-STARK mà chúng tôi biết đầy đủ chi tiết tính toán. Tuy nhiên, không ai có thể chứng minh bất kỳ cấu trúc nào trong SHA256 sẽ dẫn đến cách tiếp cận ưu việt hơn cách tiếp cận Grover. Niềm tin vào sức mạnh của SHA256 đến mức nó được sử dụng như một trong những điểm chuẩn trong quy trình mã hóa sau lượng tử của NIST (bảo mật cấp 2 được định nghĩa là sử dụng không ít tài nguyên để phá vỡ hơn là tìm ra xung đột SHA256; xem kêu gọi đề xuất phần 4.A.5).
Ngay cả khi SHA256 đã hiển thị bằng chứng về cấu trúc cho phép tấn công ưu việt hơn đối với Grover, vẫn có nhiều hàm băm khác có thể dễ dàng tích hợp vào khung zk-STARK. Vì tất cả những lý do này, chúng tôi rất tin tưởng vào tính an toàn lượng tử của khung zk-STARK.
