A commutative encryption scheme based on ElGamal encryption

A commutative encryption is a kind of an encryption system that enables a plaintext to be encrypted more than once using different users' public keys. In this system, decryption is not required before the encryption/re-encryption processes. Moreover, the resulted ciphertext can be decrypted by the designated decrypters without considering the order of public keys used in the encryption/re-encryption processes. In other words, the order of keys used in encryption and in decryption do not affect the computational result. Commutative encryption scheme is found useful in many real life applications such as in secret sharing, database integration and etc. However, regardless of its usefulness, few paper demonstrates how to construct such kind of a commutative encryption. In this paper, we propose a new commutative encryption scheme based on the ElGamel encryption and provide the security proof in the random oracle model.