Java Program for Goldwasser Micali Bit Encryption

Introduction

Shafi Goldwasser and Silvio Micali introduced probabilistic encryption in their 1982 paper "Probabilistic Encryption and How to Play Mental Poker Keeping Secrets All Partial Information". The construction was the first to achieve semantic security (now also called IND-CPA), the strong notion that an adversary learning a ciphertext cannot distinguish it from an encryption of any other plaintext, even with auxiliary information. The construction rests on the quadratic residuosity assumption, a hardness problem related to but distinct from RSA.

For Java learners, Goldwasser-Micali is the simplest semantically-secure public-key cryptosystem. The message space is a single bit, the encryption is two modular exponentiations, the decryption is a Legendre symbol. It is the bridge between deterministic RSA (which is not semantically secure) and modern probabilistic encryption schemes like EC-ElGamal and RSA-OAEP.

What is the Goldwasser-Micali Cryptosystem?

Goldwasser-Micali is a public-key probabilistic encryption scheme whose plaintext space is a single bit. It belongs to the residuosity family (alongside Benaloh and Naccache-Stern). The public key is a Blum-like modulus N=pq and a quadratic non-residue y whose Jacobi symbol mod N is +1 (so y is a non-residue modulo exactly one of p, q but a residue modulo the other). The private key is the factorization of N.

Encryption of bit b is c = y^b * r^2 mod N for random r coprime to N. The random r makes the scheme probabilistic: two encryptions of the same bit produce different ciphertexts. Decryption computes the Legendre symbol of c modulo p (one of the secret factors); if c is a quadratic residue mod p then b=0, otherwise b=1. The proof uses the fact that y is a non-residue mod p (so y^b has Legendre symbol (-1)^b) and r^2 is always a residue.

How Goldwasser-Micali Works - Step by Step

Step 1: Key generation. Pick primes p, q. For the demo we use p=7, q=11, so N=77. Find y in Z_N^* such that y is a quadratic non-residue mod N but the Jacobi symbol of y modulo N is +1; equivalently, y is a non-residue mod both p and q (so both Legendre symbols are -1, and their product is +1). We use y=10: (10/7) = -1 because 10 mod 7 = 3 and 3 is a non-residue mod 7; (10/11) = -1 because 10 mod 11 = 10 = -1 and -1 is a non-residue mod 11 (since 11 = 3 mod 4).

Step 2: Encryption. To encrypt bit b in {0, 1}, pick a random r coprime to N. Compute c = y^b * r^2 mod N. For b=0, c = r^2 is a random QR. For b=1, c = y * r^2 is a random non-QR.

Step 3: Decryption. Compute the Legendre symbol of c modulo p (the private prime). If (c/p) = 1, c is a QR mod p, so b = 0. If (c/p) = -1, c is a non-residue mod p, so b = 1. The Legendre symbol is computed as c^((p-1)/2) mod p, which equals 1 for residues and p-1 for non-residues.

Step 4: Semantic security argument. Without the factorization of N, the Jacobi symbol (c/N) is computable but does not distinguish residues from non-residues (since both can have Jacobi +1). The decisional quadratic residuosity assumption states that distinguishing QRs from non-QRs (both with Jacobi +1) is infeasible. Hence an attacker cannot distinguish an encryption of 0 from an encryption of 1, achieving semantic security.

Java Program for Goldwasser Micali Bit Encryption

import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.List;

public class GoldwasserMicaliDemo {

    private static final BigInteger P = BigInteger.valueOf(7);
    private static final BigInteger Q = BigInteger.valueOf(11);
    private static final BigInteger N = P.multiply(Q); // 77
    private static final BigInteger Y = BigInteger.valueOf(10); // non-QR, Jacobi +1
    private static final BigInteger LEGENDRE_EXP =
        P.subtract(BigInteger.ONE).divide(BigInteger.valueOf(2)); // (p-1)/2 = 3

    // c = y^b * r^2 mod N
    public static BigInteger encryptBit(int bit, BigInteger r) {
        return Y.modPow(BigInteger.valueOf(bit), N)
            .multiply(r.modPow(BigInteger.valueOf(2), N)).mod(N);
    }

    // Decrypt by computing Legendre symbol (c/p)
    public static int decryptBit(BigInteger c) {
        BigInteger legendre = c.modPow(LEGENDRE_EXP, P);
        if (legendre.equals(BigInteger.ONE)) {
            return 0;
        }
        return 1; // legendre == p - 1 means -1
    }

    // Encrypt a String by encrypting each bit of each character
    public static List<BigInteger> encryptString(String s, int seedBase) {
        List<BigInteger> cts = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            for (int b = 7; b >= 0; b--) {
                int bit = (ch >> b) & 1;
                BigInteger r = BigInteger.valueOf(
                    seedBase + i * 8 + (7 - b));
                cts.add(encryptBit(bit, r));
            }
        }
        return cts;
    }

    public static String decryptBits(List<BigInteger> cts) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < cts.size(); i += 8) {
            char ch = 0;
            for (int b = 0; b < 8; b++) {
                int bit = decryptBit(cts.get(i + b));
                ch = (char) ((ch << 1) | bit);
            }
            sb.append(ch);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println("Setup: p=" + P + " q=" + Q + " N=" + N
            + " y=" + Y);

        // Encrypt single bits with the same r to inspect
        BigInteger r = BigInteger.valueOf(3);
        for (int b = 0; b < 2; b++) {
            BigInteger c = encryptBit(b, r);
            int d = decryptBit(c);
            System.out.println("bit=" + b + " r=" + r
                + " -> c=" + c + " -> decrypt=" + d);
        }

        // Two different r for the same bit show probabilistic property
        BigInteger r1 = BigInteger.valueOf(3);
        BigInteger r2 = BigInteger.valueOf(5);
        BigInteger c1 = encryptBit(1, r1);
        BigInteger c2 = encryptBit(1, r2);
        System.out.println("bit=1 r=3 -> c=" + c1);
        System.out.println("bit=1 r=5 -> c=" + c2);
        System.out.println("Both decrypt to bit 1: "
            + decryptBit(c1) + ", " + decryptBit(c2));

        // Encrypt and decrypt a String
        String msg = "Hi";
        List<BigInteger> cts = encryptString(msg, 3);
        System.out.println("Encrypted '" + msg + "' to "
            + cts.size() + " ciphertexts");
        String recovered = decryptBits(cts);
        System.out.println("Decrypted to: '" + recovered + "'");
    }
}

