Homomorphic Encryption: Capabilities and Practical Applications

Homomorphic encryption (HE) is a class of cryptographic technique that permits computation on ciphertext, producing an encrypted result that, when decrypted, matches the output of the same operation performed on the plaintext. This property fundamentally changes the threat model for data-in-use — a problem that conventional encryption, which requires decryption before processing, cannot address. This page covers the mechanics of HE schemes, their classification, regulatory relevance, practical tradeoffs, and deployment considerations for cryptographers, compliance officers, and applied security researchers navigating the encryption service landscape.

• Definition and Scope
• Core Mechanics or Structure
• Causal Relationships or Drivers
• Classification Boundaries
• Tradeoffs and Tensions
• Common Misconceptions
• Checklist or Steps (Non-Advisory)
• Reference Table or Matrix
• References

Definition and Scope

Homomorphic encryption describes any encryption system that preserves an algebraic structure such that operations on ciphertext correspond to operations on plaintext. Under a homomorphic scheme, a third party — a cloud provider, analytics platform, or federated node — can process encrypted data without ever obtaining access to the underlying plaintext, and without holding the decryption key. The decrypted output of those computations equals what would have resulted from performing the same operations on the unencrypted data.

The concept was formally established as a research problem by Rivest, Adleman, and Dertouzos in 1978, but the first construction of a Fully Homomorphic Encryption (FHE) scheme was achieved by Craig Gentry in 2009, as published in his Stanford dissertation and the associated proceedings of the ACM Symposium on Theory of Computing (STOC 2009). That construction, based on ideal lattices, demonstrated that FHE was mathematically achievable — though at computational costs prohibitive for most practical deployments at the time.

The scope of HE extends across three primary use contexts: privacy-preserving cloud computation (where data owners outsource analytics without exposing raw records), secure multi-party computation augmentation (where federated participants compute joint outputs without revealing individual inputs), and regulatory compliance workflows (where encrypted data must be queried or analyzed without triggering data exposure obligations under frameworks such as HIPAA or GDPR). The National Institute of Standards and Technology (NIST) has acknowledged HE as a relevant technique within its broader cryptographic standards program, particularly in the context of post-quantum algorithm development documented in NIST IR 8214.

Core Mechanics or Structure

All homomorphic encryption schemes rest on the mathematical property that certain algebraic operations — addition and multiplication, typically — can be applied directly to ciphertext representations of values. The underlying security hardness assumptions in modern HE constructions are drawn from the Learning With Errors (LWE) problem and its ring variant (RLWE), both of which are considered quantum-resistant by NIST's post-quantum cryptography evaluation program (NIST PQC).

The mechanics of a typical HE operation follow this structure:

1. Key generation — A public/private key pair is generated. The public key encrypts plaintext; the private key decrypts ciphertext. In some schemes, an evaluation key (or relinearization key) is also generated to enable multiplication operations without growing ciphertext size unboundedly.
2. Encryption — Plaintext values are encoded into a polynomial ring representation and encrypted using the public key, producing ciphertext with added structured noise.
3. Homomorphic evaluation — Arithmetic operations (addition, multiplication) are applied to ciphertext. Each multiplication increases the noise embedded in the ciphertext. If the noise exceeds a threshold before bootstrapping, decryption produces incorrect results.
4. Bootstrapping (FHE only) — A computationally expensive procedure that refreshes a ciphertext by reducing accumulated noise, enabling an unbounded number of subsequent operations. Bootstrapping is the defining capability that separates Fully Homomorphic Encryption from Somewhat or Leveled HE.
5. Decryption — Only the private key holder decrypts the evaluated ciphertext, recovering the result of the computation.

The dominant scheme families — BFV (Brakerski-Fan-Vercauteren), BGV (Brakerski-Gentry-Vaikuntanathan), CKKS (Cheon-Kim-Kim-Song), and TFHE (Fast Fully Homomorphic Encryption over the Torus) — each optimize for different operation types. CKKS, for instance, supports approximate arithmetic on real numbers, making it suited for machine learning inference, while BFV and BGV support exact integer arithmetic suited to database queries.

