Garbled Circuits

Garbled….Circuits? Might sound like two unrelated terms clucked together with no context but as we go by, we present you a concept which is niche and inspired by some money problems XD

I will start with what happened last week with my friends, Alice and Bob.

Alice and Bob walk into a restaurant.

The food was great, but the bill was… let’s just say it was as big as their egos.

Neither wanted to reveal how much money they make, but one of them had to pay.

So, how did they figure out who’s richer without blurting out their bank balance? They remembered a famous problem in cryptography called Yao’s Millionaire Problem, the problem which started all and ended all.

So what even it is Yao’s Millionaire Problem?

Yao’s solution to this problem ? Turn the whole computation into a giant ‘puzzle box’ called a garbled circuit.

GCs can be useful in any such scenarios, as long as they can be converted to boolean circuits. This means that you can now compute the answer and not leak any additional information as to what the input values were . In technical terms , GCs are a cryptographic protocol which enables secure two party computation , allowing two parties to jointly compute a function over their private inputs without revealing those inputs to each other.

A thing to note is that GCs work always with two parties : A garbler and an evaluator.

For understanding sake, Garbled Circuits are mysterious puzzle boxes and in this setting, let’s say:

1. Garbler : Puzzle Maker or the Garbled Circuit Generator.
2. Evaluator: Puzzle Solver or the one which evaluates this garbled circuit.

Bringing you an example

Let’s understand this with the standard Alice and Bob scenarios.

So say Alice and Bob want to communicate and decide if they want to bid in an auction.

Both of them submitted their bids to the auctioneer, but don’t want each other nor the auctioneer to know the bid values. They just want the highest bidder as the output and not the amount of bids they put on the auctioned object.

Therefore, here we use Garbled Circuits to determine the winner of the auction (the person with the higher bid) securely, while keeping the actual bid values private.

So say, Alice is the Garbler, and thus creates the encrypted circuits and hence Bob is the evaluator.

We start with a Boolean circuit that implements the function we want to compute.

Alice, as the Garbler, transforms this circuit into a garbled version:

• Every wire in the circuit (inputs, intermediate wires, outputs) is assigned two randomly generated strings — also called keys/labels: one key represents logical 0, the other key logical 1.
  • Example: For a wire w, Alice chooses:
    • $K_w^0$ → represents value 0
    • $K_w^1$ → represents value 1 These labels are just random-looking bitstrings, typically 128-bit long.

For each gate (AND, OR, XOR, etc.), Alice creates an encrypted truth table:

• Each possible input pair of keys is encrypted to reveal only the correct output key.
• Example: For an AND gate with input wires a and b and output wire c:
  • Truth table has 4 rows: (0,0), (0,1), (1,0), (1,1).
  • Alice encrypts the corresponding output key ($K_c^o$) using the two input keys ($K_a^x$, $K_b^y$).
  • In reality, a secure cryptographic hash function or AES is used. Our XOR example is just for conceptual clarity and is not secure in practice.

Example

For each wire, Alice picks two random 4-bit keys:

• Input wire a:
  • $K_a^0$ = 1010
  • $K_a^1$ = 0111
• Input wire b:
  • $K_b^0$ = 1100
  • $K_b^1$ = 0001
• Output wire c:
  • $K_c^0$ = 1111
  • $K_c^1$ = 0100

a typical AND gate table :

Now a twist : replace 0/1 with their corresponding wire keys:

Now Alice encrypts each output key using its input keys.
instead of using an actual encryption scheme , lets define something simpler :

Enc($K_a$, $K_b$, value) = ($K_a$ XOR $K_b$) XOR output_key

Now compute:

1. Inputs (1010, 1100)

   (1010 XOR 1100) = 0110
   0110 XOR 1111 = 1001
   Ciphertext = 1001
   

2. Inputs (1010, 0001)

   (1010 XOR 0001) = 1011
   1011 XOR 1111 = 0100
   Ciphertext = 0100
   

3. Inputs (0111, 1100)

   (0111 XOR 1100) = 1011
   1011 XOR 1111 = 0100
   Ciphertext = 0100
   

4. Inputs (0111, 0001)

   (0111 XOR 0001) = 0110
   0110 XOR 0100 = 0010
   Ciphertext = 0010
   

