# What if the p and q used in keys generation of Pailler cryptosystem are composite?

I've seen a few implementations of Paillier cryptosystem that uses probable primes to choose $p$ and $q$.

Assuming that a keypair is generated with $p$ and $q$ that are coprime and that $pq$ is coprime with $(p - 1)(q - 1)$, but either $p$ or $q$ is composite, I'm wondering what security issues afflict such a key.

For example I wonder if, when $p$ is prime but $q$ is composite (so that $q = xy$ with $x$ and $y$ primes), there exists multiple public keys that can encrypt/decrypt a message.

Moreover, I'm wondering how it impacts $g$ and $r$ selection, and if the encryption function is still additively homomorphic. For example, with proper primes, one can use $r$ calculation to prove the sender of an encrypted message his control over the private key without sending the encrypted value over the channel. But is this still true for any $r$ if $p$ or $q$ are not truly primes?

Finally, which kind of cryptographic attacks are excluded by proper prime selection?

• – cygnusv Jul 15 '15 at 11:59

For starters: Paillier and RSA are based on very similar assumptions, and both systems would be broken immediately by an algorithm to factor large composites. Additionally, knowing $\phi(n)$ or $\lambda(n)$ is quite essential to both systems, because the trapdoor for decryption is based on that.

As you can see, the relation to RSA is quite close, and thus the following topics on this site are very relevant:

Now let's translate that to Paillier:

First off, in most cases if you use $q-1$ and $q$ is not prime, then the entire encryption/decryption will not work, because actually $\lambda(q)\neq p-1$ (with the Carmichael function $\lambda$). This means, that $D(E(x)) = x$ with the encryption $E$ and decryption $D$ is a primality test itself for both primes $p$ and $q$.

But let's assume, that you happen to find numbers $p$ and $q$ with $n = pq=abc$, where $a,b,c> 1$. In the key generation process you calculate $\lambda = lcm(p-1, q-1)$, which is just the Carmichael function for a proper $n=pq$. In order for the normal encryption/decryption to work, the following would have to hold: $lcm(p-1,q-1) = k \cdot lcm(\lambda(a),\lambda(b),\lambda(c))$ for some $k$, where actually $\lambda(n)=lcm(\lambda(a),\lambda(b),\lambda(c))$ is the real order of the multiplicative group (for any odd prime number $x: \lambda(x) = x-1$).

Now I suggest a closer look at Paillier's original paper, e.g. in section 3 the proof that $E_g(x,y)=g^xy^n \mod n^2$ is a bijection if the order of $g$ is a multiple of $n$. This still holds, even if $n$ has actually more than two prime factors. Similarly, $S_n = \{u < n^2 | u = 1 \mod n\}$ is still a multiplicative subgroup regardless of the prime factors of $n$ and the function $L(u)$ is still well-defined.

Now, let's estimate what the "too large order" effects. Basically, this is similar to RSA, where you can calculate $d$ modulo $\phi(n)$ or modulo $\lambda(n)$: If you use the bigger group where the order is actually less, you get a different $d$ but it works just the same. This is the same in Paillier: $\lambda$ might be a larger number, but it will work regardless (assuming the previously stated assumption is met)

Considering your other questions: The choice of $g$ is not affected by a wrong $\lambda$, especially if using the simplified version with $g=n+1$. The role of $r$ is this: In the decryption you first exponentiate it by $\lambda$, and $r^{n\lambda} = 1$ for any $r$. This is also true, if we our $\lambda$ is a multiple of the real multiplicative group order. A possible problem could arise if $r$ is a zero divisor, but even with multiple large prime factors in $n$ this is negligible. (not sure about this one right now)

About the homomorphic property: Assuming the encryption/decryption still works, this property also still holds. There is no reason why it shouldn't.

And finally about the attacks: Well, this is the same as for RSA, where we still don't know any more efficient attack than just factoring the modulus. And what we know from RSA: With a bigger number of prime factors, some algorithms become faster, e.g. when they scale with the size of the smallest prime factor. Some algorithms scale with the length of the modulus. For some more information about that, I suggest reading the answers to the previously mentioned crypto-SE questions.

As a final note: Just because large prime numbers have a negligible chance of being composite, this doesn't mean you actually have to consider this as a possible weakness: There are plenty of methods of proving or disproving primality and you can get to arbitrary confidence levels (e.g. $1 - 2^{-80}$ is quite common), and they are sufficiently fast. Prime generation itself can be done with a negligible rate of error. And if you think of the Fermat test and Carmichael numbers right now: There are other methods without such curiosities.