Article

An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation

Authors:

Anna LysyanskayaAuthors Info & Claims

EUROCRYPT '01: Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology

Pages 93 - 118

Published: 06 May 2001 Publication History

Abstract

A credential system is a system in which users can obtain credentials from organizations and demonstrate possession of these credentials. Such a system is anonymous when transactions carried out by the same user cannot be linked. An anonymous credential system is of significant practical relevance because it is the best means of providing privacy for users. In this paper we propose a practical anonymous credential system that is based on the strong RSA assumption and the decisional Diffie-Hellman assumption modulo a safe prime product and is considerably superior to existing ones: (1) We give the first practical solution that allows a user to unlinkably demonstrate possession of a credential as many times as necessary without involving the issuing organization. (2) To prevent misuse of anonymity, our scheme is the first to offer optional anonymity revocation for particular transactions. (3) Our scheme offers separability: all organizations can choose their cryptographic keys independently of each other. Moreover, we suggest more effective means of preventing users from sharing their credentials, by introducing all-or-nothing sharing: a user who allows a friend to use one of her credentials once, gives him the ability to use all of her credentials, i.e., taking over her identity. This is implemented by a new primitive, called circular encryption, which is of independent interest, and can be realized from any semantically secure cryptosystem in the random oracle model.

References

[1]

N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures. IEEE Journal on Selected Areas in Communications, 18(4):591-610, 2000.

[2]

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

[3]

M. Bellare, A. Boldyreva, A. Desai, and D. Pointcheval. Key-privacy in public-key encryption. Manuscript, 2001.

[4]

M. Bellare, J. A. Garay, and T. Rabin. Fast batch verification for modular exponentiation and digital signatures. In EUROCRYPT '98, vol. 1403 of LNCS, pp. 236-250. Springer Verlag, 1998.

[5]

J. Black, P. Rogaway, and T. Shrimpton. Encryption scheme security in the presence of key-dependent messages. Manuscript, 2001.

[6]

F. Boudot. Efficient proofs that a committed number lies in an interval. In EUROCRYPT 2000, vol. 1807 of LNCS, pp. 431-444. Springer Verlag, 2000.

[7]

S. Brands. Untraceable Off-line Cash in Wallets With Observers. In CRYPTO '93, vol. of LNCS. pp. 302-318. Springer Verlag, 1993.

[8]

S. Brands. Rethinking Public Key Infrastructures and Digital Certificates; Building in Privacy. PhD thesis, Eindhoven Institute of Technology, the Netherlands, 1999.

[9]

E. Brickell, P. Gemmel, and D. Kravitz. Trustee-based tracing extensions to anonymous cash and the making of anonymous change. In Proc. ACM-SIAMs, pp. 457- 466. ACM press, 1995.

[10]

J. Camenisch and I. Damgård. Verifiable encryption and applications to group signatures and signature sharing. Technical Report RS-98-32, BRICS, Departement of Computer Science, University of Aarhus, December 1998.

[11]

J. Camenisch and A. Lysyanskaya. Efficient non-transferable anonymous multishow credential system with optional anonymity revocation. Technical Report Research Report RZ 3295, IBM Research Division, 2000.

[12]

J. Camenisch and A. Lysyanskaya. An Efficient Nontransferable Anonymous Credential System with Optional Anonymity Revocation. http://eprint.iacr.org/2001.

[13]

J. Camenisch and M. Michels. Proving in zero-knowledge that a number n is the product of two safe primes. In EUROCRYPT '99, vol. 1592 of LNCS, pp. 107-122.

[14]

J. Camenisch and M. Stadler. Efficient group signature schemes for large groups. In CRYPTO '97, vol. 1296 of LNCS, pp. 410-424. Springer Verlag, 1997.

[15]

R. Canetti. Studies in Secure Multiparty Computation and Applications. PhD thesis, Weizmann Institute of Science, Rehovot 76100, Israel, 1995.

[16]

R. Canetti. Security and composition of multi-party cryptographic protocols. Journal of Cryptology, 13(1):143-202, 2000.

[17]

D. Chaum. Blind signatures for untraceable payments. In CRYPTO '82, pp. 199-203. Plenum Press, 1983.

[18]

D. Chaum. Security without identification: Transaction systems to make big brother obsolete. Communications of the ACM, 28(10):1030-1044, 1985.

