Engineering / Mathematics — Quadratic Residues
The Quadratic Residuosity Assumption
The quadratic residuosity assumption, its use in probabilistic encryption, and its relationship to factoring.
Executive summary
The quadratic residuosity assumption states that residues and pseudo-residues with Jacobi symbol plus one cannot be distinguished efficiently without the factorisation.
It supports Goldwasser-Micali encryption, the first scheme to achieve semantic security, at the cost of extreme ciphertext expansion.
Learning objectives
- State the assumption precisely.
- Describe Goldwasser-Micali encryption.
- Situate the assumption relative to factoring.
01The assumption
Quadratic residuosity assumption
Let n = pq with distinct odd primes and let J₁ be the set of units with Jacobi symbol +1. No efficient algorithm, given only n, distinguishes a random quadratic residue from a random element of J₁ that is not a residue, with advantage better than negligible.
The set J₁ splits exactly in half between the two classes, so guessing achieves advantage zero and the assumption says nothing does better.
| Set | Size relative to Z_n* | Efficiently recognisable? |
|---|---|---|
| Jacobi symbol −1 | 1/2 | Yes — compute the symbol |
| Quadratic residues | 1/4 | Believed not, without the factorisation |
| Pseudo-residues in J₁ | 1/4 | Believed not, without the factorisation |
02Goldwasser-Micali encryption
Key generation
Choose n = pq and a fixed pseudo-residue y with Jacobi symbol +1. Publish (n, y); keep p and q.
Encrypt a zero bit
Send r² mod n for random r — a genuine quadratic residue.
Encrypt a one bit
Send y · r² mod n — a pseudo-residue, since y is one.
Decrypt
Using p and q, test residuosity by Legendre symbols. Residue means 0, non-residue means 1.
The scheme encrypts a single bit per ciphertext, and each ciphertext is a full-size group element. For a 2048-bit modulus that is a 2048-fold expansion, which is why the scheme is of theoretical rather than practical importance.
03Relationship to factoring and other properties
- Factoring
HardestSolving it breaks the residuosity assumption - Quadratic residuosity
No harder than factoringNot known to be equivalent - Jacobi symbol
EasyPolynomial time, no factorisation needed
The assumption is formally weaker than the factoring assumption, since a factoring algorithm decides residuosity but no reduction is known in the other direction. In practice the best attack is to factor.
Homomorphic structure
Multiplying two ciphertexts XORs the underlying bits, making the scheme additively homomorphic over one bit — a property later schemes generalised.
Semantic security
Randomised encryption means identical plaintexts give different ciphertexts, defeating the dictionary attacks that deterministic schemes permit.
Descendants
Paillier and other schemes retained the homomorphic property with far better expansion, and the lineage runs to modern homomorphic encryption.
04Frequently asked questions
Why must y be a pseudo-residue rather than any non-residue?
Because a non-residue with Jacobi symbol −1 would make ciphertexts for one-bits publicly distinguishable — anyone could compute the symbol. The whole scheme rests on both classes sharing the same computable symbol.
Is the ciphertext expansion improvable?
Not within this scheme, which is inherently bit-by-bit. Paillier and related constructions achieve constant expansion while keeping a homomorphic property, and are what practical applications use.
Does the homomorphic property weaken security?
It rules out non-malleability, since ciphertexts can be combined meaningfully. That is a deliberate trade — the property is useful for computing on encrypted data, and applications requiring non-malleability need a different scheme.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 297-298.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.