# Are those two distributions indistinguishable?

The Decision composite residuosity problem problem states that is impossible to distinguish between those two ensembles: $\{x^N \mod {N^2} | x \in \mathbb{Z^*_{N{^2}}}\}$ and $\{r \in \mathbb{Z^*_{N{^2}}}\}$

Can we assume the same for these: $\{x-1+x^N \mod {N^2} | x \in \mathbb{Z^*_{N{^2}}}\}$ and $\{r \in \mathbb{Z^*_{N{^2}}}\}$

• Are you sure you've got the definition of the decisional quadratic residuosity problem right? Do you have a reference? I'm not familiar with this specific hardness assumption, but based on the name, I would have expected something called the "decisional quadratic residuosity problem" to be about $x^2 \bmod N^2$ vs $r \bmod N^2$.
– D.W.
Dec 19 '13 at 18:45
• I don't understand your comment. you are given 1 number. Either in the first form or in the other form and you have to decide whether or not there exist a quadratic residue for this number. Dec 19 '13 at 18:55
• It's Decision composite residuosity problem. And it's not about deciding if a square root exists, but if an $N$th root exists.
– K.G.
Dec 19 '13 at 19:03

I see no reason to expect $x-1+x^N \bmod N^2$ to be indistinguishable from $r$, at least not based upon the assumption you give. The map $f(x)= x^N \bmod N^2$ is a very different map from the map $g(x) = x-1+x^N \bmod N^2$. The range of $f$ is a subgroup of size $\varphi(N)$; that's not true of $g$ (for instance, the range of $g$ can potentially be the entire group of integers modulo $N^2$). The map $f$ is a $N$-regular map; I don't see any reason to expect $g$ to be $N$-regular in general, and maybe not even regular. As a third difference, $f(x+kN) = f(x)$, but $g(x+kN) = g(x)+kN$. For these reasons, I don't expect to find a simple reduction between these two indistinguishability statements.
• $f(x)$ is defined $mod N^2$ as well Dec 19 '13 at 19:09
• Thanks, @curious, that was a typo on my part. I certainly intended it to be mod $N^2$, but that did not make it from my brain to my fingers -- oops. Fixed. Thank you again.