Welcome to the resource topic for
**2023/907**

**Title:**

Efficient Zero Knowledge for Regular Language

**Authors:**
Michael Raymond, Gillian Evers, Jan Ponti, Diya Krishnan, Xiang Fu

**Abstract:**

A succinct zero knowledge proof for regular language mem-

bership, i.e., to prove a secret string behind an encryption (hash) belongs

to a regular language is useful, e.g., for asserting that an encrypted email

is free of malware. The great challenge in practice is that the regular

language used is often huge. We present zkreg, a distributed commit-

and-prove system that handles such complexity. In zkreg, cryptographic

operations are encoded using arithmetic circuits, and input acceptance is

modeled as a zero knowledge subset problem using Σ-protocols. We in-

troduce a Feedback Commit-and-Prove (FB-CP) scheme, which connects

Σ-protocols and the Groth16 system with O(1) proof size and verifier

cost. We present a close-to-optimal univariate instantiation of zk-VPD,

a zero knowledge variation of the KZG polynomial commitment scheme,

based on which an efficient zk-subset protocol is developed. We develop

a 2-phase proof scheme to further exploit the locality of Aho-Corasick

automata. To demonstrate the performance and scalability of zkreg, we

prove that all ELF files (encrypted and hashed) in a Linux CentOS 7

are malware free. Applying inner pairing product argument, we obtain

an aggregated proof of 1.96 MB which can be verified in 6.5 seconds.

**ePrint:**
https://eprint.iacr.org/2023/907

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 .