Code Explanation - Line by Line

The constants P, Q, N, Y encode the demo parameters. P=7 and Q=11 are small primes so N=77. Y=10 is a quadratic non-residue modulo both 7 and 11, so the Legendre symbols (10/7) and (10/11) are both -1 and the Jacobi symbol (10/77) = +1. This is the canonical setup for Goldwasser-Micali.

LEGENDRE_EXP = (p-1)/2 = 3 is precomputed because it is used in every decryption. The Legendre symbol (c/p) = c^3 mod p, which equals 1 if c is a QR mod p and equals p-1 = 6 if c is a non-residue mod p. The decryptBit method simply compares the computed Legendre value to 1.

The encryptBit method computes y^b * r^2 mod N in two modular exponentiations and one multiply. For bit=0, y^0 = 1, so the result is just r^2 (a random QR). For bit=1, the result is y * r^2 (a random non-QR, since y is a non-QR and r^2 is a QR, their product is a non-QR).

The encryptString and decryptBits methods extend the scheme to arbitrary messages by encrypting each bit individually. Each character of "Hi" expands to 8 ciphertexts, so a 2-character message produces 16 ciphertexts. The deterministic r in encryptString (derived from position) is only for reproducible demo output; in production you would use SecureRandom.

Sample Input and Output

Setup: p=7 q=11 N=77 y=10
bit=0 r=3 -> c=9 -> decrypt=0
bit=1 r=3 -> c=13 -> decrypt=1
bit=1 r=3 -> c=13
bit=1 r=5 -> c=19
Both decrypt to bit 1: 1, 1
Encrypted 'Hi' to 16 ciphertexts
Decrypted to: 'Hi'

The output confirms that bit=0 and bit=1 decrypt correctly with the same r, that two different r values produce different ciphertexts for the same bit (the probabilistic property), and that a 2-character message encrypts to 16 ciphertexts and decrypts back to the original.

Common Mistakes to Avoid

1. Picking y that is a quadratic residue mod N. If y is a QR, then y * r^2 is always a QR, and the Legendre symbol of the ciphertext is always 1, regardless of b. The scheme becomes trivially insecure. Always test (y/p) = -1 during key generation.

2. Picking y with Jacobi symbol -1 mod N. If Jacobi(y/N) = -1, then Jacobi(c/N) = (-1)^b, which lets an attacker learn b from the publicly computable Jacobi symbol without factoring. Always pick y such that both Legendre symbols are -1 (so the Jacobi is +1).

3. Using primes p, q with p = 1 mod 4 or q = 1 mod 4 without checking. For p = 3 mod 4, -1 is a non-residue mod p, which makes (q-1)/2-th power a simple test for residuosity. The classic Goldwasser-Micali setup uses Blum primes (p, q both 3 mod 4) to simplify the QR test.

4. Forgetting that encrypting one bit produces one ciphertext. Goldwasser-Micali is extremely bandwidth-inefficient: a 1 KB message expands to 8 KB of ciphertexts (one per bit) at the modulus size. Use ElGamal or RSA-OAEP for practical message encryption; reserve Goldwasser-Micali for theoretical constructions and teaching.

Real-World Applications

Goldwasser-Micali is rarely deployed directly because of its bandwidth inefficiency, but the construction has had enormous theoretical influence. The notion of semantic security (IND-CPA) introduced in the 1982 paper became the standard definition of security for public-key encryption; every modern scheme from RSA-OAEP to ECIES is proven secure under this definition.

The quadratic residuosity assumption is the basis for several zero-knowledge proof systems, including the Goldreich-Micali-Wigderson protocol for graph isomorphism and the Blum-Feldman-Micality non-interactive ZK proofs. The structure of Goldwasser-Micali encryption (commitment plus randomizer, both in Z_N^*) reappears in many later cryptographic primitives.

In secure multi-party computation, Goldwasser-Micali bit encryption is used as a building block for protocols that compute on encrypted bits. The GMW protocol (Gorbunov, Mohassel, Rosulek, and others) takes its name from this lineage. Bit-level encryption lets the protocol evaluate boolean gates with one round of communication per gate.

Academic e-voting schemes sometimes use Goldwasser-Micali for encrypted-ballot tally with the homomorphic XOR property: multiplying two GM ciphertexts gives an encryption of the XOR of the two bits. This is the dual of the additive homomorphism used by Benaloh and Paillier for sums of yes-votes.

Conclusion

Goldwasser-Micali is the textbook example of a semantically-secure public-key cryptosystem. Our Java program demonstrated bit-level encryption, the Legendre-symbol decryption, the probabilistic property, and string encryption by bit expansion. Next study the quadratic residuosity assumption in detail, the Benaloh and Naccache-Stern generalizations to multi-bit messages, and the modern IND-CPA definition of semantic security.