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 accumulators1 instantiated with great care2 over class groups3.

Merkle-based accumulators

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

  1. Removing quasi-commutativity1.
  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 subtree4.

Similarly, you can also use the rather beautiful Utreexo construction5, 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 accumulator6,7,8,9. Some of them do not need a trusted setup, like 6.

Even better, the recent lattice-based vector commitments by Peikert et al.10 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 Sander11. 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.

  1. One-Way Accumulators: A Decentralized Alternative to Digital Signatures, by Benaloh, Josh and de Mare, Michael, in EUROCRYPT ‘93, 1994  2

  2. A note on the low order assumption in class group of an imaginary quadratic number fields, by Karim Belabas and Thorsten Kleinjung and Antonio Sanso and Benjamin Wesolowski, in Cryptology ePrint Archive, Report 2020/1310, 2020, [URL] 

  3. Secure Accumulators from Euclidean Rings without Trusted Setup, by Lipmaa, Helger, in Applied Cryptography and Network Security, 2012 

  4. Accountable certificate management using undeniable attestations, by Ahto Buldas and Peeter Laud and Helger Lipmaa, in ACM CCS’00, 2000, [URL] 

  5. Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set, by Thaddeus Dryja, 2019, [URL] 

  6. Streaming Authenticated Data Structures, by Papamanthou, Charalampos and Shi, Elaine and Tamassia, Roberto and Yi, Ke, in EUROCRYPT 2013, 2013  2

  7. Compact Accumulator using Lattices, by Mahabir Prasad Jhanwar and Reihaneh Safavi-Naini, in Cryptology ePrint Archive, Report 2014/1015, 2014, [URL] 

  8. Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors, by Benoît Libert and San Ling and Khoa Nguyen and Huaxiong Wang, in EUROCRYPT (2), 2016, [URL] 

  9. Lattice-Based Group Signatures: Achieving Full Dynamicity with Ease, by San Ling and Khoa Nguyen and Huaxiong Wang and Yanhong Xu, in Cryptology ePrint Archive, Report 2017/353, 2017, [URL] 

  10. Vector and Functional Commitments from Lattices, by Chris Peikert and Zachary Pepin and Chad Sharp, in Cryptology ePrint Archive, Report 2021/1254, 2021, [URL] 

  11. Efficient Accumulators without Trapdoor Extended Abstract, by Sander, Tomas, in Information and Communication Security, 1999