Paper 2022/758

Static vs. Adaptive Security in Perfect MPC: A Separation and the Adaptive Security of BGW

Gilad Asharov, Bar-Ilan University
Ran Cohen, Reichman University
Oren Shochat, Bar-Ilan University

Adaptive security is a highly desirable property in the design of secure protocols. It tolerates adversaries that corrupt parties as the protocol proceeds, as opposed to static security where the adversary corrupts the parties at the onset of the execution. The well-accepted folklore is that static and adaptive securities are equivalent for perfectly secure protocols. Indeed, this folklore is backed up by a transformation by Canetti et al. (EUROCRYPT'01), showing that any perfectly secure protocol that is statically secure and satisfies some basic requirements is also adaptively secure. Yet, the transformation results in an adaptively secure protocol with inefficient simulation (i.e., where the simulator might run in super-polynomial time even if the adversary runs just in polynomial time). Inefficient simulation is problematic when using the protocol as a sub-routine in the computational setting. Our main question is whether an alternative efficient transformation from static to adaptive security exists. We show an inherent difficulty in achieving this goal generically. In contrast to the folklore, we present a protocol that is perfectly secure with efficient static simulation (therefore also adaptively secure with inefficient simulation), but for which efficient adaptive simulation does not exist (assuming the existence of one-way permutations). In addition, we prove that the seminal protocol of Ben-Or, Goldwasser, and Wigderson (STOC'88) is secure against adaptive, semi-honest corruptions with efficient simulation. Previously, adaptive security of the protocol, as is, was only known either for a restricted class of circuits or for all circuits but with inefficient simulation.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ITC - Information Theoretic Cryptography 2022
Secure multiparty computationperfect securityadaptive securityBGW protocol
Contact author(s)
Gilad Asharov @ biu ac il
cohenran @ runi ac il
oren shochat6 @ gmail com
2023-10-29: revised
2022-06-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gilad Asharov and Ran Cohen and Oren Shochat},
      title = {Static vs. Adaptive Security in Perfect MPC: A Separation and the Adaptive Security of BGW},
      howpublished = {Cryptology ePrint Archive, Paper 2022/758},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.