DCR ⇔ $d$-th Composite Residuosity

Equivalence · fully-black-box reduction · standard model · DJ01 · security loss: the converse direction is tight: one distinguisher call, advantage preserved

Statement

For every fixed $d\ge 1$, $d$-th composite residuosity — a uniform $n^d$-th power modulo $n^{d+1}$ is indistinguishable from a uniform element of ${\mathbb{Z}}_{n^{d+1}}^{\ast }$ — is equivalent to DCR, its case $d=1$. DCR implies the degree-$d$ assumption — DJ01. Conversely, a DCR distinguisher breaks the degree-$d$ assumption with the same advantage — standard.

Sketch

For the converse, reduce the challenge modulo $n^2$. Reduction maps ${\mathbb{Z}}_{n^{d+1}}^{\ast }$ onto ${\mathbb{Z}}_{n^2}^{\ast }$ with fibres of equal size, so it sends a uniform unit to a uniform unit, and it sends $r^{n^d}$ to $w^{n^d}$ for $w$ uniform in ${\mathbb{Z}}_{n^2}^{\ast }$. The $n$-th powers modulo $n^2$ form a subgroup of order $\phi (n)$, which raising to $n^{d-1}$ permutes because $\gcd (n,\phi (n))=1$ for primes of equal length; hence $w^{n^d}=(w^n{)}^{n^{d-1}}$ is a uniform $n$-th power — standard.