Fully-Homomorphic Encryption (FHE) is a main tool of Privacy-Enhancing Cryptography (PEC), alongside with Multi-Party Computation (MPC), Zero-Knowledge Proofs (ZKP), Private-Set Intersection (PSI), and others. The NIST PEC project is accompanying FHE developments and initiatives toward future useful standards.
Informally speaking, FHE allows non-interactive evaluation of functions/operations over encrypted data. This can be used as a PEC tool in myriad scenarios where privacy by design is a requirement. Conceivable and real use-cases of FHE are possible in many sectors. Some examples:
Note: This list is a work in progress. We intend to progressively refine the list to provide a more concrete and comprehensive set of examples. Suggestions and feedback are welcome.
The PEC project draws FHE context from various informative initiatives about FHE progress:
A homomorphic encryption scheme is a special type of encryption scheme that enables computing functions over encrypted data, such that a later decryption outputs the function applied over the data. A Fully homomorphic encryption scheme enables this property for any computable function. FHE can be achieved both in the public-key setting and in the symmetric-key setting.
Comparison with a regular encryption scheme. A regular encryption scheme is specified as a triple (KeyGen, Enc, Dec) of algorithms: key generation (KeyGen), encryption (Enc) and decryption (Dec). Two essential properties (among others):
The meaning of homomorphic evaluation. An homomorphic encryption scheme is a special type of encryption scheme that also supports an evaluation (Eval) operation over encrypted data. This can be expressed for functions that act on a single argument (e.g., (f(m))), or functions (or operators) that act on multiple arguments (e.g., (m_1 * m_2)). For example:
The next illustration depicts an idealized FHE functionality ((mathcal{F})), which in an idealized world would mediate the encryption, decryption and evaluation. In this example: (1) a client encrypts (color{red}x_1) and (color{red}x_2), and then (2) the server learns that two elements have been encrypted, but not their content; then (3), the server homomorphically evaluates a function ( ed{f}) over the two encrypted values, and (4) the result is learned only by the Client. Depending on the application, the function (color{red}f) may also be chosen by the client.
An actual FHE scheme "emulates" this ideal functionality, without any third party mediation.
See WPEC 2024 Talk 2b1 for a brief invited tutorial on FHE types and properties. See WPEC 2024 Talk 2b6 for a brief overview of community developed security guidelines for implementing FHE. While the conceptualization of FHE can look very clean, in practice three are various distinct approaches for FHE, each with particular advantages. It is usual to characterize the known solutions in three types, depending on the plaintext domain and types of operations:
A note on malleability (an essential feature) in FHE: Some applications of regular (non-homomoprhic) encryption schemes take advantage of a security property called indistinguishability against adaptive chosen-ciphertext attacks (IND-CCA2). FHE requires the opposite (a malleability property) as a feature: that someone with a ciphertext (e.g., (c = ext{Enc}(m))) but without the decryption key can calculate a new valid ciphertext ((c' = ext{Eval}(f,c))) for a new plaintext (m'=f(m)) that would be obtained from a known operation ((f)) on the original (unknown) plaintext.
IND-CPA-D: A minimum desired property of FHE is IND-CPA, i.e., indistinguishability against chosen plaintext attacks. While IND-CCA is nota applicable to FHE, it is important to consider the security of a scheme when an adversary can submit ciphertexts to a decryption oracle. The property IND-CPA-D is especially relevant for schemes where the result of an homomorphic evaluation may contain noise correlated with the key, and/or when the probability of decryption error is not negligible.
The NIST Threshold Call (submission deadline to be set in 2025) is a community opportunity for the public to submit FHE specifications+implementations+evaluations that showcase FHE state-of-the-art techniques and discuss their security properties.
Security and Privacy: cryptography, privacy