Coinductive Proofs of Regular Expression Equivalence in Zero Knowledge
Proceedings of the ACM on Programming Languages · 09.10.2025 · 9 (OOPSLA2) · 357-385
DOI: 10.1145/3763063 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 09.10.2025. Verfasst von John C. Kolesar und 3 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 77 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
Zero-knowledge (ZK) protocols enable software developers to provide proofs of their programs’ correctness to other parties without revealing the programs themselves. Regular expressions are pervasive in real-world software, and zero-knowledge protocols have been developed in the past for the problem of checking whether an individual string appears in the language of a regular expression, but no existing protocol addresses the more complex PSPACE-complete problem of proving that two regular expressions are equivalent. We introduce Crêpe , the first ZK protocol for encoding regular expression equivalence proofs and also the first ZK protocol to target a PSPACE-complete problem. Crêpe uses a custom calculus of proof rules based on regular expression derivatives and coinduction, and we introduce a sound and complete algorithm for generating proofs in our format. We test Crêpe on a suite of hundreds of regular expression equivalence proofs. Crêpe can validate large proofs in only a few seconds each.
Förderung
- National Science Foundation
Zitieren
APA
Kolesar, J. C., Ali, S., Antonopoulos, T., & Piskac, R. (2025). Coinductive Proofs of Regular Expression Equivalence in Zero Knowledge. Proceedings of the ACM on Programming Languages, 9(OOPSLA2), 357-385. https://doi.org/10.1145/3763063
Vancouver
Kolesar JC, Ali S, Antonopoulos T, Piskac R. Coinductive Proofs of Regular Expression Equivalence in Zero Knowledge. Proceedings of the ACM on Programming Languages. 2025;9(OOPSLA2):357-385. doi:10.1145/3763063
BibTeX
@article{Kolesar2025,
author = {Kolesar, John C. and Ali, Shan and Antonopoulos, Timos and Piskac, Ruzica},
title = {Coinductive Proofs of Regular Expression Equivalence in Zero Knowledge},
journal = {Proceedings of the ACM on Programming Languages},
year = {2025},
volume = {9},
number = {OOPSLA2},
pages = {357--385},
doi = {10.1145/3763063}
}
EUVIMED