Abstract. In CRYPTO 2010, Aguilar et al. proposed a somewhat homomorphic encryption scheme, i.e. an encryption scheme allowing to compute a limited amount of sums and products over encrypted data, with a security reduction from LWE over general lattices. General lattices (as opposed to ideal lattices) do not have an inherent multiplicative structure but, using a tensorial product, Aguilar et al. managed to obtain a scheme allowing to compute products with a polylogarithmic amount of operands. In this paper we present an alternative construction allowing to compute products with polynomiallymany operands while preserving the security reductions of the initial scheme. Unfortunately, despite this improvement our construction seems to be incompatible with Gentry’s seminal transformation allowing to obtain fully-homomorphic encryption schemes. Recently, Brakerski et al. used the tensorial product approach introduced by Aguilar et al. in a new alternative way which allows to radically improve the performance of the obtained scheme. Based on this approach, and using two nice optimizations, their scheme is able to evaluate products with exponentially-many operands and can be transformed into an efficient fully-homomorphic encryption scheme while being based on general lattice problems. However, even if these results outperform the construction presented here, we believe the modifications we suggest for Aguilar et al.’s schemes are of independent interest.
Abstract. In CRYPTO 2010, Aguilar et al. proposed a somewhat homomorphic encryption scheme, i.e. an encryption scheme allowing to compute a limited amount of sums and products over encrypted data, with a security reduction from LWE over general lattices. General lattices (as opposed to ideal lattices) do not have an inherent multiplicative structure but, using a tensorial product, Aguilar et al. managed to obtain a scheme allowing to compute products with a polylogarithmic amount of operands. In this paper we present an alternative construction allowing to compute products with polynomiallymany operands while preserving the security reductions of the initial scheme. Unfortunately, despite this improvement our construction seems to be incompatible with Gentry’s seminal transformation allowing to obtain fully-homomorphic encryption schemes. Recently, Brakerski et al. used the tensorial product approach introduced by Aguilar et al. in a new alternative way which allows to radically improve the performance of the obtained scheme. Based on this approach, and using two nice optimizations, their scheme is able to evaluate products with exponentially-many operands and can be transformed into an efficient fully-homomorphic encryption scheme while being based on general lattice problems. However, even if these results outperform the construction presented here, we believe the modifications we suggest for Aguilar et al.’s schemes are of independent interest.
Abstract: In this paper, we first introduce a new concept of approximate lattice problem (ALP), which is an extension of learning with errors (LWE). Next, we propose two ALP-based public key encryption schemes. Then, we construct two new fully homomorphic encryption scheme (FHE) based on respectively approximate principal ideal lattice problem with related modulus (APIP-RM) and approximate lattice problem with related modulus (ALP-RM). Moreover, we also extend our ALP-RM-based FHE to the ALP problem with unrelated modulus (ALP-UM). Our work is different from previous works in three aspects: (1) We extend the LWE problem to the ALP problem. This ALP problem is similar to the closest vector problem in lattice. We believe that this problem is independent of interest. (2) We construct a new FHE by using a re-randomizing method, which is different from the squashing decryption in previous works. (3) The expansion rate is merely O(k) with k a security parameter in Our FHE, which can be improved to O(logk) by using dimension reduction [BV11], whereas all previous schemes are at least O(k*logk) [BV11, Gen11, LNV11]. Our method can also decrease a factor k of the expansion rate in their schemes.
Abstract The security of most early fully homomorphic encryption schemes was based on the hardness of the Learning with Errors (LWE) problem. These schemes were inefficient in terms of per gate computations and public‐key size. More efficient schemes were later developed based on the hardness of the Ring‐LWE (RLWE) problem. While the hardness of the LWE problem is based on the hardness of the approximate shortest vector problem (GapSVP γ ) over regular lattices, the hardness of the RLWE problem is based on the hardness of the approximate shortest vector problem over ideal lattices. As of now, it has not been proved that the (GapSVP γ ) problem over ideal lattices is as difficult as the corresponding problem over regular lattices. In this work, the authors propose a multi‐bit levelled fully homomorphic encryption scheme using multivariate polynomial evaluations whose security depends on the hardness of the LWE problem. In terms of per gate computation cost, this scheme is more efficient than existing LWE‐based schemes. Further, for an appropriate choice of parameters, the per computation cost for homomorphic multiplication can be made asymptotically comparable to RLWE‐based schemes in a parallel computing environment. For homomorphic multiplication, the scheme uses a polynomial‐based technique that does not require relinearization (and key switching).
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.
In this paper, we first introduce a new concept of approximate lattice problem (ALP), which is an extension of learning with errors (LWE). Next, we propose two ALP-based public key encryption schemes. Then, we construct two new fully homomorphic encryption scheme (FHE) based on respectively approximate principal ideal lattice problem with related modulus (APIP-RM) and approximate lattice problem with related modulus (ALP-RM). Moreover, we also extend our ALP-RM-based FHE to the ALP problem with unrelated modulus (ALP-UM). Our work is different from previous works in three aspects: (1) We extend the LWE problem to the ALP problem. This ALP problem is similar to the closest vector problem in lattice. We believe that this problem is independent of interest. (2) We construct a new FHE by using a re-randomizing method, which is different from the squashing decryption in previous works. (3) The expansion rate is merely O(k) with k a security parameter in Our FHE, which can be improved to O(logk) by using dimension reduction [BV11], whereas all previous schemes are at least O(k*logk) [BV11, Gen11, LNV11]. Our method can also decrease a factor k of the expansion rate in their schemes.
Abstract. In this paper we port Brakerski’s fully homomorphic scheme based on the Learning With Errors (LWE) problem to the ring-LWE setting. We introduce two optimised versions of relinearisation that not only result in a smaller relinearisation key, but also faster computations. We provide a detailed, but simple analysis of the various homomorphic operations, such as multiplication, relinearisation and bootstrapping, and derive tight worst case bounds on the noise caused by these operations. The analysis of the bootstrapping step is greatly simplified by using a modulus switching trick. Finally, we derive concrete parameters for which the scheme provides a given level of security and becomes fully homomorphic. 1
All the existing fully homomorphic encryption schemes are based on three different problems, namely the bounded distance decoding problem over ideal lattice, the approximate greatest common divisor problem over integers, and the learning with error problem. In this paper, we unify the first two families of problems by introducing a new class of problems, which can be reduced from both problems. Based on this new problem, namely the bounded distance decoding over hidden ideal lattice, we present a new fully homomorphic encryption scheme. Since it is a combination of the two problems to some extent, the performance of our scheme lies between the ideal lattice based schemes and the integer based schemes. Furthermore, we also show a lower bound and upper bound of the problem that our scheme is based on. Assuming this security conjecture holds, we can incorporate smaller parameters, which will result in a scheme that is more efficient than both lattice based and integer based schemes. Hence, our scheme makes a perfect alternative to the state-of-art ring learning with error based schemes.