3

It is impossible to achieve (fully) information theoretic oblivious transfer (OT), since OT is complete (and so can compute all functions). Since many (most) functions cannot be securely computed information theoretically with two parties, this means that it's impossible. Having said that, we do have OT protocols that provide information-theoretic security ...


3

I worry that the first problem is harder than your instructor suspects. We had to work a little hard to get a multi party PSI protocol based on efficient OT in our paper Practical Multi-party Private Set Intersection from Symmetric-Key Techniques, by Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, Ni Trieu If I remember correctly, we may ...


2

These two cases are trivial cases, usually don't need to argue about because they are definitely simulatable. In the first case, both parties are controlled by the adversary. In the simulation, the simulator simulates both the corrupted sender and the corrupted receiver. The simulator can simply use the adversary as a subroutine to simulate each party, ...


2

The most straightward approach is to have Bob select two random symmetric keys $k_0$ and $k_1$ and have Bob publish $Encrypt_{k_0}( x_0^i )$ and $Encrypt_{k_1}( x_1^i)$. Then, Bob does an OT with Alice, allowing Alice to select between $k_0$ or $k_1$. She learns $k_b$, and then is able to decrypt all the $Encrypt_{k_b}( x_b^i )$ values, resulting in her ...


1

Any efficiently computable function can be represented by a circuit containing XOR gates and AND gates - AND gates alone would not suffice (but NAND gates would). The standard practice in secure computation is to use this {XOR, AND} basis to represent functions, since evaluating a XOR is often very cheap (it only involves cheap local operations, and no ...


1

First, what is $AND_B$? $AND_B$ is the asymmetric AND protocol, in which Alice and Bob each has a bit $x$ and $y$, at the end Alice always learns nothing (get output 0) and Bob learns $x \land y$. In Lemma 4 it says $AND_B$ can be realized by 1 invocation of $(^2_1)OT$. Then what is $G_{m+1}$? $G_{m}$ is a protocol in which Alice has a $m$-bit long string $...


1

With the most standard approaches, the cost of performing $m$ $1$-out-of-$n$ oblivious transfers of strings of length $\ell$ with security parameter $\lambda$ is $O(m(\lambda + n\ell))$ (see e.g. this paper, Section 5.3). Use $m=1$ above to have the asymptotic cost for a singe OT. Note that this can be improved in various settings - e.g., it can be typically ...


Only top voted, non community-wiki answers of a minimum length are eligible