Highly Efficient and Re-executable Private Function Evaluation with Linear Complexity

Abstract

Private function evaluation aims to securely compute a function <inline-formula><tex-math notation="LaTeX">$f(x_1, \ldots, x_n)$</tex-math></inline-formula> without leaking any information other than what is revealed by the output, where <inline-formula><tex-math notation="LaTeX">$f$</tex-math></inline-formula> is a private input of one of the parties (say <inline-formula><tex-math notation="LaTeX">$\mathsf {Party}_1$</tex-math></inline-formula> ) and <inline-formula><tex-math notation="LaTeX">$x_i$</tex-math></inline-formula> is a private input of the <inline-formula><tex-math notation="LaTeX">$i$</tex-math></inline-formula> th party <inline-formula><tex-math notation="LaTeX">$\mathsf {Party}_i$</tex-math></inline-formula> . In this article, we propose a novel and secure <i>two-party private function evaluation</i> (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 <inline-formula><tex-math notation="LaTeX">$f$</tex-math></inline-formula> , 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.