The Paillier Cryptosystem: A Homomorphic Encryption Scheme

The Paillier cryptosystem, introduced by Pascal Paillier in 1999, is a probabilistic asymmetric encryption scheme notable for its additive homomorphic properties. Unlike traditional public-key systems, Paillier allows computations to be performed directly on encrypted data, such that the decrypted result corresponds to the sum of the original plaintext values. This property enables secure data processing without exposing sensitive information, making it particularly relevant in contexts such as privacy-preserving data analysis and secure multiparty computation.

The Paillier cryptosystem has been applied in multiple domains requiring privacy-preserving computation. For example, in secure electronic voting, individual votes can be encrypted and aggregated without revealing individual choices. In cloud-based medical analytics, hospitals can perform statistical analysis on encrypted patient records, computing totals or averages while maintaining patient confidentiality. Additionally, the scheme is relevant for financial computations, where sensitive transaction data can be processed without exposing underlying balances or identities.

Paillier Cryptosystem

The Paillier cryptosystem is an asymmetric encryption scheme notable for its additive homomorphic property, which allows computations on encrypted data without ever revealing the plaintext. This property enables privacy-preserving aggregation of sensitive data, a key principle in privacy-enhancing technologies (PETs).

1. Key Generation

1. Select two large prime numbers $p$ and $q$.
2. Compute $n = p \cdot q$and $\lambda = \text{lcm}(p-1, q-1)$.
3. Choose a generator $g$g such that $g \in \mathbb{Z}_{n^2}^*$​.
4. Compute $\mu = (L(g^\lambda \mod n^2))^{-1} \mod n$, where $L(u) = (u-1)/n$.
5. The public key is $(n, g)$ and the private key is $(\lambda, \mu)$.

2. Encryption

To encrypt a message $m \in \mathbb{Z}_n$:

1. Pick a random number $r \in \mathbb{Z}_n^*$​.
2. Compute ciphertext:

$$c = g^m \cdot r^n \mod n^2$$

3. Decryption

To decrypt $c$:$$m = L(c^\lambda \mod n^2) \cdot \mu \mod n$$

Despite its advantages, the Paillier cryptosystem has limitations, including relatively high computational overhead and ciphertext expansion, which may affect performance in large-scale applications. Nevertheless, its unique combination of additive homomorphism and semantic security continues to make it a foundational tool in the field of privacy-enhancing technologies (PETs) and secure data processing.

4. Homomorphic Computation

The additive homomorphism means you can sum encrypted values without decrypting:$$E(m_1) \cdot E(m_2) \mod n^2 = E(m_1 + m_2)$$So, for example, encrypted salaries or votes can be summed in a database without ever exposing individual records.

Do you want to try Paillier cryptosystem ?

Python Example

# Install library: pip install phe
from phe import paillier

# Key generation
public_key, private_key = paillier.generate_paillier_keypair()

# Example plaintext messages
m1 = 10
m2 = 25

# Encryption
c1 = public_key.encrypt(m1)
c2 = public_key.encrypt(m2)

# Homomorphic addition
c_sum = c1 + c2  # still encrypted

# Decryption
sum_result = private_key.decrypt(c_sum)

print("Encrypted values added homomorphically and decrypted result:", sum_result)
# Output: 35