Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / fully homomorphic encryption, characterisation

Date: received 9 Feb 2016, last revised 27 Jun 2016

Contact author: martin strand at math ntnu no

Available format(s): PDF | BibTeX Citation

Note: Changes after reviewer comments.

Version: 20160627:125004 (All versions of this report)

Short URL: ia.cr/2016/105

Discussion forum: Show discussion | Start new discussion