New Signcryption from q-Diffie-Hellman Problems

Recently, Libert and Quisquater proposed an efficient signcryption scheme based on the hardness of q-Diffie-Hellman problems in Gap Diffie-Hellman groups. Their scheme is quite efficient: the signcryption operation has almost the same cost as an ElGamal encryption while the reverse operation only requires one pairing evaluation and three exponentiations. However, Tan showed that their scheme is not even secure against non-adaptive chosen ciphertext attacks. In this paper, we propose a new signcryption scheme based on the hardness of q-Diffie-Hellman problems. We prove its semantic security under the q-Diffie-Hellman Inversion problem assumption and its unforgeability under the q-Strong Diffie-Hellman problem assumption in the random oracle model. This new scheme turns out to be more efficient than all other schemes proposed to date.