Paper 2023/1013

Best of Both Worlds: Revisiting the Spymasters Double Agent Problem

Anasuya Acharya, Bar-Ilan University
Carmit Hazay, Bar-Ilan University
Oxana Poburinnaya
Muthuramakrishnan Venkitasubramaniam, Georgetown University

This work defines a notion of secure multiparty computation: MPC with fall-back security. Fall-back security for an $n$-party protocol is defined with respect to an adversary structure $\mathcal{Z}$ wherein security is guaranteed in the presence of both a computationally unbounded adversary with adversary structure $\mathcal{Z}$, and a computationally bounded adversary corrupting an arbitrarily large subset of the parties. This notion was considered in the work of Chaum (Crypto 89) via the Spymaster's double agent problem where he showed a semi-honest secure protocol for the honest majority adversary structure. Subsequent works extend this to give maliciously secure protocols tolerating threshold adversaries. Our first main result is a compiler that can transform any $n$-party protocol that is semi-honestly secure with statistical security tolerating a general adversary structure $\mathcal{Z}$ to one that (additionally) provides semi-honest fall-back security w.r.t $\mathcal{Z}$. The resulting protocol has optimal round complexity, up to a constant factor, and is optimal in assumptions and the adversary structure. Our second result fully characterizes when malicious fall-back security is feasible. More precisely, we show that malicious fallback secure protocol w.r.t $\mathcal{Z}$ exists if and only if $\mathcal{Z}$ admits unconditional MPC against a semi-honest adversary (namely, iff $\mathcal{Z} \in \mathcal{Q}^2$).

Note: This rivision includes a comparison with prior work that was missed in the earlier version and an updated version of our claims for the threshold setting.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
MPC with Fall-back SecurityBest of Both WorldsMPC Protocols Compiler
Contact author(s)
acharya @ biu ac il
carmit hazay @ biu ac il
oxanapob @ bu edu
mv783 @ georgetown edu
2023-12-18: revised
2023-06-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anasuya Acharya and Carmit Hazay and Oxana Poburinnaya and Muthuramakrishnan Venkitasubramaniam},
      title = {Best of Both Worlds: Revisiting the Spymasters Double Agent Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1013},
      year = {2023},
      doi = {10.1007/978-3-031-38557-5\_11},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.