Computationally Secure Oblivious Transfer

We describe new computationally secure protocols of 1-out-of-N oblivious transfer, k-out-of-N oblivious transfer, and oblivious transfer with adaptive queries. The protocols are very efficient compared with solutions based on generic two-party computation or on information-theoretic security.The 1-out-of-N oblivious transfer protocolrequires only log N executions of a 1-out-of-2oblivious transfer protocol. Thek-out-of-N protocol is considerably more efficient than krepetitions of 1-out-of-N oblivious transfer, as is the construction for oblivious transfer with adaptive queries. The efficiency of the new oblivious transfer protocols makes them useful for many applications. A direct corollary ofthe 1-out-of-N oblivious transfer protocol is an efficient transformationof any Private Information Retrieval protocol to a Symmetric PIR protocol.