Private function evaluation : improvements and applications

Abstract

In the problem of two-party private function evaluation (PFE), one party P_A possesses a private function f and (optionally) a private input x_A, while the other party P_B holds a private input x_B. Their goal is to compute f(x_A, x_B) for one or both parties while no other information beyond f(x_A, x_B) is revealed.

Two-party PFE has great potential to solve dilemmas existing in many real-world scenarios. For example, a traditional enterprise holds a private dataset and needs a corresponding algorithm to process it, while an algorithm-driven company possesses the algorithm but treats it as confidential. Another example is for a data trading scenario: A data seller intends to sell an evaluation result derived from her dataset rather than the entire dataset at once, while the data buyer wants to hide his evaluation done on the dataset. A two-party PFE protocol can easily solve these dilemmas.

This thesis revisits the two-party PFE problem. Based on the private function f, two-party PFE problems can be divided into two categories. One considers f as arbitrary functions, while the other considers f as limited classes of functions, \eg low-depth circuits and polynomials. Our major contributions categorized according to the function f are summarized as follows. 1. Considering f as an arbitrary function, we propose the first constant-round actively secure PFE protocol with linear complexity. Based on this result, we further provide the first constant-round publicly verifiable covertly (PVC) secure PFE protocol with linear complexity to gain better efficiency. In our constructions, as a by-product, we design a specific protocol for proving that a list of ElGamal ciphertexts is derived from an extended permutation performed on a given list of elements, which may be of independent interest. In addition, a reusability property is added to our two PFE protocols. Namely, if the same function f is involved in multiple protocol executions between P_A and P_B, the protocol could be executed more efficiently from the second execution. Moreover, we further extend this property to be global, such that it supports multiple executions for the same f in a reusable fashion between P_A and arbitrary parties playing the role of P_B.

2. Aiming at practical data trading scenarios, we introduce a specified concept of PFE, namely blind polynomial evaluation. Here, f is an arbitrary function that can be represented as a multivariate polynomial. We provide a generic construction and an instantiated blind polynomial evaluation protocol via an approach of switching the homomorphic encryption schemes of ciphertexts. Then to improve the efficiency of our protocol, we also introduce an improved zero-knowledge protocol for multi-exponentiation with encrypted bases. Finally, we combine our protocol with the blockchain paradigm to obtain a practical data trading framework.