Paper 2021/739

A New Framework for Garbled Circuits

Tomer Ashur and Efrat Cohen and Carmit Hazay and Avishay Yanai

Abstract

Garbled circuits are a fundamental cryptographic building block to encode Boolean circuits as a sequence of encrypted values. This sequence allows two parties to securely evaluate the circuit, e.g., without revealing their respective inputs. At the heart of any garbling scheme lies a randomized algorithm projecting the plain values into a larger domain. Emerging from a large body of work, the common paradigm meets two implicit properties: the circuit is garbled progressively gate-wise; and all underlying algorithms are linear. In this setting, the communication complexity is measured in the number of sent ciphertexts and shown to be optimal with a scheme sending two ciphertexts per AND gate and no ciphertexts per XOR gate (Zahur, Rosulek and Evans, Eurocrypt'15). We revisit the common paradigm and extend the seminal work of Bellare, Hoang, and Rogaway from CCS 2012 to present for the first time an abstraction of the garbling algorithm itself. This abstraction highlights how Yao's work (Yao, FOCS'86) and all its optimizations focused on improving just one aspect of the garbling. We then discuss how improving the other aspects could provide new ways to overcome the limitations of existing schemes. As a proof of concept we present a non-bijective scheme avoiding Zahur et al.'s bound, achieving a communication complexity of a single data item which is not a ciphertext.