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. For a fixed $d\ge 1$ and $n$ as above, $d$-th composite residuosity is hard if for all efficient $\mathcal{A}$, $\left|2\mathrm{Pr}\left[\mathcal{A}(1^{\lambda },n,c_b)=b\right]-1\right|$ is negligible, where $b\stackrel{\$}{\leftarrow }\{0,1\}$, $c_0:=r^{n^d}\mathrm{mod}{n}^{d+1}$ for $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_n^{\ast }$ (a uniformly random $n^d$-th power), and $c_1\stackrel{\$}{\leftarrow }{\mathbb{Z}}_{n^{d+1}}^{\ast }$; the case $d=1$ is DCR. Gives homomorphism for messages modulo $n^d$.

DCR with safe-prime moduli

DCR for moduli $n=pq$ with $p=2p^{\prime }+1$ and $q=2q^{\prime }+1$ safe primes, where $p^{\prime },q^{\prime }$ are distinct uniform $\lambda$-bit primes subject to the primality of $2p^{\prime }+1$ and $2q^{\prime }+1$ — CS02. DCR is hard for safe-prime moduli if for all efficient $\mathcal{A}$ the DCR advantage above, with $n$ sampled this way, is negligible.

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 (safe-prime moduli) ⇒ CCA-secure PKE (Cramer–Shoup) (via DCR with safe-prime moduli)
• DCR ⇒ COM
• DCR ⇒ One-round sublinear cPIR
• DCR ⇔ $d$-th Composite Residuosity
• DCR ⇒ FAC
• DCR ⇒ Highly lossy TDF (Freeman–Goldreich–Kiltz–Rosen–Segev)
• DCR ⇒ Additively homomorphic encryption
• DCR ⇒ PKE
• DCR ⇒ TDH
• DCR ⇒ TPKE

Produces Decisional composite residuosity assumption

• DCR ⇔ $d$-th Composite Residuosity (via $d$-th Composite Residuosity)