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

Sebastian Angel; Eleftherios Ioannidis; Elizabeth Margolin; Srinath Setty; Jess Woods

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: 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 proofs regular expressions lookup arguments SNARK zkSNARK
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},
      note = {\url{https://eprint.iacr.org/2023/1886}},
      url = {https://eprint.iacr.org/2023/1886}
}