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 .