Article

Strong Accumulators from Collision-Resistant Hashing

Authors:

Philippe Camacho,

Alejandro Hevia,

Marcos Kiwi,

Roberto OpazoAuthors Info & Claims

ISC '08: Proceedings of the 11th international conference on Information Security

Pages 471 - 486

https://doi.org/10.1007/978-3-540-85886-7_32

Published: 15 September 2008 Publication History

Abstract

Accumulator schemes were introduced in order to represent a large set of values as one short value called the <em>accumulator</em>. 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 <em>strong universal accumulator schemes</em>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.

References

[1]

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).

Digital Library

Google Scholar

[2]

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).

Google Scholar

[3]

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).

Digital Library

Google Scholar

[4]

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).

Google Scholar

[5]

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).

Digital Library

Google Scholar

[6]

Cramer, R., Gennaro, R., Schoenmakers, B.: A secure and optimally efficient multiauthority election scheme. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 103-118. Springer, Heidelberg (1997).

Digital Library

Google Scholar

[7]

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).

Google Scholar

[8]

Servicio de Impuestos Internos. Información sobre factura electrónica {June 19, 2008}, https://palena.sii.cl/dte/mn_info.html

Google Scholar

[9]

Fazio, N., Nicolisi, A.: Cryptographic accumulators: Definitions, constructions and applications (2003) {June 19, 2008}, http://www.cs.nyu.edu/~nicolosi/papers/accumulators.ps

Google Scholar

[10]

Kocher, P.C.: On certificate revocation and validation. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 172-177. Springer, Heidelberg (1998).

Digital Library

Google Scholar

[11]

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).

Digital Library

Google Scholar

[12]

National Institute of Standards and Technology (NIST). FIPS Publication 180: Secure Hash Standard (SHS) (May 1993).

Google Scholar

[13]

OpenSSL Project. OpenSSL Package (June 2008) {June 19, 2008}, http://www.openssl.org

Google Scholar

Cited By

View all

Zhao YYang SHuang X(2024)Lattice-based dynamic universal accumulatorComputer Standards & Interfaces10.1016/j.csi.2023.10380789:COnline publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1016/j.csi.2023.103807
Zhang XDeng Y(2023)Zero-Knowledge Functional Elementary DatabasesAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8733-7_9(269-303)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8733-7_9
Kakvi SMartin KPutman CQuaglia E(2023)SoK: Anonymous CredentialsSecurity Standardisation Research10.1007/978-3-031-30731-7_6(129-151)Online publication date: 22-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30731-7_6
Show More Cited By

Recommendations

Strong accumulators from collision-resistant hashing

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, that is, short witnesses that a certain value belongs to the set. In ...
Collision-Resistant no more: hash-and-sign paradigm revisited
PKC'06: Proceedings of the 9th international conference on Theory and Practice of Public-Key Cryptography

A signature scheme constructed according to the hash-and-sign paradigm—hash the message and then sign the hash, symbolically σ(H(M))—is no more secure than the hash function H against a collision-finding attack. Recent attacks on standard hash functions ...
Revocable Group Signatures with Compact Revocation List Using Accumulators
Information Security and Cryptology -- ICISC 2013
Abstract
Group signatures allow a group member to anonymously sign a message on behalf of the group. One of the important issues is the revocation, and lots of revocable schemes have been proposed so far. The scheme recently proposed by Libert et al. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISC '08: Proceedings of the 11th international conference on Information Security

September 2008

501 pages

ISBN:9783540858843

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 15 September 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhao YYang SHuang X(2024)Lattice-based dynamic universal accumulatorComputer Standards & Interfaces10.1016/j.csi.2023.10380789:COnline publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1016/j.csi.2023.103807
Zhang XDeng Y(2023)Zero-Knowledge Functional Elementary DatabasesAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8733-7_9(269-303)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8733-7_9
Kakvi SMartin KPutman CQuaglia E(2023)SoK: Anonymous CredentialsSecurity Standardisation Research10.1007/978-3-031-30731-7_6(129-151)Online publication date: 22-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30731-7_6
Vitto GBiryukov A(2022)Dynamic Universal Accumulator with Batch Update over Bilinear GroupsTopics in Cryptology – CT-RSA 202210.1007/978-3-030-95312-6_17(395-426)Online publication date: 7-Feb-2022
https://dl.acm.org/doi/10.1007/978-3-030-95312-6_17
Agrawal SRaghuraman S(2020)KVaC: Key-Value Commitments for Blockchains and BeyondAdvances in Cryptology – ASIACRYPT 202010.1007/978-3-030-64840-4_28(839-869)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64840-4_28
Schul-Ganz GSegev G(2020)Accumulators in (and Beyond) Generic Groups: Non-trivial Batch Verification Requires InteractionTheory of Cryptography10.1007/978-3-030-64378-2_4(77-107)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64378-2_4
Badimtsi FCanetti RYakoubov S(2020)Universally Composable AccumulatorsTopics in Cryptology – CT-RSA 202010.1007/978-3-030-40186-3_27(638-666)Online publication date: 24-Feb-2020
https://dl.acm.org/doi/10.1007/978-3-030-40186-3_27
Chase MDeshpande AGhosh EMalvai HCavallaro LKinder JWang XKatz J(2019)SEEMlessProceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security10.1145/3319535.3363202(1639-1656)Online publication date: 6-Nov-2019
https://dl.acm.org/doi/10.1145/3319535.3363202
Libert BPeters TQian C(2018)Logarithmic-Size Ring Signatures with Tight Security from the DDH AssumptionComputer Security10.1007/978-3-319-98989-1_15(288-308)Online publication date: 3-Sep-2018
https://dl.acm.org/doi/10.1007/978-3-319-98989-1_15
Yu ZAu MYang RLai JXu Q(2018)Lattice-Based Universal Accumulator with Nonmembership ArgumentsInformation Security and Privacy10.1007/978-3-319-93638-3_29(502-519)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1007/978-3-319-93638-3_29
Show More Cited By

Abstract

References

Cited By

Recommendations