MPC for Tech Giants: Enabling Cooperation Among Users and Service Providers
Explore cutting-edge research on Multi-Party Computation (MPC) models like GMPC, the Star Model, and the Gulliver MPC Model. Learn about secure protocols for committee elections and general computations, with insights on improving efficiency and security in collaborative environments.
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
MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate Amicably Bar Alon Ben-Gurion University Moni Naor Weizmann Institute of Science Eran Omri Ariel University Uri Stemmer Tel Aviv University
A Service Provider and Its (Many Weak) Users Too many users, I can t talk to everyone I want ? ?1, ,?? I also need to prevent DDoS Can we make everyone happy? I want to protect my input I m too weak to use MPC
The Star Model 1. A single server obtaining the output 2. ? = 2? ? users 3. Server is poly(?) 4. Each user is polylog(?) 5. Malicious adv. may corrupt the server and a subset of the users
The Star Model Sig Enc,pk1 pk1 Sig Enc,pk2 pk2 Need PKI
The Star Model Was considered in [BIK+ 17, BBG+ 20, RDY 21] Either semi-honest adv. or for specific functionalities PKI introduces complications with compositions Harder to formally argue security Want a model that is easier to study Need an abstraction that highlights key components
The Gulliver MPC Model (GMPC): MPC With Blocking Doesn t know the content, but knows the origin and destination
Our Results Committee Election Protocol A variant of Feige s committee election protocol All parties agree on a small committee (e.g., log2?) Fraction of mal. users does not increase too much Original protocol is very elegant The GMPC model introduces many complications
Our Results General Computation A secure protocol for any func. with ?(?) output length Secure assuming ? < 1/8 fraction of the users are corrupted Construction assumes fully homomorphic encryption (FHE) Small and shallow circuits can be computed without FHE Small and shallow: ?(?) size and ? 1 depth, fan-in, and fan-out Includes important func. such as sorting and aggregation Have applications to the shuffle model of differential privacy Can be complied into a secure protocol in the star model With PKI, can improve our results to tolerate ? < 1/4
Challenges in the GMPC Model Challenge 1: Block vs. aborts Distinguish a server blocking from a mal. user aborting Challenge 2: DDoS attacks Mal. users can flood the network (even if server is honest) Challenge 3: Concurrent composition UC security requires CRS Bounded concurrent composition requires polynomial-time users Challenge 4: Verifying long statements Users need to verify the server s computation (over ? input) They cannot even read the entire statement
Challenges in the GMPC Model Challenge 1: Block vs. aborts Distinguish a server blocking from a mal. user aborting Challenge 2: DDoS attacks Mal. users can flood the network (even if server is honest) Challenge 3: Concurrent composition UC security requires CRS (can be viewed as a committee) Bounded concurrent composition requires polynomial-time users Challenge 4: Verifying long statements Users need to verify the server s computation (over n input) They cannot even read the entire statement
Challenges in the GMPC Model Challenge 1: Block vs. aborts
Challenges in the GMPC Model Challenge 1.5: Assume it somehow uncovers the server I m on to you
Challenges in the GMPC Model Challenge 1.5: Assume it somehow uncovers the server
Tool 1: Personal Committees size = log2?
Honest Server Effectively honest parties No message is blocked
Malicious Server I m on to you
Malicious Server I m on to you
Tool 2: Sampling a Communication Graph Sample graph with polylog(?) degree and diameter For polylog(?) rounds: send alive to all neighbors I m on to you
Summary Introduce the Gulliver MPC (GMPC) model A powerful server computes a func. over the inputs of many weak users Server can block messages Construct a committee election protocol Introduce the tools of PCs and comm. graph to tackle blocking Construct a protocol for securely computing any function Can handle ?? corrupted users for ? < 1/8 Assumes fully homomorphic encryption (FHE) Can do without FHE for small and shallow circuits (e.g., aggregation)
