Revisiting the Spymasters: The Double Agent Problem
Delve into the intriguing world of spymaster tactics with a focus on the double agent problem and the feasibility of secure multiparty computation protocols. Explore motivations, related works, and groundbreaking results in this complex domain.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
Presentation Transcript
Best of Both Worlds Revisiting the Spymasters Double Agent Problem Anasuya Acharya Carmit Hazay Oxana Poburinnaya Muthuramakrishnan Venkitasubramaniam Bar-Ilan University Bar-Ilan University Georgetown University
When is MPC Feasible? Security from Unbounded Adversaries possible for honest majority Security from Arbitrary Corruption possible for PPT adversaries Together: Impossible in the plain model 5
MPC with Fallback Security One Protocol Secure in the presence of Unbounded adversary for a limited adversary structure Fall-back - PPT adversary corrupting any subset of the parties similar notion considered in [Cha89] 6
Related Work 2PC with one unbounded and one PPT corruption round optimal protocols [KM20, KO04, GMPP16, BPS22] David versus Multiple Goliaths [CDG87] Semi-Honest unconditional security for a designated party and arbitrary PPT corruption The Spymaster s Double Agent Problem [Cha89] Semi-Honest security for <n/2 unbounded corruption and arbitrary PPT corruption Malicious security for <n/3 unbounded corruption and <n/2 PPT corruption 7
Our Results Theorem. Assuming broadcast, any n-party functionality can be realized by a protocol with malicious fallback security for adversary structure Z with semi-honest security for unbounded adversaries. Remark 1. Malicious security for semi-honest adversary structure security with abort, broadcast Remark 2. Black-box in underlying assumptions improves over [Cha89, CDG87] Remark 3. Asymptotically optimal round complexity improves over [CDG87] round complexity 8
David vs Multiple Goliaths TFHE pk, [sk] pk, [sk] P1 Pn Cn C1=Enc(pk,x1) pk, [sk] P2 C2 {C} Any Functionality Semi-Honest Secure Unbounded A : all-but-Pn PPT A : any subset pk, [sk] P3 C3 Ev(f, {C}) pk, [sk] Pn-1 Cn-1 11
David vs Multiple Goliaths Dist. GC r1 P1 Pn G P2 r2 = x ? Gb(f) G Any Functionality Semi-Honest Secure Unbounded A : all-but-Pn PPT A : any subset P3 r3 OT labels X Pn-1 f(x) = Ev(G, X) rn-1 12
Compiling to Fallback Security [ ] [ ] [ ] [ ] n-Party Protocol Compiler Semi-Honest Secure Unbounded A : < n/2 parties PPT A : any subset 13
Protocol in the Online-Offline Paradigm n-Party Offline Protocol Authenticated Multiplication Triples n-Party Online Protocol Functionality F using Authenticated Triples Maliciously Fallback Secure Inspired by [HVW20] Malicious Unbounded Secure Dishonest Majority in the Fcom-hybrid [DPSZ12] Authenticated Triples n-Party Commitment n-Party Commitment Fcom Maliciously Fallback Semi-Honest Fallback Maliciously Fallback Secure 15
Fcom Fallback Secure Commitment Protocol x x n-Party Commitment Protocol Maliciously Secure Unbounded A : any subset in ZS PPT A : any subset 16
Fallback Secure Commitment Protocol 2-party Statistically Hiding Commitments 2-party Statistically Binding Commitments Hiding Secret Sharing Binding Extractable using Statistical ZK Arguments 2-party Statistically Binding Commitments Proof of Knowledge Extractable using ZK 17
Fallback Secure Commitment Protocol x ComSH(x;r) SZKAoK(x,r; c) ShareZs(x) { [x]i} ComSB([x]i;ri) ZKPoK([x]i,ri; ci) x, r, { [x]i}, ri used in look-ahead trapdoor commitment scheme [PW09] 18
PPT Adversary (Security with Abort) Future Work Best-of-both-worlds for GOD and security with abort [Kat07, IKK+11, PRS20] This Work Unbounded Adversary (Security with Abort) Guaranteed Output Delivery 19
Thank You! https://ia.cr/2023/1013 20
