Goldwasser–Micali Encryption Scheme

• : on input , run to obtain , and choose a uniform The public key is and the private key is
• : on input a public key and a message , choose a uniform and output the ciphertext

• : on input a private key and a ciphertext , determine whether is a quadratic residue modulo . If yes, output otherwise, output 1 .

If the quadratic residuosity problem is hard relative to , then the Goldwasser–Micali encryption scheme is CPA-secure.

:

Let denote the Goldwasser–Micali encryption scheme. Let be an arbitrary probabilistic polynomial-time adversary. Consider the following PPT adversary that attempts to solve the quadratic residuosity problem relative to :

Algorithm :

The algorithm is given and as input, and its goal is to determine if or .

• Set and run to obtain two single-bit messages
• Choose a uniform bit and a uniform , and then set
• Give the ciphertext to , who in turn outputs a bit . If , output otherwise, output

Let us analyze the behavior of There are two cases to consider:

Case 1: Say the input to was generated by running to obtain and then choosing a uniform Then runs on a public key constructed exactly as in , and we see that in this case the view of when run as a subroutine by is distributed identically to 's view in experiment . Since outputs 1 exactly when the output of is equal to , we have

where represents a uniform element of .

Case 2: Say the input to was generated by running to obtain and then choosing a uniform . We claim that the view of in this case is independent of the bit . To see this, note that the ciphertext given to is a uniform quadratic residue regardless of whether a 0 or a 1 is encrypted:

• When a 0 is encrypted, for a uniform , and so is a uniform quadratic residue.
• When a 1 is encrypted, for a uniform Let , and note that is a uniformly distributed element of the group Since ,   is uniformly distributed in as well.

Since 's view is independent of , the probability that in this case is exactly . That is,

where represents a uniform element of . Thus,

By the assumption that the quadratic residuosity problem is hard relative to , there is a negligible function such that

thus, . This completes the proof.