Solving the Millionaire's Problem with MPC

The foundation of the MPC framework is the Millionaires' Problem, which Yao resolved using a cryptographic primitive termed Oblivious Transfer (OT). In an OT exchange, a sender provides two pieces of information, and a receiver selects one to receive. The protocol ensures that the sender remains unaware of which item was chosen, while the receiver learns nothing about the item they did not select. This methodological choice allowed for the construction of a comparison circuit where each participant’s input is shielded by the other’s uncertainty. It revealed that the most effective way to protect sensitive data is to move the search for a result into a virtual state space where no single participant possesses the complete logical key.

The primary technical contribution of the 1982 paper is the "Garbled Circuit" protocol, which enables the evaluation of arbitrary Boolean functions. One party, the generator, transforms a circuit by replacing the 0 and 1 values on every wire with random cryptographic keys and encrypting the truth table for each gate. The second party, the evaluator, receives the garbled structure and the keys corresponding to their specific inputs via Oblivious Transfer. By iteratively decrypting the gates, the evaluator reaches the final output without ever observing the values on the internal wires of the processor. This finding effectively turned computation into a "puzzle" that can only be solved if both parties provide their respective pieces, establishing a new paradigm for decentralized information processing.

Yao’s original protocol was designed for "honest-but-curious" (semi-honest) participants - individuals who follow the rules of the protocol but will attempt to learn as much as possible from the data they receive. While later research introduced more complex mechanisms to protect against malicious adversaries who deviate from the protocol, Yao’s work established the fundamental bounds of what is computable in a private environment. He provided a "completeness theorem" for secure computation, proving that if a basic key exchange is possible, then any task achievable by a trusted third party can be simulated by a secure protocol. This finding established privacy as a universal property that can be applied to any algorithmic process.

The practical significance of Secure Multi-Party Computation is most evident in the development of modern "trustless" infrastructures for finance and medicine. By providing a method for multiple organizations to analyze their combined data without violating confidentiality, MPC enables the transition toward a decentralized data economy. This application remains the central theme in the development of "Federated Learning," where AI models are trained on private data distributed across millions of devices without the data ever being centralized. The work proved that the utility of information is not tied to its direct disclosure, suggesting that the most robust way to manage a data-driven society is to prioritize functional collaboration over raw data sharing.

The success of Andrew Yao’s protocol demonstrated that the bottleneck in collaborative computation was the requirement for absolute data transparency. The decision to model computation as a set of encrypted state transitions revealed that the primary constraint on digital trust was the reliance on centralized intermediaries. This principle remains the guiding rule for the search for practical "privacy-enhancing technologies," influencing the design of systems that balance individual sovereignty with collective intelligence. It leaves open the question of whether the communication overhead of garbled circuits can be further reduced to support real-time interaction at the scale of the global internet.