Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}}}\}$

share|improve this question
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. – curious 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
up vote 3 down vote accepted

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.

share|improve this answer
$f(x)$ is defined $mod N^2$ as well – curious 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. – D.W. Dec 19 '13 at 19:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.