PROBABILISTIC ENCRYPTION: THEORY AND APPLICATIONS (PARTIAL INFORMATION, FACTORING, PSEUDO RANDOM BIT GENERATION)

We introduce a new probabilistic model of data encryption. For this model, under suitable complexity assumptions, it is proved that extracting any information about messages from their encodings is difficult on the average for an adversary with polynomially bounded computational resources. This security holds for any message space with any probability distribution.; We provide a formal model of a public key cryptosystem and intro- duce a formal definition of security for such systems. Our security definition guarantees that no passive eavesdropper will have even a moderate success in distinguishing between any two encrypted messages. Our probabilistic encryption model achieves this security criterion.; Two concrete implementations of our model are presented. The first is secure under the assumption that factoring is intractable. The second is secure under the assumpton that it is intractable to decide whether numbers are quadratic residues modulo a composite number whose factorization is unknown. In other words, any threat to the security of the concrete implementations of our encryption model will result in an efficient algorithm for factoring or for deciding quadratic residuosity modulo composite numbers.; Two trapdoor number theoretic boolean predicates are introduced: the Quadratic Residuosity predicate and the Factoring predicate. Their relevance to cryptographical games and protocols is discussed.; Finally, we present a method for generating a pseudo random sequence of bits which are as hard to predict as it is to factor large composite numbers.; ('1)This research was supported in part by NSF grant MCS 82-04506.