The definition of Paillier Cryptosystem says that it is a probabilistic asymmetric key algorithm for public key cryptography. Can some body explain why it is called "probabilistic"?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
As user curious said in a other answer probabilistic means that the encryption of the same plaintext under the same key gives as output a different ciphertext.
This is a more general property and it is known as a basic security property: it is usually refered to as semantically secure or indistinguishability (roughly: an attacker cannot guess which one of two plaintext he provided has been encrypted). It was firstly defined and introduced by Goldwasser and Micali in their seminal paper "Probabilistic Encryption" on 1984. This property is usually achieved introducing a random token into the encryption algorithm. A very simple way to transform any deterministic encryption algorithm into a probabilistic one is to pad the plaintext with a random string before to encrypt it and do unpad it after the decryption. Under symmetric encryption it can be easily achieved using a random IV (or counter) for a secure block operation mode (as CBC or CTR).
More precisely about Pallier cryptoscheme, the encryption algorithm uses a random $r$ element per encryption.
Encryption
- Let $m$ be a message to be encrypted where $m\in \mathbb Z_{n}$;
- Select random $r$ where $r\in \mathbb Z^{*}_{n}$;
- Compute ciphertext as: $c=g^m \cdot r^n \bmod n^2 $.
answered Dec 21, 2015 at 9:03
$\begingroup$
$\endgroup$
Because each time you encrypt a message $m$, its ciphertext changes and is not the same (each time you encrypt you pickup a random element $z \leftarrow \mathbb{Z}_n^*$). If for each message there was the same ciphertext then the encryption scheme would be deterministic and would not be semantically secure or would not provide indistinguishability.
