You are looking at a specific version 20150826:085507 of this paper. See the latest version.

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 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.

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
public-key cryptographyfully homomorphic encryptiongroup-based cryptography
Contact author(s)
k nuida @ aist go jp
History
2020-10-30: last of 6 revisions
2014-02-14: received
See all versions
Short URL
https://ia.cr/2014/097
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.