Paper 2023/1886

Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs

Sebastian Angel, University of Pennsylvania
Eleftherios Ioannidis, University of Pennsylvania
Elizabeth Margolin, University of Pennsylvania
Srinath Setty, Microsoft Research
Jess Woods, University of Pennsylvania
Abstract

This paper presents Reef, a system for generating publicly verifiable succinct non-interactive zero-knowledge proofs that a committed document matches or does not match a regular expression. We describe applications such as proving the strength of passwords, the provenance of email despite redactions, the validity of oblivious DNS queries, and the existence of mutations in DNA. Reef supports the Perl Compatible Regular Expression syntax, including wildcards, alternation, ranges, capture groups, Kleene star, negations, and lookarounds. Reef introduces a new type of automata, Skipping Alternating Finite Automata (SAFA), that skips irrelevant parts of a document when producing proofs without undermining soundness, and instantiates SAFA with a lookup argument. Our experimental evaluation confirms that Reef can generate proofs for documents with 32M characters; the proofs are small and cheap to verify (under a second).

Note: - Fixed some typos over prior version, added clarification that Reef runs fine on a small laptop (no need for big machines).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Zero-knowledge proofsregular expressionslookup argumentsSNARKzkSNARK
Contact author(s)
sebastian angel @ cis upenn edu
elefthei @ seas upenn edu
ecmargo @ seas upenn edu
srinath @ microsoft com
woodsjk @ seas upenn edu
History
2024-02-02: last of 6 revisions
2023-12-07: received
See all versions
Short URL
https://ia.cr/2023/1886
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1886,
      author = {Sebastian Angel and Eleftherios Ioannidis and Elizabeth Margolin and Srinath Setty and Jess Woods},
      title = {Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1886},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1886}},
      url = {https://eprint.iacr.org/2023/1886}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.