by Ben Adida, Susan Hohenberger, and Ronald L. Rivest
(draft; to appear). February, 2005

Email phishing attacks are one of today’s most common and costly forms of digital identity theft, where an adversary tricks a user into revealing their personal information by impersonating an established company. Such attacks could be mitigated with digitally-signed emails, if these signatures did not: (1) destroy the traditional repudiability of email, and (2) require the unrealistic, widespread adoption of a Public-Key Infrastructure (PKI).In order to overcome these obstacles, we introduce, define, and implement separable a.k.a. crossdomain)identity-based ring signatures (SIBR, pronounced “cyber,” signatures). The ring structure of these signatures provides repudiability. With identity-based public keys, a full PKI is no longer required. Separability allows ring constructions across different identity-based master key domains. Together, these properties make SIBR signatures a practical solution to the email spoofing problem. Our construction yields a number of interesting components. First, we present several novel proofs of knowledge of bilinear map pre-images. We then present new identity-based identification (IBI) and signature (IBS) schemes based on these proofs. We note how our constructions share system parameters with the existing identity-based encryption schemes of Boneh-Franklin andWaters, thereby forming complete identity-based cryptosystems. We finally construct the first SIBR signature schemes by transforming our new signature schemes and certain other signature schemes.