Paper 2020/598

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

Metadata
Available format(s)
PDF
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
2020-05-22: received
See all versions
Short URL
https://ia.cr/2020/598
License
Creative Commons Attribution
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.