Key Substitution Attack and Malleability of a Short Signature Scheme with Batch Verification

Abstract:

At IWSEC 2008, F. Guo et al. proposed an efficient short signature scheme with batch verification based on C. Gentry’s scheme. In this paper, we firstly propose the key substitution attack on F. Guo et al.’s digital signature scheme and show that the malicious adversary can forge a valid signature, which can be verified with a substituted public key. Secondly, we prove that F. Guo et al.’s scheme is malleable and the attacker can produce a new valid signature on the message if he/she has known some valid signatures on the same message.

• Periodical: Applied Mechanics and Materials (Volumes 55-57)
• Pages: 1605-1608
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.55-57.1605
• Online since: May 2011
• Authors: Fan Yu Kong, Jia Yu
• Keywords: Batch Verification, Bilinear Pairing, Key Substitution Attack, Malleability, Short Signature Scheme

References

[1] 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

[2] 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

[3] 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

[4] 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

[5] 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

[6] 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

[7] A. Fiat: Batch RSA, In: CRYPTO 1989, Lecture Notes in Computer Science, Vol. 435, Springer, Heidelberg (1990), p.175–185.

DOI: 10.1007/0-387-34805-0_17

[8] M. Bellare, J. Garay and T. Rabin: Fast batch verification for modular exponentiation and digital signatures, In: EUROCRYPT 1998, Lecture Notes in Computer Science, Vol. 1403, Springer, Heidelberg (1998), p.236–250.

DOI: 10.1007/bfb0054130

[9] J. Camenisch, S. Hohenberger and M. Pedersen: Batch Verification of Short Signatures, In: EUROCRYPT 2007, Lecture Notes in Computer Science, Vol. 4515, Springer, Heidelberg (2007), p.246–263.

DOI: 10.1007/978-3-540-72540-4_14

[10] C. Gentry: Practical Identity-Based Encryption Without Random Oracles, In: EUROCRYPT 2006, Lecture Notes in Computer Science, Vol. 4004, Springer, Heidelberg (2006), p.445–464.

DOI: 10.1007/11761679_27

[11] Fuchun Guo, Yi Mu and Zhide Chen: Efficient Batch Verification of Short Signatures for a Single-Signer Setting without Random Oracles, In: IWSEC 2008, Lecture Notes in Computer Science, Vol. 5312, Springer, Heidelberg (2008), p.49–63.

DOI: 10.1007/978-3-540-89598-5_4