Fully dynamic multi-key fully homomorphic encryption (FHE) that allows an unlimited number of homomorphic operations for unconstrained parties. That is to say, it supports performing as many computational procedures on inputs (which are encrypted by an unrestricted number of parties) as needed. The existed fully dynamic multi-key FHE scheme is based on the learning with errors (LWE) problem. However, the LWE problem suffers from the intricate and laborious Gaussian sampling which extremely weakens the schemes’ efficiencies. What’s more, it has been lately revealed that Gaussian sampling creates lots of possible side-channel vulnerabilities that result in the disclosure of secret keys. The paper proposed a fully dynamic multi-key FHE that based on the learning with rounding (LWR) problem which leaves out the time-consuming Gaussian sampling required in the LWE problem while sustaining almost the same security level.
Fully dynamic multi-key fully homomorphic encryption (FHE) that allows an unlimited number of homomorphic operations for unconstrained parties. That is to say, it supports performing as many computational procedures on inputs (which are encrypted by an unrestricted number of parties) as needed. The existed fully dynamic multi-key FHE scheme is based on the learning with errors (LWE) problem. However, the LWE problem suffers from the intricate and laborious Gaussian sampling which extremely weakens the schemes’ efficiencies. What’s more, it has been lately revealed that Gaussian sampling creates lots of possible side-channel vulnerabilities that result in the disclosure of secret keys. The paper proposed a fully dynamic multi-key FHE that based on the learning with rounding (LWR) problem which leaves out the time-consuming Gaussian sampling required in the LWE problem while sustaining almost the same security level.
There has been a great deal of work on improving the efficiency of fully homomorphic encryption (FHE) scheme. Our approach, in this regard, is to use the idea of packed ciphertexts to construct a multi-bit FHE with a short public key on the basis of the learning with errors (LWE) problem. More specifically, our FHE scheme builds on a basic encryption scheme that chooses LWE samples from the Gaussian distribution and adds Gaussian error to it. This results in decreasing the number of LWE samples from 2nlogq to n + 1. We prove that our FHE scheme is pragmatically feasible and its security relies on the hardness of the LWE problem. In addition, we form a new process of key switching for multi-bit FHE based on the ideas adopted by Brakerski et al. for optimizing the process of key switching. Finally, we analyze and compare the concrete parameters between our FHE scheme and BGH13 scheme. The result shows that compared with the BGH13 scheme, our scheme has a smaller public key by a factor about logq.
Very recently, Costache and Smart proposed a fully homomorphic encryption (FHE) scheme based on the Learning with Rounding (LWR) problem, which removes the noise (typically, Gaussian noise) sampling needed in the previous lattices-based FHEs. But their scheme did not work, since the noise of homomorphic multiplication is complicated and large, which leads to failure of decryption. More specifically, they chose LWR instances as a public key and the private key therein as a secret key and then used the tensor product to implement homomorphic multiplication, which resulted in a tangly modulus problem. Recall that there are two moduli in the LWR instances, and then the moduli will tangle together due to the tensor product. Inspired by their work, we built the first workable LWR-based FHE scheme eliminating the tangly modulus problem by cleverly adopting the celebrated approximate eigenvector method proposed by Gentry et al. at Crypto 2013. Roughly speaking, we use a specific matrix multiplication to perform the homomorphic multiplication, hence no tangly modulus problem. Furthermore, we also extend the LWR-based FHE scheme to the multikey setting using the tricks used to construct LWE-based multikey FHE by Mukherjee and Wichs at Eurocrypt 2016. Our LWR-based multikey FHE construction provides an alternative to the existing multikey FHEs and can also be applied to multiparty computation with higher efficiency.
Almost all existing well‐known fully homomorphic encryption (FHE) schemes, which are based on either the learning with errors (LWE) or the ring LWE problem, require expensive Gaussian noise sampling. In this study, the authors propose an FHE scheme based on the ring learning with rounding (RLWR) problem. The learning with rounding (LWR) problem was proposed as a deterministic variant of LWE, while the RLWR is a variant of LWR. Sampling an LWR instance does not require Gaussian noise sampling process, and neither does an RLWR instance. Thus, our FHE scheme can be instantiated without the need for Gaussian noise sampling. To implement homomorphic operations, we devise a specific relinearisation method. Furthermore, we also prove that our RLWR‐based FHE scheme is IND‐CPA secure under RLWR assumption.
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.
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.
Abstract In dynamic multi-key Fully Homomorphic Encryption (MFHE) scheme, homomorphic operations on ciphertexts encrypted under different keys are allowed. Moreover, the resulting ciphertext can be further computed with ciphertexts under other keys. In 2016, Peikert and Shiehian presented a dynamic MFHE scheme that relies on using a Common Reference String (CRS) and circular security assumptions. Subsequently, various variants of dynamic MFHE schemes were proposed based on this scheme, but these variant schemes still rely on a CRS and circular security assumption. Therefore, constructing a MFHE GSW scheme relies solely on the LWE assumption and does not require a CRS remains a valuable challenge. This paper introduces a new dynamic MFHE scheme. Compared to existing solutions, our scheme does not require the circular security assumption and depends solely on the LWE assumption, which theoretically provides an enhanced level of security. Additionally, it eliminates the need for a shared CRS but instead replaces the CRS with each party independently generate random matrices. This decentralized approach enhances the ability of users to generate keys independently. The size of ciphertexts and public keys in our scheme is comparable to other existing solutions, thus maintaining efficiency in both computation and ciphertext extension.