Cryptology ePrint Archive: Report 2018/637

Efficient Fully Homomorphic Encryption Scheme

Shuhong Gao

Abstract: Since Gentry discovered in 2009 the first fully homomorphic encryption scheme, the last few years have witnessed dramatic progress on designing more efficient homomorphic encryption schemes, and some of them have been implemented for applications. The main bottlenecks are in bootstrapping and large cipher expansion (the ratio of the size of ciphertexts to that of messages). Ducas and Micciancio (2015) show that homomorphic computation of one bit operation on LWE ciphers can be done in less than a second, which is then reduced by Chillotti et al. (2016, 2017) to 13ms. This paper presents a compact fully homomorphic encryption scheme that has the following features: (a) its cipher expansion is 6 with private-key encryption and 20 with public-key encryption; (b) all ciphertexts after any number (unbounded) of homomorphic bit operations have the same size and are always valid with the same error size; (c) its security is based on the LWE and RLWE problems (with binary secret keys) and the cost of breaking the scheme by the current approaches is at least $2^{160}$ bit operations. The scheme protects function privacy and provides a simple solution for secure two-party computation and zero knowledge proof of any language in NP.

Category / Keywords: implementation / Fully homomorphic encryption, data security, lattices, learning with errors (LWE) problem, ring learning with errors (RLWE) problem, NP problems, secure two-party computation, zero knowledge proof, fast Fourier transforms (FFT).

Date: received 27 Jun 2018

Contact author: sgao at clemson edu

Available format(s): PDF | BibTeX Citation

Version: 20180706:123012 (All versions of this report)

Short URL: ia.cr/2018/637


[ Cryptology ePrint archive ]