Paper 2016/105
Can there be efficient and natural FHE schemes?
Kristian Gjøsteen and Martin Strand
Abstract
In 1978, Rivest, Adleman and Dertouzos asked for algebraic systems for which useful privacy homomorphisms exist. To date, the only acknownledged result is noise based encryption combined with bootstrapping. Before that, there were several failed attempts. We prove that fully homomorphic schemes are impossible for several algebraic structures. Then we develop a characterisation of all fully homomorphic schemes and use it to analyse three examples. Finally, we propose a conjecture stating that secure FHE schemes must either have a significant ciphertext expansion or use unusual algebraic structures.
Note: Changes after reviewer comments.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- fully homomorphic encryptioncharacterisation
- Contact author(s)
- martin strand @ math ntnu no
- History
- 2016-06-27: revised
- 2016-02-10: received
- See all versions
- Short URL
- https://ia.cr/2016/105
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/105,
author = {Kristian Gjøsteen and Martin Strand},
title = {Can there be efficient and natural {FHE} schemes?},
howpublished = {Cryptology {ePrint} Archive, Paper 2016/105},
year = {2016},
url = {https://eprint.iacr.org/2016/105}
}