At Eurocrypt '02, Cramer and Shoup [1] proposed a general paradigm to construct practical public-key encryption schemes secure against the adaptive chosen ciphertext attack as well as several concrete examples. One of these example is the scheme based on the quadratic residuosity (QR) problem. However this scheme is less efficient than the other examples. In this paper, we construct a new variant of the Cramer-Shoup encryption scheme which is related to the QR problem. Our variant is more efficient than the scheme based on the QR problem.