Partially Homomorphic Encryption (PHE)

A PHE scheme supports computation of either addition or multiplication on ciphertexts, but not both. This fundamental limitation distinguishes it from Fully Homomorphic Encryption (FHE).

• Additive PHE: Schemes like Paillier or Benaloh allow adding encrypted numbers, where Enc(a) + Enc(b) = Enc(a + b).
• Multiplicative PHE: Schemes like RSA or ElGamal allow multiplying encrypted numbers, where Enc(a) * Enc(b) = Enc(a * b).

By supporting only one homomorphic operation, PHE schemes are orders of magnitude faster and require far less computational overhead than FHE. This makes them practical for real-world applications today.

• Low Latency: Operations on ciphertexts can be performed in milliseconds, suitable for live systems.
• Minimal Ciphertext Expansion: The encrypted data (ciphertext) is typically only 2-10x larger than the original plaintext, compared to potentially 1000x+ for FHE.

PHE schemes are built on well-established cryptographic hardness assumptions, providing semantic security (IND-CPA). This means an attacker cannot learn any information about the plaintext from the ciphertext.

• Foundational Assumptions: Security relies on problems like the Decisional Composite Residuosity Assumption (Paillier) or the Decisional Diffie-Hellman assumption (ElGamal).
• Malleability: While the ciphertext can be transformed (homomorphically), this does not compromise the underlying secret data.

PHE's efficiency enables specific, high-value privacy-preserving applications without the prohibitive cost of FHE.

• Private Voting & Auctions: Additive PHE allows tallying encrypted votes or bids without revealing individual submissions.
• Private Data Aggregation: Cloud services can compute sums or averages (e.g., for salary or sensor data) on encrypted client data.
• Blockchain Privacy: Used in protocols for private balances and transactions, enabling verification without exposing amounts.

The "partial" nature of PHE imposes clear functional boundaries that developers must design around.

• No Arbitrary Computation: Cannot evaluate circuits requiring both addition and multiplication gates.
• Limited Program Expressiveness: Complex functions like machine learning inference or SQL queries with mixed operations are not possible.
• Bootstrapping Not Required: Unlike FHE, PHE does not need a complex "bootstrapping" procedure to manage noise, which is a key reason for its efficiency.

Several standardized PHE cryptosystems are widely used and studied for their specific homomorphic properties.

• Paillier Cryptosystem: The canonical additively homomorphic scheme, often used for e-voting and private aggregation.
• ElGamal Encryption: A multiplicatively homomorphic scheme foundational in many cryptographic protocols.
• RSA Cryptosystem: Exhibits multiplicative homomorphism under certain conditions, though this is not its primary design goal.

The RSA cryptosystem is multiplicatively homomorphic. Given two ciphertexts, Enc(m1) and Enc(m2), their product Enc(m1) * Enc(m2) decrypts to the product of the original messages m1 * m2. This property is a direct consequence of RSA's structure: (m1^e mod n) * (m2^e mod n) = (m1*m2)^e mod n.

• Key Use Case: Enabling secure electronic voting where encrypted votes can be multiplied to calculate a tally without revealing individual votes.
• Limitation: Only supports multiplication; cannot perform addition on ciphertexts.

The Paillier cryptosystem is additively homomorphic. It allows the addition of plaintexts through the multiplication of ciphertexts: Enc(m1) * Enc(m2) = Enc(m1 + m2). It also supports multiplication by a known constant k: Enc(m)^k = Enc(k * m).

• Key Use Cases: Privacy-preserving analytics (e.g., summing encrypted salaries), secure federated learning for model aggregation, and private set intersection protocols.
• Feature: Provides semantic security (probabilistic encryption) and is widely used in modern cryptographic protocols.

The ElGamal encryption scheme, based on the hardness of the Discrete Logarithm Problem, is multiplicatively homomorphic in its standard form. The product of two ciphertexts (c1, c2) and (c1', c2') decrypts to the product of their corresponding plaintexts.

• Mechanism: Homomorphism arises from the multiplicative property of the underlying group (e.g., a cyclic subgroup of a finite field or an elliptic curve group).
• Key Use Case: Foundational for more advanced protocols like homomorphic mix-nets and threshold cryptosystems.
• Note: An additive variant exists when implemented over elliptic curve groups with specific pairings.