Causal Relationships or Drivers

The growth of cloud-hosted data processing is the primary structural driver behind HE deployment pressure. As regulated industries — healthcare, finance, government contracting — migrate computation to third-party infrastructure, the gap between encryption-at-rest/in-transit protections and encryption-in-use becomes a compliance and liability exposure. HIPAA's Security Rule (45 CFR Part 164) and PCI DSS require protection of sensitive data, but neither framework was drafted with cloud-side computation on encrypted data in mind — creating interpretive ambiguity that HE directly resolves by ensuring plaintext is never present at the compute layer.

A second driver is the post-quantum transition. Because leading HE schemes are already built on lattice-based hardness assumptions — the same foundations NIST selected for post-quantum standards including CRYSTALS-Kyber and CRYSTALS-Dilithium (NIST FIPS 203, NIST FIPS 204) — HE implementations inherit quantum resistance without requiring separate algorithmic migration.

A third driver is federated analytics in sensitive domains. The European Union's Regulation 2018/1807 on the free flow of non-personal data, combined with GDPR data residency constraints, creates operational scenarios where joint computation across jurisdictional boundaries requires that no single node see another's raw input. HE, in combination with secure multi-party computation, provides a technical path to compliance without contractual data-sharing arrangements. For a broader view of how encryption schemes relate to this encryption resource framework, the classification of HE within the wider cryptographic taxonomy is instructive.

Classification Boundaries

HE schemes are classified along two primary axes: the depth of computation supported and the type of arithmetic supported.

By computation depth:

• Partially Homomorphic Encryption (PHE) — Supports only one operation type (addition or multiplication) to an unlimited depth. RSA unpadded multiplication and Paillier additive encryption are canonical examples.
• Somewhat Homomorphic Encryption (SHE) — Supports both addition and multiplication but only up to a fixed circuit depth before noise accumulation causes decryption failure. No bootstrapping is performed.
• Leveled Fully Homomorphic Encryption (Leveled FHE) — Supports arbitrary circuits up to a pre-specified depth, set at key generation time. Bootstrapping is not used; depth is managed by selecting parameters in advance.
• Fully Homomorphic Encryption (FHE) — Supports arbitrary circuits of unlimited depth via bootstrapping. Gentry's 2009 construction established this category. Practical FHE became viable with TFHE bootstrapping times falling below 100 milliseconds for Boolean gate operations (as documented in the TFHE library specifications by Chillotti et al.).

By arithmetic type:

• Binary/Boolean circuits — Operations over bits; TFHE optimizes for this.
• Integer arithmetic — Exact integer operations; BFV and BGV are the primary schemes.
• Approximate arithmetic — Fixed-precision real-number arithmetic with controlled rounding error; CKKS is the standard scheme.

The HElib library (developed at IBM Research) and the Microsoft SEAL library are the two most widely referenced open implementations, supporting BGV/BFV and CKKS respectively.

Tradeoffs and Tensions

The central tension in HE deployment is computational overhead. FHE operations run between 1,000x and 1,000,000x slower than equivalent plaintext computations, depending on circuit depth and scheme choice. A multiplication in CKKS on a 2048-bit polynomial ring may consume tens of milliseconds per operation; a bootstrapping pass in TFHE adds 100 to 500 milliseconds per gate refresh at security level 128. These figures, cited in benchmarks from the TFHE project documentation and HElib performance papers, mean that real-time HE applications remain constrained to narrow computational workloads.

A second tension is the approximate-vs-exact divide. CKKS introduces controlled rounding error that is mathematically bounded but non-zero. For machine learning inference over floating-point weights, this approximation is acceptable. For financial calculations requiring exact integer results — account balances, transaction counts — CKKS is structurally unsuitable, and BFV or BGV must be used despite their higher costs for deep multiplication circuits.

