Paper 2009/612
On the Impossibility of Batch Update for Cryptographic Accumulators
Philippe Camacho and Alejandro Hevia
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.
Note: Improved version.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Latincrypt 2010
- Keywords
- Cryptographic Accumulators
- Contact author(s)
- philippe camacho @ gmail com
- History
- 2020-05-11: last of 4 revisions
- 2009-12-14: received
- See all versions
- Short URL
- https://ia.cr/2009/612
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2009/612,
author = {Philippe Camacho and Alejandro Hevia},
title = {On the Impossibility of Batch Update for Cryptographic Accumulators},
howpublished = {Cryptology {ePrint} Archive, Paper 2009/612},
year = {2009},
url = {https://eprint.iacr.org/2009/612}
}
