Paper 2018/637

Efficient Fully Homomorphic Encryption Scheme

Shuhong Gao


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Fully homomorphic encryptiondata securitylatticeslearning with errors (LWE) problemring learning with errors (RLWE) problemNP problemssecure two-party computationzero knowledge prooffast Fourier transforms (FFT).
Contact author(s)
sgao @ clemson edu
2018-07-06: received
Short URL
Creative Commons Attribution


      author = {Shuhong Gao},
      title = {Efficient Fully Homomorphic Encryption Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2018/637},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.