Paillier and the Rise of Somewhat Homomorphic Encryption

Motivation:

In 1978, Rivest, Adleman and Dertouzos [1] introduced the idea of performing computations directly on encrypted data without using secret key. This concept is known as homomorphic encryption. However, their first proposal supported only one type of operation, either addition or multiplication, on encrypted data. Such schemes are called partially homomorphic encryption (PHE).

Later, in 1999, Paillier [2] improved this concept by designing an encryption scheme that allows both addition and multiplication on encrypted data, but only a limited number of times. This type of scheme is called somewhat homomorphic encryption (SHE).

Paillier Encryption:

Paillier encryption is a probabilistic asymmetric algorithm, which means it uses separate keys for encryption and decryption and also introduces randomness during encryption to ensure that the same message never encrypts to the same ciphertext. It supports important homomorphic properties that make it useful in privacy preserving applications.

The scheme works as follows.

1. Key Generation

• Choose two large prime numbers $p_1$and $p_2$.

• Compute $n = p_1 \cdot p_2$
  

• Compute $\lambda = \text{lcm}(p_1 - 1, p_2 - 1)$.

• Select a random generator $g \in \mathbb{Z}_{n^2}^*$.

• Compute $\mu = \left(L(g^{\lambda} \bmod n^2)\right)^{-1} \bmod n$, where $L(u) = \frac{u - 1}{n}$.

The public key is $(n, g)$ and the private key is $(\lambda, \mu)$

References: 

We thanks to..

[1] Ronald L Rivest, Len Adleman, Michael L Dertouzos. ON DATA BANKS AND PRIVACY HOMOMORPHISM. Foundations of Secure Computation, 4(11):169–180, 1978.

[2] Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In International conference on the theory and applications of cryptographic techniques, pages 223–238, 1999.