Secure function evaluation (SFE) allows two parties to jointly compute a known function on their private data. Private Function Evaluation (PFE) is a technique to obliviously evaluate a private function on private inputs. In the PFE setting, party P_1 inputs a private function f and party P_2 inputs private data x, and at the end of the protocol, P_2 only learns the function’s output y = f(x) while P_1 learns nothing.
In the last years, 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 inefficient than these UC-based approaches. We take another look at the linear-complexity protocol by Katz and Malka (ASIA-CRYPT’11) and propose three efficient instantiations of the protocol using the Damgaard Jurik Nielsen (DJN) cryptosystem, elliptic curve ElGamal encryption and the Brakerski/Fan- Vercauteren (BFV) homomorphic encryption scheme. We show that HE-based PFE is practical with the latest improvements in the field of ECC and RLWE-based homomorphic encryption.
Marco Holz is a PhD student in the ENCRYPTO group led by Prof. Thomas Schneider.
Biography of Marco Holz