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

64 Views Asked by At

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?

I've found a very nice mathematical introduction to the Paillier cryptosystem, but it assumes that $p$ and $q$ are primes from the very beginning.

NOTE: this is a cross-post from Crypto.SE, but since I've received no answer, I've been said to try here. In a somewhat related question, it is said (for RSA) that

If we accidentally try to perform RSA with one of p or q composite (because an error crept in the implementation of the primality test), the usual formulas φ(p⋅q)=(p−1)⋅(q−1) or λ(p⋅q)=lcm(p−1,q−1) will lead to incorrect value, and with overwhelming odds, decryption or signature verification will fail on the first real use (assuming non-malicious choice of p and q, and a random message or proper padding is used).

But what I'm wondering is actually how a malicious choice of $p$, $q$ (and $r$) could enable an attacker to obtain the same encryption for different messages.