Paper 2023/1013
Best of Both Worlds: Revisiting the Spymasters Double Agent Problem
Abstract
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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in CRYPTO 2023
- DOI
- 10.1007/978-3-031-38557-5\_11
- Keywords
- 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 - History
- 2023-12-18: revised
- 2023-06-29: received
- See all versions
- Short URL
- https://ia.cr/2023/1013
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1013, 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}, url = {https://eprint.iacr.org/2023/1013} }