Parameter selection creates a third tension: security level, ciphertext modulus size, polynomial ring dimension, and circuit depth are interdependent. Increasing ring dimension (e.g., from 4096 to 16384 coefficients) improves security and supports deeper circuits but quadruples ciphertext size and multiplies key generation time. The HomomorphicEncryption.org security standard, published by the community consortium, provides parameter recommendations at 128-bit, 192-bit, and 256-bit security levels — but selecting parameters for a novel application requires cryptographic expertise that general software engineers typically do not have.

Regulatory recognition is a fourth tension. No U.S. federal standard currently mandates or certifies specific HE schemes. NIST's Threshold Cryptography project and cryptographic standards work acknowledge HE research, but FIPS-approved algorithm lists as of 2024 do not include an HE scheme — meaning FedRAMP-authorized cloud services cannot cite HE as a FIPS-compliant control.

Common Misconceptions

Misconception: HE eliminates all privacy risk in cloud computation.
HE protects data confidentiality from the compute provider. It does not protect against a malicious evaluator returning a crafted wrong answer (a problem addressed by Verifiable Computation, not HE), nor does it protect against metadata leakage from access patterns (a problem addressed by Oblivious RAM).

Misconception: FHE means any program can run on encrypted data.
FHE supports arbitrary arithmetic circuits, but translating an arbitrary program into an HE-compatible circuit requires significant engineering. Not all operations map cleanly — branching on encrypted values, for instance, requires special treatment. Programs must be re-expressed in terms of supported operations, and the resulting circuit depth determines whether SHE or FHE is needed.

Misconception: CKKS approximate arithmetic is insecure.
A 2021 paper by Li and Micciancio (published at EUROCRYPT 2021) demonstrated that CKKS decryption can reveal information about the secret key under certain conditions in the IND-CCA model. This was widely misreported as a complete break. The vulnerability applies specifically to settings where exact decryption outputs are returned to an adversary — a non-standard deployment. Mitigations, including noise-flooding techniques, are documented in the community response and in updated CKKS implementations.

Misconception: HE and secure multi-party computation (MPC) are interchangeable.
HE and MPC both enable computation without revealing inputs, but they have different trust models and performance profiles. MPC distributes trust across parties and requires interaction between them; HE enables non-interactive computation by a single server. Hybrid constructions combining both are common in deployed privacy-preserving systems, but the two primitives address structurally distinct threat models.

Checklist or Steps (Non-Advisory)

The following sequence characterizes the evaluation and deployment pathway for an HE implementation in a regulated data environment:

1. Define the computation model — Identify the specific arithmetic operations required (addition, multiplication, comparison) and the circuit depth (number of sequential multiplications).
2. Select the appropriate HE scheme — Match circuit characteristics to scheme: PHE (Paillier) for additive-only; BFV/BGV for exact integer circuits of bounded depth; CKKS for approximate real-number arithmetic; TFHE for Boolean circuits requiring bootstrapping.
3. Determine security parameter requirements — Reference HomomorphicEncryption.org security standard to select ring dimension and ciphertext modulus at the required security level (128-bit minimum for most regulated contexts).
4. Select and audit an implementation library — Confirm the library has undergone third-party cryptographic review. Reference implementations include Microsoft SEAL, HElib, and OpenFHE.
5. Benchmark against plaintext baseline — Measure HE overhead for the target workload under production-representative data volumes. Document the multiplicative slowdown factor.
6. Map regulatory controls — Identify applicable frameworks (HIPAA, PCI DSS, FedRAMP) and document how HE addresses data-in-use requirements. Note any gaps where HE is not yet a recognized compliant control.
7. Implement noise budget management — For SHE/Leveled FHE schemes, define the maximum computation depth and verify that the noise budget is not exhausted before the final decryption step.
8. Validate output correctness — For CKKS deployments, define acceptable rounding error bounds and test against known plaintext outputs.
9. Key management integration — Integrate private key management with the organization's existing key management infrastructure (e.g., FIPS 140-3 validated hardware security modules).
10. Document threat model boundaries — Record explicitly what HE does and does not protect against in the system's security documentation, distinguishing confidentiality guarantees from integrity and access-pattern guarantees.

The broader context for how these steps fit into the reflects where HE sits relative to other cryptographic service categories.

Reference Table or Matrix