USENIX Security '24 - Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs скачать в хорошем качестве

USENIX Security '24 - Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs

Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs Sebastian Angel, Eleftherios Ioannidis, and Elizabeth Margolin, University of Pennsylvania; Srinath Setty, Microsoft Research; Jess Woods, University of Pennsylvania 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). View the full USENIX Security '24 program at https://www.usenix.org/conference/use...