Attack on Okamoto et al.’s New Short Signature Schemes.pdf

Attack on Okamoto et al.’s New Short Signature Schemes Fangguo Zhang1 and Xiaofeng Chen2 1 Department of Electronics and Communication Engineering, Sun Yat-Sen University, Guangzhou 510275, P.R.China isdzhfg@zsu.edu.cn 2 Department of Computer Science, Sun Yat-Sen University, Guangzhou 510275, P.R.China isschxf@zsu.edu.cn Abstract. We present an attack on a new short signature scheme from bilinear pairing proposed by Okamoto et al. at ITCC’05. We show that any one can derive the secret key of the signer from any two message- signature pairs and so can forge the signer’s signature for any message. This means the scheme is totally broken. Keywords: Short Signature, Bilinear Pairing, Cryptanalysis. 1 Introduction: Digital signature schemes allow a signer to transform any arbitrary message into a signed message, such that anyone can verify the validity of the signed message using the signer’s public key, but only the signer can generate signed messages. Proxy signature is a type of signature, it was first introduced by Mambo, Usuda, and Okamoto in 1996 [3]. The proxy signature schemes allow proxy sign- ers to sign messages on behalf of an original signer. Such signatures have found numerous applications, particularly in distributed computing where delegation of rights is quite common. Short digital signatures are always desirable. They are necessary in situations in which humans are asked to manually key in the signature or when working in low-bandwidth communication environments. They are also useful in general to reduce the communication complexity of any transmission. Recently, T. Okamoto, A. Inomata and E. Okamoto proposed a new and short s