Homomorphic Encryption: Mathematical Foundations, Development, Applications, and Performance Considerations

Abstract

Homomorphic encryption (HE) stands as a groundbreaking cryptographic primitive, enabling computational operations directly on encrypted data without prior decryption. This unique capability ensures that the results, once decrypted, perfectly correspond to those that would have been obtained if the operations were performed on the plaintext. This fundamental property offers an unparalleled layer of data privacy and confidentiality, positioning HE as an indispensable tool in contemporary data-driven environments where sensitive information processing must occur without any exposure of the underlying data. This comprehensive report meticulously explores the intricate mathematical underpinnings that enable HE, traces its compelling evolution from theoretical concept to practical schemes, critically examines its diverse and transformative applications across a spectrum of industries, and thoroughly analyzes the critical performance considerations that govern its real-world deployment. Furthermore, it precisely distinguishes between the various categories of homomorphic encryption schemes, namely partially, somewhat, and fully homomorphic encryption, elucidating their respective capabilities and trade-offs.

Many thanks to our sponsor Esdebe who helped us prepare this research report.

1. Introduction: The Imperative for Privacy-Preserving Computation

In the current digital epoch, marked by an unprecedented surge in data generation, aggregation, and analysis, the imperative to safeguard sensitive information has never been more pronounced. The ubiquity of cloud computing, the proliferation of artificial intelligence, and the increasing reliance on outsourced data processing have inadvertently created a ‘privacy paradox.’ While organizations and individuals seek to leverage the benefits of advanced analytics and collaborative data utilization, they are simultaneously confronted with escalating threats of data breaches, unauthorized access, and surveillance. Traditional encryption methods, while highly effective in securing data at rest and in transit, inherently demand decryption prior to processing. This creates a critical vulnerability point, as data becomes exposed in plaintext during computation, thereby compromising its confidentiality.

Homomorphic encryption directly addresses this profound challenge by introducing a revolutionary paradigm: computation on ciphertext. By allowing arbitrary or specific operations to be performed directly on encrypted data, HE ensures that sensitive information remains perpetually encrypted throughout its lifecycle—from storage and transmission to intricate processing and analysis. This groundbreaking capability is particularly salient in highly regulated and sensitive sectors such as healthcare, where patient confidentiality is paramount; finance, where transactional and personal financial data requires stringent protection; and cloud computing, where clients demand absolute assurance that their outsourced data remains private even from the cloud provider itself.

The journey of homomorphic encryption from a theoretical curiosity to a field of intense research and practical development represents one of the most significant advancements in modern cryptography. Initially conceived as a distant ‘holy grail,’ the prospect of fully homomorphic encryption (FHE)—supporting any arbitrary computation—was widely regarded as an intractable problem due to the immense computational overhead and the challenge of managing ‘noise’ inherent in cryptographic operations. However, a seminal breakthrough in 2009 by Craig Gentry irrevocably transformed this landscape, proving the theoretical feasibility of FHE and igniting a new era of cryptographic innovation. This report seeks to provide a detailed exposition of HE, covering its theoretical foundations, historical development, diverse applications, and the persistent challenges and promising future directions in this vital field.

Many thanks to our sponsor Esdebe who helped us prepare this research report.

2. Mathematical Foundations of Homomorphic Encryption: The Algebra of Confidentiality

At its core, homomorphic encryption is rooted in the mathematical concept of a homomorphism, a structure-preserving map between two algebraic structures. In the context of cryptography, this means there is a function (encryption) that maps elements from a plaintext space to a ciphertext space such that operations performed in the ciphertext space correspond precisely to analogous operations in the plaintext space upon decryption. This elegant mathematical property allows for meaningful computation on encrypted data without ever needing to reveal the plaintext.

Let P denote the plaintext space (e.g., integers, binary strings), and C denote the ciphertext space. Let E be the encryption function and D be the decryption function. A cryptosystem is homomorphic with respect to an operation *p in the plaintext space and *c in the ciphertext space if, for any plaintexts m1, m2 in P:

D(E(m1) *c E(m2)) = m1 *p m2

This equation encapsulates the essence of homomorphic encryption: an operation on ciphertexts yields a ciphertext whose decryption is the result of the desired operation on the corresponding plaintexts. The security of HE schemes typically relies on the computational hardness of certain mathematical problems, such as integer factorization, the discrete logarithm problem, or various lattice problems.

2.1 Partially Homomorphic Encryption (PHE)

Partially Homomorphic Encryption schemes represent the simplest form of homomorphic encryption, characterized by their ability to support an unlimited number of only one specific type of operation—either addition or multiplication—on encrypted data. While limited in their computational versatility, PHE schemes are generally much more efficient than their ‘somewhat’ or ‘fully’ homomorphic counterparts and find practical utility in specific, well-defined scenarios.

2.1.1 Multiplicatively Homomorphic Schemes: RSA

One of the earliest and most well-known examples of a multiplicatively homomorphic cryptosystem is RSA, proposed by Rivest, Adleman, and Dertouzos in 1978 [Rivest et al., 1978]. In RSA, the encryption of a plaintext message ‘m’ is given by E(m) = m^e mod n, where ‘e’ is the public exponent and ‘n’ is the modulus. If we have two encrypted messages, E(m1) and E(m2), their product in the ciphertext space behaves as follows:

E(m1) * E(m2) = (m1^e mod n) * (m2^e mod n)
= (m1^e * m2^e) mod n
= (m1 * m2)^e mod n

