1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mikeazo Mar 23 '18 at 12:05
  • $\begingroup$ 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 $\endgroup$ – Adam Jones Mar 23 '18 at 12:18
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

When one needs homomorphic encryption, one shall not use RSA. There is no reason to use Paillier unless we need homomorphic encryption.

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.

By contrast, Paillier encryption is semantically secure and additively homomorphic. The price to pay is a larger cryptogram (twice the size of RSA at equivalent security), much more costly encryption than RSA, sizably more costly decryption.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.