Are there cryptographic accumulators without trusted setup?

tl;dr: Yes, there are: Merkle-based, RSA-or-class-group based and lattice-based ones.

---

RSA accumulators over class groups

Practically, the only (somewhat-fast) accumulators without trusted setup (and constant-sized proofs) are RSA accumulators¹ instantiated with great care² over class groups³.

Merkle-based accumulators

Theoretically 😄, if you relax your definition of “accumulators” by:

1. Removing quasi-commutativity¹.
2. Allowing for logarithmically-sized proofs (instead of constant-sized proofs)

…then, naturally you can use a Merkle prefix tree (a.k.a., a Merkle trie) to represent a set and obtain an accumulator.

Another approach is to either use (1) a binary search tree or (2) a tree with sorted leaves, where each internal node stores the minimum and the maximum element in its subtree⁴.

Similarly, you can also use the rather beautiful Utreexo construction⁵, which is also Merkle-based but does not support non-membership proofs.

Lattice-based accumulators

Even more theoretically 😆, assuming you don’t care about performance at all, you might use a lattice-based accumulator⁶,⁷,⁸,⁹. Some of them do not need a trusted setup, like ⁶.

Even better, the recent lattice-based vector commitments by Peikert et al.¹⁰ can be turned into an accumulator. (Interestingly, I think accumulator proof sizes here could be made “almost” $O(\log_k{n})$-sized, for arbitrary $k$, if one used their lattice-based Verkle construction which, AFAICT, requires a trusted setup.)

RSA moduli of unknown complete factorization (UFOs)

One last theoretical idea is to generate an RSA group with a modulus $N$ of unknown factorization using the “RSA UFO” technique by Sander¹¹. Unfortunatly, such $N$ are too large and kill performance. Specifically, instead of the typical 2048-bit or 4096-bit, RSA UFO $N$’s are hundreds of thousands of bits (or larger?). Improving this would be a great avenue for future work.