Fully Homomorphic Encryption: Cryptography for Cloud Protection
Introduction
In recent years, the adoption of Cloud Computing solutions has grown significantly thanks to the economic, performance, and scalability benefits offered by the services of major international providers. These platforms make it possible to reduce the management costs of on-premise infrastructures, facilitating the sharing and processing of large amounts of data while integrating advanced Machine Learning (ML)-based tools. However, entrusting data to external providers can introduce significant confidentiality risks, especially in sensitive contexts (such as Defense and Healthcare), where information sharing is subject to strict regulatory constraints and high confidentiality requirements.
From a security perspective, three states can be distinguished in which data may exist throughout its lifecycle:
- Data-in-transit: refers to data during transmission between different devices, users, or systems.
- Data-at-rest: refers to data stored on physical or virtual storage media, such as local disks, databases, and Cloud infrastructures.
- Data-in-use: includes data while being processed by applications or computer systems, for example, during the execution of Machine Learning algorithms.
While the first two states can be effectively protected using established cryptographic techniques, such as Diffie-Hellman for key exchange and AES for encryption, protecting data in use remains a significant challenge, since traditional processing generally requires data to be available in plaintext. To address this issue, several cryptographic techniques have been developed, including Multi-Party Computation (MPC), which allows multiple participants to jointly compute a function over their respective private inputs while preserving confidentiality through an interactive protocol, and Functional Encryption (FE), which enables a user holding a specific decryption key to obtain the result of evaluating a given function on encrypted data without directly accessing the plaintext message. Among the techniques aimed at ensuring the confidentiality of data-in-use, Homomorphic Encryption (HE) is also particularly relevant. This cryptographic technique makes it possible to perform operations directly on encrypted data without having to decrypt it during processing.
Fully Homomorphic Encryption
The term Homomorphic Encryption derives from the mathematical concept of homomorphism, which describes the property of preserving certain operations between two structures. In cryptography, this property makes it possible to perform operations on encrypted data and obtain a result that, once decrypted, corresponds to the result that would have been obtained by applying the same operations to the plaintext data. Formally, given an encryption algorithm Enc() and two operations \ast_1 and \ast_2, a cryptographic scheme is said to be homomorphic with respect to these operations if, for every pair of messages m_1 and m_2 belonging to the message space, the following relation holds:
Enc(m_1) \ast_2 Enc(m_2) = Enc(m_1 \ast_1 m_2)
This property allows operations to be performed directly on encrypted data, producing a ciphertext corresponding to the result of the operation on the plaintext messages. By combining multiple homomorphic operations, it is therefore possible to evaluate more complex functions without decrypting the data.
Based on the supported operations and evaluation limits, homomorphic encryption schemes can be divided into three main categories:
- PHE (Partially Homomorphic Encryption): allows a single type of homomorphic operation, such as addition or multiplication, to be performed an arbitrary number of times;
- SHE (Somewhat Homomorphic Encryption): supports multiple types of homomorphic operations, but within specific limits on the number of evaluations that can be performed;
- FHE (Fully Homomorphic Encryption): allows arbitrary computational circuits to be evaluated on encrypted data, without intrinsic limits on computation depth.
History
The first ideas concerning the possibility of performing operations directly on encrypted data date back to 1978, with the paper “On Data Banks and Privacy Homomorphisms” by Rivest, Adleman, and Dertouzos. In the following decades, cryptographic research led to the development of numerous PHE and SHE schemes, while the implementation of an FHE scheme still seemed out of reach. A major breakthrough occurred in 2009, when Craig Gentry presented the first FHE scheme in his doctoral dissertation, demonstrating the feasibility of encryption capable of supporting arbitrarily complex computations on encrypted data. His work also introduced the concept of bootstrapping, a fundamental mechanism for constructing fully homomorphic schemes, which laid the foundation for subsequent developments and will be described in greater detail below.
In the following years, research led to continuous performance improvements, giving rise to several generations of FHE schemes. Gentry’s 2009 proposal is generally regarded as the first generation of FHE schemes, while the second generation includes schemes such as BGV and BFV, which introduced significant efficiency improvements and paved the way for the first practical applications. The third generation, comprising schemes such as FHEW and TFHE, further optimized homomorphic operations and the bootstrapping process. Finally, the CKKS scheme, introduced in 2016 and associated with the so-called fourth generation, expanded the application possibilities of FHE, particularly through its support for operations on real and approximate values, making it especially suitable for processing data in Machine Learning algorithms.
Learning With Errors (LWE) and Bootstrapping
Most Fully Homomorphic Encryption (FHE) schemes base their computational security on the Learning With Errors (LWE) problem, whose difficulty stems from the presence of an error vector introduced during encryption, which makes it computationally difficult to recover either the plaintext message or the secret key. Although this error is essential to the security of the scheme, it tends to increase as homomorphic operations are performed, with its growth depending on the type and number of operations carried out. When the error exceeds a certain threshold, determined by the chosen cryptographic parameters, the correctness of decryption can no longer be guaranteed. Therefore, supporting an arbitrary number of homomorphic operations requires a mechanism capable of reducing the accumulated error without compromising the correctness of the computations.
To address this issue, in 2009 Craig Gentry introduced the concept of bootstrapping, a procedure that reduces the error of a ciphertext by homomorphically evaluating the decryption function. The idea is to start with a ciphertext c_1 = Enc_{k_1}(m), whose error is approaching the critical threshold, and use a second key k_2 to encrypt the ciphertext again, obtaining c_2 = Enc_{k_2}(c_1). The server can then homomorphically evaluate the decryption function using the ciphertext and a bootstrapping key, which contains the key k_1 encrypted under k_2. The result is a new ciphertext encrypting the same message m under key k_2, but with a sufficiently reduced error level to allow further homomorphic computations. By repeating this procedure whenever necessary, it is possible to construct FHE schemes capable of supporting computations of arbitrary depth.
The bootstrapping process is illustrated in the figure: the blue and green rectangles represent encryption under keys k_1 and k_2, respectively, while the thermometers graphically illustrate the error level associated with each ciphertext.

