In the key generation of the threshold version of RSA or the threshold version of the Paillier cryptosystem (e.g. "Shoup - 2000 - Practical threshold signatures" or "Fouque et al. - 2000 - Sharing decryption in the context of voting or lotteries") a square $v$ in $\mathbb{Z}_N^*$ ($\mathbb{Z}_{N^2}^*$ respectively) is used for the verification of the private key shares. For a private key share $s_i$ the public verification key $v_i$ is then $v_i = v^{s_i}$, where $v$ is an element of the cyclic subgroup of squares in $\mathbb{Z}_N^*$.

My question is, why does $v$ has to be a square?


This is to ensure $v$ is in the cyclic sub-group $G$ of $Z_N^*$ that has a large enough order $m=p'\cdot q'$. Moreover, with a large probability $v$ is a generator of $G$, so that $v_i=v^{s_i}$ is a one-to-one mapping from $s_i$ to $v_i$, which is important when proving correctness of the shares.

  • $\begingroup$ So if I understand correctly, we choose $v$ to be a square in order to have with high probability a generator of a large cyclic group. As there exists no generator for $\mathbb{Z}_N^*$, the group $G$ with $p'q'$ elements is large enough (only about 2 bits smaller than $pq$). I was wondering if it is also important that if $v$ is a square, then the Jacobi Symbol of $v_i$ will be always 1, and thus the last bit of $s_i$ is not leaked (whether $s_i$ is even or odd). $\endgroup$ – ZoDiaC Jul 8 '18 at 7:58
  • $\begingroup$ yes, that is also true. $\endgroup$ – Changyu Dong Jul 8 '18 at 9:58

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.