Upon decryption, this yields m1 * m2. Thus, RSA is multiplicatively homomorphic. However, RSA is not additively homomorphic, meaning it cannot perform additions on ciphertexts directly. Its utility is further limited by its susceptibility to certain attacks if used incorrectly and its general inefficiency for operations beyond simple multiplication.

2.1.2 Additively Homomorphic Schemes: Paillier and ElGamal

The Paillier cryptosystem, introduced by Pascal Paillier in 1999, is a prominent example of an additively homomorphic scheme [Paillier, 1999]. Its encryption function E(m) for a plaintext ‘m’ typically involves modular exponentiation. The core property of the Paillier scheme is that the product of two ciphertexts corresponds to the sum of their plaintexts:

D(E(m1) * E(m2)) = m1 + m2

More specifically, if E(m1) = g^m1 * r1^n mod n^2 and E(m2) = g^m2 * r2^n mod n^2, then:

E(m1) * E(m2) = (g^m1 * r1^n) * (g^m2 * r2^n) mod n^2
= g^(m1+m2) * (r1*r2)^n mod n^2

Decryption of this result yields m1 + m2. The Paillier cryptosystem is widely used in applications like secure voting, electronic cash systems, and privacy-preserving statistical analysis where only summation of values is required. Similarly, the ElGamal cryptosystem (under specific group operations) also exhibits additive homomorphism.

The primary limitation of PHE schemes is their inability to perform a combination of different operations or multiple operations of the same type in a flexible manner. Attempting to combine operations, such as adding and then multiplying, typically breaks the homomorphic property or renders the ciphertext undecryptable due to noise accumulation or structural incompatibilities.

2.2 Somewhat Homomorphic Encryption (SHE)

Somewhat Homomorphic Encryption schemes represent a significant step beyond PHE by supporting both addition and multiplication operations on encrypted data. This dual capability allows for the computation of arbitrary functions, provided those functions can be expressed as Boolean or arithmetic circuits. However, SHE schemes come with a crucial limitation: there is a predefined bound on the number or depth of homomorphic operations that can be performed before the accumulating ‘noise’ in the ciphertext becomes too large, rendering the ciphertext undecryptable.

2.2.1 The Challenge of Noise

The concept of ‘noise’ is central to lattice-based homomorphic encryption, which forms the basis for most modern SHE and FHE schemes. In these systems, a ciphertext is essentially a representation of the plaintext plus a small, carefully chosen random error term (the ‘noise’). This noise is essential for security, ensuring that the ciphertext appears random to an adversary. However, with each homomorphic operation (especially multiplication), the noise component tends to grow. If the noise grows beyond a certain threshold, the decryption function can no longer distinguish the original plaintext from the noise, and decryption fails.

SHE schemes can typically perform a limited number of operations, often referred to as a ‘multiplicative depth.’ For instance, a SHE scheme might allow for two multiplications followed by several additions, but attempting a third multiplication might push the noise past the acceptable limit. This means that SHE schemes are only suitable for computing functions that can be represented by circuits of limited depth.

Some of the early constructions towards FHE, including Gentry’s initial scheme before the bootstrapping component, were essentially SHE schemes. While not universally applicable like FHE, SHE schemes can be highly efficient for specific computations that fit within their operational depth limits, providing a bridge between the highly constrained PHE and the full generality of FHE.

2.3 Fully Homomorphic Encryption (FHE)

Fully Homomorphic Encryption schemes are the ultimate goal in homomorphic cryptography, capable of supporting an arbitrary number of both addition and multiplication operations on ciphertexts without any predefined limits on the computational depth or complexity. This means an FHE scheme can compute any function representable as an arithmetic or Boolean circuit on encrypted data, making it universally applicable for privacy-preserving computation.

2.3.1 Gentry’s Breakthrough and Bootstrapping

The theoretical possibility of FHE was first proven by Craig Gentry in 2009 in his seminal Ph.D. dissertation [Gentry, 2009]. His breakthrough addressed the noise accumulation problem inherent in SHE schemes through an ingenious technique called ‘bootstrapping.’

Bootstrapping is a homomorphic refreshing mechanism that allows a noisy ciphertext to be ‘cleaned’ or ‘re-encrypted’ into a fresh, less noisy ciphertext that encrypts the same plaintext. Conceptually, bootstrapping works by homomorphically evaluating the decryption circuit of the HE scheme itself. To do this, the secret decryption key is encrypted under the public key, and the decryption circuit is run on the noisy ciphertext, using this encrypted secret key. The output is a refreshed ciphertext that, upon decryption, yields the original plaintext but with significantly reduced noise.

The process can be summarized as:

1. A noisy ciphertext C is given.
2. The secret decryption key SK is encrypted under the public key: E(SK).
3. The decryption function D(C, SK) is homomorphically evaluated using the noisy ciphertext C and the encrypted secret key E(SK).
4. The result is E(plaintext), which is a new, less noisy ciphertext encrypting the original plaintext.

Gentry’s innovation was the idea of ‘squashing’ the decryption circuit—making it simple enough to be homomorphically evaluated before the noise became too overwhelming. The ability to bootstrap indefinitely means that FHE schemes can theoretically compute circuits of infinite depth, thus achieving full homomorphism. While computationally expensive, bootstrapping is the cornerstone that distinguishes FHE from SHE.

2.3.2 Lattice-Based Cryptography

