Can Alice and Bob Guarantee Output to Carol at Ben Gurion University?
Featuring a diverse group of experts from universities such as Ben Gurion University and Georgetown University, this content delves into the dynamics of guaranteeing output in a collaborative setting. The narrative revolves around ensuring a successful outcome for Carol and explores the potential challenges and strategies involved.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Can Alice and Bob Guarantee Output to Carol? Bar Alon Eran Omri Ariel University Ben Gurion University Muthu Venkitasubramaniam Georgetown University
A Question Domain: {? 1,2,3 :1 ? 2} Domain: {? 1,2,3,4 :1 ? 3} Can this be done securely against 2 corruptions s.t. an honest Lisa always gets an output? ? ? ? ? Output receiving party Output receiving party Spoiler: only one can be done Is ? ? = ? Is ? ? = ?
Why Should We Care? Is there something in common? Sure, but I must Is there a new disease? guarantee my output This is private data Let s use an MPC protocol
Is This Possible? [GMW 87, RB 88]: Possible if there is an honest majority [Cleve 86]: Impossible in general if there is no honest majority Does not hold for the solitary output setting [Halevi, Ishai, Kushilevitz, Makriyannis, Rabin 19]: Initiated the study of solitary output secure computation Identified a class of solitary output functionalities that cannot be securely computed without an honest majority Impossibility does not include set disjointness Set disjointness is possible for certain parameters
Is This Possible? [Halevi, Ishai, Kushilevitz, Makriyannis, Rabin 19]: Initiated the study of solitary output secure computation Identified a class of solitary output functionalities that cannot be securely computed without an honest majority Impossibility does not include set disjointness Set disjointness is possible for certain parameters A party can input Three party: All inputs are sets of a fixed size ? Three party: A party can input the entire considered universe Left open: Three parties, domain is ? 1,2,3 :1 ? 2
Our Main Question For what parameters can set disjointness be securely computed without an honest majority? What solitary output functionalities can be securely computed without an honest majority?
Our Main Model Three parties Two inputs Output receiving party has no input The output is a bit At most 2 corruptions ? ? Output receiving party
Our Results A Characterization We characterize the set of solitary output functionalities ?:? ? {0,1} that can be securely computed Impossibility can be extended via player partitioning argument ? ? Output receiving party
Our Results Set Disjointness Consider set disjointness disj?,? with input domain ? ? :? ? ? ? , Then disj?,? can be securely computed ? is even 1 ? < ?/2 For ? {0,?/2} it can be computed by Halevi et al. ? ? Output receiving party
Our Results Multiparty In the ?-party setting, if any set of ? ? + 1 parties can fix the output distribution of ?, then ? can be securely computed tolerating ? corruptions
Our Techniques Impossibility of disj2,3 Domain is {? 1,2,3 :1 ? 2} disj2,3?,? = 1 if and only if ? ? = Is given by the matrix {1} {2} {3} {1,2} {1,3} {2,3} 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0
Warmup Impossibility of Fairness [Makriyannis 14]: {1} {2} {3} {1,2} {1,3} {2,3} 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 ? ? The (possibly) flipped output out1 out out2 out Consider the following experiment: 1. ?,? are sampled uniformly at random 2. Party flips its output iff. its input is of size 2 Pr out?= 1 = 2/3, out1 and Independently of other party s input out2 are correlated
Warmup Impossibility of Fairness [Makriyannis 14]: {1} {2} {3} {1,2} {1,3} {2,3} 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 ? ? Homer gains information out1 out2 Consider the following experiment: 1. ?,? are sampled uniformly at random 2. Party flips its output iff. its input is of size 2 Pr out?= 1 = 2/3, out1 and Independently of other party s input out2 are correlated
Warmup Impossibility of Fairness [Makriyannis 14]: {1} {2} {3} {1,2} {1,3} {2,3} 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 ? ? Homer gains information out1 out2 Can be used to bias the (possibly) flipped output of Marge towards either 0 or 1: Pr out2 However, Pr out2= 1 = 2/3 independently of ? cannot be simulated #rounds = 1 2/3 ? 1/?
Impossibility of Solitary Output Computation Output of Lisa if Homer aborts Issue: Nothing to bias Obs.: out2 Idea: Bias out2 using out2 Attack: Homer acts like before, Lisa acts honestly to obtain out2 The guess depends on whether out2 = out2 and guess |?| ? = 1 out2 ? ? Reveals information was biased towards 1 or 0: = 1 = Pr out2 = Pr out2 flip(?) = 1 flip(?) Pr out2
Impossibility of Solitary Output Computation The guess depends on whether out2 ? ? was biased towards 1 or 0: = 1 = Pr out2 = Pr out2 Pr Guessing correctly 2/3 + ?(1/?) flip(?) = 1 flip(?) Pr out2 However, Pr Sim guesses correctly 2/3 Reveals information Last step is where it fails for even ?
The Characterization Define the matrix ? ?,? = ?(?,?). Then ? cannot be securely computed if and only if vectors ? and ? s.t. ?? ? = (1, ,1) ? ? = 1, ,1? and ??< 1 ??< 1 ? ? ? ? Intuitively, ? and ? encode locking strategies Tells how to sample the input and when to flip the output, s.t. the output distribution is independent of the other party s input The constraint on the sum bounds the amount of information gained from the output
Summary Considered solitary output functionalities ?:? ? {0,1} Output receiving party has no input We characterize the set of these functionalities that can be securely computed against 2 corruptions Impossibility can be extended via player partitioning argument We characterize the family of set disjointness functions that can be computed in this setting
Open Questions 1. For what parameters can private set intersection be securely computed? PSI ?,? = ? ? 2. More generally, characterize the set of non-Boolean solitary output functionalities that can be securely computed 3. What happens in the multiparty setting (even for Boolean)?
