No fully-black-box reduction from two-round OT to two-round semi-honest MPC

Unconditional · against fully-black-box reductions · ABG+20

Statement

There is a three-party functionality that no two-round protocol secure against semi-honest adversaries computes using a two-round OT protocol only as a black box. Hence there is no fully-black-box construction of two-round semi-honest MPC from two-round OT, and the non-black-box use of the OT in the two-round protocols of GS18 and BL18 is necessary. A similar separation holds when one starts from any two-party functionality other than OT — ABG+20.

Notes

• ABG+20 also present a complete 4-party functionality, and give evidence that ruling out a complete 3-party functionality, or black-box constructions of 3-round MPC from 2-round OT, is difficult — ABG+20.
• Three rounds suffice with black-box use: two-round semi-honest OT gives three-round semi-honest MPC that uses the OT only as a black box — PS21.
• With non-black-box use of the OT, two rounds suffice (two-round OT ⇒ two-round semi-honest MPC) — GS18, BL18.