Modern FHE schemes are predominantly based on lattice-based cryptography, which relies on the computational hardness of certain problems on mathematical lattices. The most common underlying hard problems are the Learning With Errors (LWE) problem and its ring-based variant, Ring-LWE (RLWE). These problems are considered resistant even to quantum computer attacks, making lattice-based FHE a promising candidate for post-quantum cryptography [Regev, 2005].

In LWE, an adversary tries to recover a secret vector ‘s’ given a set of linear equations in a finite field, where each equation is perturbed by a small random ‘error’ or ‘noise’ term. The hardness of LWE makes it suitable for constructing encryption schemes where ciphertexts inherently contain noise. The mathematical properties of lattices allow for controlled noise growth during homomorphic operations, which is crucial for the successful application of bootstrapping.

2.3.3 Key FHE Families

Since Gentry’s breakthrough, several FHE schemes have been developed, each with different optimizations and characteristics:

• BGV (Brakerski-Gentry-Vaikuntanathan, 2011): This scheme was one of the first practical FHE constructions, introducing ‘levelled FHE’ where computations are arranged in levels, and noise growth is carefully managed without immediate bootstrapping for every operation. It often uses Residue Number System (RNS) for efficient arithmetic [Brakerski et al., 2011].
• BFV (Brakerski/Fan-Vercauteren, 2012/2013): Similar to BGV, BFV is also a RNS-friendly scheme that supports operations on integers. It is often favored for exact computations and is widely implemented in FHE libraries like Microsoft SEAL and HElib [Fan & Vercauteren, 2012].
• CKKS (Cheon-Kim-Kim-Song, 2017): This scheme is revolutionary as it supports approximate arithmetic, making it ideal for computations involving real numbers or floating-point numbers, such as those found in machine learning algorithms. CKKS manages noise differently, allowing for a controlled loss of precision rather than requiring exact results, which significantly improves efficiency for approximate computations [Cheon et al., 2017].
• TFHE/FHEW (Torrent, FHEW team, 2016 onwards): These schemes are optimized for very fast bootstrapping, making them highly suitable for evaluating Boolean circuits and operating on small plaintext spaces (e.g., bits). They are particularly efficient for applications requiring fast, iterative operations on binary data or low-precision integers [Chillotti et al., 2016].

The continuous development of these FHE schemes, along with optimized implementations in open-source libraries, signifies the maturation of the field and its increasing move towards practical applicability.

Many thanks to our sponsor Esdebe who helped us prepare this research report.

3. Evolution and Development of Homomorphic Encryption: A Journey to Practicality

The trajectory of homomorphic encryption, from an abstract concept to a burgeoning field of applied cryptography, spans over four decades. This evolution has been marked by periods of theoretical stagnation, sudden breakthroughs, and continuous refinement aimed at bridging the gap between theoretical possibility and practical utility.

3.1 Early Conceptualizations and the ‘Holy Grail’ (Pre-2009)

The foundational idea of computing on encrypted data was first introduced in 1978 by Ron Rivest, Len Adleman, and Michael Dertouzos, the very pioneers of RSA encryption [Rivest et al., 1978]. They posed the question: ‘Is it possible to construct an encryption scheme which permits one to operate on encrypted messages without knowing the decryption key?’ This question laid the groundwork for the field, but for many years, the answer remained elusive for schemes capable of arbitrary computations. Researchers developed partial homomorphic schemes like RSA and Paillier, proving the concept for specific operations, but a scheme capable of both addition and multiplication for an unlimited number of times was widely considered the ‘holy grail’ of cryptography—a theoretically profound but practically unattainable goal.

Early attempts at constructing FHE schemes faced insurmountable challenges related to noise management and computational overhead. Any operation on encrypted data tended to increase the ‘noise’ or ‘error’ component within the ciphertext, eventually making decryption impossible. The computational complexity of even the simplest operations on encrypted data made any theoretical construction impractical for real-world use cases.

3.2 Gentry’s Breakthrough and the First Generation (2009)

The landscape of homomorphic encryption was irrevocably altered in 2009 when Craig Gentry, then a Ph.D. student at Stanford University, published his groundbreaking dissertation, ‘A Fully Homomorphic Encryption Scheme’ [Gentry, 2009]. Gentry’s work provided the first plausible construction for an FHE scheme. His design was based on ideal lattices, a specialized type of mathematical lattice, and crucially introduced the technique of ‘bootstrapping’ (as detailed in Section 2.3.1). While Gentry’s initial scheme was revolutionary in proving the concept, it was prohibitively slow. Operations were estimated to be orders of magnitude slower than plaintext operations, and the ciphertext sizes were enormous. However, its theoretical significance was immense; it shifted FHE from an impossibility to a complex but achievable goal, inspiring a surge of research activity.

3.3 Second-Generation Schemes: Efficiency and Leveled FHE (2010-2015)

Following Gentry’s breakthrough, researchers rapidly sought to improve the efficiency and practicality of FHE. This period saw the development of ‘second-generation’ schemes that focused on reducing computational overhead and refining noise management techniques. A key innovation during this period was the concept of ‘leveled FHE,’ where schemes are designed to support a predetermined maximum number of homomorphic operations without needing to invoke the expensive bootstrapping procedure for every operation. Bootstrapping would only be required if the computation exceeded this predefined depth.

