Kristiyan Haralambiev
New York University

Efficient Ring Signatures without Random Oracles

We describe the first efficient ring signature scheme secure, without random
oracles, based on standard assumptions. Our ring signatures are based in
bilinear groups. For $l$ members of a ring our signatures consist of $2l+2$
group elements and require $2l+3$ pairings to verify. We prove our scheme secure
in the strongest security model proposed by Bender, Katz, and Morselli: namely,
we show our scheme to be anonymous against full key exposure and unforgeable
with respect to insider corruption. A shortcoming of our approach is that all
the users' keys must be defined in the same group.

Hovav Shacham and Brent Waters