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

  • $\begingroup$ 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$. $\endgroup$ – D.W. Dec 19 '13 at 18:45
  • $\begingroup$ 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. $\endgroup$ – curious Dec 19 '13 at 18:55
  • 3
    $\begingroup$ It's Decision composite residuosity problem. And it's not about deciding if a square root exists, but if an $N$th root exists. $\endgroup$ – 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.

  • $\begingroup$ $f(x)$ is defined $mod N^2$ as well $\endgroup$ – curious Dec 19 '13 at 19:09
  • $\begingroup$ 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. $\endgroup$ – D.W. Dec 19 '13 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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