• BGV (Brakerski-Gentry-Vaikuntanathan, 2011): This scheme, developed by Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan, offered significant improvements over Gentry’s original construction [Brakerski et al., 2011]. BGV introduced techniques for ‘modulus switching’ and ‘scale-invariant’ encryption, which helped manage noise more effectively and allowed for more flexible control over parameters, leading to more efficient operations. It was also one of the first schemes to leverage the ‘Learning With Errors’ (LWE) and ‘Ring-LWE’ (RLWE) problems, which offer strong security guarantees and are amenable to efficient implementation.
• BFV (Brakerski/Fan-Vercauteren, 2012/2013): Independently developed by Brakerski and later by Fan and Vercauteren, the BFV scheme is another prominent second-generation FHE scheme [Brakerski, 2012; Fan & Vercauteren, 2012]. Similar to BGV, BFV also utilizes RLWE and modulus switching. It is often considered simpler to implement than BGV for exact integer arithmetic and has become one of the most widely adopted schemes in various FHE libraries for computations requiring precise results.
• LTV (Lopez-Alt, Tromer, Vaikuntanathan, 2012): This scheme, developed by Alfonso Lopez-Alt, Eran Tromer, and Vinod Vaikuntanathan, explored the use of NTRU-based lattices, offering an alternative approach to constructing FHE [Lopez-Alt et al., 2012]. While it showed promise, BGV and BFV based on RLWE gained more widespread adoption due to their flexibility and proven security properties.

These second-generation schemes marked a significant step towards making FHE viable for practical applications by improving efficiency and establishing a robust theoretical framework for leveled FHE.

3.4 Third and Fourth-Generation Schemes: Practicality, Approximate Numbers, and Fast Bootstrapping (2016-Present)

The most recent generations of FHE schemes have focused on further optimizing performance, broadening applicability, and making HE more accessible to developers. This includes schemes tailored for specific types of computations and major advancements in bootstrapping efficiency.

• CKKS (Cheon-Kim-Kim-Song, 2017): Perhaps one of the most impactful developments for practical applications, the CKKS scheme (named after Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song) introduced homomorphic encryption for arithmetic of approximate numbers [Cheon et al., 2017]. Unlike earlier schemes that require exact integer arithmetic, CKKS allows for computations on real or complex numbers with controlled precision loss. This is crucial for applications like machine learning, where floating-point operations are ubiquitous. CKKS manages noise growth by rescaling ciphertexts, sacrificing some precision at each step but preventing noise from overwhelming the signal. This design makes CKKS highly efficient for many practical tasks, especially privacy-preserving machine learning.
• TFHE/FHEW (Torrent, FHEW team, 2016 onwards): These schemes, primarily driven by Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachene for TFHE, and others for FHEW, focused on dramatically improving the speed of the bootstrapping operation itself [Chillotti et al., 2016]. TFHE (Torque FHE) and FHEW (Faster Homomorphic Encryption for Wires) are optimized for Boolean circuits (bit-level operations) and small plaintext integers. Their innovation lies in achieving extremely fast, ‘bootstrapping on-the-fly,’ which significantly reduces the latency for certain types of computations. This makes them particularly suitable for private inference on small neural networks, encrypted comparison operations, and general circuits that operate on binary data.

3.4.1 Libraries and Standardization Efforts

Concurrent with the algorithmic advancements, significant effort has been directed towards developing robust and user-friendly open-source FHE libraries. These libraries abstract away much of the underlying mathematical complexity, making FHE accessible to a broader range of developers:

• Microsoft SEAL (Simple Encrypted AI Library): A widely used library supporting BFV and CKKS schemes, maintained by Microsoft Research.
• HElib: Developed by IBM Research, HElib implements BGV and CKKS, pioneering techniques like ‘batching’ and ‘bootstrapping’ within a library context.
• OpenFHE: An open-source FHE library initiated by DARPA, unifying and providing a common API for various FHE schemes (BFV, BGV, CKKS, TFHE) and promoting interoperability.
• Concrete (FHE.org): A library focused on TFHE-style schemes, offering highly optimized implementations for boolean and integer operations.
• Lattigo: A Go library for lattice-based cryptography, implementing BFV, CKKS, and TFHE.

These libraries, along with initiatives like homomorphicencryption.org, which works towards standardization and interoperability, are crucial for driving the adoption and practical deployment of FHE solutions.

3.4.2 Hardware Acceleration

Given the inherent computational intensity of FHE, hardware acceleration is emerging as a vital area of research and development. Specialized hardware, such as Field-Programmable Gate Arrays (FPGAs) and Application-Specific Integrated Circuits (ASICs), are being designed to accelerate computationally heavy operations like polynomial multiplications, number-theoretic transforms (NTTs), and bootstrapping. These hardware solutions promise to significantly reduce the execution time and energy consumption of FHE computations, potentially making real-time FHE applications viable in the future.

Many thanks to our sponsor Esdebe who helped us prepare this research report.

4. Practical Applications Across Industries: Secure Data in Action

Homomorphic encryption’s unique ability to process data while maintaining its encrypted state opens up a vast array of possibilities across numerous industries, fundamentally transforming how organizations can leverage sensitive information without compromising privacy or regulatory compliance.

4.1 Healthcare: Safeguarding Patient Data

Healthcare is arguably one of the most critical sectors where HE can have a transformative impact. The highly sensitive nature of patient health information (PHI) necessitates stringent privacy measures, often hindering collaborative research and advanced analytics. HE enables:

