### Cryptanalysis of Au et al. Dynamic Universal Accumulator

Alex Biryukov, 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.

Note: Author's preprint version

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.CT-RSA 2021
DOI
10.1007/978-3-030-75539-3_12
Keywords
accumulatoruniversaldynamiccryptanalysisanonymous credentials
Contact author(s)
giuseppe vitto @ uni lu
aleksei @ affine group
alex biryukov @ uni lu
History
2021-05-31: revised
See all versions
Short URL
https://ia.cr/2020/598

CC BY

BibTeX

@misc{cryptoeprint:2020/598,
author = {Alex Biryukov and Aleksei Udovenko and Giuseppe Vitto},
title = {Cryptanalysis of Au et al. Dynamic Universal Accumulator},
howpublished = {Cryptology ePrint Archive, Paper 2020/598},
year = {2020},
doi = {10.1007/978-3-030-75539-3_12},
note = {\url{https://eprint.iacr.org/2020/598}},
url = {https://eprint.iacr.org/2020/598}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.