[19]

D. Chaum and J.-H. Evertse. A secure and privacy-protecting protocol for transmitting personal information between organizations. In CRYPTO '86, vol. 263 of LNCS, pp. 118-167. Springer-Verlag, 1987.

[20]

D. Chaum and E. van Heyst. Group signatures. In EUROCRYPT '91, vol. 547 of LNCS, pp. 257-265. Springer-Verlag, 1991.

[21]

L. Chen. Access with pseudonyms. In Cryptography: Policy and Algorithms, vol. 1029 of LNCS, pp. 232-243. Springer Verlag, 1995.

[22]

R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In CRYPTO '98, vol. 1642 of LNCS, pp. 13-25, 1998, Springer Verlag.

[23]

R. Cramer and V. Shoup. Signature schemes based on the strong RSA assumption. In Proc. 6th ACM CCS, pp. 46-52. ACM press, 1999.

[24]

I. Damgård. Efficient concurrent zero-knowledge in the auxiliary string model. In EUROCRYPT 2000, vol. 1807 of LNCS, pp. 431-444. Springer Verlag, 2000.

[25]

I. Damgård. Payment systems and credential mechanism with provable security against abuse by individuals. In CRYPTO '88, vol. 403 of LNCS, pp. 328-335.

[26]

C. Dwork, J. Lotspiech, and M. Naor. Digital signets: Self-enforcing protection of digital information. In Proc. 28th STOC, 1996.

[27]

T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In CRYPTO '84, vol. 196 of LNCS, pp. 10-18. Springer Verlag, 1985.

[28]

A. Fiat and A. Shamir. How to prove yourself: Practical solution to identification and signature problems. In CRYPTO '86, vol. 263 of LNCS, pp. 186-194, 1987.

[29]

E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In CRYPTO '97, vol. 1294of LNCS, pp. 16-30, 1997.

[30]

R. Gennaro, S. Halevi, and T. Rabin. Secure hash-and-sign signatures without the random oracle. In EUROCRYPT '99, vol. 1592 of LNCS, pp. 123-139, 1999.

[31]

S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. In Proc. 27th FOCS, pages 291-304, 1985.

[32]

O. Goldreich, B. Pfitzman, and R. Rivest. Self-delegation with controlled propagation--or--what if you lose your laptop. In CRYPTO '98, vol. 1642 of LNCS, pp. 153-168, 1998.

[33]

J. Kilian and E. Petrank. Identity escrow. In CRYPTO '98, vol. 1642 of LNCS, pp. 169-185, Springer Verlag, 1998.

[34]

A. Lysyanskaya, R. Rivest, A. Sahai, and S. Wolf. Pseudonym systems. In Selected Areas in Cryptography, vol. 1758 of LNCS. Springer Verlag, 1999.

[35]

S. Micali, C. Rackoff, and B. Sloan. The notion of security for probabilistic cryptosystems. SIAM Journal on Computing, 17(2):412-426, 1988.

[36]

B. Pfitzmann and M. Waidner. Composition and integrity preservation of secure reactive systems. In Proc. 7th ACM CCS, pp. 245-254. ACM press, 2000.

[37]

M. Stadler, J.-M. Piveteau, and J. Camenisch. Fair blind signatures. In EUROCRYPT '95, vol. 921 of LNCS, pp. 209-219. Springer Verlag, 1995.

Cited By

Fuchsbauer GJafargholi ZPietrzak K(2022)A Quasipolynomial Reduction for Generalized Selective Decryption on TreesAdvances in Cryptology -- CRYPTO 201510.1007/978-3-662-47989-6_29(601-620)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-662-47989-6_29
Aloufi AHu PSong YLauter K(2021)Computing Blindfolded on Data Homomorphically Encrypted under Multiple Keys: A SurveyACM Computing Surveys10.1145/347713954:9(1-37)Online publication date: 8-Oct-2021
https://dl.acm.org/doi/10.1145/3477139
Peng KEmura KWang Y(2021)Perfect ZK Argument of Knowledge of Discrete Logarithm in A Cyclic Group with Unknown OrderProceedings of the 8th ACM on ASIA Public-Key Cryptography Workshop10.1145/3457338.3458287(33-40)Online publication date: 24-May-2021
https://dl.acm.org/doi/10.1145/3457338.3458287
Show More Cited By

