Article

Accumulators from bilinear pairings and applications

Author:

Lan NguyenAuthors Info & Claims

CT-RSA'05: Proceedings of the 2005 international conference on Topics in Cryptology

Pages 275 - 292

https://doi.org/10.1007/978-3-540-30574-3_19

Published: 14 February 2005 Publication History

Abstract

We propose a dynamic accumulator scheme from bilinear pairings and use it to construct an identity-based (ID-based) ring signature scheme with constant-size signatures and to provide membership revocation to group signature schemes, identity escrow schemes and anonymous credential systems. The ID-based ring signature scheme and the group signature scheme have very short signature sizes. The size of our group signatures with membership revocation is only half the size of those in the well-known ACJT00 scheme, which does not provide membership revocation. The schemes do not require trapdoor, so system parameters can be shared by multiple groups belonging to different organizations. All schemes are provably secure in formal models. We generalize the definition of accumulators and provide formal models for ID-based ad-hoc anonymous identification schemes and identity escrow schemes with membership revocation.

References

[1]

G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik. A practical and provably secure coalition-resistant group signature scheme. CRYPTO 2000, Springer-Verlag, LNCS 1880, pp. 255-270.

[2]

G. Ateniese, and B. de Medeiros. Efficient Group Signatures without Trapdoors. ASIACRYPT 2003, Springer-Verlag, LNCS 2894, pp. 246-268.

[3]

N. Baric and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. EUROCRYPT 1997, Springer-Verlag, LNCS 1233, pp. 480-494.

[4]

M. Bellare, H. Shi, and C. Zhang. Foundations of Group Signatures: The Case of Dynamic Groups. Cryptology ePrint Archive: Report 2004/077.

[5]

J. Benaloh and M. de Mare. One-way accumulators: A decentralized alternative to digital signatures. EUROCRYPT 1993, Springer-Verlag, LNCS 765, pp. 274-285.

[6]

D. Boneh, and X. Boyen. Short Signatures Without Random Oracles. EUROCRYPT 2004, Springer-Verlag, LNCS 3027, pp. 56-73.

[7]

D. Boneh, and X. Boyen. Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles. EUROCRYPT 2004, Springer-Verlag, LNCS 3027, pp. 223-238.

[8]

D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. ASIACRYPT 2001, Springer-Verlag, LNCS 2248, pp.514-532.

[9]

E. Bresson, J. Stern, and M. Szydlo. Threshold ring signatures and applications to ad-hoc groups. CRYPTO 2002, Springer-Verlag, LNCS 2442, pp. 465-480.

[10]

J. Camenisch, and M. Michels. A group signature scheme with improved efficiency. ASIACRYPT 1998, Springer-Verlag, LNCS 1514.

[11]

J. Camenisch, and A. Lysyanskaya. Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. CRYPTO 2002, Springer-Verlag, LNCS 2442, pp. 61-76.

[12]

D. Chaum, and E. van Heyst. Group signatures. CRYPTO 1991, LNCS 547, Springer-Verlag.

[13]

Y. Dodis, A. Kiayias, A. Nicolosi, and V. Shoup. Anonymous Identification in Ad Hoc Groups. EUROCRYPT 2004, Springer-Verlag, LNCS 3027, pp. 609-626.

[14]

A. Fiat, and A. Shamir. How to prove yourself: practical solutions to identification and signature problems. CRYPTO 1986, Springer-Verlag, LNCS 263, pp. 186-194.

[15]

J. Killian, and E. Petrank. Identity escrow. CRYPTO 1998, Springer-Verlag, LNCS 1642, pp. 169-185.

[16]

S. Mitsunari, R. Sakai, and M. Kasahara. A new traitor tracing. IEICE Trans. Vol. E85-A, No.2, pp.481-484, 2002.

[17]

L. Nguyen. Accumulators from Bilinear Pairings and Applications. Full version.

[18]

L. Nguyen, and R. Safavi-Naini. Efficient and Provably Secure Trapdoor-free Group Signature Schemes from Bilinear Pairings. ASIACRYPT 2004, Springer-Verlag, LNCS.

[19]

R. Rivest, A. Shamir, and Y. Tauman. How to leak a secret. ASIACRYPT 2001, Springer-Verlag, LNCS 2248, pp.552-565.

[20]

A. Shamir, Identity-based cryptosystems and signature schemes. CRYPTO 1984, LNCS 196, Springer-Verlag, pp. 47-53.

[21]

