Paper 2024/562
Practical Proofs of Parsing for Context-free Grammars
Abstract
In this work-in-progress, we present a series of protocols to efficiently prove statements about strings in context-free grammars (CFGs). Our main protocol for proving proofs of correct parsing for strings in a CFG flexibly accommodates different instantiations of zero-knowledge proof systems as well as accumulation schemes. While improvements in the modular cryptographic primitives can be carried over for improvements in our protocols, even simpler proof systems, which do not support state-of-the-art techniques such as permutation checks can generate proofs of correct parsing of a string of size $n$ by proving the correctness of a circuit of size $\mathcal{O}(cn)$, where $c$ is the cost of verifying a set membership proof in the chosen accumulation scheme.
Note: Work in progress with future work plan in section 4.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- parsingcontext-free grammarszero-knowledge proofs
- Contact author(s)
-
hmalvai2 @ illinois edu
gregory neven @ chainlinklabs com
soc1024 @ illinois edu
siam hussain @ smartcontract com - History
- 2024-04-12: approved
- 2024-04-11: received
- See all versions
- Short URL
- https://ia.cr/2024/562
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/562,
author = {Harjasleen Malvai and Gregory Neven and Andrew Miller and Siam Hussain},
title = {Practical Proofs of Parsing for Context-free Grammars},
howpublished = {Cryptology ePrint Archive, Paper 2024/562},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/562}},
url = {https://eprint.iacr.org/2024/562}
}
