Cryptology ePrint Archive: Report 2017/976

Improvements for Gate-Hiding Garbled Circuits

Mike Rosulek

Abstract: Garbled circuits have been highly optimized for practice over the last several years. Today's most efficient constructions treat different types of gates (e.g., AND vs XOR) differently; as such, they leak the type of each gate. In many applications of garbled circuits, the circuit itself is public, so such leakage is tolerable. In other settings, however, it is desirable to hide the type of each gate.

In this paper we consider optimizing garbled circuits for the gate-hiding case. We observe that the best state-of-the-art constructions support only a limited class of gate functions, which turns out to undermine their improvements in several settings. These state-of-the-art constructions also require a non-minimal hardness assumption.

We introduce two new gate-hiding constructions of garbled circuits. Both constructions achieve the same communication complexity as the best state-of-the-art schemes, but support a more useful class of boolean gates and use only the minimal assumption of a secure PRF.

Category / Keywords: cryptographic protocols / garbled circuits, Yao's protocol, private function evaluation

Original Publication (with major differences): Indocrypt 2017

Date: received 4 Oct 2017

Contact author: rosulekm at eecs oregonstate edu

Available format(s): PDF | BibTeX Citation

Version: 20171005:143343 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]