Highly Efficient and Re-Executable Private Function Evaluation With Linear Complexity

Private function evaluation aims to securely compute a function $f(x_1, \ldots, x_n)$ without leaking any information other than what is revealed by the output, where $f$ is a private input of one of the parties (say $\mathsf {Party}_1$) and $x_i$ is a private input of the $i$th party $\mathsf {Party}_i$. In this article, we propose a novel and secure two-party private function evaluation (2PFE) scheme based on the DDH assumption. Our scheme introduces a reusability feature that significantly improves the state-of-the-art. Accordingly, our scheme has two variants, one is utilized in the initial execution of the function $f$, and the other is utilized in its subsequent evaluations. To the best of our knowledge, this is the first and most efficient 2PFE scheme that enjoys a reusablity feature. Our protocols achieve linear communication and computation complexities and a constant number of rounds which is at most three.

1 Introduction

Development of computing devices with the proliferation of the Internet has prompted enormous opportunities for cooperative computation. These computations could occur between trusted or partially trusted partners, or even between competitors. Secure multiparty computation (MPC) protocols allow two or more parties to collaborate and compute a public functionality using their private inputs without the need for a trusted third-party. However, the generic solutions for MPC are not adequate for some particular cases where the function itself is also sensitive and required to be kept private. Private function evaluation (PFE) is a special case of MPC, where the function to be computed is known by only one party. PFE is useful in several real-life applications where an algorithm or a function itself needs to remain secret for reasons such as protecting intellectual property or security classification level. Recently, designing efficient PFE protocols have been a challenging and attractive task for cryptography researchers [1], [2], [3], [4], [5], [6], [7], [8].