Ring signatures without random oracles

ABSTRACT

Since the formalization of ring signature by Rivest, Shamir and Tauman in 2001, there are lots of variations appeared in the literature. Almost all of the variations rely on the random oracle model for security proof. In this paper, we propose a ring signature scheme based on bilinear pairings, which is proven to be secure against adaptive chosen message attack without using the random oracle model. It is one of the first in the literature to achieve this security level.

REFERENCES

• 1: Masayuki Abe , Miyako Ohkubo , Koutarou Suzuki, 1-out-of-n Signatures from a Variety of Keys, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.415-432, December 01-05, 2002
• 2: M. Bellare, A. Boldyreva, and A. Palacio. An Uninstantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem. In C. Cachin and J. Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, Proceedings, volume 3027 of Lecture Notes in Computer Science, pages 171--188. Springer, 2004.
• 3: M. Bellare, D. Micciancio, and B. Warinschi. Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions. In E. Biham, editor, Advances in Cryptology - EUROCRYPT 2003, Proceedings, volume 2656 of Lecture Notes in Computer Science, pages 614--629. Springer, 2003.
• 4: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 5: A. Bender, J. Katz, and R. Morselli. Ring Signatures: Stronger Definitions, and Constructions without Random Oracles. To appear in TCC 06. Cryptology ePrint Archive, Report 2005/304, 2005.
• 6: D. Boneh and X. Boyen. Short signatures without random oracles. In C. Cachin and J. Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, Proceedings, volume 3027 of Lecture Notes in Computer Science, pages 56--73. Springer, 2004.
• 7: D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In E. Biham, editor, Advances in Cryptology - EUROCRYPT 2003, Proceedings, volume 2656 of Lecture Notes in Computer Science, pages 416--432. Springer, 2003.
• 8: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 9: Emmanuel Bresson , Jacques Stern , Michael Szydlo, Threshold Ring Signatures and Applications to Ad-hoc Groups, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.465-480, August 18-22, 2002
• 10: Jan Camenisch , Markus Stadler, Efficient Group Signature Schemes for Large Groups (Extended Abstract), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.410-424, August 17-21, 1997
• 11: Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.209-218, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276741]
• 12: D. Chaum and E. van Heyst. Group signatures. In D. W. Davies, editor, Advances in Cryptology - EUROCRYPT '91, Proceedings, volume 547 of Lecture Notes in Computer Science, pages 257--265. Springer, 1991.
• 13: S. Chow, L. Hui, and S. Yiu. Identity Based Threshold Ring Signature. In Information Security and Cryptology - ICISC 2004, Revised Papers, volume 3506 of Lecture Notes in Computer Science, pages 218--232, Seoul, Korea, 2004. Springer--Verlag. Also available at Cryptology ePrint Archive, Report 2004/179.
• 14: S. Chow, S. Yiu, and L. Hui. Efficient Identity Based Ring Signature. In Applied Cryptography and Network Security, Third International Conference, ACNS 2005, Proceedings, volume 3531 of Lecture Notes in Computer Science, pages 499--512. Springer--Verlag, 2005. Also available at Cryptology ePrint Archive, Report 2004/327.
• 15: Ronald Cramer , Ivan Damgård , Berry Schoenmakers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.174-187, August 21-25, 1994
• 16: Y. Dodis, A. Kiayias, A. Nicolosi, and V. Shoup. Anonymous Identification in Ad Hoc Groups. In C. Cachin and J. Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, Proceedings, volume 3027 of Lecture Notes in Computer Science, pages 609--626. Springer, 2004.
• 17: J. Groth, R. Ostrovsky, and A. Sahai. Perfect Non-Interactive Zero Knowledge for NP. Cryptology ePrint Archive, Report 2005/290, 2005.
• 18: F. Laguillaumie and D. Vergnaud. Multi-designated Verifiers Signatures. In J. Lopez, S. Qing, and E. Okamoto, editors, Information and Communications Security, 6th International Conference, ICICS 2004, Proceedings, volume 3269 of Lecture Notes in Computer Science, pages 495--507. Springer--Verlag, 2004.
• 19: Ronald L. Rivest , Adi Shamir , Yael Tauman, How to Leak a Secret, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.552-565, December 09-13, 2001
• 20: W. Susilo and Y. Mu. Non-Interactive Deniable Ring Authentication. In J. I. Lim and D. H. Lee, editors, Information Security and Cryptology - ICISC 2003, Revised Papers, volume 2971 of Lecture Notes in Computer Science, pages 386--401. Springer--Verlag, 2004.
• 21: W. Susilo, Y. Mu, and F. Zhang. Perfect Concurrent Signature Schemes. In J. Lopez, S. Qing, and E. Okamoto, editors, Information and Communications Security, 6th International Conference, ICICS 2004, Proceedings, volume 3269 of Lecture Notes in Computer Science, pages 14--26. Springer--Verlag, Oct. 2004.
• 22: V. K. Wei. Tight Reductions among Strong Diffie-Hellman Assumptions. Cryptology ePrint Archive, Report 2005/057, 2005.
• 23: J. Xu, Z. Zhang, and D. Feng. A Ring Signature Scheme Using Bilinear Pairings. In C. H. Lim and M. Yung, editors, Information Security Applications, 5th International Workshop, WISA 2004, Revised Papers, volume 3325 of Lecture Notes in Computer Science, pages 163--172. Springer--Verlag, 2004.
• 24: Fangguo Zhang , Kwangjo Kim, ID-Based Blind Signature and Ring Signature from Pairings, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.533-547, December 01-05, 2002
• 25: F. Zhang, R. Safavi-Naini, and W. Susilo. An Efficient Signature Scheme from Bilinear Pairings and Its Application. In F. Bao, R. H. Deng, and J. Zhou, editors, Public Key Cryptography - PKC 2004, Proceedings, volume 2947 of Lecture Notes in Computer Science, pages 277--290. Springer, 2004.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security, Theory

Keywords:
bilinear pairings, random oracle model, ring signature