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)
- 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
-
CC BY