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$, and let $g$ be a random element of ${\mathbb{Z}}_{n^2}^{\ast }$ of order $n\lambda (n)$ (where $\lambda$ is Carmichael’s function). 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,g,c)=1\right]-1\right|,$$

where $c$ is either a uniformly random $n$-th power (i.e., $c=r^n\mathrm{mod}{n}^2$ for $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_n^{\ast }$) or a uniformly random element of ${\mathbb{Z}}_{n^2}^{\ast }$, each with probability $1/2$.

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

Known Results

• DCR implies the Paillier cryptosystem, which achieves additive homomorphism: given $\mathsf{Enc}(m_1)$ and $\mathsf{Enc}(m_2)$, one can compute $\mathsf{Enc}(m_1+m_2\mathrm{mod}n)$ without decryption — Pai99
• DCR follows from factoring hardness — Pai99
• The converse is open: it is not known whether DCR implies factoring
• DCR → CPA-secure PKE with additive homomorphism — Pai99
• DCR → COM (statistically hiding, computationally binding) — standard
• DCR → threshold encryption (via Paillier with distributed key generation) — standard

Variations

$d$-th Composite Residuosity

Generalizes DCR to $d$-th powers modulo $n^{d+1}$. 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