Abstract
Accumulator schemes were introduced in order to represent a large set of values as one short value called the accumulator. These schemes allow one to generate membership proofs, i.e. short witnesses that a certain value belongs to the set. In universal accumulator schemes, efficient proofs of non-membership can also be created. Li, Li and Xue [11], building on the work of Camenisch and Lysyanskaya [5], proposed an efficient accumulator scheme which relies on a trusted accumulator manager. Specifically, a manager that correctly performs accumulator updates.
In this work we introduce the notion of strong universal accumulator schemes which are similar in functionality to universal accumulator schemes, but do not assume the accumulator manager is trusted. We also formalize the security requirements for such schemes. We then give a simple construction of a strong universal accumulator scheme which is provably secure under the assumption that collision-resistant hash functions exist. The weaker requirement on the accumulator manager comes at a price; our scheme is less efficient than known universal accumulator schemes — the size of (non)membership witnesses is logarithmic in the size of the accumulated set in contrast to constant in the scheme of Camenisch and Lysyanskaya.
Finally, we show how to use strong universal accumulators to solve a practical concern, the so called e-Invoice Factoring Problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barić, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signed scheme without trees. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 480–494. Springer, Heidelberg (1997)
Bayer, D., Haber, S., Stornetta, W.S.: Improving the efficiency and reliability of digital time-stamping. In: Capocelli, R.M., DeSantis, A., Vaccaro, U. (eds.) Sequences II: Methods in Communication, Security, and Computer Science, pp. 329–334. Springer, Heidelberg (1993)
Benaloh, J., De Mare, M.: One-way accumulators: A decentralised alternative to digital signatures. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 274–285. Springer, Heidelberg (1994)
Boneh, D., Venkatesan, R.: Breaking RSA not be equivalent to factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 59–71. Springer, Heidelberg (1998)
Camenisch, J., Lysyanskaya, A.: Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 61–76. Springer, Heidelberg (2002)
Cramer, R., Gennaro, R., Schoenmakers, B.: A secure and optimally efficient multi-authority election scheme. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 103–118. Springer, Heidelberg (1997)
Damgård, I.: Collision free hash functions and public key signature schemes. In: Price, W.L., Chaum, D. (eds.) EUROCRYPT 1987. LNCS, vol. 304, pp. 203–216. Springer, Heidelberg (1988)
Servicio de Impuestos Internos. Información sobre factura electrónica [June 19, 2008], https://palena.sii.cl/dte/mn_info.html
Fazio, N., Nicolisi, A.: Cryptographic accumulators: Definitions, constructions and applications (2003) [June 19, 2008], http://www.cs.nyu.edu/~nicolosi/papers/accumulators.ps
Kocher, P.C.: On certificate revocation and validation. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 172–177. Springer, Heidelberg (1998)
Li, J., Li, N., Xue, R.: Universal accumulators with efficient nonmembership proofs. In: Katz, J., Yung, M. (eds.) ACNS 2007. LNCS, vol. 4521. Springer, Heidelberg (2007)
National Institute of Standards and Technology (NIST). FIPS Publication 180: Secure Hash Standard (SHS) (May 1993)
OpenSSL Project. OpenSSL Package (June 2008) [June 19, 2008], http://www.openssl.org
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Camacho, P., Hevia, A., Kiwi, M., Opazo, R. (2008). Strong Accumulators from Collision-Resistant Hashing. In: Wu, TC., Lei, CL., Rijmen, V., Lee, DT. (eds) Information Security. ISC 2008. Lecture Notes in Computer Science, vol 5222. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85886-7_32
Download citation
DOI: https://doi.org/10.1007/978-3-540-85886-7_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85884-3
Online ISBN: 978-3-540-85886-7
eBook Packages: Computer ScienceComputer Science (R0)