Clear DefinitionsAccumulator-based Cryptography
1 min read
Pronunciation
[ə-kyoo-myuh-lay-ter-bayst krip-tog-ruh-fee]
Analogy
Think of an accumulator as a magic blender: you toss in fruits (elements), blend them into a smoothie (accumulator), and yet you can still prove a particular fruit was included without showing the rest.
Definition
A class of cryptographic primitives that allow one to succinctly commit to a set of values and later prove membership (or non‑membership) without revealing the entire set. Accumulators yield constant‑size commitments and proofs.
Key Points Intro
Cryptographic accumulators enable compact set commitments and efficient membership proofs.
Key Points
Constant-size proofs: Membership witnesses remain small regardless of set size.
Dynamic vs. static: Some accumulators support adding/removing elements after setup.
Trusted setup: RSA-based accumulators require trapdoor generation; pairing-based do not.
Verification efficiency: Proofs verify in time independent of set cardinality.
Example
A UTXO-based blockchain uses an RSA accumulator to let light clients verify coin inclusion with a short witness rather than downloading all UTXOs.
Technical Deep Dive
RSA accumulators compute A = g^{∏x_i mod N} mod N under an RSA modulus N. A membership witness for x_i is w_i = g^{∏_{j≠i} x_j mod N}. Verification checks w_i^{x_i} ≡ A mod N. Bilinear pairing accumulators replace RSA with groups G1, G2 and pairing e(), enabling dynamic updates without trapdoor. Protocols integrate accumulator roots in block headers and update witnesses via authenticated data structures.
Security Warning
Trapdoor knowledge (factorization of N) breaks soundness. Always generate and then destroy trapdoor material in a verifiable MPC ceremony.
Caveat
RSA accumulators require a trusted setup; pairing-based variants avoid this but incur heavier computation.
Accumulator-based Cryptography - Related Articles
No related articles for this term.