With the rapid development of cloud computing, it raises real questions on privacy protection, which greatly limits the use of cloud computing.However, fully homomorphic encryption (FHE) can make cloud computing consistent with privacy.In this paper, we propose a simpler FHE scheme based on ring LWE problem, with a smaller size of ciphertext and a lower noise-expansion factor for homomorphic multiplication.Then based on our optimized RLWE-based FHE scheme, we propose a fast single-database private information retrieval protocol, combining with batching and number theoretic transform technology.
With the rapid development of cloud computing, it raises real questions on privacy protection, which greatly limits the use of cloud computing.However, fully homomorphic encryption (FHE) can make cloud computing consistent with privacy.In this paper, we propose a simpler FHE scheme based on ring LWE problem, with a smaller size of ciphertext and a lower noise-expansion factor for homomorphic multiplication.Then based on our optimized RLWE-based FHE scheme, we propose a fast single-database private information retrieval protocol, combining with batching and number theoretic transform technology.
Fully Homomorphic Encryption (FHE) is a powerful encryption system in cloud computing that allows homomorphic computations on encrypted data without decrypting them. Multi-key fully homomorphic encryption (MFHE), as an extension to FHE, allows homomorphic computations on ciphertexts encrypted under different keys. However, most MFHE schemes require a Common Random/Reference String (CRS), while the few that do not are based on the Learning With Errors (LWE) problem, which means that they can only deal with single bit plaintext. Consequently, MFHE schemes based on the Ring Learning With Errors (RLWE) problem are more desirable, as they can handle polynomial plaintext. Requiring the CRS seems to weaken the semantic definition of MFHE, where all users generate their own keys independently. In this paper, we study the RLWE-based MFHE in the CRS model and propose the first RLWE-based MFHE without a CRS. To this end, we remove the CRS by designing a relinearization algorithm without a CRS. Like previous MFHE schemes, our RLWE-based MFHE without CRS has a simple 1-round threshold decryption, which implies a 3-round secure MPC protocol in the plain model from the RLWE assumption.
A multi-bit somewhat homomorphic encryption scheme based on Learning With Errors over Rings (RLWE) assumption is provided, which use canonical embedding to transform elements over a ring into vectors, thus the operation of polynomial multiplication can be performed within O(nlog n) scalar operations, and cipher text size is reduced as well. CPA security of this scheme can be reduced into RLWE assumption. Moreover, an efficient private information retrieval protocol that employs this scheme is presented.
The idea of computing on encrypted data without decryption dates back to the notion of privacy homomorphisms introduced by Rivest, Adleman, and Dertouzos (1978). Their proposals built using the elegant structure of Chinese Remainder Theorem (CRT), were later shown to be insecure under simple known-plaintext attacks. Subsequent CRT-based fully homomorphic encryption (FHE) over the integers addresses this algebraic transparency by injecting noise and basing security on approximate common divisor–type assumptions, but the resulting designs are burdened by large public keys and costly ciphertext refresh procedures. In this work, we develop a new CRT-based FHE scheme whose security relies on the Ring-LWE (RLWE) hardness assumption. For this purpose, we introduce the CRT-RLWE problem. We show that the problem is at least as hard as the RLWE, thereby positioning our construction within the established post-quantum security landscape of RLWE-based cryptography. Our scheme retains an explicit CRT embedding, separating a message component modulo a prime-power plaintext modulus and an auxiliary CRT component, while using RLWE-style key and ring arithmetic for compactness and efficiency. Finally, we make it fully homomorphic by using a new bootstrapping procedure, that adopts the recryption paradigm for BGV/BFV schemes utilizing the linear transformation and digit extraction techniques.
Fully Homomorphic Encryption (FHE) provides a good solution to directly operate on the ciphertext, and the decryption result is equivalent to the corresponding operation on the plaintext. As a technique suitable for distributed environments, multi-key Fully Homomorphic Encryption (MKFHE) scheme is the most common variant of the FHE scheme since it allows encrypted data to be computed under different keys. Unfortunately, the existing dynamic MKFHE schemes based on learning with errors (LWE) still suffer from the inefficiency of long public keys, which typically grow cube in size along the lattice dimension. Moreover, there current constructions fail to provide reliable and fast algorithms to simultaneously expand ciphertexts with multiple additional keys. In order to solve the above problems, a new faster dynamic MKFHE scheme with shorter public key in asymmetric key setting from LWE is proposed in this paper, in which the size of the public key is further reduced from O~(n3(K+L)2) to O~(n2(K+L)2). In addition, our scheme cleverly adopts the dual-user cooperation method in distributed system to realize the ciphertext expansion locally, thereby reducing the computing overhead of the cloud server. More interestingly, we design a flexible parallel ciphertext expansion algorithm for the first time based on the basic algorithm. This algorithm realizes the ciphertext expansion when multiple keys are added at the same time, thus significantly improving the computational efficiency of ciphertext expansion in the dynamic MKFHE scheme. Finally, the CPA-secure of our scheme based on standard LWE assumptions is proven.
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.
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.