Abstract. We provide protocols for the following two-party problem: One party, the sender, has N values and the other party, the receiver, would like to learn k of them, deciding which ones in an adaptive manner (i.e. the ith value may depend on the rst i ?1 values). The sender does not want the receiver to obtain more than k values. This is a variant of the well known Oblivious Transfer (OT) problem and has applications in protecting privacy in various settings. We present e cient protocols for the problem that require an O(N) computation in the preprocessing stage and xed computation (independent of k) for each new value the receiver obtains. The on-line computation involves roughly log N invocations of a 1-out-2 OT protocol. The protocols are based on a new primitive, sum consistent synthesizers.
Oblivious transfer with adaptive queries was proposed by Naor and Pinkas REF where the receiver can query the ith value depending on the first i−1 values.
Oblivious Transfer with Adaptive Queries
CRYPTO
Computer Science