Generalized Goldwasser and Micali’s Type Cryptosystem

In 1982, Goldwasser and Micali proposed the first probabilistic public key cryptosystem with indistinguishability under chosen plaintext attack security based on the quadratic residuosity assumption. Ciphertext expansion of Goldwasser’s scheme is quite large, thereby the scheme is inefficient. A lot of schemes have been proposed to reduce the ciphertext expansion. Some schemes use the same encryption algorithm as Goldwasser’s scheme with different parameters and keys, which we call them Goldwasser and Micali’s type (GM-type) schemes. GM-type schemes can be divided into two categories according to different parameters and decryption algorithms. In this paper, we propose the first generalized GM-type scheme combining these two categories. All GM-type schemes are special cases of our generalized GM-type scheme. The ciphertext expansion of our scheme is smaller than that of any other GM-type schemes.