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 ${\mathrm{QR}}_N=\{a\in {\mathbb{Z}}_N^{\ast }:\exists x,x^2\equiv a(\mathrm{mod}N)\}$ and ${\mathrm{J}}_N=\{a\in {\mathbb{Z}}_N^{\ast }:\left(\frac{a}{N}\right)=1\}\supseteq {\mathrm{QR}}_N$. When $p\equiv q\equiv 3(\mathrm{mod}4)$, the group ${\mathrm{J}}_N$ splits evenly: exactly half its elements are in ${\mathrm{QR}}_N$ and half are in ${\mathrm{J}}_N\setminus {\mathrm{QR}}_N$, so membership is information-theoretically hidden.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{qr}}_{\calA}(\secpar)$}
\begin{algorithmic}
\State $(p, q) \getsr$ distinct $\secpar$-bit primes with $p \equiv q \equiv 3 \pmod{4}$; $N \gets pq$
\State $b \getsr \{0,1\}$
\If{$b = 0$}
  \State $r \getsr \ZZ_N^*$; $a \gets r^2 \bmod N$
  \Comment{$a \in \QR_N$}
\Else
  \State $a \getsr \J_N \setminus \QR_N$
  \Comment{$a$ has Jacobi symbol 1 but is not a square}
\EndIf
\State $b' \gets \calA(1^\secpar, N, a)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

QR is hard if for all efficient $\mathcal{A}$,

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

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