Accumulator (cryptography)

In cryptography, an accumulator is a function that takes a set of elements as input and produces a single, short value representing that set. This short value, the accumulator value, serves as a compact digest of the entire set. Accumulators are designed to efficiently prove the membership (or non-membership) of elements in a set without revealing the entire set itself. They are similar in purpose to hash functions and Merkle trees, but offer different trade-offs in terms of efficiency and functionality.

The core properties of an accumulator are:

• Compactness: The accumulator value is much smaller than the size of the set it represents, allowing for efficient storage and transmission.

• Membership Proofs: It should be possible to generate a proof demonstrating that a particular element is a member of the set represented by the accumulator. These proofs should also be relatively small.

• Non-Membership Proofs (Optional): Some, but not all, accumulator schemes allow for the generation of proofs demonstrating that a particular element is not a member of the set. Constructing efficient non-membership proofs is often more complex than constructing membership proofs.

• Collision Resistance: Ideally, it should be computationally infeasible to find two different sets that produce the same accumulator value. This property is essential for the integrity of the accumulator.

• One-Wayness: Given an accumulator value, it should be computationally infeasible to determine the elements that were accumulated to produce that value. This property prevents the reconstruction of the original set from the accumulator value alone.

Accumulators can be classified based on various characteristics, including:

• Dynamic vs. Static: Static accumulators are created for a fixed set of elements, and membership cannot be modified after the accumulator is created. Dynamic accumulators allow for the addition and deletion of elements over time, with corresponding updates to the accumulator value.

• Universal vs. Member-Specific: Universal accumulators allow for membership proofs to be generated for any element. Member-specific accumulators require specific information about the element to be known during the accumulation process to later produce a proof of membership.

• Type of Accumulation Function: Different mathematical structures are used to construct accumulators, such as RSA accumulators, bilinear map accumulators, and hash-based accumulators. Each approach offers different security properties and performance characteristics.

Accumulators have various applications in cryptography and computer science, including:

• Verifiable Data Structures: Accumulators can be used to create verifiable data structures, where the integrity of the data can be easily verified using the accumulator value and membership proofs.

• Cryptographic Accumulation of Certificates: In certificate revocation systems, accumulators can efficiently represent the set of revoked certificates, allowing for compact and verifiable revocation status checks.

• Anonymous Credentials: Accumulators can be used to prove the possession of certain attributes without revealing the specific values of those attributes.

• Blockchain Technologies: Accumulators are being explored for use in blockchain technologies to improve the efficiency of state verification and membership testing.

The security of accumulator schemes relies on the underlying cryptographic assumptions used in their construction, such as the hardness of the RSA problem or the discrete logarithm problem.