The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.
The scheme is an additive homomorphic cryptosystem; this means that, given only the public key and the encryption of
The scheme works as follows: If using p,q of equivalent length, a simpler variant of the above key generation steps would be to set
[1] The simpler variant is recommended for implementational purposes, because in the general form the calculation time of
A notable feature of the Paillier cryptosystem is its homomorphic properties along with its non-deterministic encryption (see Electronic voting in Applications for usage).
Paillier cryptosystem exploits the fact that certain discrete logarithms can be computed easily.
For example, by binomial theorem, This indicates that: Therefore, if: then Thus: The original cryptosystem as shown above does provide semantic security against chosen-plaintext attacks (IND-CPA).
The so-called decisional composite residuosity assumption (DCRA) is believed to be intractable.
Because of the aforementioned homomorphic properties however, the system is malleable, and therefore does not enjoy the highest level of semantic security, protection against adaptive chosen-ciphertext attacks (IND-CCA2).
Usually in cryptography the notion of malleability is not seen as an "advantage," but under certain applications such as secure electronic voting and threshold cryptosystems, this property may indeed be necessary.
Imagine paying for an item online without the vendor needing to know your credit card number, and hence your identity.
The Paillier cryptosystem plays a crucial role in enhancing the security of electronic auctions.
By ensuring the confidentiality of actual bidding values while revealing auction results, the Pailler cryptosystem successfully promotes fair practices.
[3] The homomorphic property of Paillier cryptosystem is sometimes used to build Threshold ECDSA signature.