Garbled Circuits: Yao's Secure Two-Party Computation (2D) |…

What Are Garbled Circuits?

Garbled circuits are a cryptographic protocol developed by Charles Rackoff and Shafi Goldwasser, but popularized by Andrew Yao. They enable two parties to jointly compute a function on their private inputs without revealing those inputs or the computation details to each other. This is achieved through a series of complex steps involving encryption and decryption.

The process involves creating a circuit that represents the desired function, then 'garbling' it into an encrypted form where each wire and gate is associated with multiple possible values, but only one value per wire is valid for any given input combination.

How Do Garbled Circuits Work?

To construct a garbled circuit, the two parties first agree on a set of encryption keys. One party (the generator) creates a table for each gate in the circuit, encrypting it with different keys based on the possible inputs from both parties. Each entry in these tables corresponds to one of the 16 possible input combinations for a single AND or OR gate.

The other party (the evaluator) receives the garbled circuit and their own secret key. They can then traverse the circuit, decrypting each wire as needed based on their inputs and the corresponding keys provided by the generator. The result is computed without either party learning anything about the other's input.

live demo · related simulation● LIVE

Why Does It Matter?

Garbled circuits are crucial for privacy-preserving computation, allowing secure collaboration in various fields such as finance, healthcare, and data analysis. They ensure that sensitive information remains confidential while still enabling useful computations to be performed.

The protocol is particularly valuable in scenarios where multiple parties need to compute a function on shared or private data without revealing the underlying data itself.

Real-World Applications

Garbled circuits have been applied in secure voting systems, where voters can cast their ballots privately and securely. They are also used in secure auctions to ensure that bidders' valuations remain confidential.

In the realm of machine learning, garbled circuits enable collaborative training of models without exposing sensitive data or algorithms.

Frequently asked questions

How does Yao's protocol ensure privacy?

Yao's protocol ensures privacy by encrypting each wire in the circuit with multiple keys. Only one key is valid for any given input combination, and this key is only known to the evaluator who holds their own secret key.

Can garbled circuits be used for more than just AND and OR gates?

Yes, garbled circuits can handle a wide range of logical operations. More complex functions are broken down into simpler gates (AND, OR, NOT) that are then combined to form the desired computation.

What is the main challenge in implementing garbled circuits?

The primary challenge lies in generating and distributing the large number of keys required for each gate. This process can be computationally intensive and resource-demanding, especially for complex functions with many gates.

Are there any limitations to using garbled circuits?

While powerful, garbled circuits are not without limitations. They require significant computational resources and bandwidth, making them less practical for real-time applications or large-scale computations.

Try it live

Everything above runs in your browser — open Garbled Circuits: Yao's Secure Two-Party Computation (2D) and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Garbled Circuits: Yao's Secure Two-Party Computation (2D) simulation