Another Attack on Tso's Short Signature Scheme Based on Bilinear Pairings

Abstract:

In 2009, R. Tso et al. proposed an efficient pairing-based short signature scheme which is provably secure in the Random Oracle Model. In this paper, we propose a new key substitution attack on Raylin Tso et al.’s short signature scheme. For a given message and the corresponding valid signature, the malicious attacker can generate a substituted public key. Everyone verifies the signature successfully with the malicious attacker’s substituted public key. Therefore, Raylin Tso et al.’s short signature scheme has a security flaw in the multi-user setting.

• Periodical: Applied Mechanics and Materials (Volumes 63-64)
• Pages: 785-788
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.63-64.785
• Online since: June 2011
• Authors: Fan Yu Kong, Lei Wu, Jia Yu
• Keywords: Bilinear Pairing, Digital Signature Scheme, Information Security, Key Substitution Attack, Short Signature

References

[1] D. Boneh, B. Lynn, and H. Shacham: Short signatures from the Weil pairing, In: Advances in Cryptology - Asiacrypt 2001, Lecture Notes in Computer Science, Vol. 2248, Springer-Verlag (2001), pp.514-532.

DOI: 10.1007/3-540-45682-1_30

[2] D. Boneh, and X. Boyen: Short signatures without random oracles, In: Advances in Cryptology - Eurocrypt 2004, Lecture Notes in Computer Science, Vol. 3027, Springer-Verlag (2004), pp.56-73.

DOI: 10.1007/978-3-540-24676-3_4

[3] S. Blake-Wilson and A. Menezes: Unknown key-share attacks on the station-to-station (STS) protocol, In: Public Key Cryptography – PKC 1999, Lecture Notes in Computer Science, Vol. 1560, Springer-Verlag (1999), pp.154-170.

DOI: 10.1007/3-540-49162-7_12

[4] A. Menezes and N. Smart: Security of signature schemes in a multiuser setting, Designs Codes and Cryptography, Vol. 33, no. 3 (2004), pp.261-274.

DOI: 10.1023/b:desi.0000036250.18062.3f

[5] Jens-Matthias Bohli, Stefan Rohrich and Rainer Steinwandt: Key substitution attacks revisited: Taking into account malicious signers, International Journal of Information Security, no. 5 (2006), pp.30-36.

DOI: 10.1007/s10207-005-0071-2

[6] C. H. Tan: Key Substitution Attacks on Some Provably Secure Signature Schemes, IEICE Transactions on Fundamentals, Vol. E87-A, no. 1 (2004), pp.1-2.

DOI: 10.1093/ietfec/e88-a.2.611

[7] C. H. Tan: Key substitution attacks on provably secure short signature schemes, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E88-A, no. 2 (2005), pp.611-612.

DOI: 10.1093/ietfec/e88-a.2.611

[8] C. H. Tan: On Waters' Signature Scheme, IEICE Transactions on Fundamentals, Vol. E89-A, no. 10 (2006), pp.2684-2685.

DOI: 10.1093/ietfec/e89-a.10.2684

[9] Raylin Tso, Takeshi Okamoto, and Eiji Okamoto: Efficient short signatures from pairing, In: Proceedings of the 6th International Conference on Information Technology: New Generations, IEEE Computer Society (2009), pp.417-422.

DOI: 10.1109/isit.2008.4594982

[10] S. Mitsunari, R. Sakai, and M. Kasahara: A new traitor tracing, IEICE Transactions Fundamentals, Vol. E85-A, no. 2 (2002), pp.481-484.

[11] F. Kong, and J. Yu: Key Substitution Attacks on Two Short Signature Schemes from Bilinear Pairings, In: International Conference on Intelligent Information Technology Application - IITA 2010, IEEE (2010), Volume 3, p.262 – 264.