Paper 2024/474

Accumulation without Homomorphism

Benedikt Bünz, New York University
Pratyush Mishra, University of Pennsylvania
Wilson Nguyen, Stanford University
William Wang, New York University

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.

Available format(s)
Cryptographic protocols
Publication info
proof-carrying dataincrementally verifiable computationaccumulation schemesfolding
Contact author(s)
bb @ nyu edu
prat @ upenn edu
wdnguyen @ stanford edu
ww @ priv pub
2024-03-25: revised
2024-03-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benedikt Bünz and Pratyush Mishra and Wilson Nguyen and William Wang},
      title = {Accumulation without Homomorphism},
      howpublished = {Cryptology ePrint Archive, Paper 2024/474},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.