International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 14 February 2014

Koji Nuida
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.