I am looking for an accumulator with the following properties:

  1. Transparent: No trusted setup (rules out RSA and pairing-based accumulators)
  2. Publicly updatable: No central authority (rules out digital signatures)
  3. Constant-sized witnesses: (rules out Merkle accumulator)

Are there accumulators with all the above properties?

The intended use case is a public blockchain without a "super user"/"admin"/"authority" managing the accumulator. In particular, witnesses should be publicly verifiable, accumulator updates (additions and/or deletions) should be public, and witnesses should be updatable from publicly broadcasted auxiliary information.

  • $\begingroup$ Regarding 1) Actually, that does not rule out RSA. It's possible to generate an RSA key in a distributed fashion, where no single party holds the private key. Regarding 2), I think you need to be more specific, I am not sure what you actually mean. $\endgroup$
    – tylo
    Dec 18 '17 at 12:34
  • $\begingroup$ Regarding 1), would you mind linking to a paper of the distributed construction? $\endgroup$
    – Randomblue
    Dec 19 '17 at 15:58
  • $\begingroup$ Efficient Generation of Shared RSA key by Boneh and Franklin (1997, although google scholar shows it with 2001), Robust efficient distributed RSA-key generation by Frankel, MacKenzie and Yung (1998). $\endgroup$
    – tylo
    Dec 20 '17 at 13:54
  • $\begingroup$ Constant-sized witnesses is going to limit what can be accumulated, I guess. $\endgroup$
    – fgrieu
    Jan 29 '18 at 13:27

Later edit: Actually, some new Stanford work shows how to obtain transparent RSA accumulators using class groups. This was also discussed in Secure Accumulators from Euclidean Rings without Trusted Setup, by Helger Lipmaa.

The Stanford work also shows how to publicly add and remove elements in the accumulator. And the proofs are constant-sized.

Original answer: If you're willing to generate RSA keys in a distributed fashion, then you might as well go for bilinear accumulators, since you can also generate $q$-SDH parameters for them in a distributed fashion and they will be faster for non-membership proofs and also support subset proofs.

Depending on how you squint your eyes, yes, bilinear accumulators have all of those properties.

  1. No trusted setup: just use MPC to generate $q$-SDH public parameters.
  2. Publicly updatable: given old set $X$ and updates $U$ s.t. new set $X' = X \cup U$, anybody can simply recompute $acc(X')$.
  3. Constant-sized witnesses: bilinear accumulator witnesses are 1 group element for membership and 1 group element plus 1 field element for non-membership.
  4. Witnesses should be publicly-verifiable: in bilinear accumulator they are
  5. Accumulator updates (additions and/or deletions) should be public(ly made): anybody can recompute an updated bilinear accumulator
  6. Witnesses should be updatable from publicly-broadcasted auxiliary information: I know membership witnesses can be easily updated in $O(1)$ time after 1 addition to the accumulator. Not sure about non-membership witnesses. However, given the new set $X'$, anybody can compute a new witness in $O(n)$ time.

Hope this helps!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.