Eli Margolin
April 10, 2024 at 11:00 AM on Zoom / Soda Hall
Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs
Abstract: This talk will present 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. I’ll 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).
Bio: Eli Margolin is a PhD student at the University of Pennsylvania advised by Sebastian Angel. Her work focuses on adapting traditional security tooling to be more privacy preserving, with a focus on Zero Knowledge Proofs and their applications. You can find more information about her on her website: ecmargo.github.io