# About Naccache-Stern higher residue cryptosystem definition

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$$?

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.
• 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$? Commented Dec 19, 2023 at 15:49
• @hectorvr14 that's right and it will be true for any $x$ coprime to $n$ rather than just the powers of $g$. Commented Dec 19, 2023 at 15:52