Abstract

Many works aiming to optimize round complexity assume that broadcast comes "for free." In practice, however, broadcast must be implemented either through a bulletin board or via protocols over point-to-point channels—both of which incur significant costs. This raises a natural question: what guarantees can still be achieved if the broadcast rounds in round-optimal protocols are replaced with point-to-point communication? This question has been thoroughly investigated in the computational setting, both in the dishonest majority case with setup ([CGZ20], EUROCRYPT'20) and without setup ([CDRSXY23], TCC'23), as well as in the honest majority setting with setup ([DMRSY21], CRYPTO'21; [DRSY23], EUROCRYPT'23). More recently, this question was investigated in the context of round-optimal information-theoretic MPC ([CDRSY], currently under submission). This talk will survey the current state-of-the-art in this area and present key upper and lower bound techniques developed so far.