Cryptanalysis of a Dynamic Universal Accumulator over Bilinear Groups

In this paper we cryptanalyse the two accumulator variants proposed by Au et al., which we call the alpha-based construction and the common reference string-based (CRS-based) construction.
We show that if non-membership witnesses are issued according to the alpha-based construction, an attacker that has access to multiple witnesses is able to efficiently recover the secret accumulator parameter alpha and completely break its security.
More precisely, if p is the order of the underlying bilinear group, the knowledge of O(log p log log p) non-membership witnesses permits to successfully recover alpha. Further optimizations and different attack scenarios allow to reduce the number of required witnesses to O(log p), together with practical attack complexity. Moreover, we show that accumulator's collision resistance can be broken if just one of these non-membership witnesses is known to the attacker.
We then show how all these attacks for the alpha-based construction can be easily prevented by using instead a corrected expression for witnesses.

Although outside the original security model assumed by Au \etal but motivated by some possible concrete application of the scheme where the Manager must have exclusive rights for issuing witnesses (e.g. white/black list based authentication mechanisms), we show that if non-membership witnesses are issued using the CRS-based construction and the CRS is kept secret by the Manager, an attacker accessing multiple witnesses can reconstruct the CRS and compute witnesses for arbitrary new elements. In particular, if the accumulator is initialized by adding m secret elements, the knowledge of m non-membership witnesses allows to succeed in such attack.