Privacy-enhancing cryptography

We are interested in the development of cryptographic protocols allowing for privacy-friendly technology supporting anonymity and pseudonymity on the Internet.

We have developed cryptographic protocols for an anonymous credential system (or pseudonym system) [CL00,CL01]. Such a system consists of users and organizations. Organizations know the users only by pseudonyms. Different pseudonyms of the same user cannot be linked. Yet, an organization can issue a credential to a pseudonym, and the corresponding user can prove possession of this credential to another organization (who knows her by a different pseudonym), without revealing anything more than the fact that she owns such a credential. Some of these protocols are currently implemented in the identity mixer project.

Group signature schemes are a relatively recent cryptographic concept introduced by Chaum and van Heyst in 1991. In contrast to ordinary signatures they provide anonymity to the signer, i.e., a verifier can only tell that a member of some group signed. However, in exceptional cases such as a legal dispute, any group signature can be ``opened'' by a designated group manager to reveal unambiguously the identity of the signature's originator. At the same time, no one - including the group manager - can misattribute a valid group signature.

The salient features of group signatures make them attractive for many specialized applications, such as voting and bidding. They can, for example, be used in invitations to submit tenders. All companies submitting a tender form a group and each company signs its tender anonymously using the group signature. Once the preferred tender is selected, the winner can be traced while the other bidders remain anonymous. More generally, group signatures can be used to conceal organizational structures, e.g., when a company or a government agency issues a signed statement. Group signatures can also be integrated with an electronic cash system whereby several banks can securely distribute anonymous and untraceable e-cash. This offers concealing of the cash-issuing banks' identities.

A concept dual to group signature schemes is identity escrow. It can be regarded as a group-member identification scheme with revocable anonymity. A group signature scheme can be turned into an identity escrow scheme by signing a random message and then proving the knowledge of a group signature on the chosen message. We have developped the most efficient such schemes [ACJT00].

The main difference between confirmer-signatures and ordinary digital signatures is that a confirmer-signature can be verified only with the assistance of a semi-trusted third party, the confirmer. Additionally, the confirmer can selectively convert single confirmer-signatures into ordinary signatures. If this is a standard signature such as RSA or DSS, we say that the confirmer signature scheme provides perfect conversion - a property unmet so far.

We points out that previous models for confirmer signature schemes are too restricted to address the case where several signers share the same confirmer. More seriously, we show that various proposed scheme (some of them provable secure in these restricted models) are vulnerable to an adaptive ``re-signing'' attack. We define a new stronger model that covers this kind of attack and provide a generic solution that enjoys perfect conversion. We also exhibit a concrete instance thereof [CM00].

[CL02b]

Jan Camenisch, Anna Lysyanskaya: A Signature Scheme for Efficient Protocols. In Third Conference on Security in Communication Networks, 2002)

[CH02]

Jan Camenisch, Els Van Herreweghen: Design and Implementation of the Idemix Anonymous Credential System. Research Report RZ 3419, IBM Research Division, June 2002. Also appeared in ACM Computer and Communication Security 2002

[CL02a]

Jan Camenisch, Anna Lysyanskaya: Dynamic accumulators and application to efficient revocation of anonymous credentials. In Advances in Cryptology -- Crypto 2002.

[CL01]

Jan Camenisch, Anna Lysyanskaya: An Identity Escrow Scheme with Appointed Verifiers. (To appear in Advances in Cryptology -- Crypto 2001)

[CL00]

Jan Camenisch, Anna Lysyanskaya: Efficient Non-transferable Anonymous Multi-show Credential System with Optional Anonymity Revocation. Research Report RZ 3295 (#93341), IBM Research, November 2000. (Extended abstract in: Advances in Cryptology -- Eurocrypt 2001, revised full version available here )

[C00]

Jan Camenisch: Efficient anonymous fingerprinting with group signatures. In Asiacrypt '00, LNCS 1976, Springer-Verlag, Berlin 2000.

[CD00]

Jan Camenisch, Ivan Damgaard: Verifiable encryption, group encryption, and their applications to separable group signatures and signature sharing schemes. In Asiacrypt '00, LNCS 1976, Springer-Verlag, Berlin 2000.

[H00]

Els Van Herreweghen: Secure Anonymous Signature-based Transactions. In ESORICS 2000, LNCS, Springer-Verlag, Berlin 2000.

[ACJT00]

Giuseppe Ateniese, Jan Camenisch, Marc Joye, Gene Tsudik: A practical and provably secure coalition-resistant group signature scheme. In Crypto 2000, LNCS 1880, Springer-Verlag, Berlin 2000.

[CM00]

Jan Camenisch and Markus Michels: Confirmer signature schemes secure against adaptive adversaries. In Eurocrypt 2000, LNCS 1880, Springer-Verlag, Berlin 2000.

[PWP00]

Birgit Pfitzmann, Michael Waidner, Andreas Pfitzmann: Secure and Anonymous Electronic Commerce: Providing Legal Certainty in Open Digital Systems Without Compromising Anonymity. Research Report RZ 3232 (#93278), IBM Research, May 2000.