### 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.

Available format(s)
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
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
History
Short URL
https://ia.cr/2018/637

CC BY

BibTeX

@misc{cryptoeprint:2018/637,
author = {Shuhong Gao},
title = {Efficient Fully Homomorphic Encryption Scheme},
howpublished = {Cryptology ePrint Archive, Paper 2018/637},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/637}},
url = {https://eprint.iacr.org/2018/637}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.