Paper 2005/283

Revisiting Oblivious Signature-Based Envelopes

Samad Nasserian and Gene Tsudik

Abstract

Secure, anonymous and unobservable communication is becoming increasingly important due to the gradual erosion of privacy in many aspects of everyday life. This prompts the need for various anonymity- and privacy-enhancing techniques, e.g., group signatures, anonymous e-cash and secret handshakes. In this paper, we investigate an interesting and practical cryptographic construct Oblivious Signature-Based Envelopes (OS-BEs) recently introduced in [15]. OSBEs are very useful in anonymous communication since they allow a sender to communicate information to a receiver such that the receiver s rights (or roles) are unknown to the sender. At the same time, a receiver can obtain the information only if it is authorized to access it. This makes OSBEs a natural fit for anonymity-oriented and privacy-preserving applications, such as Automated Trust Negotiation and Oblivious Subscriptions. Previous results yielded three OSBE constructs: one based on RSA and two based on Identity-Based Encryption (IBE). Our work focuses on the ElGamal signature family: we succeed in constructing practical and secure OSBE schemes for several well-known signature schemes, including: Schnorr, Nyberg-Rueppel, ElGamal and DSA. As experiments with the prototype implementation il-lustrate, our schemes are more efficient than previous techniques. Furthermore, we show that some OSBE schemes, despite offering affiliation privacy for the receiver, introduce no additional cost over schemes that do not offer this feature.

Note: A previous version of this paper contained some errors which we fixed. The present version is a result of a major revision. In particular, it includes a thorough proof of security for the Schnorr-OSBE scheme as well as an in-depth discussion of implementation and efficiency/experiments.