This paper has two main areas of focus. First, we examine previous definitions of security for ring signature schemes and suggest that most of these prior definitions are too weak, in the sense that they do not take into account certain realistic attacks. We propose new definitions of anonymity and unforgeability which address these threats, and give separation results proving that our new notions are strictly stronger than previous ones. Second, we show the first constructions of ring signature schemes in the standard model. One scheme is based on generic assumptions and satisfies our strongest definitions of security. Two additional schemes are more efficient, but achieve weaker security guarantees and more limited functionality.
Category / Keywords: public-key cryptography / Ring signatures, anonymity, standard model, definitions, constructions, public-key cryptography Publication Info: An extended abstract of this paper will appear in TCC 2006. Date: received 7 Sep 2005, last revised 14 Dec 2005 Contact author: ruggero at cs umd edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: New scheme added. Version: 20051215:023340 (All versions of this report) Short URL: ia.cr/2005/304 Discussion forum: Show discussion | Start new discussion