Topology-hiding garbled circuits without universal circuits

At present, garbled circuits play a vital role in secure multi-party computations. Originating from the garbling scheme of Yao, there is much work on how to hide these types of Boolean gates. At the same time, the universal circuit becomes the primary tool for hiding circuit topologies, which are also part of the private information on circuits. However, this technique is limited to the asymptotically lower bound on the size of the universal circuit where the transformation of the Boolean circuit into a universal circuit leads to an increase in the size of the circuit. In this paper, we propose a new topology-hiding garbling scheme. Our construction has a smaller size of the garbled input than folklore way. Our scheme builds on recent work on updatable laconic oblivious transfer (ULOT) in CRYPTO 2017 and the ULOT scheme is modified to hide the database’s location for receivers. Based on the new scheme, our topology-hiding garbling scheme is proven to provide topology-hiding indistinguishability-based selective security. The topology-hiding garbling scheme also produces a secure two-round private function evaluation scheme for semi-honest adversaries with linear communication costs.