Paper 2023/1886
Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs
, University of PennsylvaniaAbstract
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: This version is different from the USENIX Security version in that it includes all appendices.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. USENIX Security
- 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-03-22: last of 7 revisions
- 2023-12-07: received
- See all versions
- Short URL
- https://ia.cr/2023/1886
- License
-
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},
url = {https://eprint.iacr.org/2023/1886}
}
