2026-07-24T11:55:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22651 2026-04-17T05:31:51Z ddc:004 open_access

Accumulation Without Homomorphism Bünz, Benedikt Mishra, Pratyush Nguyen, Wilson Wang, William Proof-carrying data incrementally verifiable computation accumulation schemes Accumulation schemes are a simple yet powerful primitive that enable highly efficient constructions of incrementally verifiable computation (IVC). Unfortunately, all prior accumulation schemes rely on homomorphic vector commitments whose security is based on public-key assumptions. It is an interesting open question to construct efficient accumulation schemes that avoid the need for such assumptions. In this paper, we answer this question affirmatively by constructing an accumulation scheme from non-homomorphic vector commitments which can be realized from solely symmetric-key assumptions (e.g., Merkle trees). We overcome the need for homomorphisms by instead performing spot-checks over error-correcting encodings of the committed vectors. Unlike prior accumulation schemes, our scheme only supports a bounded number of accumulation steps. We show that such bounded-depth accumulation still suffices to construct proof-carrying data (a generalization of IVC). We also demonstrate several optimizations to our PCD construction which greatly improve concrete efficiency. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benedikt Bünz and Pratyush Mishra and Wilson Nguyen and William Wang 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.23 urn:nbn:de:0030-drops-226510 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.23 eng https://creativecommons.org/licenses/by/4.0/legalcode