Three hospitals want to compute the average patient outcome across their databases without sharing individual patient data. Describe how MPC solves this and what security guarantee it provides.
Think about your answer, then reveal below.
Model answer: Each hospital is a party with private input (their aggregate statistics). An MPC protocol computes the combined average, revealing only the final result to all parties. The security guarantee (via ideal/real simulation) is that each hospital learns nothing about the other hospitals' data beyond what is implied by the final average combined with their own input. For example, if the average is 75 and Hospital A's average is 80, Hospital A learns that the combined average of B and C is lower than 80, but learns nothing more specific about B or C individually.
MPC cannot prevent information that is logically implied by the output — if only two hospitals participate, each can deduce the other's average from the combined average and their own input. This is inherent: it's information the output reveals, not a protocol weakness. MPC guarantees that the protocol leaks nothing beyond this logical minimum.
Question 2 Multiple Choice
The ideal/real paradigm defines MPC security by comparison to an ideal world with a trusted third party. Why is this approach better than listing specific attacks the protocol must resist?
AListing attacks is equivalent but less elegant
BThe ideal/real paradigm provides a universal security guarantee: anything that could go wrong in the real protocol could also go wrong in the ideal world (where the only possible 'attack' is choosing a bad input or learning from the output). This automatically protects against all possible attacks — known and unknown — without needing to enumerate them. A specific attack list would inevitably miss some attacks
CThe ideal/real paradigm is easier to prove but provides weaker guarantees
DThe paradigm only applies to protocols with three or more parties
The ideal world is maximally secure by construction — a trusted party handles everything, so the only 'leakage' is the function output. Proving that the real protocol is indistinguishable from this ideal means the real protocol inherits all security properties of the ideal world. This captures privacy (inputs are hidden), correctness (output is accurate), independence of inputs (parties can't choose inputs based on others' inputs), and more — all from a single definition.
Question 3 True / False
With an honest majority of participants (more than half are non-corrupted), MPC can achieve information-theoretic security without any computational assumptions.
TTrue
FFalse
Answer: True
The BGW protocol (Ben-Or, Goldwasser, Wigderson, 1988) achieves this using Shamir secret sharing and local computation on shares. Each party secret-shares their input among all parties. The function is computed on shares using addition (free — add shares locally) and multiplication (requires one round of interaction per gate). With an honest majority, corrupted parties cannot reconstruct any secret, providing unconditional privacy. Without an honest majority (e.g., two-party computation), information-theoretic security is impossible and computational assumptions (typically OT) are required.
Question 4 Multiple Choice
MPC for a function f guarantees that corrupted parties learn nothing beyond f's output. But what if f's output itself reveals sensitive information — for example, computing 'does any party's salary exceed $1M' reveals something about high earners?
AMPC prevents this by encrypting the output
BMPC cannot solve this — it guarantees the protocol leaks nothing beyond the output, but the function choice determines what the output reveals. If the function itself leaks too much, the parties must choose a different function. This is a function design problem, not a protocol problem
CAdding more rounds of interaction prevents output-based leakage
DDifferential privacy inside MPC solves this automatically
MPC faithfully computes the agreed function and ensures nothing extra leaks. If the function is 'output all inputs,' MPC computes it securely but the output reveals everything. The parties must agree on a function whose output reveals only what they're comfortable sharing. Combining MPC with differential privacy (adding noise to the output) can address output-based leakage, but this is a complementary technique, not part of MPC itself.
Question 5 Short Answer
Yao's garbled circuits enable two-party computation where one party 'garbles' the circuit and the other evaluates it. Why can't the evaluator learn intermediate wire values?
Think about your answer, then reveal below.
Model answer: Each wire carries a random label (one for 0, one for 1) rather than the actual bit value. The evaluator processes garbled truth tables that map input labels to output labels using symmetric encryption — they can decrypt exactly one entry per gate (the one matching their input labels) and learn the output label, but cannot determine whether the label represents 0 or 1. Only the final output wires have their labels decoded to actual bits. The evaluator computes the correct output without ever learning any intermediate bit value.
The garbled circuit construction is the foundation of practical two-party MPC. The garbler (who constructs the circuit) must not learn the evaluator's input — this is achieved by the evaluator obtaining their input labels via oblivious transfer, which ensures the garbler does not learn which labels were selected.