RSA Accumulators

Imagine you need to convince a stranger that a particular name is on a list — without handing them the whole list, and without letting them infer the other names. That is exactly what a cryptographic accumulator does.

An RSA accumulator takes any finite set of values and collapses them into a single large integer called the accumulation value. Anyone who holds that one integer can later receive a short membership proof for a specific element and verify — with just one modular exponentiation — that the element really is in the set.

The trick is pure number theory: repeatedly raising a base to prime-encoded powers modulo a special RSA modulus. First described by Benaloh and de Mare (EUROCRYPT 1993) and significantly extended by Baric and Pfitzmann (1997) and Boneh, Bünz and Fisch (CRYPTO 2019), RSA accumulators sit at the heart of privacy-preserving systems that need constant-size commitments to large datasets.

What makes them powerful — and subtle — is the strong RSA assumption: forging a fake membership proof is as hard as computing roots modulo a number whose factorization you do not know.

This demo uses small numbers so every step is visible. A real RSA accumulator would use a 2048-bit modulus; here we work modulo a tiny RSA-like product so you can follow each multiplication by hand.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="params-row">
  <span class="param-label">{{label_modulus}} <b id="lbl-n"></b></span>
  <span class="param-label">{{label_base}} <b id="lbl-g"></b></span>
</div>
<div class="set-area">
  <div class="set-header">{{label_set}}</div>
  <div class="chips" id="set-chips"></div>
  <div class="add-row">
    <select id="add-select"></select>
    <button id="btn-add" type="button">{{btn_add}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div class="accum-row">
  <span class="param-label">{{label_accumulator}}</span>
  <span class="accum-value" id="accum-val">—</span>
</div>
<div class="proof-area" id="proof-area" style="display:none">
  <div class="set-header">{{label_prove}}</div>
  <div class="chips" id="proof-chips"></div>
</div>
<div class="status" id="status"></div>
<div class="steps" id="steps"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.params-row { display: flex; gap: 1.4rem; margin-bottom: .7rem; }
.param-label { font-size: .85rem; color: #555; }
.set-area, .proof-area { border: 1px solid #cdd9e3; border-radius: 10px; padding: .6rem .8rem; margin-bottom: .6rem; }
.set-header { font-size: .78rem; font-weight: 700; color: #7a8fa0; text-transform: uppercase; letter-spacing: .05em; margin-bottom: .4rem; }
.chips { display: flex; flex-wrap: wrap; gap: .35rem; min-height: 2rem; }
.chip { display: inline-flex; align-items: center; gap: .3rem; padding: .25rem .55rem; border-radius: 20px; font: 700 13px ui-monospace, monospace; background: #1d3557; color: #fff; cursor: pointer; user-select: none; transition: background .12s; }
.chip:hover { background: #2e4f7a; }
.chip.proving { background: #0a7d33; }
.chip .remove { font-size: .9em; opacity: .7; }
.add-row { display: flex; gap: .5rem; margin-top: .5rem; }
select { font: 600 13px system-ui; padding: .3rem .5rem; border: 1px solid #cdd9e3; border-radius: 8px; background: #fff; cursor: pointer; }
button { font: 600 13px system-ui; padding: .35rem .75rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.accum-row { display: flex; align-items: center; gap: .7rem; margin-bottom: .5rem; }
.accum-value { font: 700 20px ui-monospace, monospace; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-bottom: .3rem; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.steps { font-size: .82rem; color: #555; line-height: 1.7; }
.steps b { color: #1d3557; }

// Code not found

Notice that the accumulation value is always a single integer — no matter how many elements are in the set. The membership proof for any element is also a single integer: the accumulator computed over the rest of the set. Verification is one modular exponentiation, done in constant time regardless of set size.

The construction is elegant, but the security rests on a precise hardness assumption.

How accumulation works. Choose a large RSA modulus $N = p \cdot q$ (with $p, q$ secret primes) and a base $g$. To accumulate a set $\{e_1, e_2, \dots, e_k\}$ of distinct odd primes, compute:

$$A = g^{e_1 \cdot e_2 \cdots e_k} \bmod N$$

Membership proof. To prove element $e_i$ is in the set, compute the witness — the accumulator of all other elements:

$$w_i = g^{e_1 \cdots e_{i-1} \cdot e_{i+1} \cdots e_k} \bmod N$$

Verification. A verifier checks in one step:

$$w_i^{e_i} \equiv A \pmod{N}$$

Why it is secure. The strong RSA assumption states: given $N$ and $A$, it is computationally infeasible to find any pair $(w, e)$ with $e > 1$ such that $w^e \equiv A \pmod{N}$ — unless you already know the factorization of $N$. A forger who invents a fake witness for an element not in the set would have to compute such a root, which is believed to be as hard as factoring.

Unlike simpler hash-based commitments, RSA accumulators support non-membership proofs too (via Bezout coefficients), dynamic updates (adding or removing elements with adjustable witnesses), and batch proofs that aggregate many membership checks into one. The price is a trusted or distributed setup to generate $N$ without anyone knowing $p$ and $q$.

Whenever a system needs to commit to a large set and answer membership questions efficiently, RSA accumulators are a natural fit:

• Certificate revocation: instead of distributing a growing Certificate Revocation List (CRL), a CA publishes one accumulation value; clients verify revocation with a single exponentiation.
• Anonymous credentials: a user can prove they hold a credential in a certified set without revealing which one, using zero-knowledge proofs built on top of the accumulator witness.
• Blockchain light clients: Ethereum's Verkle tree proposal and various UTXO-set commitments draw on accumulator ideas so lightweight nodes can verify state without downloading the full chain.
• Set-membership range proofs: any proof that a value lies in a range $[a, b]$ can be reduced to proving membership in a set, with the accumulator keeping the proof size constant.

RSA accumulators share the "one small proof for a big set" goal with Bloom filters, but they offer soundness — a false membership proof is cryptographically impossible — whereas Bloom filters only bound the probability of false positives. The tradeoff is setup complexity and the RSA group structure.

RSA accumulators distill a beautiful idea: repeated modular exponentiation is both commutative and one-way under the strong RSA assumption. That pair of properties lets you collapse any finite set into a single integer, issue tiny proofs of membership, and make forgery as hard as breaking RSA itself.

The next time you see a blockchain node verify state with a short proof, or a certificate authority issue a compact revocation token, there is a good chance a construction built on this same principle — raising $g$ to a product of primes — is quietly doing the work. For deeper structure, explore how these ideas connect to discrete logarithm hardness and the broader world of zero-knowledge proofs.