Reference : Cryptanalysis of a Dynamic Universal Accumulator over Bilinear Groups
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
Security, Reliability and Trust
Cryptanalysis of a Dynamic Universal Accumulator over Bilinear Groups
Biryukov, Alexei mailto [University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS) >]
Udovenko, Aleksei [CryptoExperts, Paris, France]
Vitto, Giuseppe mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux >]
Topics in Cryptology – CT-RSA 2021
Topics in Cryptology – CT-RSA 2021
May 17–20, 2021
[en] accumulator ; universal ; dynamic ; cryptanalysis ; anonymous credentials
[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.
Fonds National de la Recherche - FnR
Researchers ; Professionals
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
FnR ; FNR11684537 > Alex Biryukov > FinCrypt > Security, Scalability, And Privacy In Blockchain Applications And Smart Contracts > 01/08/2018 > 31/07/2021 > 2017

File(s) associated to this reference

Fulltext file(s):

Limited access
cryptanalysis_accumulator.pdfAuthor postprint500.61 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.