Fast Garbling of Circuits over 3-Valued Logic

被引:2
作者
Lindell, Yehuda [1 ]
Yanai, Avishay [1 ]
机构
[1] Bar Ilan Univ, Ramat Gan, Israel
来源
PUBLIC-KEY CRYPTOGRAPHY - PKC 2018, PT I | 2018年 / 10769卷
基金
欧洲研究理事会;
关键词
D O I
10.1007/978-3-319-76578-5_21
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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).
引用
收藏
页码:620 / 643
页数:24
相关论文
共 12 条
[1]  
[Anonymous], 1987, 19 ACM STOC, DOI [DOI 10.1145/28395.28420, 10.1145/28395.28420]
[2]   Linicrypt: A Model for Practical Cryptography [J].
Carmer, Brent ;
Rosulek, Mike .
ADVANCES IN CRYPTOLOGY (CRYPTO 2016), PT III, 2016, 9816 :416-445
[3]  
de Haan L, 2005, ORACLE MAGAZINE
[4]  
Goldreich O., 2004, Basic Applications
[5]  
ISO/IEC, 2016, 907522016 ISOIEC
[6]  
Kleene StephenCole., 1952, BIBLIOTHECA MATH
[7]  
Kolesnikov V, 2008, LECT NOTES COMPUT SC, V5126, P486, DOI 10.1007/978-3-540-70583-3_40
[8]   A Proof of Security of Yao's Protocol for Two-Party Computation [J].
Lindell, Yehuda ;
Pinkas, Benny .
JOURNAL OF CRYPTOLOGY, 2009, 22 (02) :161-188
[9]  
Microsoft, NULL UNKN TRANS SQL
[10]  
Pinkas B, 2009, LECT NOTES COMPUT SC, V5912, P250, DOI 10.1007/978-3-642-10366-7_15