Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Cryptanalysis of a Dynamic Universal Accumulator over Bilinear Groups
Biryukov, Alexei; Udovenko, Aleksei; Vitto, Giuseppe
2021In Topics in Cryptology – CT-RSA 2021
Peer reviewed


Full Text
Author postprint (512.63 kB)

This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use

All documents in ORBilu are protected by a user license.

Send to


Keywords :
accumulator; universal; dynamic; cryptanalysis; anonymous credentials
Abstract :
[en] 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.
Disciplines :
Computer science
Author, co-author :
Biryukov, Alexei ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Udovenko, Aleksei  ;  CryptoExperts, Paris, France
Vitto, Giuseppe ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux
External co-authors :
Language :
Title :
Cryptanalysis of a Dynamic Universal Accumulator over Bilinear Groups
Publication date :
Event name :
Topics in Cryptology – CT-RSA 2021
Event date :
May 17–20, 2021
Audience :
Main work title :
Topics in Cryptology – CT-RSA 2021
Peer reviewed :
Peer reviewed
Focus Area :
Security, Reliability and Trust
FnR Project :
FNR11684537 - Security, Scalability, And Privacy In Blockchain Applications And Smart Contracts, 2017 (01/08/2018-31/07/2021) - Alex Biryukov
Funders :
FNR - Fonds National de la Recherche [LU]
Available on ORBilu :
since 12 January 2022


Number of views
83 (21 by Unilu)
Number of downloads
12 (1 by Unilu)

Scopus citations®
Scopus citations®
without self-citations
WoS citations


Similar publications

Contact ORBilu