About the Naccache-Stern cryptosystem, I have found two different encryption algorithms:

  • In the original paper from Naccache and Stern, the encryption step is performed by calculating $c = g^m \hspace{2mm} (mod \hspace{2mm} n)$, with $m$ being the plaintext, with $\sigma$ being optionally kept private. Then decryption is performed by applying some series of congruences mod n, which are easy to understand.
  • However, on Wikipedia (https://en.wikipedia.org/wiki/Naccache%E2%80%93Stern_cryptosystem), and many other sites, such as Crypto Wiki, the encryption step is performed differently: previously, an element $x \in \mathbb{Z}_{n}$ is randomly selected, and the plaintext $m$ is encrypted as $c = x^{\sigma}g^{m} \hspace{2mm} mod \hspace{2mm} n$, forcing $ \sigma$ to be part of the public key. Now, as for the explanation on why decryption works, they apply the following congruence: $$ c_{i} = c^{\phi(n)/p_{i}} \equiv x^{\sigma\phi(n)/p_{i}}g^{m\phi(n)/p_{i}} \hspace{2mm} mod \hspace{2mm} n \equiv g^{m\phi(n)/p_{i}} \hspace{2mm} mod \hspace{2mm} n $$ so basically, the same process as in the paper is applied, but with this different step, which I don't understand why is correct. Eventually, we get $c_{i}$ is an element of the cyclic subgroup generated by $g$.

So, my questions here are:

  • Is this congruence true? If so, why, if $x$ was randomly chosen?
  • Does this mean that $x$ is also an element of the cyclic subgroup generated by $g$?

1 Answer 1


Yes, the congruence is true it follows because $p_i$ divides $\sigma$ and so $\sigma\phi(n)/p_i\equiv 0\pmod{\phi(n)}$. The blinding value $x$ is chosen in order to provide ciphertext indistinguishability. By multiplying by a random $x^\sigma$, any given plaintext can encrypt in multiple ways. Showing that two ciphertext correspond to the same plaintext is equivalent to showing that their quotient mod $n$ is a $\sigma$th power (and hence solving the $\sigma$th power residuacity problem).

It is not necessary for $x$ to be in the same subgroup as that generated by $g$, in particular $x$ could be a non-residue for both $p$ and $q$ and still work as a blinding factor. This is important as it should be hard to distinguish elements of $\langle g\rangle$ from elements $-\langle g\rangle$ by quadratic residuacity whereas the sender can cheaply pick a blinding factors without this information.

  • $\begingroup$ Thank you so much for your answer! Just to see if I got it right, since $\sigma\phi(n)/p_{i} \equiv 0 \hspace{2mm} mod \hspace{1mm} \phi(n)$, then that power of $x$ is congruent to 1 modulo $n$? $\endgroup$
    – hectorvr14
    Commented Dec 19, 2023 at 15:49
  • 1
    $\begingroup$ @hectorvr14 that's right and it will be true for any $x$ coprime to $n$ rather than just the powers of $g$. $\endgroup$
    – Daniel S
    Commented Dec 19, 2023 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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