Paper 2020/853

Linear-Complexity Private Function Evaluation is Practical

Marco Holz, Ágnes Kiss, Deevashwer Rathee, and Thomas Schneider


Private function evaluation (PFE) allows to obliviously evaluate a private function on private inputs. PFE has several applications such as privacy-preserving credit checking and user-specific insurance tariffs. Recently, PFE protocols based on universal circuits (UCs), that have an inevitable superlinear overhead, have been investigated thoroughly. Specialized public key-based protocols with linear complexity were believed to be less efficient than UC-based approaches. In this paper, we take another look at the linear-complexity PFE protocol by Katz and Malka (ASIACRYPT'11): We propose several optimizations and split the protocol in different phases that depend on the function and inputs respectively. We show that HE-based PFE is practical when instantiated with state-of-the-art ECC and RLWE-based homomorphic encryption. Our most efficient implementation outperforms the most recent UC-based PFE implementation of Alhassan et al. (JoC'20) in communication for all circuit sizes and in computation starting from circuits of a few thousand gates already.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ESORICS 2020
Private function evaluationhomomorphic encryptionsecure computation.
Contact author(s)
kiss @ encrypto cs tu-darmstadt de
holz @ encrypto cs tu-darmstadt de
2020-09-14: last of 2 revisions
2020-07-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marco Holz and Ágnes Kiss and Deevashwer Rathee and Thomas Schneider},
      title = {Linear-Complexity Private Function Evaluation is Practical},
      howpublished = {Cryptology ePrint Archive, Paper 2020/853},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.