An Efficient Outsourced Oblivious Transfer Extension Protocol and Its Applications

Oblivious transfer (OT) is a cryptographic primitive originally used to transfer a collection of messages from the sender to the receiver in an oblivious manner. OT extension protocol reduces expensive asymmetric operations by running a small number of OT instances first and then cheap symmetric operations. While most earlier works discussed security model or communication and computation complexity of OT in general case, we focus on concrete application scenarios, especially where the sender in the OT protocol is a database with less computation and limited interaction capability. In this paper, we propose a generic outsourced OT extension protocol (OTex) that outsources all the asymmetric operations of the sender to a semihonest server so as to adapt to specific scenarios above. We give OTex a standard security definition, and the proposed protocol is proven secure in the semihonest model. In OTex, the sender works on the fly and performs only symmetric operations locally. Whatever the number of rounds OT to be executed and the length of messages in OT to be sent, our protocol realizes optimal complexity. Besides, OTex can be used to construct high-level protocols, such as private membership test (PMT) and private set intersection (PSI). We believe our OTex construction may be a building block in other applications as well