• Secure Genomic Data Analysis: Researchers can analyze encrypted genomic datasets to identify disease markers, predict predispositions, and develop personalized medicine without ever seeing individual genetic sequences in plaintext. For example, a pharmaceutical company could collaborate with multiple hospitals to analyze encrypted patient genomes to find correlations with drug efficacy or side effects, without any single entity needing access to the raw genetic data [Canpolat et al., 2023].
• Privacy-Preserving Electronic Health Records (EHR) Processing: Hospitals and clinics can store EHRs in an encrypted format in the cloud and perform complex queries (e.g., ‘find all patients over 60 with a specific blood pressure range and a history of heart disease’) directly on the encrypted data, allowing for population health management and improved diagnostics while ensuring PHI remains confidential.
• Collaborative Medical Research: Multiple research institutions can pool encrypted datasets for large-scale studies on rare diseases, drug discovery, or epidemiological patterns, overcoming data silo issues and accelerating medical breakthroughs without exposing sensitive patient details.
• Telemedicine and Remote Patient Monitoring: Data from wearable health devices or remote consultations can be encrypted and analyzed to detect anomalies or track patient progress, ensuring that highly personal health metrics are never revealed to unauthorized parties, including the service provider.

4.2 Finance: Fortifying Financial Security and Compliance

The financial sector deals with vast quantities of highly sensitive transactional and personal financial data, making privacy and regulatory compliance (e.g., GDPR, CCPA) paramount. HE offers robust solutions for:

• Advanced Fraud Detection: Financial institutions can utilize HE to analyze encrypted transaction patterns across multiple banks or accounts to detect sophisticated fraud schemes and anomalies in real-time, without any single institution needing access to the plaintext transaction details of others. This enables a more holistic view of potential threats while maintaining individual customer privacy.
• Privacy-Preserving Risk Assessment and Credit Scoring: Banks can assess loan applications or calculate credit scores based on encrypted financial profiles, ensuring that sensitive income, debt, and spending habits remain confidential. This allows for more accurate and fair risk models without exposing personal financial data to credit bureaus or other intermediaries.
• Anti-Money Laundering (AML) and Sanctions Screening: HE can facilitate secure cross-institutional analysis of suspicious transaction patterns for AML compliance. Banks can submit encrypted customer transaction data to a central analytics engine, which can identify potential money laundering activities or sanction violations without decrypting any individual customer’s data, thus safeguarding privacy while enhancing national security.
• Secure Financial Product Development: Financial analysts can test and optimize complex investment strategies or derivatives models using encrypted market data, ensuring proprietary algorithms and sensitive market insights remain protected even when processed in shared environments.

4.3 Cloud Computing: Trusting the Untrusted Cloud

Cloud computing inherently involves entrusting data to third-party providers, which raises significant privacy concerns. HE fundamentally changes this dynamic, allowing users to leverage cloud infrastructure without compromising data confidentiality:

• Secure Data Outsourcing and Processing: Clients can store sensitive data (e.g., intellectual property, confidential business reports) on cloud servers in an encrypted format. They can then delegate computational tasks to the cloud, such as data analytics, database queries, or statistical analysis, all performed on the encrypted data. The cloud provider never gains access to the plaintext, thus becoming an ‘untrusted’ but secure computing environment.
• Encrypted Database Management Systems (DBMS): HE enables encrypted SQL queries on encrypted databases. Users can search, filter, and aggregate data without exposing the content of the database or the query itself to the database server. This is a game-changer for data privacy in cloud-hosted databases.
• Confidential Serverless Computing: Functions in serverless architectures can operate on encrypted inputs, produce encrypted outputs, and store encrypted intermediate results. This extends the privacy guarantee to dynamic, event-driven computation models.

4.4 Government and Defense: Intelligence and Public Services

Governments and defense agencies handle some of the most sensitive and classified information, making HE a powerful tool for secure data sharing and analysis:

• Secure Intelligence Analysis: Agencies can securely combine and analyze encrypted intelligence data from various sources (e.g., different departments, allied nations) to identify threats, anticipate geopolitical shifts, or optimize resource allocation, without needing to decrypt the raw intelligence. This enables more comprehensive analysis while maintaining strict classification boundaries.
• Privacy-Preserving Public Services: For public welfare programs, census data analysis, or epidemiological studies, government bodies can process aggregated encrypted demographic data to inform policy decisions, ensuring individual citizens’ privacy is protected while leveraging valuable population-level insights.
• Secure Multi-Party Data Sharing: Collaborations between different government departments or international bodies often involve sensitive data. HE can facilitate joint analysis of encrypted datasets, enabling collective decision-making without revealing confidential information to all participating parties.

4.5 Artificial Intelligence and Machine Learning: Privacy-Preserving AI (PPAI)

The convergence of AI and HE is a rapidly evolving field, addressing the critical need for privacy in machine learning, where models often train on vast amounts of sensitive personal data:

