LWR-Based Fully Homomorphic Encryption, Revisited

Abstract EN

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.