Evaluating the Use of Fully Homomorphic Encryption in Secure Multi-party Computation
Homomorphic encryption schemes allow anyone in possession of the public key to perform operations on
the encrypted data without decrypting it. Until recently, all known homomorphic encryption schemes were
either additively homomorphic or multiplicatively homomorphic. However, recently a fully homomorphic
encryption scheme has been suggested by Craig Gentry.
This scheme is currently still far from being practical. However, it is a serious ﬁrst step towards fully-homomorphic encryption schemes. One area of application of homomorphic encryption is secure multi-party computation. The problem of secure multi-party computation was ﬁrst introduced by Yao and subsequently used for privacy-preserving protocol design in many areas of applications such as data mining, queries on encrypted databases, anonymous data collection, or privacy-preserving auctions to mention just a few.
While the original work by Yao allows to compute many types of functions securely, its performance typically makes it impractical today. Therefore many algorithms to securely compute particular functions more eﬃciently have been proposed. An example for such a function is computing the intersection of private input sets.
An interesting question that arises with the occurrence of fully-homomorphic encryption schemes now is:
Can they be used to further speed up the secure computation of particular functions in terms of number of
encryptions, decryption, homomorphic operations required? How eﬃcient would a fully-homomorphic en-
cryption scheme have to be in order to outperform current homomorphic schemes when computing particular
Graduand: Florian Weingarten
Supervisor: Georg Neugebauer