Partially Homomorphic Encryption (PHE)

PHE schemes are cryptographically restricted to evaluating either addition or multiplication on ciphertexts, but not both. This fundamental limitation distinguishes them from Fully Homomorphic Encryption (FHE).

• Additive PHE (e.g., Paillier): Allows Enc(a) + Enc(b) = Enc(a+b).
• Multiplicative PHE (e.g., ElGamal): Allows Enc(a) * Enc(b) = Enc(a*b).
• Attempting the unsupported operation results in a non-decryptable ciphertext or a random value.

Unlike Somewhat Homomorphic Encryption (SWHE), PHE schemes do not suffer from a strict noise budget that limits the number of sequential operations. You can perform an arbitrary number of the supported operation without corrupting the ciphertext.

• An additive PHE scheme can sum millions of encrypted values without decryption failure.
• This property is critical for encrypted aggregation in federated learning and secure voting.

Because PHE avoids the costly noise management techniques required by FHE—such as bootstrapping and relinearization—it is orders of magnitude faster. Ciphertext sizes are also significantly smaller.

• Paillier addition is a modular multiplication, making it practical for real-time systems.
• ElGamal multiplication is a group exponentiation, far lighter than lattice-based FHE operations.
• This efficiency makes PHE deployable on standard hardware without specialized accelerators.

Most PHE schemes rely on well-understood, hard mathematical problems that predate the lattice-based cryptography dominating modern FHE. This provides a long track record of cryptanalysis.

• Paillier is based on the Decisional Composite Residuosity Assumption (DCRA).
• ElGamal is based on the Decisional Diffie-Hellman (DDH) assumption.
• RSA (multiplicative PHE) is based on the integer factorization problem.
• These schemes are not inherently post-quantum secure, unlike lattice-based FHE.

The primary real-world application of additive PHE is securely computing the sum of encrypted values without revealing individual contributions. This is the backbone of privacy-preserving analytics.

• Federated Learning: A server aggregates encrypted model updates from clients using Secure Aggregation protocols built on Paillier.
• Private Billing: Smart meters can sum encrypted consumption data without exposing granular usage patterns.
• E-Voting: Ballots are encrypted additively to tally results while preserving voter anonymity.

Standard PHE schemes provide Indistinguishability under Chosen-Plaintext Attack (IND-CPA). This guarantees that an adversary cannot distinguish between the encryptions of two different messages, even if they can choose the plaintexts.

• This is achieved through probabilistic encryption, where the same plaintext encrypts to different ciphertexts each time.
• Paillier uses a random nonce r during encryption: c = g^m * r^n mod n^2.
• IND-CPA ensures that ciphertexts reveal zero information about the underlying data.