Generic 2-Party PFE with Constant Rounds and Linear Active Security, and Efficient Instantiation

The paper considers generic construction of 2-party private function evaluation (PFE) in the malicious adversary model. There is hitherto only one concrete design of actively secure 2-party PFE protocol (Liu et al. at PKC 2022, and LWY hereafter) with constant rounds and linear complexity. One interesting feature of LWY is its function reusability (i.e., the same function is involved in multiple executions of LWY) which makes its execution more efficiently from the second execution. Nevertheless, in its first execution (in particular for those settings where only one invocation of the function is required), LWY is quite involved and too inefficient to be of practical use. For these settings (of non-reusable private functions), we initiate a generic construction of 2-party PFE protocol with constant rounds and linear complexity in the malicious adversary model based on Yao’s garbled circuit and singly homomorphic encryption. When instantiated with ElGamal encryption and Groth secret shuffle (J. Cryptology 2010), the generic construction effectuates a novel concrete design of 2-party PFE, which has better performance and reduces 51.2% communication bits and 52.4% computation costs, compared to LWY (in its first execution) at the same security level. It even outperforms several 2-party PFE protocols (Katz and Malka at AISACRYPT 2011, and Mohassel and Sadeghian at EUROCRYPT 2013) that are secure in the semi-honest adversary model from the communication perspective. The proposed PFE and LWY thus make optimal solutions available for non-reusable and reusable private functions, respectively.