You are looking at a specific version 20200715:115747 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.