Cryptology ePrint Archive: Report 2020/598

Cryptanalysis of Au et al. Dynamic Universal Accumulator

Alex Biryukov and Aleksei Udovenko and Giuseppe Vitto

Abstract: In this paper we cryptanalyse the two accumulator variants proposed by Au et al., namely the $a$-based construction and the reference string-based ($RS$-based) construction. We show that if non-membership witnesses are issued according to the $a$-based construction, colluding users can efficiently discover the secret accumulator parameter $a$ and takeover the Accumulator Manager. More precisely, if $p$ is the order of the underlying bilinear group, the knowledge of $O(log(p)loglog(p))$ non-membership witnesses permits to successfully recover $a$. 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 collision resistance can be broken if just one of these non-membership witnesses is known to the attacker.

In the case when non-membership witnesses are issued using the $RS$-based construction (with $RS$ kept secret by the Manager), we show that a group of colluding users can reconstruct the $RS$ and compute witnesses for arbitrary new elements. In particular, if the accumulator is initialized by adding $m$ secret elements, $m$ colluding users that share their non-membership witnesses will succeed in such attack.

Category / Keywords: cryptographic protocols / accumulator, universal, dynamic, cryptanalysis, anonymous credentials

Date: received 20 May 2020, last revised 20 May 2020

Contact author: giuseppe vitto at uni lu, aleksei@affine group, alex biryukov@uni lu

Available format(s): PDF | BibTeX Citation

Version: 20200522:151354 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]