A survey of ring signature

Abstract

Ring signature allows specifying a set of possible signers without revealing which member actually produces the signature. This concept was first formalized in 2001 by Rivest, Shamir and Tauman. In this paper, we review the state-of-the-art of ring signature, summarize the study of ring signature schemes in the literature and investigate their relationships with other existing cryptographic schemes. We also describe a large number of extensions, modifications and applications of ring signatures after the original version of this work. Some problems in the study of this field were presented as well. Finally, we discuss a number of interesting open problems and point out the possible future work.

References

1. Rivest R L Shamir A Tauman Y How to leak a secretBoyd CProceedings of ASIACRYPT'01. Lecture Notes in ComputerScienceBerlinSpringer-Verlag 2001 2248552565 2. Chaum D Heyst V E Group signaturesDavies D WProceedingsof EUROCRYPT'91. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 1991 547257265 3. Abe M Ohkubo M Suzuki K 1-out-of-n signatures from a variety of keysZheng Y LProceedingsof ASIACRYPT'02. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2002 2501415432 4. Zhang F G Kim K ID-based blind signature andring signature from pairingsZheng Y LProceedings of ASIACRYPT'02. Lecture Notes in ComputerScienceBerlinSpringer-Verlag 2002 2501533547 5. Bresson E Stern J Szydlo M Threshold ring signatures and applications to ad-hoc groupsYung MProceedingsof CRYPTO'02. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2002 2442465480 6. Naor M Deniablering authenticationYung MProceedings of CRYPTO'02. Lecture Notes in ComputerScienceBerlinSpringer-Verlag 2002 2442481498 7. Susilo W Mu Y Non-interactive deniable ringauthenticationLim J ILee D HICISC2003. Lecture Notes inComputer ScienceBerlinSpringer-Verlag 2004 2971386401 8. Lv J Q Wang X M Verifiable ring signatureDMS Proceedings of CANS'03 2003 663665 9. Gao C Z Yao Z A Li L A ring signature scheme based on the Nyberg-Rueppel signatureschemeZhou JYung MHan YACNS 2003. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2003 2846169175 10. Herranz J Sáez G Forking lemmas for ring signatureschemesJohansson TMaitra SProceedings of INDOCRYPT'03.Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2003 2904266279 11. Zhang F G Reihaneh S N Lin C Y New proxy signature, proxy blind signature and proxy ringsignature schemes from bilinear pairings 12. Chen L Q Kudla C Paterson K G Concurrent signaturesCachin CCamenisch JProceedingsof EUROCRYPT'04. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2004 3027287305 13. Wong D S Fung K Liu J K et al.On the RS-code construction of ring signature schemesand a threshold setting of RSTQing S HGollmann DZhou J YProceedings of ICICS 2003. Lecture Notes in ComputerScienceBerlinSpringer-Verlag 2003 28363446 14. Liu J K Wei V K Wong D S Linkable spontaneous anonymous group signature for Ad-hocgroupsWang H XProceedings of ACISP'04. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2004 3108325335 15. Tsang P P Wei V K Chan T K et al.Separable linkable threshold ring signaturesCanteaut AViswanathanKProceedings of INDOCRYPT'04. LectureNotes in Computer ScienceBerlinSpringer-Verlag 2004 3348384398 16. Dodis Y Kiayias A Nicolosi A et al.Anonymous identification in Ad-hoc groupsCachin CCamenisch JProceedings of EUROCRYPT'04. Lecture Notes in ComputerScienceBerlinSpringer-Verlag 2004 3027609626 17. Benaloh J Mare M D One-way accumulators: a decentralizedalternative to digital signaturesHellesethTAdvances in Cryptology- EUROCRYPT'93.Lecture Notes in Computer ScienceBerlinSpringer-Verlag 1993 765274285 18. Gan Z Chen K F A new verifiable ring signatureschemeActa Scientlarum Naturalium UniversitatisSunyatseni 2004 43(Supp 2)132134 (in Chinese) 19. Awasthi A K Sunder L ID-based ring signature andproxy ring signature schemes from bilinear pairings 20. Herranz J Sáez G New identity-based ring signatureschemesLopez JQing S HOkamoto EProceedings of ICICS 2004. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2004 32692739 21. Lv J Q Ren K Chen X et al.Ring authenticated encryption: a new type of authenticatedencryptionProceedings of SCIS 2004SendiIEICEPress 2004 11791184 22. Cao T Lin D Xue R Improved ring authenticated encryption schemeProceedings of JICC 2004International Academic Publishers World Publishing Corporation 2004 341346 23. Wang J L Zhang J H Wang Y M A group signature scheme based on ring signature ideaACTA Electronic Sinica 2004 32(3)408410 (in Chinese) 24. Chan T K Fung K Liu J K et al.Blind spontaneous anonymous group signatures forAd-hoc groupsCastelluccia C et al.Proceedings of ESAS 2004. Lecture Notes inComputer ScienceBerlinSpringer-Verlag 2005 33138294 25. Chow S S M Hui L C K Yiu S M Identity based threshold ring signaturePark CChee SICISC 2004. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2005 3506218232 26. Liu J K Wong D S On the security models of (threshold)ring signature schemesPark CChee SProceedingsof ICISC 2004. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2005 3506204217 27. Tsang P P Wei V K Chan T K et al.Separable linkable threshold ring signaturesCanteaut AViswanathanKProceedings of INDOCRYPT'04. LectureNotes in Computer ScienceBerlinSpringer-Verlag 2004 3348384398 28. Herranz J Sáez G Distributed ring signaturesfor Identity-Based scenarios 29. Wu Q H Wang J L Wang Y M A t-out-of-n ring signature based on DLPAdvance in ChinaCrypt'04BeijingScience Press 2004 209214 30. Isshiki T Tanaka K An (n-t)-out-of-n thresholdring signature schemeBoyd CManuel JNieto GProceedings of ACISP 2005. Lecture Notes in ComputerScienceBerlinSpringer-Verlag 2005 3574406416 31. Au M H Liu J K Tsang P P et al.A suite of ID-based threshold ring signature schemeswith different levels of anonymity 32. Lee K C Wei H Hwang T Convertible ring signatureIEEProceedings of Communications 2005 152(4)411414 33. Tsang P P Wei V K Short linkable ring signaturesfor E-voting, E-cash and attestationDengR H et al.Proceedings of ISPEC 2005.Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2005 34394860 34. Nguyen L Accumulatorfrom bilinear pairings and application to ID-based ring signaturesand group membership revocationMenezes AProceedings of CT-RSA 2005. Lecture Notes in ComputerScienceBerlinSpringer-Verlag 2005 3376275292 35. Wu Q H Zhang F G Susilo W et al.An efficient static blind ring signature schemeWon DKim SProceedings of ICISC 2005. Lecture Notes in ComputerScienceBerlinSpringer-Verlag 2006 3935410423 36. Lei Q Jiang Z T Wang Y M Ring-based anonymous fingerprinting schemeHao YLiu JWang Y et al.Proceedings of CIS 2005.Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2005 380210801085 37. Liu J K Wong D S Solutions to Key Exposure problemin ring signature 38. Zhang F G Chen X F Cryptanalysis and improvementof an ID-based Ad-hoc anonymous identification scheme at CT-RSA 05 39. Chen Y Q Susilo W Mu Y Identity-based anonymous designated ring signaturesGuizani MChen HProceedings of IWCMC'06USAACM Press 2006 189194 40. Chow S S M Liu J K Wei V K et al.Ring signature without random oracles 41. Bender A Katz J Morselli R Ring signatures: stronger definitions, and constructionswithout random oraclesHalevi SRabin TProceedingsof TCC 2006. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2006 38766079 42. Huang X Y Zhang F T Wu W An identity-based ring signcryption schemeACTA Electronic Sinica 2006 34(2)263266 (in Chinese) 43. Susilo W Mu Y Deniable ring authenticationrevisitedJakobsson MYung MZhou JProceedings of ACNS 2004. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2004 3089149163 44. Wang C H Liu C Y A new ring signature schemewith signer-admission propertyInformationSciences 2007 177(3)747754 45. Au M H Chow S S M Susilo W et al.Short linkable ring signatures revisitedAtzeni A SLioy AProceedings of EuroPKI 2006. Lecture Notes in ComputerScienceBerlinSpringer-Verlag 2006 4043101115 46. Liu J K Wei V K Wong D S A separable threshold ring signature schemeLim J ILee D HProceedings of ICISC 2003. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2004 29711226 47. Liu J K Wong D S Linkable ring signatures securitymodels and new schemesGervasi OGavrilova M LKumarV et al.Proceedings of ICCSA 2005.Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2005 3481614623 48. Liu J K Susilo W Wong D S Ring signatures with designated linkabilityYoshiura HSakurai KRannenberg K et al.Proceedings of IWSEC 2006. Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2006 4266104119 49. Zhang C L Liu Y He D Q A new verifiable ring signature scheme based on Nyberg-RueppelschemeProceedings of ICSP2006USAIEEE Press 2006 50. Fujisaki E Suzuki K Traceable ring signature 51. Lang W M Yang Z K Cheng W Q et al.An improved identity-based proxy ring signatureschemeHigh Technology Letters 2005 11(1)1719 52. Li J Chen X F Yuen T H et al.Proxy ring signature: formal definitions, efficientconstruction and new variantProceedingsof CIS 2006USAIEEE Press 2006 12591264 53. Herranz J Laguillaumie F Blind ring signatures secureunder the Chosen-Target-CDH assumptionKatsikasS K et al.Proceedings of ISC 2006.Lecture Notes in Computer ScienceBerlinSpringer-Verlag 2006 4176117130 54. Cao T J Lin D D Xue R ID-based ring authenticated encryptionProceedings of AINA'05USAIEEE Press 2005 591596 55. Ma C G Yang Y X Transferable off-line electroniccashChinese Journal of Computers 2005 28(3)301308 (in Chinese) 56. Ma C G Yang Y X Hu Z M et al.A fair electronic check systems with reusable refundACTA Electronic Sinica 2005 33(9)15621566 (in Chinese)