Insights into Secure Computation with Minimal Interaction
This paper revisits the concept of secure computation with minimal interaction, focusing on the challenges and possibilities of achieving secure multiparty computation in 2 rounds. Specifically exploring scenarios with 3 and 4 parties, the study delves into the reasons for choosing n=3, n=4, and t=1 in cases of malicious corruption. The research highlights the importance of structure and rounds in ensuring security while addressing the complexities of MPC in different party and corruption settings.
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.
E N D
Presentation Transcript
Secure Computation with Minimal Interaction, Revisited Yuval Ishai (Technion) Ranjit Kumaresan (MIT) Eyal Kushilevitz (Technion) Anat Paskin-Cherniavsky (Ariel)
Secure Multiparty Computation IDEAL Parties submit inputs Parties get back outputs IDEAL REAL Done by MPC [Yao86,GMW87, ] lose the minimal structure Broadcast requires 2 rounds Even with broadcast, 3 rounds necessary when t 2 [GIKR02]
This Talk Revisit question of MPC in 2 rounds Specifically, n = 3 and n = 4 cases Tolerating t = 1 malicious corruption Minimal setting: no broadcast, no set up Why 2 rounds? Minimal structure MPC impossible in 1 round Why n = 3, n = 4? Why t = 1? n = 2: 5-round lower bound [KO04] n 5: 2-round [IKP10] Guaranteed output delivery No broadcast, no set up 3-round lower bound for t > 1 [GIKR02] Typically small number of parties More than 1 corruption unlikely E.g.: sharemind, danish beet Redundancy recoverability
Prior Work: 3-party Broadcast impossible for t = 1; need computational assumptions LWE+PKE/iO+CRS 2-round MPC for t < n/2 [GGHR14, AJL+12,GLS15,MW15] Prior Work: 4-party 2-round perfect SFE impossible [GIKR02] 2-round SFE with selective abort security [IKP10] Statistical VSS: 1-round sharing, 2-round reconstruction [PCRR09] 2-round sharing, 1-round reconstruction [Agr12] LWE + PKE / iO + CRS 2-round MPC for t < n/2 2-round general SFE in preprocessing model [IKMOP13] Correlated randomness size = Exponential in input size
Our Results: 3-party 2-round, no broadcast, no set up, t =1 malicious corruption General SFE with selective abort security Adv can selectively deny output to individual parties Blackbox PRG, stat. security for NC1 Concrete efficiency comparable to semihonest Yao Our Results: 4-party 2-round, no broadcast, no set up, t = 1 malicious corruption Statistical VSS (implies 2-round coin tossing, simultaneous broadcast) 1 round sharing, 1 round reconstruction Statistical Linear Function Evaluation with guaranteed output delivery Impossibility for general SFE; even with broadcast; even with non-rushing adv Computational General SFE with guaranteed output delivery Assumption: one-to-one one-way functions General SFE in preprocessing model with guaranteed output delivery Correlated randomness = O(input size); Blackbox PRG, stat. security for NC1 All +ve results previously unknown even with broadcast channel
Talk Outline Tools: PSM, secret sharing 3-party security with selective abort 4-party statistical VSS 4-party linear function evaluation 4-party impossibility of statistical SFE 4-party computational SFE 4-party statistical SFE in preprocessing model
Private Simultaneous Messages PSM [FKN94] f(x, y) Multiple clients sharing randomness Single referee gets one message from each client Referee learns only f(x,y) Simple PSM protocol via garbled circuits : Randomness defines GC/GC input keys Client mesg = GC + input keys based on client input Keys validated via authentication (MAC/Hash) Referee rejects if GC s don t match or keys invalid Else evaluates GC to learn f(x,y) Shared randomness x y Secret Sharing Additive sharing 2-out-of-2 sharing Secret s s1 + s2 Shares: s1, s2 1-private 3-party CNF sharing Secret s s1 + s2 + s3 Shares: (s2, s3), (s3, s1), (s1, s2) Pairs of shares have common values Efficient extendability: Given secret & one share, possible to compute other shares
Talk Outline Tools: PSM, secret sharing 3-party security with selective abort 4-party statistical VSS 4-party linear function evaluation 4-party impossibility of statistical SFE 4-party computational SFE 4-party statistical SFE in preprocessing model
2-Round 3-Party Protocol with Selective Abort Security Round 1 Round 2 PSM shared randomness Additive input sharing PSM protocol messages Round 2 PSM protocol reconstructs inputs Joint view of pairs of parties defines inputs Evaluates f on reconstructed inputs Insecure against malicious adversary Selective Abort Inconsistent inputs (next slide) Selective Abort: Blue PSM aborted
2-Round 3-Party Protocol with Selective Abort Security Round 1 Round 2 Additive sharing of x PSM messages corresponding to y x Inconsistent inputs attack Blue, Red PSM evaluate f on y Green PSM evaluates f on x Honest parties accept wrong output View Reconstruction Trick PSM reconstructs secret share of PSM client input ought to be held by PSM referee (in addition to eval. f) Accept output only if reconstructed share matches distributed share Stat. security for NC1; Comp. security with blackbox PRG
Talk Outline Tools: PSM, secret sharing 3-party security with selective abort 4-party statistical VSS 4-party linear function evaluation 4-party impossibility of statistical SFE 4-party computational SFE 4-party statistical SFE in preprocessing model
Verifiable Secret Sharing Privacy: dealer input secret hidden from adv Commitment: unique secret defined at end of sharing is reconstructed Correctness: unique secret equals honest dealer s input CNF sharing Na ve VSS Secret s s1 + s2 + s3 Shares: (s2, s3), (s3, s1), (s1, s2) Sharing: 1-private 3-party CNF Parties share common value Recon.: Broadcast shares Defines inconsistency graphs Inconsistent CNF shares Consistent CNF shares
Protocol Idea: Cut & choose + MAC Trick Dealer sends k MACs to disputed parties (+ CNF shares) Undisputed party gets k MAC keys from dealer Sends random k/2 keys to a disputed party (priv. channels) Sends all k MAC keys to the other (priv. channels) Decision for disputed parties : Compute VOTES Self: all k/2 MACs pass Other: all k/2 MACs pass +at least 1 of remaining k/2 MACs pass Both/No VOTE: discard dealer; else choose winning share Analysis Honest dealer/Bad party: No VOTE without forging 1 of unknown k/2 MAC for bad share Honest disputed party always gets VOTE Bad dealer: Unanimous agreement on VOTES except with negl(k) prob. Stat. 4-party VSS in 2 rounds
Talk Outline Tools: PSM, secret sharing 3-party security with selective abort 4-party statistical VSS 4-party linear function evaluation 4-party impossibility of statistical SFE 4-party computational SFE 4-party statistical SFE in preprocessing model
2-Round 4-Party Statistical Linear Function Evaluation Round 1 Simulation Extraction Same as VSS: CNF Sharing + MAC distribution Extract 0 Resolvable Exactly one disputed party gets VOTE Extract: input reconstructed using value got from winning share Protocol Ideas: PSM + View Reconstruction Trick Private evaluation of function Inconsistency graphs Challenge: different parties hold different versions Exploit linearity to force parties output to be consistent with extracted input Identifiable Both/None get VOTE Input reconstructed using value got from xoring both losing shares
Talk Outline Tools: PSM, secret sharing 3-party security with selective abort 4-party statistical VSS 4-party linear function evaluation 4-party impossibility of statistical SFE 4-party computational SFE 4-party statistical SFE in preprocessing model
Impossibility for 4-party stat. nonlinear function evaluation y_0, y_1 y_0, y_1 y_0, y_1 b b b Message consistent with b = 0 Message consistent with b = 1 Compute output based on these messages only; Output = y_0 Compute output based on these messages only; Output = y_1 Sampling possible Privacy: message does not reveal b Comp. unbounded adv can sample such pairwise consistent messages Attack obtains both outputs Guaranteed output delivery: output can be computed even if adversary aborts Not simulatable in the IDEAL world!
Talk Outline Tools: PSM, secret sharing 3-party security with selective abort 4-party statistical VSS 4-party linear function evaluation 4-party impossibility of statistical SFE 4-party computational SFE 4-party statistical SFE in preprocessing model
2-Round 4-Party Computational SFE Round 1 Round 2 y_0, y_1 y_0, y_1 y_0, y_1 b b b Broadcast com(b) Secret share decommitment Pairwise PSM evaluates function BUT delivers output only if reconstructed decommitment (from shares) opens com(b) Binding Pairwise messages cannot be consistent with both b = 0 and b = 1 Guaranteeing output delivery via View Reconstruction Trick --One honest pair might hold valid decommitment, other honest pairs might not --Adversary aborts in the 2nd round; does not deliver any messages IDEA: PSM also reconstructs views that ought to be held by PSM referee
Talk Outline Tools: PSM, secret sharing 3-party security with selective abort 4-party statistical VSS 4-party linear function evaluation 4-party impossibility of statistical SFE 4-party computational SFE 4-party statistical SFE in preprocessing model
2-Round 4-Party Stat. SFE in Preprocessing Model r1, s2, s3, s4 r2, s1, s3, s4 r4, s1, s2, s3 r3, s1, s2, s4 Correlated Randomness Random pad for each party CNF share each random pad Round 2 Pairwise PSM messages for function: Checks if masked inputs match Check consistency of CNF shares of randomness Unmask within PSM to get true inputs Evaluate function on true inputs Compute CNF share ought to be held by PSM ref Output accepted if reconstructed CNF share matches Round 1 Broadcast masked input Set pairwise PSM rand
Conclusions 2 rounds, no broadcast or set up Tools: PSM, secret sharing 3-party stat. selective abort security 4-party statistical VSS 4-party stat. linear function evaluation 4-party impossibility of statistical SFE 4-party computational SFE (1-1 owf) 4-party statistical SFE in preprocessing model Thank You!
