Strong RSA ⇒ accumulator

Fully-black-box reduction · standard model · BP97 · security loss: tight: a forged witness gives a strong-RSA solution by one extended-gcd computation

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