Fast Garbling of Circuits over 3-Valued Logic

In the setting of secure computation, a set of parties wish to compute a joint function of their private inputs without revealing anything but the output. Garbled circuits, first introduced by Yao, are a central tool in the construction of protocols for secure two-party computation (and other tasks like secure outsourced computation), and are the fastest known method for constant-round protocols. In this paper, we initiate a study of garbling multivalent-logic circuits, which are circuits whose wires may carry values from some finite/infinite set of values (rather than only True and False). In particular, we focus on the three-valued logic system of Kleene, in which the admissible values are True, False, and Unknown. This logic system is used in practice in SQL where some of the values may be missing. Thus, efficient constant-round secure computation of SQL over a distributed database requires the ability to efficiently garble circuits over 3-valued logic. However, as we show, the two natural (naive) methods of garbling 3-valued logic are very expensive. In this paper, we present a general approach for garbling three-valued logic, which is based on first encoding the 3-value logic into Boolean logic, then using standard garbling techniques, and final decoding back into 3-value logic. Interestingly, we find that the specific encoding chosen can have a significant impact on efficiency. Accordingly, the aim is to find Boolean encodings of 3-value logic that enable efficient Boolean garbling (i.e., minimize the number of AND gates). We also show that Boolean AND gates can be garbled at the same cost of garbling XOR gates in the 3-value logic setting. Thus, it is unlikely that an analogue of free-XOR exists for 3-value logic garbling (since this would imply free-AND in the Boolean setting).