The Goldwasser-Micali (GM) cryptosystem was the first probabilistic public-key system proven semantically secure. It is homomorphic with respect to the XOR operation (addition modulo 2).

• Mechanism: Encrypts a single bit (0 or 1). The product of two ciphertexts decrypts to the XOR of the two original bits.
• Foundation: Its security is based on the quadratic residuosity problem.
• Historical Significance: Pioneered the concepts of semantic security and probabilistic encryption, though it is less efficient for bulk data than later schemes like Paillier.

A critical distinction exists between the homomorphic properties of textbook RSA and secure, padded RSA used in practice.

• Textbook RSA: The basic c = m^e mod n formulation is deterministic and multiplicatively homomorphic, as described. This is insecure for direct use.
• Padded RSA (e.g., OAEP): Standards like Optimal Asymmetric Encryption Padding (OAEP) add randomness and redundancy to plaintexts before encryption. This breaks the homomorphic property entirely to achieve security against adaptive chosen-ciphertext attacks (IND-CCA2).

Conclusion: The homomorphic property is typically a side effect of an algebraic structure that must be deliberately removed for standard secure encryption.

PHE schemes are limited to one type of operation, which defines their application scope and differentiates them from Fully Homomorphic Encryption (FHE).

• Fixed Functionality: A Paillier system cannot multiply ciphertexts; an RSA system cannot add them. Complex computations requiring both operations are impossible.
• Efficiency Advantage: PHE schemes are orders of magnitude faster and more practical than current FHE implementations for their supported operations.
• Practical Trade-off: PHE is used when the computation is known and simple (e.g., sums, products, votes). FHE is required for arbitrary computations (e.g., evaluating encrypted circuits, running general programs).

A core limitation of PHE is that each scheme supports only one type of operation—either addition (e.g., Paillier) or multiplication (e.g., RSA, ElGamal)—on ciphertexts. This restricts complex computations that require both operations, necessitating protocol workarounds like multi-party computation (MPC) or switching between different encryption schemes, which adds complexity and overhead.

PHE operations cause significant ciphertext expansion, where encrypted data is much larger than the plaintext. This leads to:

• Increased storage and bandwidth costs.
• Slower computation times compared to plaintext processing.
• Higher gas costs when used on-chain, making it impractical for many blockchain applications without careful optimization and selective use.

Basic PHE schemes like textbook RSA or raw ElGamal are only secure against Chosen-Plaintext Attacks (CPA). In real-world scenarios where an adversary can obtain decryptions of other ciphertexts, they are vulnerable to Chosen-Ciphertext Attacks (CCA). Achieving CCA security requires additional cryptographic techniques like Optimal Asymmetric Encryption Padding (OAEP), which may not be compatible with the homomorphic property.

PHE inherits standard public-key infrastructure (PKI) challenges. Security depends entirely on:

• The secrecy of the private decryption key.
• Secure key generation, distribution, and storage.
• Trust in the entity holding the decryption key in a client-server model, which can create a central point of failure or trust, contrary to decentralized ideals.

PHE provides confidentiality but not inherent verifiability of computations. A malicious server could return an incorrect result on encrypted inputs, and the client cannot directly verify the computation's integrity without decrypting, which defeats the purpose. This requires combining PHE with zero-knowledge proofs or verifiable computation schemes to ensure correct execution.

PHE is often evaluated against more advanced privacy technologies:

• Fully Homomorphic Encryption (FHE): Supports arbitrary computations but is currently orders of magnitude slower than PHE.
• Secure Multi-Party Computation (MPC): Distributes trust among parties but requires continuous communication. The choice involves a trade-off between functionality, performance, and trust model. PHE is optimal for specific, simple operations where its limitations are acceptable.

A fundamental cryptographic primitive that allows a party to commit to a value (like a bid or a vote) while keeping it hidden, with the ability to reveal it later. The commitment is binding (cannot be changed) and hiding (value is secret). Often used in conjunction with ZKPs and as a building block in more complex protocols like private auctions on blockchain.

A method for distributing control of a cryptographic operation (like decryption or signing) across multiple parties. A threshold number of participants (e.g., 3 out of 5) must collaborate to perform the operation, preventing any single point of failure or compromise. This enhances security for private keys in institutional custody and decentralized autonomous organizations (DAOs).