Improving the Efficiency of Private Function Evaluation via Optimized Universal Circuits

Private Function Encryption (PFE) enables two par ties, one holding a private input x and the other in possession of a private function f, to compute f(x) in such that each party learns nothing substantial beyond f(x). PFE is typically achieved by evaluating Yao’s two-party computation protocol over a universal circuit that encodes the private function into a private input. Thus, the efficiency of the PFE protocol highly relies on the size of the underlying universal circuit. A universal circuit (UC) is a general purpose circuit that can simulate arbitrary circuits (up to a certain sizen).In1976,Valiantprovidedarecursiveconstructionofuniver sal circuits and gave a theoretical construction of UC of asymptotic (multiplicative) size 4.75n log n respectively, which matches the asymptotic lower bound Ω(n log n) up to some constant fac tor. More recently, (Kiss et al. 2016) validated the practicality of universal circuits in real-world privacy-preserving applications. Subsequent work by (Günther et al. 2017) and (Alhassan et al. 2020) enhanced UCs’ practicality through hybrid constructions with various optimizations. This work focuses onoptimizing thesize efficiency of universal circuits. Our contributions are three-fold: Optimized component: We first optimize the underlying component of Valiant’s universal circuits to achieve anasymptotic size of 4.5nlogn. More efficient framework: We propose an improved frame work for constructing universal circuits, under which we give a UC construction of asymptotic size 3nlogn. This improves the previous state-of-the-art construction by 33%, which corresponds to the same fraction of reduction in the communication cost of UC-based PFE protocols. Tigher lower bound: To complement our constructive results, weshowthat the (multiplicative) size of the universal circuits is lower bounded by 2n log n. We implement the 2-way universal circuits and evaluate their performance against other implementations, confirming our theo retical analysis.