I sometimes read in papers that a (sub-)group generator $g$ is taken from $\mathrm{QR}(n)$ instead of $\mathbb{Z}^*_n$, where $n = p \cdot q$ and $p$ and $q$ are prime. Is there a reason for this? What properties does $\mathrm{QR}(n)$ have? Is it an especially big subgroup?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
Well, the reason that a specific cryptographical object needs to work in a specific subgroup probably has to do with the details of that object, and the cryptographical properties it needs from the subgroup.
One obvious possibility is that they need to avoid leaking information via the Jacobi symbol; that is an easily computed function that maps values in $Z^*_n$ into the values in the set $\{1, 0, -1\}$; it is interesting because the RSA operation preserves it; $Jacobi(x) = Jacobi(RSA(x))$ (where $RSA$ is either the public or the private operation, and $Jacobi$ implicitly relies on $n$).
Depending on what you're doing, this property may allow people to track which inputs refer to which outputs (for example, if you're shuffling values by encrypting them, and then randomly permuting them). One way of making sure this sort of thing doesn't lead to a problem is to specify that all input values are in $QR(n)$; all these values have Jacobi symbol 1, and so there's no leakage.
It's also easy to create random values in $QR(n)$; pick a random number $r$ relatively prime to n, and compute $r^2 \bmod n$; that's a random value in $QR(n)$
As for the size of $QR(n)$, well, that'd be $(p-1)(q-1)/4 \approx N/4$; obviously, that's a fairly sizable group.