now , we have the garbled column : Alice sends Bob the encrypted rows in random order:

Row 1: 1001
Row 2: 0100
Row 3: 0100
Row 4: 0010

Evaluation

Suppose Bob’s inputs are a=1, b=1:

• He holds $K_a^1$ = 0111 and $K_b^1$ = 0001.
• He tries decrypting each row with his keys, but only Row 4 gives a meaningful result: 0010.
• That decrypts to the correct output key $K_c^1$ = 0100.

He doesn’t learn anything about the other possible outputs, only the one consistent with his actual inputs.

That’s exactly what “garbled” means: the circuit is scrambled into encrypted tables of random-looking cipher texts, where only the correct input keys can unlock the right output key.

Thus the encrypted circuit = collection of these “garbled tables” (encrypted gate tables) + wire labels (the random keys).

How it works in the auction

1. Circuit definition: The comparison function (is Alice_bid > Bob_bid?) is represented as a Boolean circuit.
2. Garbler step (Alice):
   • Assigns random keys to every wire.
   • Builds garbled tables for each gate using symmetric encryption.
   • Sends the garbled circuit to Bob.
3. Input encoding:
   • Alice directly gives Bob the keys corresponding to her bid’s bits.
   • Bob gets his input keys via Oblivious Transfer (OT) so Alice doesn’t know which bits he chose.
4. Evaluation (Bob):
   • Using the garbled circuit and his keys, he evaluates gate by gate, always being able to decrypt only one row per gate.
   • At the end, he obtains output keys (e.g., one corresponding to “Alice wins” or “Bob wins”).
5. Decoding:
   • Alice provides a decoding map that tells Bob how to interpret the final output keys (e.g., this key = “Alice”, that key = “Bob”).

So, when Alice and Bob bid in an auction, no one learns their bids. The only thing revealed? The winner. Privacy stays intact, egos survived intact. While it sounds perfect, there’s one crucial flaw in our story so far. Remember:

• Alice knows both possible keys for every wire, since she created them.
• Bob should only learn the keys for his actual input bits — but Alice must not learn what Bob chose.
• This is where OT comes in.

Oblivious Transfer

Oblivious Transfer (OT) is a cryptographic protocol that allows Bob to obtain exactly one piece of information from Alice’s collection, without Alice knowing which piece Bob retrieved.

Involves sending data such that only a part of it arrives and the sender doesn’t know which part actually arrives. And the receiver can choose what they can read.

Useful in Multi Part Computations.

How they are used in Garbled Circuits?

In the garbled circuit protocol, Bob needs to obtain the wire keys corresponding to his private input bits, but Alice shouldn’t learn what Bob’s input actually is.

Early (‘vanilla’) GCs were often considered impractical for large computations because the entire circuit, including the output translation tables, had to be garbled and sent afresh for every single evaluation. This communication overhead was huge.

Although a lot of optimizations have been researched, one basic one is the Point-and-Permute Optimization, which has proven to solve the overhead.

Point-and-Permute Optimization

The Problem it Solves: In basic garbled circuits, when Bob evaluates a garbled gate, he has to try decrypting all entries in the garbled gate’s truth table until he finds one that decrypts correctly. For a 2-input gate, this means up to 4 decryption attempts per gate.

The Solution: Point-and-permute adds a permutation bit (or “select bit”) to each wire key.

Conclusion?

Garbled circuits aren’t just theoretical—they’re used in real-world applications like privacy-preserving auctions, secure voting, and even machine learning where data must remain confidential, which obviously are relevant :))

To conceptually recap, Garbled Circuits allow two parties to compute a function using an encrypted version of a logic circuit.

The protocol relies on two main pillars: (1) the garbling of the circuit itself, and (2) Oblivious Transfer for secure input acquisition.

However, early GCs were inefficient because Bob had to try decrypting all rows in each gate. But with optimizations like point-and-permute, where each key has a random “pointer” bit that tells Bob which row to decrypt, evaluation becomes much faster.

Garbled Circuits signing off~

Enabling trust and privacy in the modern world since 1980s~~~

Co-written with @pranavjeet, who somehow made sense of my half-baked thoughts.

Source: https://web.mit.edu/sonka89/www/papers/2017ygc.pdf