Identity-based mediated RSA revisited

In SSYM 2001, Boneh, Ding, Tsudik and Wong presented encryption and signature schemes based on the identity-based mediated RSA (ID-MRSA), in which the users are not allowed to decrypt/sign messages without the permission of a security mediator (the SEM). This allows a simple key revocation. Subsequently, in CT-RSA 2003, Ding and Tsudik presented a security proof for these schemes. In particular, they stated that 'IB-mRSA/OAEP encryption offers equivalent the semantic security to RSA/OAEP against adaptive chosen ciphertext attacks in the random oracle model if the key generation function is division intractable'. To make the key generation function division intractable, Ding and Tsudik used a division intractable hash function to generate division intractable public keys. In this paper, we show that using a division intractable hash function does not necessarily mean that the key generation function is division intractable. We also modify the ID-MRSA so that the generated keys are always division intractable. We also show that these modifications do not passively affect the efficiency of the ID-MRSA.