Lecture Notes: Secure Multi-Party Computation (MPC)

Outline of the Lecture

• What is Secure Multi-Party Computation (MPC)?
• Real-world applications of MPC.
• Dimensions of studying secure MPC problems.
• Challenges in dealing with malicious adversaries.

Motivation Behind Secure Multi-Party Computation

• Definition: Secure MPC allows multiple mutually distrusting entities to perform joint computations on their confidential data without revealing their inputs.
• Entities: Denoted as p1, p2, ..., pn, each with confidential data (x1, x2, ..., xn).
• Objective: Compute a publicly known function f without additional disclosure of inputs beyond what can be inferred from the own input and the function output.

Goals of Secure MPC

• Ensure data confidentiality (no additional information revealed).
• Ensure data availability (data must be accessible for computation).
• Analogy: Jewels locked in a locker - kept safe but must be available for use.

Real World Applications of Secure MPC

1. Privacy-Preserving Data Mining:

   • Hospitals (e.g., three hospitals) want to run analytics on combined patient records without disclosing individual records.
   • Function f: Data mining operation to compute statistics (e.g., patient counts).

2. Secure E-Auction:

   • N bidders bidding for an object; only the highest bid should be revealed.
   • Each bidder learns whether their bid is less than the winning bid but nothing else.
   • Function f: Max function to determine the highest bid.

3. Yao's Millionaires Problem:

   • Two millionaires want to find out who is richer without disclosing their exact wealth.
   • Example of two-party computation.

4. Satellite Collision Prevention:

   • Two nations with secret satellite trajectories want to compute collision probability without revealing their trajectories.

Dimensions of Secure MPC

1. Function Representation:

   • Functions can be represented as Boolean circuits or arithmetic circuits over algebraic structures.

2. Communication Model:

   • Synchronous Model: Assumes message delivery times are known.
   • Asynchronous Model: No guarantees on message delivery times; models real-world networks like the internet.

3. Corruption Capacity:

   • Threshold Model: Adversary can corrupt at most t out of n parties.
   • Non-Threshold Model: Adversarial structure allows for more general corruption scenarios.

4. Corruption Power:

   • Computationally Bounded Adversaries: Can use cryptographic tools.
   • Computationally Unbounded Adversaries: No restrictions on resources, requires different protocols.

5. Type of Corruption:

   • Passive Corruption: Eavesdropping only.
   • Crash Corruption: Can stop parties from functioning.
   • Active (Malicious) Corruption: Can control corrupt parties fully, leading to arbitrary behavior.

6. Corruption Time:

   • Static Corruption: Corruptions are decided before the protocol starts.
   • Adaptive Corruption: Corruptions can occur during protocol execution based on observed information.

Challenges in Byzantine Corruptions

• Example of the broadcast problem:
  • Designated sender must send a message identically to all parties, but may be corrupted and send different messages.
  • Solution requires interaction among parties to agree on a consistent version of the message.

Summary of the Lecture

• Introduced the problem of secure multi-party computation (MPC).
• Discussed various real-world applications and challenges.
• Explored dimensions to study the secure MPC problem.
• Focus of this course is on protocols that tolerate active and malicious corruptions.

References

• Week one of the part one of the course (Lectures 1, 2, and 3) for more details on dimensions studied in secure MPC.