Adaptively Secure Computation for RAM Programs
Laasya Bangalore, Rafail Ostrovsky, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam
Abstract:
In this work, we study the communication complexity of secure multiparty computation under minimal assumptions in the presence of an adversary that can adaptively corrupt all parties eventually. Specifically, we are interested in understanding the complexity when modeling the underlying function as a RAM program. Under minimal assumptions, the work of Canetti et al. (STOC 2017) and Benhamouda et al. (TCC 2018) give protocols whose communication complexity grows quadratically in the circuit size when the computation is expressed as a Boolean circuit. In this work, we obtain the first two-round two-party computation protocol, which is secure against adaptive adversaries who can adaptively corrupt all parties where the communication complexity is proportional to the square of the RAM complexity of the function up to polylogarithmic factors assuming the existence of non-committing encryption.
comment:
EUROCRYPT (2) 2022: 187-216
Fetch PDF file of the paper