Welcome to the resource topic for 2023/1886
Title:
Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs
Authors: Sebastian Angel, Eleftherios Ioannids, Elizabeth Margolin, Srinath Setty, Jess Woods
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).
ePrint: https://eprint.iacr.org/2023/1886
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .