Decisional composite residuosity assumption

The decisional composite residuosity (DCR) assumption states that it is computationally hard to distinguish a random $n$-th power residue modulo $n^2$ from a uniformly random element of ${\mathbb{Z}}_{n^2}^{\ast }$, where $n=pq$ is an RSA modulus. Introduced by Paillier as the hardness basis for an additively homomorphic encryption scheme — Pai99.

Assumption

Let $n=pq$ for random $\lambda$-bit primes $p,q$. The DCR advantage of an adversary $\mathcal{A}$ is

$${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{dcr}}(\lambda ):=\left|2\mathrm{Pr}\left[\mathcal{A}(1^{\lambda },n,c_b)=b\right]-1\right|,$$

where $b\stackrel{\$}{\leftarrow }\{0,1\}$, $c_0:=r^n\mathrm{mod}{n}^2$ for $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_n^{\ast }$ (a uniformly random $n$-th power), and $c_1\stackrel{\$}{\leftarrow }{\mathbb{Z}}_{n^2}^{\ast }$.

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

Known Results

• DCR ⇒ Additively homomorphic encryption
• DCR ⇒ FAC; whether factoring hardness implies DCR hardness is open.
• DCR ⇒ PKE
• DCR ⇒ COM
• DCR ⇒ TPKE

Variations

$d$-th Composite Residuosity

Generalizes DCR to $n^d$-th powers modulo $n^{d+1}$ — DJ01. Gives homomorphism for messages modulo $n^d$.

Attacks

• DCR is broken if factoring $n$ is easy — knowing $p$ and $q$ determines the group structure
• Quantum attacks: Shor’s algorithm factors $n$ in polynomial time, breaking DCR — Shor97
• No sub-exponential classical attack on DCR independent of factoring is known

Participates in

Builds on Decisional composite residuosity assumption

• $d$-th Composite Residuosity ⇒ Additively homomorphic encryption (via $d$-th Composite Residuosity)
• DCR ⇒ COM
• DCR ⇒ FAC
• DCR ⇒ Additively homomorphic encryption
• DCR ⇒ PKE
• DCR ⇒ TDH
• DCR ⇒ TPKE