An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data layout
2. Security and privacy
  1. Security services

Recommendations

Anonymous credentials light
CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security

We define and propose an efficient and provably secure construction of blind signatures with attributes. Prior notions of blind signatures did not yield themselves to the construction of anonymous credential systems, not even if we drop the ...
Anonymous authentication with optional shared anonymity revocation and linkability
CARDIS'06: Proceedings of the 7th IFIP WG 8.8/11.2 international conference on Smart Card Research and Advanced Applications

In this paper we propose three smartcard-based variants of anonymous authentication using unique one-time pseudonyms. The first variant can be used to authenticate a user. However, his identity cannot be revealed and linked to other pseudonyms unless ...
PAPR: Publicly Auditable Privacy Revocation for Anonymous Credentials
Topics in Cryptology – CT-RSA 2023
Abstract
We study the notion of anonymous credentials with Publicly Auditable Privacy Revocation (PAPR). PAPR credentials simultaneously provide conditional user privacy and auditable privacy revocation. The first property implies that users keep their ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EUROCRYPT '01: Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology

May 2001

543 pages

ISBN:3540420703

Editor:
Birgit Pfitzmann

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 06 May 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

291
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fuchsbauer GJafargholi ZPietrzak K(2022)A Quasipolynomial Reduction for Generalized Selective Decryption on TreesAdvances in Cryptology -- CRYPTO 201510.1007/978-3-662-47989-6_29(601-620)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-662-47989-6_29
Aloufi AHu PSong YLauter K(2021)Computing Blindfolded on Data Homomorphically Encrypted under Multiple Keys: A SurveyACM Computing Surveys10.1145/347713954:9(1-37)Online publication date: 8-Oct-2021
https://dl.acm.org/doi/10.1145/3477139
Peng KEmura KWang Y(2021)Perfect ZK Argument of Knowledge of Discrete Logarithm in A Cyclic Group with Unknown OrderProceedings of the 8th ACM on ASIA Public-Key Cryptography Workshop10.1145/3457338.3458287(33-40)Online publication date: 24-May-2021
https://dl.acm.org/doi/10.1145/3457338.3458287
Gunasinghe HKundu ABertino EKrawczyk HChari SSingh KSu D(2019)PrivIdEx: Privacy Preserving and Secure Exchange of Digital Identity Assets.The World Wide Web Conference10.1145/3308558.3313574(594-604)Online publication date: 13-May-2019
https://dl.acm.org/doi/10.1145/3308558.3313574
Abe MGroth JKohlweiss MOhkubo MTibouchi M(2019)Efficient Fully Structure-Preserving Signatures and Shrinking CommitmentsJournal of Cryptology10.1007/s00145-018-9300-532:3(973-1025)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s00145-018-9300-5
Abe MCamenisch JDowsley RDubovitskaya M(2019)On the Impossibility of Structure-Preserving Deterministic PrimitivesJournal of Cryptology10.1007/s00145-018-9292-132:1(239-264)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s00145-018-9292-1
Fuchsbauer GHanser CSlamanig D(2019)Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous CredentialsJournal of Cryptology10.1007/s00145-018-9281-432:2(498-546)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00145-018-9281-4
Wu CFan CHuang JTseng YKikuchi H(2018)Probably Secure Efficient Anonymous Credential SchemeInternational Journal of Software Innovation10.4018/IJSI.20180701026:3(18-35)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.4018/IJSI.2018070102
Linna FXiaofeng SWeiwei ZHaodan RJingzhi LDeyang SSuining MTao QNakayama MLou FBannier BWatanabe H(2018)An anonymous authentication mechanism based on Kerberos and HIBCProceedings of the 10th International Conference on Education Technology and Computers10.1145/3290511.3290569(392-396)Online publication date: 26-Oct-2018
https://dl.acm.org/doi/10.1145/3290511.3290569
Bemmann KBlömer JBobolz JBröcher HDiemert DEidens FEilers LHaltermann JJuhnke JOtour BPorzenheim LPukrop SSchilling ESchlichtig MStienemeier M(2018)Fully-Featured Anonymous Credentials with Reputation SystemProceedings of the 13th International Conference on Availability, Reliability and Security10.1145/3230833.3234517(1-10)Online publication date: 27-Aug-2018
https://dl.acm.org/doi/10.1145/3230833.3234517
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents