Paper 2023/907

Efficient Zero Knowledge for Regular Language

Michael Raymond, Hofstra University
Gillian Evers, Hofstra University
Jan Ponti, Hofstra University
Diya Krishnan, Ramanujan Homeschool Academy
Xiang Fu, Hofstra University

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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. SecureCOM 2023
zero knowledge proofzkSNARKAho-Corasick Automatacommit-and-provecommitment schemes
Contact author(s)
Michael Raymond1 @ comcast net
gillian e2019 @ gmail com
jan michael ponti @ outlook com
diya is smart @ gmail com
Xiang Fu @ hofstra edu
2023-09-10: last of 2 revisions
2023-06-11: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Michael Raymond and Gillian Evers and Jan Ponti and Diya Krishnan and Xiang Fu},
      title = {Efficient Zero Knowledge for Regular Language},
      howpublished = {Cryptology ePrint Archive, Paper 2023/907},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.