Cryptology ePrint Archive: Report 2020/853

Linear-Complexity Private Function Evaluation is Practical

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

Abstract: 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.

Category / Keywords: cryptographic protocols / Private function evaluation, homomorphic encryption, secure computation.

Original Publication (with minor differences): ESORICS 2020

Date: received 8 Jul 2020, last revised 15 Jul 2020

Contact author: kiss at encrypto cs tu-darmstadt de,holz@encrypto cs tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20200715:115747 (All versions of this report)

Short URL: ia.cr/2020/853