Endorsed E-Cash

July 20, 2008

Jan Camenisch, Anna Lysyanskaya and Mira Meyerovich. IEEE Security and Privacy 2007.

Abstract. An electronic cash (e-cash) scheme lets a user withdraw money from a bank and then spend it anonymously. E-cash can be used only if it can be securely and fairly exchanged for electronic goods or services. In this paper, we introduce and realize endorsed e-cash. An endorsed e-coin consists of a lightweight endorsement x and the rest of the coin which is meaningless without x. We reduce the problem of exchanging e-cash to that of exchanging endorsements. We demonstrate the usefulness of endorsed e-cash by exhibiting simple and efficient solutions to two important problems: (1) optimistic and unlinkable fair exchange of e-cash for digital goods and services; and (2) onion routing with incentives and accountability for the routers. Finally, we show how to represent a set of n endorsements using just one endorsement; this means that the complexity of the fair exchange protocol for n coins is the same as for one coin, making e-cash all the more scalable and suitable for applications. Our fair exchange of multiple e-coins protocol can be applied to fair exchanges of (almost) any secrets.

Published Version

P-signatures and Noninteractive Anonymous Credentials

July 20, 2008

Mira Belenkiy, Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya. TCC 2008.

Abstract. In this paper, we introduce P-signatures. A P-signature scheme consists of a signature scheme, a commitment scheme, and (1) an interactive protocol for obtaining a signature on a committed value; (2) a non − interactive proof system for proving that the contents of a commitment has been signed; (3) a noninteractive proof system for proving that a pair of commitments are commitments to the same value. We give a definition of security for P-signatures and show how they can be realized under appropriate assumptions about groups with a bilinear map. We make extensive use of the powerful suite of non-interactive proof techniques due to Groth and Sahai. Our P-signatures enable, for the first time, the design of a practical non-interactive anonymous credential system whose security does not rely on the random oracle model. In addition, they may serve as a useful building block for other privacy-preserving authentication mechanisms.

Published Version | Full Version

Delegatable Anonymous Credentials

July 20, 2008

Mira Belenkiy, Jan Camenisch, Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Hovav Shacham.

Please contact me for a copy.

Disjunctive Multi-Level Secret Sharing

July 20, 2008

Mira Belenkiy. Cryptology ePrint Archive: Report 2008/018.

Abstract. A disjunctive multi-level secret sharing scheme divides users into different levels. Each level L is associated with a threshold t_L, and a group of users can only recover the secret if, for some L, there are at least t_L users at levels 0….L in the group. We present a simple ideal disjunctive multi-level secret sharing scheme — in fact, the simplest and most direct scheme to date. It is the first polynomial-time solution that allows the dealer to add new users dynamically. Our solution is by far the most efficient; the dealer must perform O(t) field operations per user, where t is the highest threshold in the system. We demonstrate the simplicity of our scheme by extending our construction into a distributed commitment scheme using standard techniques.

Technical Report

Making P2P Accountable without Losing Privacy

July 20, 2008

Mira Belenkiy, Melissa Chase, Chris Erway, John Jannotti, Alptekin Kupcu, Anna Lysyanskaya, Eric Rachlin. WPES 2007.

Peer-to-peer systems have been proposed for a wide variety of applications, including file-sharing, web caching, distributed computation, cooperative backup, and onion routing. An important motivation for such systems is self-scaling. That is, increased participation increases the capacity of the system. Unfortunately, this property is at risk from selfish participants. The decentralized nature of peer-to-peer systems makes accounting difficult. We show that e-cash can be a practical solution to the desire for accountability in peer-to-peer systems while maintaining their ability to self-scale. No less important, e-cash is a natural fit for peer-to-peer systems that attempt to provide (or preserve) privacy for their participants. We show that e-cash can be used to provide accountability without compromising the existing privacy goals of a peer-to-peer system.

We show how e-cash can be practically applied to a file sharing application. Our approach includes a set of novel cryptographic protocols that mitigate the computational and communication costs of anonymous e-cash transactions, and system design choices that further reduce overhead and distribute load. We conclude that provably secure, anonymous, and scalable peer-to-peer systems are within reach.

Published Version

How to Win the Clone Wars: Efficient Periodic n-Times Anonymous Authentication

July 20, 2008

Jan Camenisch, Susan Hohenberger, Markulf Kohlweiss, Anna Lysyanskaya and Mira Meyerovich. ACM CCS 2006.

Abstract. We create a credential system that lets a user anonymously authenticate at most n times in a single time period. A user withdraws a dispenser of n e-tokens. She shows an etoken to a verifier to authenticate herself; each e-token can be used only once, however, the dispenser automatically refreshes every time period. The only prior solution to this problem, due to Damgard et al. [29], uses protocols that are a factor of k slower for the user and verifier, where k is the security parameter. Damgard et al. also only support one authentication per time period, while we support n. Because our construction is based on e-cash, we can use existing techniques to identify a cheating user, trace all of her e-tokens, and revoke her dispensers. We also offer a new anonymity service: glitch protection for basically honest users who (occasionally) reuse e-tokens. The verifier can always recognize a reused e-token; however, we preserve the anonymity of users who do not reuse e-tokens too often.

Published Version | Full Version

Siegreich im Klonkrieg: Effiziente, Periodische n-Fach Anonyme Authentifizierung

July 20, 2008

Jan Camenisch, Susan Hohenberger, Markulf Kohlweiss, Anna Lysyanskaya and Mira Meyerovich.  D-A-CH Mobility 2006.

See also. How to Win the Clone Wars: Efficient Periodic n-Times Anonymous Authentication. Jan Camenisch, Susan Hohenberger, Markulf Kohlweiss, Anna Lysyanskaya and Mira Meyerovich. ACM CCS 2006.

Abstract. Wie verhindert man, dass ein anonymer Sensor ofter als viermal pro Tag Informationen ubermittelt? Mittels E-Cash naturlich! Anonymitat ist insbesondere fur mobile personengebundene Sensoren wesentlich, die andernfalls den Aufenthaltsort ihrer Besitzer preisgeben. Die Einschr ankung der Meldefrequenz ist notig, um die uneingeschr ankte Verbreitung von Roguesensoren zu verhindern.

Wir stellen ein System vor, das es Sensoren erlaubt, Daten bis zu n mal pro Zeitperiode anonym zu authentifizieren. Bei der Initialisierung erhalt der Sensor uber ein Abhebeprotokoll einen E-Token Spender
mit n E-Tokens. Um Daten zu authentifizieren, zeigt der Sensor eines dieser E-Token in einem interaktiven Protokoll mit dem Empfanger. Jedes E-Token kann nur einmal verwendet werden, allerdings werden
Spender pro Zeitperiode automatisch neu aufgefullt. Die einzige bekannte Losung fur dieses Problems
fur n = 1, vorgestellt von Damgard et al. [20], verwendet Protokolle, die um den Faktor k langsamer
sind. Der Sicherheitsparameter k bestimmt dabei die Wahrscheinlichkeit 2−k, mit der ein Sensor uner-
kannt zwei Datens atz verschicken kann.

Published Version