Asymmetric Encryption Systems - Contemporary Cryptography - page 360

This means that if x is a quadratic residue modulo n , then the Jacobi symbol
of x modulo n must be 1, but the converse is not true (i.e., even if the Jacobi symbol
of x modulo n is 1, x must not be a quadratic residue modulo n ). If, however, the
Jacobi symbol of x modulo n is

− 1, then we know that x is a quadratic nonresidue

modulo n :

x
n

=

x ∈ QNR n ⇐ − 1

QR n = J n \

Again referring to Section 3.3.7, QR n refers to the set of all

pseudosquares modulo n .If n = pq ,then

|QR n | | QR n | = =( p − 1)( q − 1) / 4 .

This means that half of the elements in J n are quadratic residues and the other
half are pseudosquares modulo n . So if an arbitrary element of J n is given, it is
computationally difficult to decide whether it is a square or a pseudosquare modulo
n . Probabilistic encryption as proposed by Goldwasser and Micali takes advantage
of this computational difficulty.

14.3.1.1 Key Generation Algorithm

Similar to the RSA public key cryptosystem, the Generate algorithm employed by
probabilistic encryption takes as input a security parameter and generates as output
two primes p and q and a modulus n = pq of about the security parameter's size.
Furthermore, the algorithm selects a pseudosquare y

∈ QR n . The pair ( n, y ) then
represents the public key, and ( p, q ) represents the private key. So each user holds as
secret the factorization of his or her modulus n .

14.3.1.2 Encryption Algorithm

The Encrypt algorithm employed by probabilistic encryption must specify how a
k -bit plaintext message m = m 1 m 2 ...m k is encrypted so that only the recipient
(or somebody holding the recipient's private key) is able to decrypt it. As its name
suggests, the Encrypt algorithm is probabilistic. It takes as input a public key ( n, y )
and a message m , and it generates as output the ciphertext c .
For every message bit m i ( i =1 ,...,k ),the Encrypt algorithm chooses

x i ∈ R Z n and computes c i as follows: