Strong RSA ⇒ accumulator
Statement
If the strong RSA assumption holds, the RSA accumulator over a domain of superpolynomially many primes, with , , witness and verification that accepts iff is in the domain and , is a collision-free accumulator — BP97.
Sketch
Let . A witness for a prime satisfies with ; for Bézout coefficients , the element satisfies , an -th root of with — standard.
Notes
- Arbitrary elements are accumulated by first mapping them to primes, injectively or with a hash for which finding two inputs with the same prime is hard — BP97.
- The accumulator is also dynamic: Strong RSA (safe-prime moduli) ⇒ dynamic accumulator — CL02.