Paper 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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. ESORICS 2020
- Keywords
- Private function evaluationhomomorphic encryptionsecure computation.
- Contact author(s)
- kiss @ encrypto cs tu-darmstadt de,holz @ encrypto cs tu-darmstadt de
- History
- 2020-09-14: last of 2 revisions
- 2020-07-12: received
- See all versions
- Short URL
- https://ia.cr/2020/853
- License
-
CC BY