# Verification in Threshold RSA or Threshold Paillier

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.
• 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). – ZoDiaC Jul 8 '18 at 7:58