Digital Signature Scheme Based on the Inverse Bilinear Pairing Operation Problem

First, based on the bilinear pairings, a new computing problem, inverse bilinear paring operation problem (IBPOP), is proposed, which is proved to be not easier than the computing diffie-Hellman problem (CDHP) and not harder than discrete logarithm problem (DLP). So, if the symbol ldquolesrdquo denotes the increase of the hardness of computing problem, it can be deduced that CDHPlesIBPOPlesDLP. Then, based on the hardness assumption of IBPOP, by using the bilinear pairing, a certificate-based and randomized signature scheme is proposed. Under the hardness assumption of IBPOP, the signature scheme can be proved to be secure in random oracle. On the other hand, the security of most of the known pairing-based signature schemes depends on the hardness assumption of CDHP, which is a stronger assumption than the new scheme. The new signature is an efficient pairing-based one, since there is only one operation of pairings in it.