Welcome to the resource topic for 2024/474
Title:
Accumulation without Homomorphism
Authors: Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, William Wang
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.
ePrint: https://eprint.iacr.org/2024/474
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 .