Cut-and-Choose Bilateral Oblivious Transfer and Its Application in Secure Two-party Computation

Abstract. In secure two-party computation protocols, the cut-and-choose paradigm is used to prevent the malicious party who constructs the garbled circuits from cheating. In previous realization of the cut-and-choose technique on the garbled circuits, the delivery of the random keys is divided into multiple stages. Thus, the round complexity is high and the consistency of cut-and-choose challenge should be proved. In this paper, we introduce a new primitive called cut-and-choose bilateral oblivious transfer, which transfers all necessary keys of garbled circuits in one process. Specifically, in our oblivious transfer protocol, the sender inputs two pairs (x0, x1), (y0, y1) and a bit τ; the receiver inputs two bits σ and j. After the protocol execution, the receiver obtains xτ, yσ for j = 1, and x0, x1, y0, y1 for j = 0. By the introduction of this new primitive, the round complexity of secure two-party computation protocol can be decreased; the cut-and-choose challenge j is no need to be opened anymore, therefore the consistency proof of j is omitted. In addition, the primitive is of independent interest and could be useful in many cut-and-choose scenarios