• Training Models on Encrypted Data: HE allows machine learning models (e.g., linear regression, logistic regression, decision trees, and increasingly, simpler neural networks) to be trained directly on encrypted datasets. This means sensitive training data (e.g., medical images, financial records) can be used to build powerful AI models without ever exposing individual records to the model developer or cloud infrastructure [Phong et al., 2017].
• Confidential Inference: Once a model is trained (either on plaintext or encrypted data), HE can be used for privacy-preserving inference. A user can submit encrypted input data (e.g., an encrypted image for classification, an encrypted query for a recommendation system) to an encrypted model. The model computes the prediction on the encrypted input, and the result is returned as an encrypted output, which only the user can decrypt. This ensures that both the input query and the model’s prediction remain private.
• Federated Learning with Enhanced Privacy: In federated learning, models are trained locally on decentralized datasets, and only model updates (gradients) are aggregated. HE can further enhance this by encrypting these model updates before aggregation, protecting against inference attacks on gradients and ensuring that the central aggregator cannot glean information about individual participants’ data [Bonawitz et al., 2017].

4.6 Other Emerging Applications

• Blockchain and Cryptocurrencies: HE can enable private smart contracts where computation on confidential data can occur without revealing the underlying values on a public ledger. It can also enhance privacy for transactions, allowing verification without disclosing sender, receiver, or amount.
• Secure Voting Systems: For electronic voting, HE can be used to tally encrypted votes, ensuring that individual votes remain secret while guaranteeing the accuracy of the final count.
• Supply Chain Management: Companies can securely share encrypted sensitive data (e.g., production costs, inventory levels, supplier performance) with partners to optimize supply chain operations without revealing proprietary information.

Many thanks to our sponsor Esdebe who helped us prepare this research report.

5. Performance Considerations and Enduring Challenges

While homomorphic encryption offers unparalleled privacy guarantees, its practical deployment is intrinsically linked to overcoming significant performance challenges. The computational complexity inherent in HE schemes, particularly FHE, necessitates careful consideration of various trade-offs.

5.1 Computational Overhead

The most prominent challenge for HE is its substantial computational overhead. Operations performed on ciphertexts are orders of magnitude slower and more resource-intensive than their plaintext counterparts. This overhead can range from 10^3 to 10^6 times slower, depending on the scheme, parameters, and the complexity of the operation [Albrecht et al., 2017].

• Polynomial Arithmetic: Modern HE schemes, especially lattice-based ones, rely heavily on polynomial arithmetic over finite fields. These operations involve large polynomials (often with thousands or tens of thousands of coefficients) and modular reductions, which are computationally expensive.
• Ciphertext and Key Expansion: Encrypting even a small piece of data results in a significantly larger ciphertext (often thousands of times larger than the plaintext). Similarly, public keys and evaluation keys (used for homomorphic operations) can be very large, consuming considerable memory and requiring more computation during key setup and use.
• Modular Operations: All arithmetic in HE schemes is performed modulo large prime numbers. These modular operations, particularly modular inversions and exponentiations, add to the computational burden.

The high computational cost limits HE’s applicability in real-time or latency-sensitive applications. Current applications often focus on scenarios where batch processing or offline computation is acceptable, or where the privacy benefits strongly outweigh the performance penalties.

5.2 Noise Management and Bootstrapping Cost

As discussed, noise accumulation is a fundamental aspect of lattice-based HE. While essential for security, its growth with each operation poses a significant challenge.

• Bootstrapping as a Bottleneck: Bootstrapping, the process of refreshing a noisy ciphertext, is the most computationally intensive operation in an FHE scheme. While it enables arbitrary computation depth, its high cost often dictates the overall performance of FHE applications. Optimizing bootstrapping has been a major focus of research (e.g., TFHE/FHEW schemes).
• Leveled FHE and Parameter Selection: To mitigate the frequent use of bootstrapping, many applications leverage ‘leveled FHE.’ In this approach, parameters are chosen to support a specific, maximum number of homomorphic operations (a ‘multiplicative depth’) without requiring bootstrapping within that limit. If the computation exceeds this depth, bootstrapping becomes necessary. The selection of these parameters is a delicate balance between security, efficiency, and the desired computational depth.
• Noise Reduction Techniques: Besides bootstrapping, techniques like key switching and ciphertext modulus reduction (e.g., in BGV/BFV via modulus switching or in CKKS via rescaling) are employed to manage noise more efficiently during homomorphic operations. These techniques contribute to the overall complexity and performance characteristics of the schemes.

5.3 Scalability and Resource Consumption

Beyond raw computational speed, scalability remains a critical concern for HE, particularly FHE:

• Ciphertext Size and Communication Overhead: The large size of ciphertexts significantly impacts storage requirements and network bandwidth. Storing and transmitting encrypted data generated by HE schemes can be prohibitively expensive, especially for large datasets or real-time communication.
• Key Management and Size: Public keys for FHE can be massive, often in the order of hundreds of megabytes to gigabytes. This impacts key distribution, storage, and the initial setup time for cryptographic contexts. Evaluation keys, used for operations like homomorphic multiplication and key switching, can be even larger.
• Memory Footprint: FHE operations, especially bootstrapping, can consume substantial amounts of RAM, often several gigabytes, limiting deployment on resource-constrained devices or large-scale cloud environments without careful optimization.

Addressing scalability issues requires innovations not just in algorithms but also in efficient implementations, memory management, and potentially specialized hardware architectures.

5.4 Development Complexity and Tooling

Despite the availability of libraries, developing applications using HE still presents a steep learning curve for many programmers. The intricacies of parameter selection, understanding noise budgets, optimizing circuit design for homomorphic operations, and debugging on encrypted data require specialized cryptographic knowledge. While libraries like SEAL and HElib simplify parts of the process, they do not entirely remove the need for deep understanding. The tooling and compiler support for automatically converting arbitrary code into homomorphic circuits are still in nascent stages.

