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 ⇒ HE
• FAC ⇒ DCR
• The converse is open: it is not known whether DCR implies factoring
• DCR ⇒ PKE
• DCR ⇒ COM
• DCR ⇒ HE
• DKG + HE ⇒ TPKE

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

Participates in

Builds on Decisional composite residuosity assumption

• DCR + Sparse Learning Parity with Noise ⇒ Somewhat homomorphic encryption (SHE)
• DCR ⇒ COM
• DCR ⇒ HE
• DCR ⇒ Partially homomorphic encryption (PHE)
• DCR ⇒ PKE

Produces Decisional composite residuosity assumption

• FAC ⇒ DCR