Probabilistic Encryption

URL: https://www.sciencedirect.com/science/article/pii/0022000084900709 Authors: Shafi Goldwasser, Silvio Micali

Abstract

A new probabilistic model of data encryption is introduced. For this model, under suitable complexity assumptions, it is proved that extracting any information about the cleartext from the ciphertext is hard on the average for any polynomial time adversary. The proof holds for any message space. A concrete encryption scheme based on the quadratic residuosity problem is given. This scheme is the first to satisfy the new security definition (semantic security / IND-CPA security). The encryption algorithm is a 1-bit at a time scheme where encrypting 0 yields a random quadratic residue and encrypting 1 yields a random quadratic non-residue with Jacobi symbol 1.