Quadratic residuosity assumption

The quadratic residuosity (QR) assumption states that it is computationally hard to decide whether a given integer $a$ with Jacobi symbol $\left(\frac{a}{N}\right)=1$ is a quadratic residue modulo $N=pq$. The Jacobi symbol restriction ensures that quadratic residuosity is information-theoretically hidden; the QR assumption makes this computationally hard. It underlies the first provably CPA-secure public-key encryption scheme — GM84.

Assumption

Let $N=pq$ for random $\lambda$-bit primes $p\equiv q\equiv 3(\mathrm{mod}4)$ (or general primes). Let ${\text{QR}}_N=\{a\in {\mathbb{Z}}_N^{\ast }:\exists x,x^2\equiv a(\mathrm{mod}N)\}$ and ${\text{J}}_N=\{a\in {\mathbb{Z}}_N^{\ast }:\left(\frac{a}{N}\right)=1\}\supseteq {\text{QR}}_N$. The QR advantage of $\mathcal{A}$ is

$${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{qr}}(\lambda ):=\left|2\mathrm{Pr}\left[\mathcal{A}(1^{\lambda },N,a)=1\right]-1\right|,$$

where $a$ is uniformly random in ${\text{QR}}_N$ (with probability 1/2) or uniformly random in ${\text{J}}_N\setminus {\text{QR}}_N$ (with probability 1/2).

QR is hard if for all efficient $\mathcal{A}$, ${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{qr}}(\lambda )$ is negligible.

Known Results

• QR → CPA-secure PKE: Goldwasser-Micali encryption (the first IND-CPA PKE scheme) encrypts one bit at a time — GM84
• Goldwasser-Micali is multiplicatively homomorphic: $\mathsf{Enc}(b_1)\cdot \mathsf{Enc}(b_2)=\mathsf{Enc}(b_1\oplus b_2\mathrm{mod}2)$ — GM84
• QR follows from factoring hardness: knowing $p$ and $q$ allows computing the Legendre symbols $\left(\frac{a}{p}\right)$ and $\left(\frac{a}{q}\right)$ — GM84
• QR → statistically hiding commitment scheme — standard
• The original ZK proof of GMR85 was for quadratic residuosity — GMR85

Variations

Quadratic residuosity over ${\mathbb{Z}}_p$ (prime field)

For a prime $p$, deciding quadratic residuosity modulo $p$ is easy (via the Legendre symbol). The hardness only arises for composite moduli.

Higher residuosity

Generalizes QR to $d$-th power residuosity modulo $N$. Underlies Goldwasser-Micali generalizations and the Benaloh cryptosystem.

Attacks

• QR is broken if factoring $N$ is easy: knowing $p,q$ determines all Legendre symbols
• Quantum attacks: Shor’s algorithm factors $N$ and breaks QR — Shor97