Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
thanks a lot, this helps... –  user4811 Jan 21 '13 at 19:33
add comment

Your Answer

 
discard

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.