Private Function Encryption (PFE) enables two parties, 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 size$n$). In 1976, Valiant provided a recursive construction of universal circuits and gave a theoretical construction of UC of asymptotic (multiplicative) size$4.75 n\log n$respectively, which matches the asymptotic lower bound$\Omega (n\log n)$up to some constant factor. 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 on optimizing the size efficiency of universal circuits. Our contributions are three-fold:•Optimized component:We first optimize the underlying component of Valiant's universal circuits to achieve an asymptotic size of$4.5 n\log n$4.5nlogn.•More efficient framework:We propose an improved framework for constructing universal circuits, under which we give a UC construction of asymptotic size$3n\log n$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, we show that the (multiplicative) size of the universal circuits is lower bounded by$2n\log n$2nlogn.We implement the 2-way universal circuits and evaluate their performance against other implementations, confirming our theoretical analysis.

Through tremendous efforts, the communication cost of secure multi-party computation (MPC) in the honest-majority setting has been significantly improved. In particular, the state-of-the-art honest-majority MPC protocol by Escudero et al. (CCS'22) takes 12 field elements in total per multiplication gate for arithmetic circuits in the online phase. However, it still requires$12 log (5n/4$) bits of online communication per AND gate for Boolean circuits. That is, for Boolean circuits, no MPC protocol with constant online communication is known. In this paper, we present an unconditionally secure MPC protocol for Boolean circuits in the honest-majority setting, which has constant online communication complexity and the offline communication complexity linear to the number$n$of parties. We first describe the semi-honest MPC protocol and then show how to extend it to achieve malicious security, where the maliciously secure protocol has the same communication cost as the semi-honest protocol. In particular, our protocol achieves the amortized communication cost 36 bits per AND gate in the online phase and 30n + 24 bits per AND gate in the offline phase.