Welcome to the resource topic for 2024/562
Title:
Practical Proofs of Parsing for Context-free Grammars
Authors: Harjasleen Malvai, Gregory Neven, Andrew Miller, Siam Hussain
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.
ePrint: https://eprint.iacr.org/2024/562
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .