Paper 2014/097

A Simple Framework for Noise-Free Construction of Fully Homomorphic Encryption from a Special Class of Non-Commutative Groups

Koji Nuida

Abstract

We propose a new and simple framework for constructing fully homomorphic encryption (FHE) which is completely different from the previous work. We use finite non-commutative (a.k.a., non-abelian) groups which are "highly non-commutative" (e.g., the special linear groups of size two) as the underlying structure. We show that, on such groups, the AND and NOT operations on plaintext bits (which are sufficient to realize an arbitrary operation by composing them) can be emulated by a "randomized commutator" (which essentially requires the non-commutativity) and division operations on ciphertext elements, respectively. Then we aim at concealing the "core structure" of ciphertexts by taking conjugation by a secret element (where the non-commutativity is again essential), rather than adding noise to the ciphertext as in the previous FHE schemes. The "noise-freeness" of our framework yields the fully-homomorphic property directly, without the bootstrapping technique used in the previous schemes to remove the noise amplified by the homomorphic operations. This makes the overall structure of the FHE schemes significantly simpler and easier to understand. Although a secure instantiation based on the framework has not been found, we hope that the proposed framework itself is of theoretical value, and that the framework is flexible enough to allow a secure instantiation in the future.