Cryptology ePrint Archive: Report 2009/612
On the Impossibility of Batch Update for Cryptographic Accumulators
Abstract: 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. In their survey on accumulators [FN02], Fazzio and Nicolisi noted that the Camenisch and Lysyanskaya's construction[CL02] 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 it was possible to build a cryptographic
accumulator where the time to update witnesses is independent from the number of changes in the accumulated set.
Recently, Wang et al. answered positively by giving a construction for an accumulator with batch update in [WWP07, WWP08]. 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.
Category / Keywords: Cryptographic Accumulators
Publication Info: accumulators
Date: received 10 Dec 2009, last revised 15 Dec 2009
Contact author: philippe camacho at gmail com
Available format(s): PDF | BibTeX Citation
Note: Bug abstract.
Version: 20091216:011612 (All versions of this report)
Short URL: ia.cr/2009/612
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]