Homomorphic Encryption

A scheme that supports an unlimited number of operations but only of a single type (either addition or multiplication) on ciphertexts.

• Examples: RSA (multiplicative), Paillier (additive), ElGamal (multiplicative).
• Use Case: Secure electronic voting (Paillier for tallying encrypted votes) or private set intersection.
• Performance: Relatively efficient and practical for specific, constrained computations.

A scheme that supports both addition and multiplication but only for a limited number of operations (a bounded computational depth).

• Mechanism: Noise grows with each operation; exceeding the 'capacity' makes decryption impossible.
• Use Case: Prototype for building more powerful FHE schemes or for circuits with a known, shallow depth.
• Limitation: Not suitable for arbitrary, complex computations without careful circuit design.

A scheme that supports both addition and multiplication an unlimited number of times, enabling arbitrary computations on encrypted data.

• Breakthrough: First realized by Craig Gentry in 2009 using a bootstrapping technique to 'refresh' ciphertext noise.
• Modern Schemes: BGV, BFV, CKKS, and TFHE. CKKS is notable for efficient approximate arithmetic on real numbers.
• Challenge: Computationally intensive, though modern compilers (e.g., Microsoft SEAL, OpenFHE) and hardware acceleration are closing the performance gap.

A specific FHE scheme (Cheon-Kim-Kim-Song) optimized for approximate arithmetic on encrypted real or complex numbers, which is crucial for machine learning.

• Key Property: Trade-off between precision and performance, allowing for much faster operations on encrypted vectors and matrices.
• Primary Use: Privacy-preserving machine learning inference and training on encrypted data, as it naturally handles the floating-point-like computations of neural networks.
• Output: Decryption yields a result close to the plaintext computation, within a controlled error bound.

The computationally expensive but essential noise management operation that 'refreshes' a ciphertext, reducing its inherent noise and allowing for further homomorphic operations.

• Analogy: Resetting a odometer before it overflows. Without bootstrapping, SHE schemes have limited depth.
• Impact: Bootstrapping is the primary performance bottleneck in FHE. Recent research focuses on bootstrapping in minutes or seconds rather than hours.
• Advanced Technique: Programmable Bootstrapping (in TFHE) allows for the evaluation of any univariate function during the refresh operation.

A related but distinct cryptographic paradigm where a secret key is tied to a specific function f. Decrypting a ciphertext with this key reveals only the result of f(plaintext), not the plaintext itself.

• Contrast with FHE: FHE outputs an encrypted result; Functional Encryption outputs a plaintext result but with strictly controlled leakage.
• Use Case: A key for 'sum of salaries' decrypts a payroll database to reveal only the total, not individual salaries.
• Synergy: Can be combined with FHE in advanced privacy-preserving architectures for granular result control.

Provides a cryptographic foundation for verifiable and private democratic processes and market mechanisms.

• Electronic Voting: Votes are encrypted and tallied homomorphically, producing an encrypted total that is then decrypted to reveal the result, ensuring individual voter privacy and tally integrity.
• Sealed-Bid Auctions: Bids are encrypted and submitted. The auctioneer can homomorphically compute the maximum bid to determine the winner without revealing any other bid values.
• Privacy-Preserving Surveys: Aggregate statistics (e.g., average salary in a department) can be computed from encrypted individual responses.

While powerful, Homomorphic Encryption has significant engineering trade-offs that dictate its current practical application:

• Computational Overhead: Ciphertext operations are orders of magnitude slower than operations on plaintext, requiring careful performance engineering.
• Ciphertext Expansion: Encrypted data is significantly larger than its plaintext equivalent, impacting storage and network bandwidth.
• Supported Operations: Most practical schemes (e.g., CKKS for approximate arithmetic, BFV/BGV for exact) support a limited set of operations (additions, multiplications), constraining algorithm design.
• Use with Other Techniques: It is often used in hybrid architectures alongside Trusted Execution Environments (TEEs) and Secure Multi-Party Computation (MPC) to balance performance and security.

A cryptographic protocol that enables multiple parties to jointly compute a function over their private inputs while keeping those inputs concealed from each other.

• Key Difference from HE: MPC distributes trust across parties, whereas Homomorphic Encryption allows computation by a single untrusted party on encrypted data.
• Edge AI Application: Useful for privacy-preserving model training across multiple edge nodes or for secure aggregation of model updates in federated learning, without a central aggregator seeing raw data.

Encompasses techniques designed to protect the privacy of local training data and the integrity of model updates in a decentralized learning paradigm where models are trained across many edge devices.

• Key Techniques: Includes secure aggregation (often using MPC or HE), differential privacy for updates, and Byzantine-robust aggregation.
• Role of HE: Homomorphic Encryption can be used to perform secure aggregation on the central server, allowing it to compute the average of encrypted model updates from devices without decrypting any individual update.

A secure, isolated area of a main processor that ensures the confidentiality and integrity of code and data loaded inside it, even from a compromised operating system.

• Hardware Examples: Intel Software Guard Extensions (SGX), ARM TrustZone, AMD Secure Encrypted Virtualization (SEV).
• Edge AI Application: Provides a hardware root of trust for edge AI workloads. While HE performs computation on ciphertext, a TEE creates a secure enclave to run computations on plaintext that is protected from the rest of the system. They are often used together for optimal security and performance.