Efficient probabilistic public-key encryption schemes with |n|+k bit plaintexts

Based on the intractable problems of nth residuosity and quadratic residuosity, by choosing proper parameters and without increasing the length of ciphertexts, the efficiency and the size of plaintexts of a probabilistic public-key encryption scheme proposed by Paillier and Pointcheval were improved. The improved encryption scheme can encrypt |n|+k bit messages with higher efficiency. Security and efficiency analysis of the improved encryption scheme were also provided, and the security of the improved scheme is equivalent to that of the original encryption scheme, the higher residuosity problem and quadratic residuosity problem modulo n. Compared to the original Paillier-Pointcheval encryption scheme, the improved encryption scheme has features of higher efficiency, lower traffic date and larger size of plaintexts.