I'm reading papers related to the IPS compiler.

I'm confused about one point: The paper IPS08 (PDF) proposed a protocol with $O(s)$ communication for a circuit of size $s$ in the OT-Hybrid model.

Are they actually assuming a bit-OT Hybrid model, where parties can perform OT on single bits? For example, the communication of GMW is counted as $O(m^2 s)$ for m parties with circuit size s.


1 Answer 1


They do not specifically assume a bit-OT… but at least in the semi-honest case, it seems that having an ideal bit-OT is indeed sufficient.

If you are wondering about the fact that they do not specify which kind of OT they use: their purpose was to focus on a black box use of the primitive; bit OT and string OT can be easily reduced in black box to each other.

And if you are wondering about the fact that the communication is only $O(s)$: the costs of the OTs are not counted, as they are replaced by an ideal primitive to which all the players have access.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.