Cryptology ePrint Archive: Report 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 show that, the AND operator on plaintext bits is emulatable, with negligible error probability, by the commutator operator on a finite non-commutative group with appropriately rerandomized inputs, provided the group is large and "far from being commutative" in a certain sense. The NOT operator is also easily emulated on such a group; hence the FHE functionality is realized. Finally, in order to realize security, we propose some possible strategies for concealing the core structure of the FHE functionality, based on techniques in combinatorial or computational group theory. In contrast to the previous noise-based constructions of FHE, our proposed construction does not suffer from increasing noise in ciphertexts and therefore needs no bootstrapping procedures, which is the most inefficient part in the previous schemes.

Category / Keywords: public-key cryptography / public-key cryptography, fully homomorphic encryption, group-based cryptography

Date: received 10 Feb 2014, last revised 26 Aug 2015

Contact author: k nuida at aist go jp

Available format(s): PDF | BibTeX Citation

Note: Revision to avoid an attack found for the instantiation of the scheme in the previous (19-Aug-2015) version; see Page 13 for this attack.

Version: 20150826:085507 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]