article · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2025

Accumulation Without Homomorphism

Bünz, Benedikt, Mishra, Pratyush, Nguyen, Wilson, Wang, William

Cited by 0Open access

Abstract

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.

Cite this paper

APA 7

Bünz, B., Mishra, P., Nguyen, W., & Wang, W. (2025). Accumulation Without Homomorphism. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). https://doi.org/10.4230/lipics.itcs.2025.23

MLA 9

Bünz, Benedikt, et al. “Accumulation Without Homomorphism.” DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), 2025, https://doi.org/10.4230/lipics.itcs.2025.23.

Chicago

Bünz, Benedikt, Pratyush Mishra, Wilson Nguyen, and William Wang. 2025. “Accumulation Without Homomorphism.” DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). https://doi.org/10.4230/lipics.itcs.2025.23.

Harvard

Bünz, B. et al. (2025) ‘Accumulation Without Homomorphism’, DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). Available at: https://doi.org/10.4230/lipics.itcs.2025.23.

BibTeX

@article{bunz2025accumulation,
  title = {{Accumulation Without Homomorphism}},
  author = {Bünz, Benedikt and Mishra, Pratyush and Nguyen, Wilson and Wang, William},
  journal = {DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)},
  year = {2025},
  doi = {10.4230/lipics.itcs.2025.23}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.