5.5 Security vs. Efficiency Trade-offs

There is an inherent trade-off between the security level (e.g., 128-bit, 256-bit security) and the efficiency of an HE scheme. Higher security levels typically require larger parameters (e.g., higher polynomial degrees, larger moduli), which directly translate to increased ciphertext sizes, slower operations, and higher resource consumption. Choosing the appropriate security level is a crucial design decision that balances cryptographic robustness with practical performance requirements.

Many thanks to our sponsor Esdebe who helped us prepare this research report.

6. Distinctions Between Partial and Fully Homomorphic Encryption: A Spectrum of Capabilities

Understanding the fundamental differences between Partially Homomorphic Encryption (PHE), Somewhat Homomorphic Encryption (SHE), and Fully Homomorphic Encryption (FHE) is crucial for selecting the most appropriate scheme for a given application. They represent a spectrum of capabilities, efficiency, and complexity.

6.1 Operational Capabilities and Flexibility

• Partially Homomorphic Encryption (PHE): PHE schemes are the most restrictive. They support an unlimited number of only one type of operation. For instance, RSA is exclusively multiplicatively homomorphic, while Paillier is exclusively additively homomorphic. This means a PHE scheme can perform only additions, or only multiplications, but cannot combine them or switch between them. Their ‘computational depth’ is effectively limited to one operation chain of a specific type.

  • Example: Securely summing votes in an election (Paillier) or calculating the product of encrypted values (RSA).

• Somewhat Homomorphic Encryption (SHE): SHE schemes offer greater flexibility than PHE by supporting both addition and multiplication operations. This allows them to compute arbitrary functions expressible as arithmetic or Boolean circuits. However, they are limited by a fixed, small number of operations or a finite multiplicative depth before noise accumulation renders the ciphertext undecryptable. They cannot be ‘refreshed’ via bootstrapping to extend this depth indefinitely.

  • Example: Evaluating a simple machine learning model like logistic regression, which involves a fixed number of multiplications and additions, or a shallow decision tree.

• Fully Homomorphic Encryption (FHE): FHE schemes represent the pinnacle of homomorphic capabilities. They support an arbitrary number of both addition and multiplication operations, enabling the computation of any function on encrypted data. This ‘unlimited depth’ is achieved through the crucial bootstrapping mechanism, which periodically refreshes the noise level of ciphertexts, allowing computations to continue indefinitely.

  • Example: Complex data analytics pipelines, deep neural network inference, or secure general-purpose cloud computing where the exact computational requirements are unknown or highly variable.

6.2 Performance and Resource Efficiency

• PHE: These are generally the most efficient in terms of computational speed, ciphertext size, and key size. Their limited operational capabilities simplify the underlying mathematics and reduce the cryptographic overhead. They are often performant enough for specific, constrained tasks.

  • Efficiency: High.
  • Ciphertext/Key Size: Smallest.

• SHE: SHE schemes are less efficient than PHE but more efficient than FHE. They incur moderate computational overhead and generate larger ciphertexts and keys than PHE due to the need to support multiple types of operations and manage limited noise growth. The absence of frequent bootstrapping contributes to their relatively better performance compared to FHE.

  • Efficiency: Moderate.
  • Ciphertext/Key Size: Moderate.

• FHE: FHE schemes are the least efficient in their current state, exhibiting the highest computational overhead, largest ciphertext sizes, and largest key sizes. The complexity arises from the need to support arbitrary operations and, most notably, the computational cost of bootstrapping. Bootstrapping is often the dominant factor in FHE performance, making FHE significantly slower and more resource-intensive than PHE or SHE.

  • Efficiency: Low (highest overhead).
  • Ciphertext/Key Size: Largest.

6.3 Practical Applicability and Use Cases

• PHE: Best suited for applications where the exact computational task is known in advance and involves only a single type of operation. Examples include secure summation (e.g., voting, aggregated statistics), private information retrieval (PIR) using specific homomorphic properties, or simple private set intersection. PHE schemes are often easier to implement and deploy for these niche applications.

• SHE: Applicable to scenarios requiring a fixed, limited computational depth, where the privacy benefits justify the moderate overhead. This includes simpler privacy-preserving machine learning models (e.g., training a shallow neural network or logistic regression classifier), specific secure querying of databases, or evaluating fixed-depth logical circuits.

• FHE: Ideal for applications demanding maximum flexibility and the ability to perform arbitrarily complex computations on encrypted data. This encompasses generic privacy-preserving cloud computing, complex multi-party data analytics, deep learning inference and potentially training, secure delegated computation, and confidential smart contracts. While still facing performance challenges, FHE is the only solution for truly general-purpose privacy-preserving computation.

In summary, the choice among PHE, SHE, and FHE is a practical one, driven by the specific computational requirements, acceptable performance overhead, and the desired level of privacy and flexibility. As research progresses, the performance gap between these categories continues to narrow, making FHE increasingly viable for a wider range of applications.

Many thanks to our sponsor Esdebe who helped us prepare this research report.

7. Conclusion: The Promise and Path Forward for Homomorphic Encryption

Homomorphic encryption represents a profound paradigm shift in cryptography, offering a transformative capability to perform meaningful computations directly on encrypted data without ever exposing the underlying plaintext. This unique property is not merely an incremental improvement; it fundamentally redefines the boundaries of data privacy and security in an increasingly data-centric and interconnected world. From its early theoretical conception in the late 1970s to Craig Gentry’s groundbreaking proof-of-concept in 2009, and through the subsequent generations of efficiency-focused schemes like BGV, BFV, CKKS, and TFHE, the field has matured rapidly. What was once considered an intractable cryptographic ‘holy grail’ is now a tangible, albeit complex, reality.