Although bootstrapping makes it possible to control error growth and therefore perform an arbitrary number of homomorphic operations, its computational cost remains one of the main limitations of FHE schemes. More generally, processing encrypted data requires significantly more resources and execution time than equivalent operations on plaintext data. Optimizing the performance of leading FHE schemes is therefore a central research objective and an important requirement for promoting the adoption of this technology in real-world application scenarios.
Hardware Acceleration for FHE
The significant computational overhead associated with Fully Homomorphic Encryption (FHE) schemes mainly stems from the need to perform operations on polynomials, which are used to represent ciphertexts. In particular, polynomial multiplications are more computationally expensive than arithmetic operations performed on plaintext data. To reduce their complexity, techniques such as the Fast Fourier Transform (FFT) and a variant applicable over finite fields, known as the Number Theoretic Transform (NTT), are employed. Despite these optimizations, such operations are performed very frequently during homomorphic computations and can account for a significant portion of the overall computational cost.
A second critical factor is bootstrapping, which is required to limit the growth of accumulated error during computations and preserve decryption correctness. This procedure requires a large number of operations on ciphertexts and can account for more than 90% of computation time in certain application scenarios. Since FFT and NTT are fundamental components of numerous operations in FHE schemes and can represent a substantial portion of the computational workload, accelerating them is one of the main strategies for improving the overall performance of homomorphic encryption.
To address these challenges and improve the performance of FHE schemes, dedicated hardware accelerators have been developed in recent years, both in academia and industry, primarily based on three technologies: GPUs, FPGAs, and ASICs. Each of these solutions has specific characteristics in terms of flexibility, performance, and energy efficiency:
- Graphics Processing Unit (GPU): processors characterized by a high degree of parallelism, particularly well suited to accelerating repetitive and computationally intensive operations, such as FFT and NTT transforms.
- Field-Programmable Gate Array (FPGA): reconfigurable hardware devices that allow specialized architectures to be designed for FHE operations, offering a compromise between flexibility and efficiency.
- Application-Specific Integrated Circuit (ASIC): integrated circuits designed to perform specific operations, capable of delivering high performance and energy efficiency, at the expense of higher development costs and lower flexibility compared with other solutions.
Conclusions
Fully Homomorphic Encryption is a technology with enormous potential for protecting data in the Cloud, as it makes it possible to delegate computations to external infrastructures without revealing plaintext information, thereby helping to overcome one of the main limitations of traditional cryptographic solutions. The importance of this technology is demonstrated by the growing number of studies and projects dedicated to its optimization, as well as by the strong interest shown by both the academic community and industry. Although the performance of current schemes is not yet sufficient to enable their efficient use in many application contexts, progress made in recent years, both at the algorithmic level and through the development of dedicated hardware accelerators, is gradually narrowing this gap. FHE is therefore becoming increasingly viable in specific scenarios, where confidentiality requirements may justify the higher computational cost, and is emerging as a promising technology for the future development of secure Cloud services.
This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.
For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.
The authors
Marco Rinaudo, a bachelor’s degree in Mathematics from the University of Turin and a master’s degree with a specialization in Cryptography from the University of Trento. Following a 2022 curricular internship at Telsy, he has been part of the Cryptography Research Group since January 2023.