Abstract. Fully homomorphic encryption (FHE) is a form of public-key encryption that enables arbitrary computation over encrypted data. The past few years have seen several realizations of FHE under differ-ent assumptions, and FHE has been used as a building block in many cryptographic applications. Adaptive security for public-key encryption schemes is an important se-curity notion proposed by Canetti et al. It is intended to ensure security when encryption is used within an interactive protocol and parties may be adaptively corrupted by an adversary during the course of the protocol execution. Due to the extensive applications of FHE to protocol design, it is natural to understand whether adaptively secure FHE is achievable. In this paper we show two contrasting results in this direction. First, we show that adaptive security is impossible for FHE satisfying the (stan-dard) compactness requirement. On the other hand, we show a construc-tion of adaptively secure FHE that is not compact, but that does achieve circuit privacy.
Abstract. Fully homomorphic encryption (FHE) is a form of public-key encryption that enables arbitrary computation over encrypted data. The past few years have seen several realizations of FHE under differ-ent assumptions, and FHE has been used as a building block in many cryptographic applications. Adaptive security for public-key encryption schemes is an important se-curity notion proposed by Canetti et al. It is intended to ensure security when encryption is used within an interactive protocol and parties may be adaptively corrupted by an adversary during the course of the protocol execution. Due to the extensive applications of FHE to protocol design, it is natural to understand whether adaptively secure FHE is achievable. In this paper we show two contrasting results in this direction. First, we show that adaptive security is impossible for FHE satisfying the (stan-dard) compactness requirement. On the other hand, we show a construc-tion of adaptively secure FHE that is not compact, but that does achieve circuit privacy.
This thesis presents a comprehensive analysis of Fully Homomorphic Encryption (FHE), a transformative advancement in contemporary cryptography. The exponential growth in digital data, coupled with the escalating demand for remote data processing, has elevated the importance of robust information security and privacy mechanisms. Homomorphic Encryption (HE) schemes facilitate the outsourcing of computations to untrusted third parties without exposing the underlying sensitive information, significantly enhancing data privacy assurances. Traditional encryption methods effectively protect data at rest and in transit; however, they inherently lack the capability to perform operations directly on encrypted data. FHE addresses this fundamental shortcoming by enabling intricate computations to be conducted on encrypted data without the necessity of decryption. The thesis begins by outlining the historical development of encryption systems and fundamental cryptographic concepts. It details the progression from the "privacy homomorphism" concept introduced by Rivest, Adleman, and Dertouzos in 1978 to Craig Gentry's seminal work in 2009, which presented the first practical FHE scheme. The key milestones in the evolution of FHE and major contributions in the literature are presented from both theoretical and practical perspectives. Subsequently, the mathematical structures and concepts underlying FHE are discussed in depth. Topics such as lattices, rings and fields, polynomials, number fields, canonical embedding, and ideal structures are examined as the foundational building blocks ensuring the security of FHE. In particular, challenging problems provided by Lattice-Based Cryptography, such as Learning with Errors (LWE), serve as the mathematical basis for FHE's resistance to attacks. The thesis also analyzes the structure, functioning, and differences between modern FHE schemes (such as Brakerski, Gentry and Vaikuntanathan (BGV), Fan and Vercauteren (BFV), and Cheon-Kim-Kim-Song (CKKS)). The practical applications, advantages, limitations, and recent optimization techniques of these schemes are thoroughly examined. Special attention is given to the opportunities FHE offers in sectors where data privacy is paramount, including healthcare, finance, and cloud computing. Key practical challenges such as high computational costs, large key and ciphertext sizes, and noise management are highlighted. Innovations to address these challenges, including hardware accelerators, software optimizations, and open-source libraries (like HELib and SEAL), are explored in detail. The thesis also covers contemporary research areas such as multi-key FHE, privacy-preserving computation in artificial intelligence, and post-quantum cryptography. In conclusion, this thesis presents a broad perspective on FHE, covering its mathematical foundations and practical application potential, while evaluating current developments, limitations, and future research directions. The wider and more efficient xxv adoption of FHE will open new possibilities for information security and privacy. In this context, the thesis aims to serve as a comprehensive resource for both academic and industrial communities. Keywords: Bootstrapping, Relinearization, Ring Learning with Errors, BGV, BFV, CKKS.
We present a framework for constructing compact FHE (fully homomorphic encryption) which is circuit-private in the malicious setting. That is, even if both maliciously formed public key and ciphertext are used, encrypted outputs only reveal the evaluation of the circuit on some well-formed input x ∗. Previous literature on FHE only considered semi-honest circuit privacy. Circuit-private FHE schemes have direct applications to computing on encrypted data. In that setting, one party (a receiver) holding an input x wishes to learn the evaluation of a circuit C held by another party (a sender). The goal is to make receiver’s work sublinear (and ideally independent) of C, using a 2-message protocol. Maliciously circuit-private FHE immediately gives rise to such a protocol which is secure against a malicious receiver.
Since Gentry's breakthrough construction of fully homomorphic encryption from lattice-based assumptions (STOC 2009), homomorphic cryptography has attracted a lot of attention. In short, homomorphic cryptography schemes allow performing computation on encrypted data without knowing anything about the underlying plaintext. This branch of cryptography has become increasingly useful in building new protocols and schemes with intriguing security and functionality features. In this thesis, we continue to study the applications of homomorphic cryptography and the lattice-based techniques underlying them in realizing new and enhanced cryptographic primitives. We obtain the following results: -We construct the first noninteractive zero knowledge argument (and proof) system for all of NP from standard lattice assumptions. Noninteractive zero knowledge argument systems have found many applications in enhancing the functionality as well as the security of cryptographic schemes and protocols. Constructing noninteractive zero knowledge arguments from lattice assumption has been a long standing open question. We finally close this problem. -We consider multi-key fully homomorphic encryption (FHE) schemes. Traditional fully homomorphic encryption schemes allow computation on plaintext encrypted under a single key. The notion of multi-key fully homomorphic encryption allows homomorphic computation on data encrypted under different keys. We construct multi-key FHE schemes which are naturally dynamic: ciphertexts under new keys can join even during the homomorphic computation. -Finally, we focus on constrained pseudorandom functions (C-PRFs), which are pseudorandom functions (PRFs) with additional functional capabilities. We propose a new approach for building C-PRFs from lattices, and also significantly enhance the underlying lattice parameters.
A fully homomorphic encryption (FHE) scheme allows a client to encrypt and delegate its data to a server that performs computation on the encrypted data that the client can then decrypt. While FHE gives confidentiality to clients' data, it does not protect the server's input and computation. Nevertheless, FHE schemes are still helpful in building delegation protocols that reduce communication complexity, as the ciphertext's size is independent of the size of the computation performed on them. We can further extend FHE by a property called circuit privacy, which guarantees that the result of computing on ciphertexts reveals no information on the computed function and the inputs of the server. Thereby, circuit private FHE gives rise to round optimal and communication efficient secure two-party computation protocols. Unfortunately, despite significant efforts and much work put into the efficiency and practical implementations of FHE schemes, very little has been done to provide useful and practical FHE supporting circuit privacy. In this work, we address this gap and design the first randomized bootstrapping algorithm whose single invocation sanitizes a ciphertext and, consequently, serves as a tool to provide circuit privacy. We give an extensive analysis, propose parameters, and provide a C++ implementation of our scheme. Our bootstrapping can sanitize a ciphertext to achieve circuit privacy at an 80-bit statistical security level in between 1.3 and 0.9 seconds, depending which Gaussian sampling algorithm is used, and whether the parameter set targets a fast Fourier or a number theoretic transform-based implementation. In addition, we can perform non-sanitized bootstrapping in around 0.27 or 0.14 seconds. Crucially, we do not need to increase the parameters to perform computation before or after sanitization takes place. For comparison's sake, we revisit the Ducas-Stehlé washing machine method. In particular, we give a tight analysis, estimate efficiency, review old, and provide new parameters.
Abstract. Fully homomorphic encryption (FHE) enables secure computation over the encrypted data of a single party. We explore how to extend this to multiple parties, using threshold fully homomorphic encryption (TFHE). In such scheme, the parties jointly generate a common FHE public key along with a secret key that is shared among them; they can later cooperatively decrypt ciphertexts without learning anything but the plaintext. We show how to instantiate this approach efficiently, by extending the recent FHE schemes of Brakerski, Gentry and Vaikuntanathan (CRYPTO ’11, FOCS ’11, ITCS ’12) based on the (ring) learning with errors assumption. Our main tool is to exploit the property that such schemes are additively homomorphic over their keys. Using TFHE, we construct simple multiparty computation protocols secure against fully malicious attackers, tolerating any number of corruptions, and providing security in the universal composability framework. Our protocols have the following properties: Low interaction: 3 rounds of interaction given a common random string, or 2 rounds with a public-key infrastructure. Low communication: independent of the function being computed (proportional to just input and output sizes). Cloud-assisted computation: the bulk of the computation can be efficiently outsourced to an external entity (e.g. a cloud service) so that the computation of all other parties is independent of the complexity of the evaluated function. 1
Fully homomorphic encryption (FHE) is a form of public-key encryption that allows the computation of arbitrary functions on encrypted data without decrypting the data. As a result, it is a useful tool with numerous applications. Certificateless encryption (CLE) is a type of public-key encryption that combines the advantages of PKI-based public-key encryption with those of identity-based encryption (IBE). Thus, certificateless fully homomorphic encryption (CLFHE) has aroused considerable research interest. Recently, Chen, Hu, and Lian proposed a leveled certificateless homomorphic encryption (CLHE) scheme and proved its semantic security based on the learning with errors (LWE) problem in the random oracle model. However, their scheme supports only homomorphic addition, but not homomorphic multiplication. In this work, we construct two leveled CLFHE schemes using the approximate eigenvector method presented by Gentry, Sahai, and Waters. Based on the hardness of the LWE problem, we prove that one scheme satisfies adaptive semantic security and anonymity in the random oracle model, whereas the other satisfies selective semantic security and anonymity in the standard model.