A  note on adding zero-knowledge to STARKs

Ulrich Haböck; Al Kindi

Paper 2024/1037

A note on adding zero-knowledge to STARKs

Ulrich Haböck, Polygon Labs, StarkWare

Al Kindi, Polygon Labs

Abstract

We discuss zero-knowledge in the context of univariate argument systems which use the FRI proximity test for Reed-Solomon codes as polynomial commitment scheme. We confine ourselves to small-field STARK, i.e. arguments with an arithmetization over a small finite field (the basefield), and we dwell on two techniques widely used in practice: Randomization by polynomials over the basefield, and decomposing the overall quotient into polynomials of smaller degree. In particular the latter is a source for mistakes, both in literature as well as in software implementations. The current, updated version further includes a separate discussion on perfect zero-knowledge in permutation arguments.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: STARK FRI proof of proximity zero-knowledge
Contact author(s): ulrich haboeck @ gmail com
al-kindi @ polygon technology
History: 2025-02-22: last of 4 revisions; 2024-06-26: received; See all versions
Short URL: https://ia.cr/2024/1037
License: CC BY-SA

BibTeX

@misc{cryptoeprint:2024/1037,
      author = {Ulrich Haböck and Al Kindi},
      title = {A  note on adding zero-knowledge to {STARKs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1037},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1037}
}