Paper 2016/105 Original: eprint.iacr.org/2016/105 ↗
Can there be efficient and natural FHE schemes?
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2016-06-27: last updated
- 2016-02-10: published
- Short URL
- https://ia.cr/2016/105
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}