My Discovery of Homomorphic and Fully Homomorphic Encryption#

Disclaimer: I am not an expert in Homomorphic Encryption (HE) or Fully Homomorphic Encryption (FHE). This post documents my discovery and initial exploration of these fascinating topics as part of my academic journey. The content reflects my learning process and understanding at the time of writing.

Table of Contents#

  1. Introduction
  2. Development and State of the Art
  3. Solutions and Real Use-Cases
  4. Example with Code
  5. Conclusion
  6. Sources and References

Introduction#

Homomorphic encryption is like manipulating the invisible, the unknown: calculating on encrypted data to obtain usable results, thus maintaining absolute confidentiality on the data. The idea of being able to process data without ever seeing it, without ever decrypting it, was science fiction a few decades ago. And yet, recent advances in the field already make it possible to do so, whether “partially” (HE) or “completely” thanks to Fully Homomorphic Encryption (FHE).

This innovation, which promises to transform cybersecurity, artificial intelligence, and the way we use cloud services, refers to a method of calculating directly on encrypted data without having to decrypt it beforehand, therefore working with the data without really having access to it.

Homomorphic Encryption Concept Basic concept of homomorphic encryption - computing on encrypted data

This revolutionary concept, once considered inaccessible, has been the subject of intense research over the past decades, and today homomorphic encryption represents a substantial and booming market, particularly due to the explosion of AI in recent years and the demands for cloud technologies.

How does Homomorphic Encryption work? What challenges and real use cases do they encounter as of today?

In this report, we will go through the evolution of homomorphic encryption, draw up a state of the art and delve into its technical functioning. We will also present demonstrations via code to give a practical understanding of how HE works and its future.

Development (State of the Art)#

Homomorphic encryption is based on a simple but powerful idea: allowing an operator (often an untrusted third party) to manipulate encrypted data without having access to the plaintext information.

In other words, the data remains protected throughout the computation process, and only the holder of the private key can obtain the result after decryption. Most FHE algorithms are asymmetric and enable the storage, transfer, and computation of data in a secure shared manner, without needing to trust the third party.

Here is an illustration to better understand the concept:

Server Computing on Encrypted Data Server receives encrypted message x and computes function f without seeing the plaintext

Here, the server receives an encrypted message x and computes a function f which is arbitrary, meaning it can be any polynomial function.

History and Invention#

The concept of homomorphic encryption was first conceptualized in the 1970s with the introduction of the first partially homomorphic encryption methods, including the RSA algorithm. For instance, RSA encryption is homomorphic with respect to multiplication, allowing operations on encrypted data within a single mathematical domain.

The idea of fully homomorphic encryption (FHE), which would be capable of supporting both additions and multiplications (and thereby compute any arbitrary function), was first proposed by Rivest, Adleman, and Dertouzos in 1978. However, it was not until 2009 that Craig Gentry, a researcher at IBM, developed the first practical FHE scheme.

This was an important discovery in the field of cryptography, and several generations of homomorphic encryption algorithms have been developed since:

Pre-FHE (Before 2009)#

Encryption schemes that only support a single operation, such as RSA (multiplication only).

First Generation FHE (2009)#

Following Craig Gentry’s breakthrough, using lattice-based cryptography. Gentry’s scheme introduced key concepts:

  • Reduction to the lattice problem (LWE - Learning With Errors): This problem is considered difficult to solve, even for quantum computers
  • Bootstrapping: A mechanism for “refreshing” a ciphertext to support an unlimited number of operations by reducing noise accumulated over time

Second Generation FHE (2011+)#

Lattice-based encryption algorithms, particularly RLWE (Ring Learning With Errors) and NTRU, which are more efficient than the first generation.

Third Generation FHE (2013+)#

Based on the GSW cryptosystem, which uses matrix-based encryption and focuses on efficiently handling matrix operations. Variants like FHEW (2014) and TFHE (2016) further optimize the bootstrapping process.

Fourth Generation FHE (2016+)#

The CKKS scheme, which operates on real numbers using approximate encryption, making it ideal for applications like AI and statistics where small computational errors are acceptable.

Mathematical Principles#

Homomorphic Operations Diagram Mathematical representation of homomorphic operations

At its core, homomorphic encryption relies on mathematical structures, particularly those related to algebraic operations such as addition and multiplication. A homomorphism is a mapping between two algebraic structures that preserves the operations of the structures.

In the context of homomorphic encryption, we define a homomorphic encryption scheme as a function Enc that satisfies the following properties for any plaintexts x and y:

Enc(x) + Enc(y) = Enc(x + y)
Enc(x) × Enc(y) = Enc(x × y)

And then being able to decipher it with the computation of the function f:

Dec(Eval(f, Enc(x+y))) = Eval(f, (x+y))
Dec(Eval(f, Enc(x×y))) = Eval(f, (x×y))

Homomorphic Encryption Process Complete homomorphic encryption process from plaintext to result

Types of Homomorphic Encryption#

  1. Partially Homomorphic Encryption (PHE): Supports only a single operation (either addition or multiplication)
  2. Leveled Fully Homomorphic Encryption (Leveled-FHE): Allows a limited number of both operations up to a certain depth
  3. Fully Homomorphic Encryption (FHE): Supports an arbitrary number of additions and multiplications

LWE & Initialization#

