Cryptographic protocols for secure two-party computation (2PC) perform arbitrary computation on secret inputs. 2PC has been applied to privacy-preserving record linkage and machine learning, for areas such as medicine where maintaining privacy is crucial. One of the most practical techniques for 2PC is garbled circuits, which are based entirely on symmetric key cryptography, except for an initial oblivious transfer (OT) phase. When garbled circuits are combined with OT extension, a technique where symmetric key cryptography is used to generate many OTs based on an initial batch of 128, it becomes a computationally efficient 2PC protocol that requires only minimal cryptographic assumptions. However, the protocol requires significant communication, which typically becomes a bottleneck.
We present an efficient framework for 2PC based on garbled circuits and OT extension. Our techniques trade some computational efficiency for reduced communication, lessening the communication bottleneck. Our OT extension is the first to improve on the communication efficiency of IKNP (Ishai et al., Crypto 2003) without using additional non-symmetric-key assumptions. Our garbling scheme is the first that uses less communication than the half-gates scheme of Zahur, Rosulek, and Evans (Eurocrypt 2015).
