An efficient probabilistic encryption scheme (Q912074)

In this paper we present a new probabilistic encryption algorithm in which system security is polynomially secure. We first review and develop some properties associated with the quadratic residue modulo n, where n is a product of two primes, each congruent to 3 modulo 4. Then we generalize these properties to the case where n is a product of any number of such primes. The encryption algorithm utilizes the public key concept and iteratively encrypts a sequence of single bit or of multiple bits. The scheme provides for a digital signature as well.