LWR-Based Fully Homomorphic Encryption, Revisited
Authors:
Open Access
- 23 April 2018
- journal article
- research article
- Published by Wiley in Security and Communication Networks
- Vol. 2018, 1-12
Abstract
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.Keywords
Funding Information
- National Basic Research Program of China (2014CB340603, 2017YFB0802000, 61672030, 61272040, U1705264, 2017QDL002, Y201737292)
- National Key Research and Development Program of China (2014CB340603, 2017YFB0802000, 61672030, 61272040, U1705264, 2017QDL002, Y201737292)
- National Natural Science Foundation of China (2014CB340603, 2017YFB0802000, 61672030, 61272040, U1705264, 2017QDL002, Y201737292)
- National Natural Science Foundation of China (2014CB340603, 2017YFB0802000, 61672030, 61272040, U1705264, 2017QDL002, Y201737292)
- National Natural Science Foundation of China (2014CB340603, 2017YFB0802000, 61672030, 61272040, U1705264, 2017QDL002, Y201737292)
- Hangzhou Normal University (2014CB340603, 2017YFB0802000, 61672030, 61272040, U1705264, 2017QDL002, Y201737292)
- Department of Education of Zhejiang Province (2014CB340603, 2017YFB0802000, 61672030, 61272040, U1705264, 2017QDL002, Y201737292)
This publication has 23 references indexed in Scilit:
- Faster Bootstrapping with Polynomial Error2014
- Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based2013
- Learning with Rounding, Revisited2013
- Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller2012
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP2012
- Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages2011
- Fully Homomorphic Encryption over the Integers2010
- Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes2010
- On lattices, learning with errors, random linear codes, and cryptographyJournal of the ACM, 2009
- A Pseudorandom Generator from any One-way FunctionSIAM Journal on Computing, 1999