The widespread applicability of HE spans critical sectors, including healthcare, finance, cloud computing, government, and artificial intelligence. It promises to unlock new possibilities for collaborative data analysis, secure outsourcing, and privacy-preserving machine learning, enabling organizations to extract valuable insights from sensitive data while rigorously upholding confidentiality and complying with evolving data protection regulations. The ability to conduct genomic research without revealing individual patient data, detect financial fraud without exposing customer transactions, or train AI models on encrypted datasets without compromising personal privacy exemplifies the profound societal impact that HE is poised to deliver.

Despite these remarkable advancements and immense potential, significant challenges persist. The primary hurdles remain the substantial computational overhead, particularly associated with bootstrapping in FHE schemes, and the resultant large ciphertext and key sizes, which impact scalability and resource consumption. The current performance characteristics often limit HE to batch processing or applications where latency is not a critical constraint. Furthermore, the inherent complexity of HE schemes necessitates a steep learning curve for developers, hindering broader adoption outside of specialized cryptographic research teams. While open-source libraries have significantly democratized access, the journey towards truly user-friendly and highly optimized development environments is ongoing.

Looking ahead, the trajectory of homomorphic encryption is one of continued innovation and refinement:

• Algorithmic Optimization: Ongoing research will undoubtedly yield even more efficient HE schemes and more sophisticated bootstrapping techniques, pushing the boundaries of what is computationally feasible. Hybrid schemes that combine different HE approaches or integrate HE with other privacy-enhancing technologies like Secure Multi-Party Computation (SMC) or Trusted Execution Environments (TEEs) are also promising avenues.
• Hardware Acceleration: The development of specialized hardware (FPGAs, ASICs) designed to accelerate the computationally intensive polynomial arithmetic and number-theoretic transforms central to HE will be crucial. These hardware solutions promise to bridge the performance gap, potentially enabling real-time HE applications.
• Software Engineering and Tooling: Efforts to create high-level programming languages, compilers, and debugging tools that automatically transform general-purpose code into homomorphic circuits will be vital for mainstream adoption. Abstraction layers that shield developers from the intricate cryptographic details will empower a broader community to build HE-powered applications.
• Standardization and Interoperability: Continued collaboration through initiatives like homomorphicencryption.org will foster standardization, ensuring interoperability between different HE libraries and promoting a robust ecosystem for development and deployment.

In conclusion, homomorphic encryption stands as a pivotal technology for the future of digital privacy and secure computation. While challenges related to performance, scalability, and ease of development remain formidable, the relentless pace of research and development is steadily transforming HE from a theoretical marvel into a practical tool. As the demand for robust data privacy continues to escalate globally, homomorphic encryption is poised to play an increasingly central and indispensable role in safeguarding sensitive information, fostering trust, and enabling new paradigms of secure data utility in an increasingly digital and interconnected world.

Many thanks to our sponsor Esdebe who helped us prepare this research report.

References

• Albrecht, M. R., Curtis, S., & Deo, J. (2017). A Survey of Homomorphic Encryption in the Wild. Cryptology ePrint Archive, Report 2017/1169.
• Bonawitz, K., et al. (2017). Practical Secure Aggregation for Federated Learning on User-Held Data. arXiv preprint arXiv:1710.06963.
• Brakerski, Z. (2012). Fully Homomorphic Encryption from Ring-LWE and Error Correction. Advances in Cryptology – CRYPTO 2012. Springer, Berlin, Heidelberg.
• Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2011). Fully Homomorphic Encryption without Bootstrapping. Advances in Cryptology – CRYPTO 2011. Springer, Berlin, Heidelberg.
• Canpolat, Y., et al. (2023). A Survey on Privacy-Preserving Approaches for Genomic Data in Healthcare. Future Internet, 15(2), 70.
• Cheon, J. H., Kim, A., Kim, M., & Song, Y. (2017). Homomorphic Encryption for Arithmetic of Approximate Numbers. Advances in Cryptology – ASIACRYPT 2017. Springer, Cham.
• Chillotti, I., Gama, N., Georgieva, M., & Izabachene, M. (2016). Faster Homomorphic Encryption in Practice. International Conference on the Theory and Application of Cryptology and Information Security – ASIACRYPT 2016. Springer, Berlin, Heidelberg.
• Fan, J., & Vercauteren, F. (2012). Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144.
• Gentry, C. (2009). A Fully Homomorphic Encryption Scheme. Ph.D. dissertation, Stanford University.
• Lopez-Alt, A., Tromer, E., & Vaikuntanathan, V. (2012). On-the-Fly Multiparty Computation on the Cloud via Fully Homomorphic Encryption. Proceedings of the forty-fourth annual ACM symposium on Theory of computing.
• Paillier, P. (1999). Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Advances in Cryptology – EUROCRYPT ’99. Springer, Berlin, Heidelberg.
• Phong, L. T., et al. (2017). Privacy-preserving deep learning. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security.
• Regev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing.
• Rivest, R. L., Adleman, L., & Dertouzos, M. L. (1978). On Data Banks and Privacy Homomorphisms. Foundations of Secure Computation.