# Paillier VS RSA

I was wondering if there are major pros or cons of choosing the Paillier algorithm over RSA except for Pailliers being additively homomorphic and RSA multiplicative?

• Do you need the homomorphic property of these? RSA is much more broadly available, so unless there is a good reason, I'd stick with it. Mar 23 '18 at 12:05
• For my university project i was told to design some system implementing Pailliers algorithm, was just curious if there were any major differences other than stated above Mar 23 '18 at 12:18

The Paillier cryptosystem has the built in property that a particular cleartext may have many different ciphertexts making it much more resillient "out-of-the-box" to a wide array of various cryptographic attacks. This is due to the injection of additional randomness into the encryption which is removable with the key due to the quadratic residuosity property. In implementation a similar effect may be achieved in RSA via padding or other schemes, but in Pallier, it exists in the foundation of the algorithm, the so-called "textbook" version, which is not the case for the RSA "textbook" version. Recall that the pailler encryption function is as follows for a message $m$, $r\in_R\mathbb{Z}_n$ and standard values $$Enc(m)=g^mr^n\mod n^2$$ Thus every message $m$ may have many equally valid ciphertexts depending on the magnitude of $n$ and the divisibility relationships between some of these values. Additionally, as mentioned for security, adding padding to the RSA algorithm to increase the security also destroys the multiplicative homomorphism. Here is a paper which addresses some of these details in greater depth.
RSA can be semantically secure or homomorphic, not both. Textbook RSA (where the ciphertext is simply $c=m^e\bmod N$) is multiplicatively homomorphic, but suffers from a major flaw: a guess of plaintext $m$ can be trivialy checked, which is often a disaster (think of a name on the class roll, or the price of an item). In practice, it is used RSA where $m$ is transformed before encryption with addition of randomness (e.g. RSAES-OAEP), which is secure, but looses the homomorphic property entirely.