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?
$\begingroup$
$\endgroup$
2
-
$\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$– mikeazoMar 23, 2018 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 JonesMar 23, 2018 at 12:18
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Mar 23, 2018 at 18:13