License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2022.15
URN: urn:nbn:de:0030-drops-164933
Go to the corresponding LIPIcs Volume Portal

Asharov, Gilad ; Cohen, Ran ; Shochat, Oren

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

LIPIcs-ITC-2022-15.pdf (0.7 MB)


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 with 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.

BibTeX - Entry

  author =	{Asharov, Gilad and Cohen, Ran and Shochat, Oren},
  title =	{{Static vs. Adaptive Security in Perfect MPC: A Separation and the Adaptive Security of BGW}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-164933},
  doi =		{10.4230/LIPIcs.ITC.2022.15},
  annote =	{Keywords: secure multiparty computation, perfect security, adaptive security, BGW protocol}

Keywords: secure multiparty computation, perfect security, adaptive security, BGW protocol
Collection: 3rd Conference on Information-Theoretic Cryptography (ITC 2022)
Issue Date: 2022
Date of publication: 30.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI