Yao’s Garbled Circuits is a cryptographic protocol that enables two parties to jointly evaluate a function over their private inputs without revealing those inputs to each other. Introduced by Andrew Yao in 1986, this protocol is foundational in the field of secure multi-party computation (SMC).
How It Works:
- Circuit Construction: The function to be evaluated is represented as a Boolean circuit.
- Garbled Circuit Generation: One party, known as the garbler, encrypts the circuit’s gates and wires, creating a “garbled” version.
- Oblivious Transfer: The other party, the evaluator, uses oblivious transfer to obtain the necessary encrypted wire labels corresponding to their input values.
- Evaluation: The evaluator processes the garbled circuit using the obtained labels, ultimately computing the function’s output without learning anything about the garbler’s inputs.
Applications:
Garbled circuits are utilized in various scenarios, including:
- Privacy-Preserving Computations: Allowing computations on sensitive data without exposing the data itself.
- Secure Auctions: Enabling participants to bid without revealing their bids to others.
- Private Information Retrieval: Allowing users to retrieve information from a database without revealing which data they are accessing