Research Article
Efficient Zero Knowledge for Regular Language
@INPROCEEDINGS{10.1007/978-3-031-64948-6_19, author={Michael Raymond and Gillian Evers and Jan Ponti and Diya Krishnan and Xiang Fu}, title={Efficient Zero Knowledge for Regular Language}, proceedings={Security and Privacy in Communication Networks. 19th EAI International Conference, SecureComm 2023, Hong Kong, China, October 19-21, 2023, Proceedings, Part I}, proceedings_a={SECURECOMM}, year={2024}, month={10}, keywords={zero knowledge proof zkSNARK Aho-Corasick Automata commit-and-prove commitment schemes}, doi={10.1007/978-3-031-64948-6_19} }- Michael Raymond
Gillian Evers
Jan Ponti
Diya Krishnan
Xiang Fu
Year: 2024
Efficient Zero Knowledge for Regular Language
SECURECOMM
Springer
DOI: 10.1007/978-3-031-64948-6_19
Abstract
A succinct zero knowledge proof for regular language membership, 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(\texttt {zkreg }), a distributed commit-and-prove system that handles such complexity. In(\texttt {zkreg }), cryptographic operations are encoded using arithmetic circuits, and input acceptance is modeled as a zero knowledge subset problem using(\varSigma )-protocols. We introduce a Feedback Commit-and-Prove (FB-CP) scheme, which connects(\varSigma )-protocols and the Groth16 system withO(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(\texttt {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 s.
