Paper 2017/839

Noiseless Fully Homomorphic Encryption

Jing Li and Licheng Wang

Abstract

We try to propose two fully homomorphic encryption (FHE) schemes, one for symmetric (aka. secret-key) settings and another under asymmetric (aka. public-key) scenario. The presented schemes are noiseless in the sense that there is no noise" factor contained in the ciphertexts. Or equivalently, before performing fully homomorphic computations, our schemes do not incorporate any noise-control process (such as bootstrapping, modulus switching, etc) to refresh the ciphertexts, since our fully homomorphic operations do not induce any noise. Instead of decrypting approximately, our proposal works in an exact homomorphic manner, no matter the inputs are the rst-hand ciphertexts that come from the encryptions of plaintexts, or the second-hand ciphertexts that come from homomorphic combinations of other ciphertexts. Therefore in essential, our schemes have no limitation on the depth of the fully homomorphic operations over the ciphertexts. Our solution is comprised of three steps. First, Ostrovsky and Skeith's idea for building FHE from a multiplicative homomorphic encryption (MHE) over a non-abelian simple group is extended so that FHE can be built from an MHE over a group ring that takes an underlying non-abelian simple group as the natural embedding. Second, non-trivial zero factors of the underlying ring are plugged into the encoding process for entirely removing the noise after fully homomorphic operations, and a slight but signicant modication towards Ostrovsky-Skeith's NAND gate representation is also introduced for avoiding computing inverse matrices of the underlying group ring. In such manner, a symmetric FHE scheme is produced. Finally, based on the proposed symmetric FHE scheme, an asymmetric FHE scheme is built by taking a similar diagram to the well-known GM84 scheme. But dierent from GM84 that only supports ciphertext homomorphism according to the logically incomplete gate XOR, our scheme supports ciphertext homomorphism according to the logically complete gate NAND.