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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/105}},
      url = {https://eprint.iacr.org/2016/105}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.