Homomorphic Encryption Standard

Martin R. Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin E. Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, Vinod Vaikuntanathan

This document represents a landmark community effort to move Homomorphic Encryption (HE) from a theoretical curiosity into a standardized cryptographic tool. Authored by a "who's who" of modern cryptography, it establishes the first unified framework for implementing and deploying HE.

TL;DR

This paper provides the first comprehensive industry standard for Homomorphic Encryption, defining unified notation, scheme specifications (BGV, BFV, GSW), and concrete security parameter recommendations. By aligning researchers and developers on security levels (128, 192, and 256-bit), it paves the way for HE adoption in regulated sectors like healthcare and finance.

What Problem Does This Paper Address?

Homomorphic Encryption is the "holy grail" of privacy-preserving computation: it allows a server to process data while it is still encrypted, returning an encrypted result that only the data owner can decrypt.

Before this document, the field was a "Wild West." Different research groups used varying notations, distinct security assumptions, and inconsistent parameter choices. This lack of standardization made it nearly impossible for government agencies or large-scale industries (like medical or financial sectors) to audit or adopt the technology. The paper addresses this by providing a "ground truth" for what constitutes a secure and standard HE implementation.

Methods

The paper standardizes the field through three primary pillars:

  1. Unified API and Notation: It defines a standard set of algorithms that any HE scheme should implement, including ParamGen (parameter generation), KeyGen, Encrypt, Decrypt, and the homomorphic operators EvalAdd and EvalMult.
  2. Scheme Specification: It provides detailed descriptions of the most practical "Leveled" HE schemes:
  3. BGV and BFV: The primary workhorses for integer arithmetic.
  4. GSW: A scheme noted for its "asymmetric noise growth," which is critical for the "bootstrapping" process (refreshing a ciphertext to allow for more computations).
  5. Security Parameter Selection: The authors use the Learning with Errors (LWE) and Ring-LWE (RLWE) problems as the security foundation. They evaluate the cost of the best-known lattice-based attacks (like uSVP and dual attacks) to provide tables of recommended ring dimensions ($n$) and ciphertext moduli ($q$).

Datasets

As a theoretical and standardization paper, it does not use traditional training datasets. Instead, it relies on the LWE-estimator, a benchmark tool that calculates the bit-complexity of breaking specific LWE instances. The results are based on the state of the estimator as of March 2018. It also references existing software libraries—such as SEAL, HElib, and PALISADE—as the practical baseline for these standards.

Key Insights and Ideas

  • The Noise Invariant: The paper formalizes the idea that every HE operation adds "noise" to a ciphertext. Standardization is largely about managing this noise so that decryption remains possible while keeping the parameters small enough for efficiency.
  • Lattice Reduction as the Yardstick: The authors acknowledge that security is a moving target. They base their recommendations on the "sieve" and "qsieve" cost models for the BKZ lattice reduction algorithm, which is currently the most efficient way to attack these schemes.
  • Post-Quantum by Default: Because LWE-based schemes are inherently resistant to known quantum attacks, the standard includes specific "Post-quantum security" tables, anticipating a future where quantum computers are a reality.
  • Advanced Features: The document goes beyond basic encryption to discuss Threshold HE (where multiple parties must cooperate to decrypt) and Evaluation Privacy (ensuring the encrypted result doesn't leak which function was performed).

Key Results

The paper’s most practical contribution is a series of Recommended Parameter Tables.

  • It defines three security tiers: 128-bit, 192-bit, and 256-bit.
  • For a standard 128-bit security level using a power-of-two cyclotomic ring with dimension $n=1024$, the paper recommends a maximum ciphertext modulus ($\log q$) of 29 bits.
  • It provides separate recommendations for different secret key distributions: Uniform, Error-based, and Ternary ($\{-1, 0, 1\}$), allowing developers to trade off performance for security based on their specific use case.

Limitations and Future Work

The authors acknowledge that this is a "living document" with several areas left for future versions:

  • Approximate Numbers (CKKS): While mentioned, the CKKS scheme (essential for real-world floating-point arithmetic and machine learning) was not fully specified in this initial version.
  • Non-Power-of-Two Rings: The current recommendations focus on specific ring types; more general algebraic structures are slated for future study.
  • Sparse Secrets: The security of using very "sparse" secret keys (to speed up computation) is not yet fully understood by the community and thus was not standardized.
  • API and Applications: Future sections (3.0 and 4.0) are planned to cover standardized API designs and specific application deployment guidelines.

Summary updated

BibTeX
@article{albrecht2019homomorphic,
  author = {Martin R. Albrecht and Melissa Chase and Hao Chen and Jintai Ding and Shafi Goldwasser and Sergey Gorbunov and Shai Halevi and Jeffrey Hoffstein and Kim Laine and Kristin E. Lauter and Satya Lokam and Daniele Micciancio and Dustin Moody and Travis Morrison and Amit Sahai and Vinod Vaikuntanathan},
  title = {{Homomorphic Encryption Standard}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2019},
  url = {https://openreview.net/forum?id=5T77DF6Auo},
}
Figure