IACR News item: 12 June 2023
Michael Raymond, Gillian Evers, Jan Ponti, Diya Krishnan, Xiang Fu
ePrint Report
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.
Additional news items may be found on the IACR news page.