Paillier Cryptosystem

The Paillier cryptosystem's defining property is its additive homomorphism. This allows the encrypted sum of two plaintexts to be computed directly from their ciphertexts, without decryption. Formally, given two ciphertexts Enc(m1) and Enc(m2), the product Enc(m1) * Enc(m2) mod n² decrypts to (m1 + m2) mod n. This enables secure aggregation of values, such as summing client model updates in federated learning, where only the combined total is revealed.

Paillier encryption is semantically secure under the Decisional Composite Residuosity Assumption (DCRA). This means an adversary cannot learn any partial information about a plaintext from its ciphertext, even when given the public key. Security is achieved through probabilistic encryption: encrypting the same message multiple times yields different, computationally indistinguishable ciphertexts due to the use of a random blinding factor r. This prevents frequency analysis and chosen-plaintext attacks.

Beyond simple addition, Paillier supports scalar multiplication on ciphertexts. Given a ciphertext Enc(m) and a known integer k, raising the ciphertext to the power of k (Enc(m)^k mod n²) decrypts to the product k * m mod n. This allows a central server to perform weighted averaging in federated learning by multiplying encrypted client updates by a known scalar (e.g., based on dataset size) before secure summation, all while the data remains encrypted.

A unique feature is the self-blinding property. Any valid ciphertext can be transformed into another, different ciphertext that decrypts to the same plaintext. This is done by multiplying the ciphertext by an encryption of zero (Enc(0)). This property is crucial for ciphertext refreshment in multi-round protocols, allowing ciphertexts to be re-randomized to prevent linkage attacks across protocol rounds without changing the underlying plaintext value.

Standard Paillier uses a single private key for decryption. A threshold variant distributes the decryption capability among multiple parties. The private key is secret-shared among n parties, and a predefined threshold t of them must collaborate to decrypt a ciphertext. No single party holds the full key. This enhances security in distributed systems like secure aggregation, preventing any single aggregator from unilaterally decrypting individual client contributions.

Paillier operations are computationally intensive compared to symmetric encryption. Key characteristics:

• Ciphertext Expansion: Plaintexts are modulo n, while ciphertexts are modulo n², leading to a 2x expansion in size.
• Performance: Encryption and decryption involve modular exponentiation with large numbers (typically 2048-bit or larger n).
• Application: Its primary use is in secure multi-party computation (MPC) and federated learning for secure summation, where the computational cost is justified by the strong privacy guarantee. It is often combined with differential privacy for layered protection.

Homomorphic Encryption is a cryptographic paradigm that allows computations to be performed directly on encrypted data. The Paillier scheme is a specific type known as additive homomorphic encryption, where the product of two ciphertexts decrypts to the sum of their corresponding plaintexts. This property is the core enabler for secure aggregation in federated learning, as the server can sum encrypted model updates without decrypting them first. Other forms include:

• Somewhat Homomorphic Encryption (SHE): Supports a limited number of operations.
• Fully Homomorphic Encryption (FHE): Supports an unlimited number of arbitrary computations (addition and multiplication) but with significantly higher computational overhead than Paillier.

Secure Multi-Party Computation is a broader cryptographic subfield that enables multiple parties to jointly compute a function over their private inputs while revealing only the final output. Secure aggregation in federated learning is a specific instance of an MPC problem. While Paillier provides a solution using public-key cryptography, MPC often employs different techniques like secret sharing and garbled circuits. Key distinctions include:

• Trust Model: MPC protocols often assume no single trusted party, whereas Paillier-based aggregation typically involves a central (but untrusted) server.
• Interaction: MPC protocols can be highly interactive, requiring multiple communication rounds between parties.
• Flexibility: MPC can compute arbitrary functions, while Paillier natively supports only addition.

Differential Privacy is a rigorous mathematical framework for quantifying and limiting the privacy loss incurred by an individual when their data is included in an analysis. It is often used in conjunction with cryptographic techniques like Paillier. In a federated learning pipeline:

• Paillier provides input privacy, ensuring the server never sees a client's raw model update.
• Differential Privacy (often via the Gaussian Mechanism) provides output privacy, adding calibrated noise to the aggregated model update before it is released, bounding the influence of any single client's data. This combination defends against privacy attacks that might leverage the final model parameters.

Learning With Errors is a foundational computational problem in lattice-based cryptography. Its conjectured hardness forms the security basis for many post-quantum cryptographic schemes, including modern Fully Homomorphic Encryption systems like CKKS and BFV. While the original Paillier cryptosystem is based on the composite residuosity assumption and is vulnerable to quantum attacks via Shor's algorithm, LWE-based constructions are believed to be quantum-resistant. For long-term security in federated learning systems, LWE-based homomorphic encryption is a leading candidate to eventually replace or complement classical schemes like Paillier.

Additive Secret Sharing is a lightweight cryptographic technique where a secret value (e.g., a model update) is split into multiple shares that sum to the original secret. No subset of shares reveals any information about the secret unless all are combined. This is a core mechanism in many Secure Multi-Party Computation-based secure aggregation protocols (like the Bonawitz Protocol), as an alternative to Paillier. Advantages include:

• Information-theoretic security: Security based on randomness, not computational assumptions.
• Efficiency: Often faster than public-key operations.
• Dropout Resilience: Protocols can be designed so that shares from dropped clients can be canceled out.

A Trusted Execution Environment is a secure, isolated area within a main processor (e.g., Intel SGX, AMD SEV) that guarantees the confidentiality and integrity of code and data loaded inside it. TEEs offer a hardware-based alternative to cryptographic protocols for secure aggregation. In this paradigm, client updates are sent encrypted to the server and are only decrypted and aggregated inside the secure enclave, invisible to the host operating system. Compared to Paillier:

• Performance: Can be faster for complex aggregation functions.
• Functionality: Supports arbitrary computations, not just addition.
• Trust Model: Shifts trust from cryptographic hardness to the hardware manufacturer and the enclave's attestation mechanism.