Decryption of Naccache–Stern cryptosystem is not guaranteed for large keys

Question

Naccache-Stern cryptosystem is mainly based on Chinese Remainder Theorem. According to its wiki page and Partially Homomorphic encryption book, I generated following keys.

1- Picked a family of k small distinct primes. I set k to 6 and primes are

pi = {3, 5, 7, 11, 13, 17}

2- Divide the set in half and find the multiplication of primes as

u = 3x5x7 = 105
v = 11x13x17 = 2431

3- Find sigma as multiplication of u and v

σ = u x v = 105 x 2431 = 255255

4- Choose large primes a and b such that both p = 2au+1 and q=2bv+1 are prime as well

a = 19903238899171
b = 5031940459031

p = 2au + 1 = 2x19903238899171x105+1 = 4179680168825911
q = 2bv + 1 = 2x5031940459031x2431+1 = 24465294511808723

5- Set n to p x q

n = pq = 4179680168825911 x 24465294511808723 = 102257106295492317188047918221653
ϕ(n) = (p-1)(q-1) = 102257106295492288543073237587020

6- Generate a generator g that satisfies g^(ϕ(n)/pi) != 1.

g=28805426433623101967928508095048

7- My plaintext is 17. I will encrypt this as

c = g^m mod n = 28805426433623101967928508095048 ^ 17 mod 102257106295492317188047918221653 
c = 56869948461238576264190303866429

8- Decryption requires following steps

ci = c ^(ϕ(n) / pi) mod n
ci = 56869948461238576264190303866429 ^ (102257106295492288543073237587020 / 3) mod 102257106295492317188047918221653
ci = 55506363668208546317381600107672

Then we need to solve DLP from

ci == g^(j x ϕ(n) / pi) mod n for j = 1 to pi

However, there is no j satisfying the following equation.

55506363668208546317381600107672 == 28805426433623101967928508095048^(j*102257106295492288543073237587020/3) mod 102257106295492317188047918221653

I also added the guaranteeing decryption step in Benaloh which is not mentioned in wiki or book. This resolves decryption issues for small keys (35 bit for a and b) but it becomes problematic for larger keys.

Am I skipping some important steps in key generation or this cryptosystem does not guarantee decryption always? If decryption is not guaranteed, then is there a way to check out decryption is guaranteed while generating keys?

Answer 1

The question's $g$ is not suitable. Try e.g. $g=30359963453720570073793540267704$.

I read the question's condition 6 as: $\forall p_i\in\mathcal S,\quad g^{\varphi(n)/i}\bmod n\ne1$, with $\mathcal S$ the set $\{3,5,7,11,13,17\}$. This condition is met, and necessary, but it's not sufficient.

That's because in the Naccache–Stern cryptosystem, the order of $g$ modulo $n$ must be $\varphi(n)/4$ per the key generation procedure of the wiki reference.

Thus we also need $g^{(p-1)(q-1)/4}\bmod n=1$, and that's what's missing. As an aside, we also want to include $a$ and $b$ in the set $\mathcal S$, since they also are odd divisors of $\varphi(n)$; however that addition is unlikely to change the outcome.

---

In order to minimize trial and error in generating $g$, we can generate $g_p\in[1,p)$ of order $(p-1)/2$ modulo $p$ separately from $g_q\in[1,q)$ of order $(q-1)/2$ modulo $q$, and then compute $g$ per the Chinese Remainder Theorem as $g=\bigl((g_p-g_q)(q^{-1}\bmod p)\bmod p\bigr)\,q+g_q$.

To generate $g_p$, we can pick a random $h_p\in[1,p)$, compute $g_p=h_p^{\,2}\bmod p$, until $g_p^{\,(p-1)/i}\bmod p\ne1$ for each odd $i$ dividing $p-1$ (there are four $i$ in the question: $3$, $5$, $7$, $19903238899171$). Generation of $g_q$ is similar.

---

Another issue is that the question makes encryption per $c=g^m\bmod n$ rather than $c=x^\sigma\,g^m\bmod n$ for random $x$ as it's supposed to do. That compromises security (in particular by allowing to test a guess of $m$).