Extending Cut-and-Choose Oblivious Transfer

Motivated by the recent rapid progress in improving efficiency of secure computation, we study cut-and-choose oblivious transfer - a basic building block of state-of-the-art constant round two-party secure computation protocols. In particular, we study the question of realizing cut-and-choose oblivious transfer and its variants in an OT-hybrid model. Towards this, we provide new definitions of cut-and-choose oblivious transfer (and its variants) that suffice for its application in cut-and-choose techniques for garbled circuit based two-party protocols. Our main result is that it is possible to realize cut-and-choose OT and its variants with very little concrete communication overhead while using only a small number of calls to the OT functionality. Further, our new definitions lead us to a construction for multistage cut-and-choose OT (a variant useful in the multiple execution setting) that is more efficient than prior work.