Most modern (third generation FHE) algorithms like TFHE (2016) and FHEW (2014) use the Learning With Error (LWE) problem to generate their keys. The LWE problem is based on a mathematical problem that is proven NP-hard.

Mathematically, it can be described as follows:

Given a secret vector s of n elements, a random matrix A of dimension L×n, and a small error vector e, the task is to find s from the “noisy” equation:

b = A·s + e mod q

The noise e makes it extremely difficult to recover s. With this, we can create secret key s for our encryption scheme.

Computing and Noise#

Noise Growth in Homomorphic Operations How noise grows during homomorphic computations

For any homomorphic encryption scheme using noise, computation on the cipher inevitably makes this noise grow. For example, when we add two ciphertexts, their noise components also add up:

v₁ + v₂ = ((u₁ᵀ + u₂ᵀ)s + (e₁ + e₂) + (m₁ + m₂))

Noise Overflow Problem When noise grows too large, decryption fails

This is where bootstrapping comes into play: the server uses the secret key to decipher the noisy cipher, which resets the noise level. However, to maintain confidentiality, the secret key is encrypted by another key called the public bootstrapping key.

Fast Fully Homomorphic Encryption over Torus (TFHE)#

TFHE represents a significant advancement in FHE, focusing on fast gate-by-gate operations and efficient bootstrapping. Unlike earlier schemes, TFHE works at the level of binary and logic gates.

Key innovations in TFHE include:

  • External product: Allows for key switching
  • CMUX: Basic multiplexing for if/else cases
  • Sample extraction and Blind rotation
  • Programmable bootstrapping: Evaluation of arbitrary binary gates during bootstrapping

TFHE Applications TFHE is optimized for boolean operations and logic gates

TFHE is particularly well-suited for:

  • Secure Binary Decision Making
  • Private Search and Queries
  • Encrypted Control Systems
  • Lightweight IoT Applications
  • Boolean-heavy Machine Learning tasks

Solutions and Real Use-Cases#

Despite being in its fourth generation, FHE still faces significant challenges in terms of computational efficiency. However, it has found applications in fields where privacy is paramount:

Current Applications#

  • Healthcare: Medical data processing without decryption
  • Finance: Credit scoring and fraud detection on encrypted data
  • Machine Learning: Training models on encrypted datasets

Companies Working on FHE#

  • Inpher: FHE solutions for finance and healthcare
  • CryptoExperts: Cryptography consulting and HE research
  • NuCipher: Secure multi-party computation with FHE elements
  • Zama: Making FHE more accessible for AI and cloud computing

Security Considerations#

FHE schemes face several challenges:

  • Noise sensitivity: Each operation adds noise that can corrupt data
  • Side-channel attacks: Vulnerabilities during bootstrapping
  • Parameter selection: Poor choices can leave encryption vulnerable

Example with Code#

Let’s examine a practical example using CKKS scheme with the TenSEAL library (Python API for Microsoft SEAL):

Setting Up the Data# 

# Dummy sensitive medical data (blood pressure readings)
sensitive_data = [120, 130, 125, 140, 115, 135]

Key Generation and Encryption# 

def encrypt_data(data):
    context = ts.context(
        ts.SCHEME_TYPE.CKKS,
        poly_modulus_degree=8192,
        coeff_mod_bit_sizes=[60, 40, 40, 60]
    )
    context.generate_galois_keys()
    context.global_scale = 2**40
    
    return ts.ckks_vector(context, data), context

Server-Side Computation# 

# Encrypt data on client side
encrypted_data, context = encrypt_data(sensitive_data)

# Server performs computation without seeing the data
sum_vector = encrypted_data.sum()
mean_vector = sum_vector * (1.0/len(sensitive_data))

Code Example Output Encrypted data representation and operations

Benchmark Results Performance comparison: FHE vs clear computation

Performance Analysis#

As shown in the benchmark, FHE computation is approximately 40 times slower than clear computation. This performance gap is due to several factors:

  • Python API overhead on top of C++ core
  • Non-optimized parameters for this specific application
  • General computational complexity of homomorphic operations

Conclusion#

Homomorphic encryption, although still in an optimization phase, is one of the most promising advances in cryptography for protecting data privacy in the long term, including in post-quantum scenarios. The progress made in the last decade, especially with lattice-based cryptosystems, is bringing this technology closer to wider adoption in sectors such as healthcare, finance, and AI.

Projects such as Microsoft SEAL, HElib (IBM), and PALISADE provide valuable resources to experiment with real implementations and could help widespread adoption of HE in privacy-critical computations. In the future, the evolution of homomorphic encryption will likely be linked to advances in post-quantum cryptography and continued increases in computing power, enabling better data security and more privacy.

Sources and References#

Key Resources#

Academic Papers#

  • Rivest, R., Adleman, L., & Dertouzos, M. (1978). On data banks and privacy homomorphisms
  • Gentry, C. (2009). A fully homomorphic encryption scheme
  • Cheon, J.H., Kim, A., Kim, M., Song, Y. (2017). Homomorphic Encryption for Arithmetic of Approximate Numbers (CKKS)

This post represents my academic exploration and discovery of Homomorphic Encryption during my studies. While I continue to deepen my knowledge in this fascinating field, I hope this overview provides insight into the revolutionary potential of computing on encrypted data.