V. To, R. Safavi-Naini, and F. Zhang. New traitor tracing schemes using bilinear map. DRM Workshop 2003.

[22]

G. Tsudik, and S. Xu. Accumulating Composites and Improved Group Signing. ASIACRYPT 2003, Springer-Verlag, LNCS 2894, pp. 269-286.

[23]

F. Zhang, and K. Kim. ID-Based Blind Signature and Ring Signature from Pairings. ASIACRYPT 2002, Springer-Verlag, LNCS 2501, pp. 533-547.

Cited By

Barbàra FFredda FSchifanella C(2024)Commit-Chains Without Smart Contracts for Blockchain Applications in Local CommunitiesProceedings of the 2024 International Conference on Information Technology for Social Good10.1145/3677525.3678664(216-224)Online publication date: 4-Sep-2024
https://dl.acm.org/doi/10.1145/3677525.3678664
Civit PDzulfikar MGilbert SGuerraoui RKomatovic JVidigueira MKuznetsov PGelles ROlivetti D(2024)DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive CommunicationProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662792(145-156)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662792
Feng HLu ZTang QKuznetsov PGelles ROlivetti D(2024)Dragon: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive ConsistencyProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662771(469-479)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662771
Show More Cited By

Index Terms

Accumulators from bilinear pairings and applications

Recommendations

Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials
CRYPTO '02: Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology

We introduce the notion of a dynamic accumulator. An accumulator scheme allows one to hash a large set of inputs into one short value, such that there is a short proof that a given input was incorporated into this value. A dynamic accumulator allows one ...
Short traceable signatures based on bilinear pairings
IWSEC'06: Proceedings of the 1st international conference on Security

We propose a short traceable signature scheme based on bilinear pairings. Traceable signatures, introduced by Kiayias, Tsiounis and Yung (KTY), support an extended set of fairness mechanisms (mechanisms for anonymity management and revocation) when ...
Toward the fair anonymous signatures: deniable ring signatures
CT-RSA'06: Proceedings of the 2006 The Cryptographers' Track at the RSA conference on Topics in Cryptology

Ring signature scheme, proposed by Rivest et al., allows a signer to sign a message anonymously. In the ring signature scheme, the signer who wants to sign a document anonymously first chooses some public keys of entities (signers) and then generates a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CT-RSA'05: Proceedings of the 2005 international conference on Topics in Cryptology

February 2005

384 pages

ISBN:3540243992

Editor:
Alfred Menezes
Department of Combinatorics & Optimization, University of Waterloo

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 14 February 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

138
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 03 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Barbàra FFredda FSchifanella C(2024)Commit-Chains Without Smart Contracts for Blockchain Applications in Local CommunitiesProceedings of the 2024 International Conference on Information Technology for Social Good10.1145/3677525.3678664(216-224)Online publication date: 4-Sep-2024
https://dl.acm.org/doi/10.1145/3677525.3678664
Civit PDzulfikar MGilbert SGuerraoui RKomatovic JVidigueira MKuznetsov PGelles ROlivetti D(2024)DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive CommunicationProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662792(145-156)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662792
Feng HLu ZTang QKuznetsov PGelles ROlivetti D(2024)Dragon: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive ConsistencyProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662771(469-479)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662771
Barthoulot ABlazy OCanard S(2024)Cryptographic Accumulators: New Definitions, Enhanced Security, and Delegatable ProofsProgress in Cryptology - AFRICACRYPT 202410.1007/978-3-031-64381-1_5(94-119)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-64381-1_5
Liu-Zhang CMatt CThomsen S(2024)Asymptotically Optimal Message Dissemination with Applications to BlockchainsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58734-4_3(64-95)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58734-4_3
Baldimtsi FKarantaidou IRaghuraman S(2024)Oblivious AccumulatorsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57722-2_4(99-131)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57722-2_4
Hong ZGuo SZhou EChen WHuang HZomaya A(2023)GriDB: Scaling Blockchain Database via Sharding and Off-Chain Cross-Shard MechanismProceedings of the VLDB Endowment10.14778/3587136.358714316:7(1685-1698)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.14778/3587136.3587143
Eldefrawy KGenise NJarecki S(2023)Short Concurrent Covert Authenticated Key Exchange (Short cAKE)Advances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8742-9_3(75-109)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8742-9_3
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
Fiore DKolonelos DPerthuis P(2023)Cuckoo Commitments: Registration-Based Encryption and Key-Value Map Commitments for Large SpacesAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8733-7_6(166-200)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8733-7_6
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents