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 encryp- tion;
(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 2160 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.
Bio: Shuhong Gao received his BS (1983) and MS (1986) from Department of Mathematics, Sichuan
University, China, and PhD (1993) from Department of Combinatorics and Optimization, University of
Waterloo, Canada. From 1993 to 1995, he was an NSERC Postdoctoral Fellow in Department of
Computer Science, University of Toronto, Canada. He joined Clemson University in USA in 1995 as an
assistant professor in Mathematical Sciences, and was promoted to associate professor in 2000 (with
early tenure) and to full professor in 2002. Professor Gao's research interests include coding theory,
cryptography, symbolic computation, computational number theory and computational algebraic
geometry. More information about his research and teaching can be found at Applicable
Algebra Lab: https://www.ces.clemson.edu/aca/
