2010 | OriginalPaper | Buchkapitel
On the Impossibility of Batch Update for Cryptographic Accumulators
verfasst von : Philippe Camacho, Alejandro Hevia
Erschienen in: Progress in Cryptology – LATINCRYPT 2010
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A cryptographic accumulator is a scheme where a set of elements is represented by a single short value. This value, along with another value called witness, allows to prove membership into the set. If new values are added or existent values are deleted from the accumulator, then the accumulated value changes and the witnesses need to be updated. In their survey on accumulators [6], Fazio and Nicolosi noted that Camenisch and Lysyanskaya’s construction [3] was such that the time to update a witness after
m
changes to the accumulated value was proportional to
m
. They posed the question whether
batch update
was possible, namely if a cryptographic accumulator where the time to update witnesses is independent from the number of changes in the accumulated set exists. Recently, Wang et al. answered positively by giving a construction for an accumulator with
batch update
[9,10]. In this work, we show that the construction is not secure by exhibiting an attack. Moreover, we prove it cannot be fixed. If the accumulated value has been updated
m
times then the time to update a witness must be at least Ω(
m
) in the worst case.