# GMW

Created by Oded **Goldreid**, Silvio **Micali**, and Avi **Wigderson**, **GMW** is a **multi-party computation (MPC)** protocol designed for boolean or arithmetic circuits for $$n$$-parties where $$n \ge 2$$. We’ll focus on the creation of boolean circuits in GMW for simplicity.

## 2-party GMW <a href="#d3bb" id="d3bb"></a>

Let’s start with 2-party GMW. Say we have two parties: <mark style="color:red;">Alice</mark> and <mark style="color:green;">Bob</mark>, and we have one boolean gate with 2 input bits $$\textcolor{red}i$$ (known by <mark style="color:red;">Alice</mark>) and $$\textcolor{green}j$$ (known by <mark style="color:green;">Bob</mark>) and one output bit $$k$$.

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2FQvpVAjifYYcrYVENcYBH%2Fimage.png?alt=media&#x26;token=f8e90106-0cf0-4d0c-858b-0f9fc4060c27" alt=""><figcaption><p>A boolean gate</p></figcaption></figure>

In the GMW protocol, every party first undergoes a process of secret sharing with the other parties on the input bits they know:

For her input bit $$\textcolor{red}i$$, <mark style="color:red;">Alice</mark> chooses a random bit share $$\textcolor{green}{s\_i^b}$$ to send to <mark style="color:green;">Bob</mark>. Meanwhile, she creates a personal bit share $$\textcolor{red}{s\_i^a}$$ for herself such that $$\textcolor{red}{s\_i^a}\oplus\textcolor{green}{s\_i^b}=\textcolor{red}i$$.

The same, but opposite, occurs for <mark style="color:green;">Bob</mark>. <mark style="color:green;">Bob</mark> chooses a random bit share $$\textcolor{red}{s^a\_j}$$ to send to <mark style="color:red;">Alice</mark> and then creates a personal bit share $$\textcolor{green}{s^b\_j}$$ such that $$\textcolor{red}{s^a\_j}\oplus \textcolor{green}{s^b\_j}=\textcolor{green}j$$.

Therefore a single gate will be portrayed as so by each party:

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2FqdNdmr0dePhXj0c5N0yS%2Fimage.png?alt=media&#x26;token=900f69fc-5352-4003-8dfe-8cf24a2f7bbb" alt=""><figcaption><p>A single boolean gate implemented across 2 parties <mark style="color:red;">Alice</mark> and <mark style="color:green;">Bob</mark></p></figcaption></figure>

Here, we can see that the output of all parties will be XOR-ed together for the final result between all parties.

### Boolean Gates <a href="#id-66c1" id="id-66c1"></a>

Since [a full boolean circuit can be created with XOR and AND gates](https://fractalyze.gitbook.io/intro/~/revisions/GBuVDfZJZBNDtoleSgnx/yaos-garbled-circuits#optimizations-on-yao), let’s see how XOR and AND gates can be implemented in the 2-party GMW system.

### XOR <a href="#id-1e57" id="id-1e57"></a>

A XOR gate is extremely easy to implement in this scenario. A XOR gate means that our $$k$$ output above is $$(\textcolor{red}i\oplus\textcolor{green}j)=(\textcolor{red}{s\_i^a}\oplus \textcolor{green}{s\_i^b})\oplus(\textcolor{red}{s\_j^a}\oplus \textcolor{green}{s\_j^b})=(\textcolor{red}{s\_i^a}\oplus \textcolor{red}{s\_j^a})\oplus(\textcolor{green}{s\_i^b}\oplus \textcolor{green}{s\_j^b})$$. This means that each party can compute the XOR on their own shares and the final output of each party can be XOR-ed together to get the total XOR result.

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2FqCwj19tsc6fkpAlo2SFO%2Fimage.png?alt=media&#x26;token=c5188354-c575-4436-a337-19ebe541df87" alt=""><figcaption><p>A single XOR gate implemented in 2-party GMW</p></figcaption></figure>

### AND

Implementing an AND gate is a bit more complicated. Since the $$k$$ output for an AND gate should be $$(\textcolor{red}i\land\textcolor{green}j)=(\textcolor{red}{s\_i^a}\oplus \textcolor{green}{s\_i^b})\land(\textcolor{red}{s\_j^a}\oplus \textcolor{green}{s\_j^b})$$, this means that each party can’t compute a portion of the AND gate output by themselves. Instead, we’ll first transform $$(\textcolor{red}{s\_i^a}\oplus \textcolor{green}{s\_i^b})\land(\textcolor{red}{s\_j^a}\oplus \textcolor{green}{s\_j^b})$$ as per the following logic equivalence statement:

$$
\begin{align\*}k &=(\textcolor{red}i\land\textcolor{green}j)\\&=(\textcolor{red}{s\_i^a}\oplus \textcolor{green}{s\_i^b})\land(\textcolor{red}{s\_j^a}\oplus \textcolor{green}{s\_j^b})\\&=\bm((\textcolor{red}{s\_i^a}\land \textcolor{red}{s\_j^a})\oplus(\textcolor{green}{s\_i^b}\land \textcolor{green}{s\_j^b})\bm)\oplus\bm((\textcolor{red}{s\_i^a}\land \textcolor{green}{s\_j^b})\oplus(\textcolor{green}{s\_i^b}\land \textcolor{red}{s\_j^a})\bm)\end{align\*}
$$

Looking closely at this resulting statement, we see that the former half’s parts $$(\textcolor{red}{s\_i^a}\land \textcolor{red}{s\_j^a})$$ and $$(\textcolor{green}{s\_i^b}\land \textcolor{green}{s\_j^b})$$ can be easily computed by the respective parties <mark style="color:red;">Alice</mark> and <mark style="color:green;">Bob</mark> individually, yet the latter half $$(\textcolor{red}{s\_i^a}\land \textcolor{green}{s\_j^b})\oplus(\textcolor{green}{s\_i^b}\land \textcolor{red}{s\_j^a})$$ appears to require some communication between the two parties.

To communicate the latter half between the parties, we set one party as the sender (<mark style="color:red;">Alice</mark>) and one party as the receiver (<mark style="color:green;">Bob</mark>).

<mark style="color:red;">Alice</mark> knows her own shares $$\textcolor{red}{s\_i^a}$$ and $$\textcolor{red}{s\_j^a}$$, but doesn’t know <mark style="color:green;">Bob’s</mark> shares $$\textcolor{green}{s\_i^b}$$ and $$\textcolor{green}{s\_j^b}$$; however, <mark style="color:red;">Alice</mark> still knows that each of <mark style="color:green;">Bob’s</mark> shares is either $$0$$ or $$1$$. Knowing this, <mark style="color:red;">Alice</mark> can create 4 potential outcomes of $$(\textcolor{red}{s\_i^a}\land \textcolor{green}{s\_j^b})\oplus(\textcolor{green}{s\_i^b}\land \textcolor{red}{s\_j^a})$$ using the different permutations of $$\textcolor{green}{s\_i^b}$$ and $$\textcolor{green}{s\_j^b}$$ as $$(0,0),(0,1),(1,0),(1,1)$$. The following table shows the possible outcomes if <mark style="color:red;">Alice’s</mark> shares of $$\textcolor{red}{s\_i^a}$$ and $$\textcolor{red}{s\_j^a}$$ were $$0$$ and $$1$$, respectively.

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2FF4L7uoATeuE0lMrCtlMk%2Fimage.png?alt=media&#x26;token=ea3c48a9-8b34-43ff-bcf5-2aa215629175" alt=""><figcaption><p>Potential outcomes of the logical statement given <span class="math">\textcolor{red}{s_i^a}=0</span> and <span class="math">\textcolor{red}{s_j^a}=1</span></p></figcaption></figure>

Next, <mark style="color:red;">Alice</mark> creates a random bit $$\textcolor{red}r$$ (let’s say $$\textcolor{red}r=0$$ in our example) and encrypts all the possible outcomes by computing them with $$\oplus \textcolor{red}r$$.

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2FliKnzn3BVdAcX90OIenW%2Fimage.png?alt=media&#x26;token=af24af16-9cb5-4a8a-9e67-9ca49a295796" alt=""><figcaption><p>Potential outcomes of the logical statement <span class="math">\oplus \textcolor{red}r</span> given <span class="math">\textcolor{red}{s_i^a}=0</span> and <span class="math">\textcolor{red}{s_j^a}=1</span></p></figcaption></figure>

Finally, <mark style="color:red;">Alice</mark> sends this “Encrypted Possible Outcomes” table to a 1-out-of-4 oblivious transfer (OT) protocol. On the other side, <mark style="color:green;">Bob</mark> inputs their shares $$\textcolor{green}{s\_i^b}=0$$ and $$\textcolor{green}{s\_j^b}=1$$ to the same OT protocol. Through OT, <mark style="color:green;">Bob</mark> obtains the value of $$\textcolor{red}r\oplus\bm((\textcolor{red}{s\_i^a}\land \textcolor{green}{s\_j^b})\oplus(\textcolor{green}{s\_i^b}\land \textcolor{red}{s\_j^a})\bm)$$ specific to his shares’ values without learning of the other three encrypted possible outcomes, and <mark style="color:red;">Alice</mark> does not know which value <mark style="color:green;">Bob</mark> has obtained.

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2Fgit-blob-14cb6834aafbc461e3e38b8c37f1e66257a953aa%2FScreenshot%202025-01-17%20at%203.12.45%E2%80%AFPM.png?alt=media" alt=""><figcaption><p>1-out-of-4 OT protocol between <mark style="color:red;">Alice</mark> and <mark style="color:green;">Bob</mark> for <span class="math">\textcolor{red}r\oplus\bm((\textcolor{red}{s_i^a}\land \textcolor{green}{s_j^b})\oplus(\textcolor{green}{s_i^b}\land \textcolor{red}{s_j^a})\bm)</span></p></figcaption></figure>

As a result of <mark style="color:red;">Alice’s</mark> computation and interaction with <mark style="color:green;">Bob</mark> in a 1-out-of-4 OT protocol, the AND gate results of both parties can now be determined. <mark style="color:red;">Alice</mark> sets her AND gate result as $$(\textcolor{red}{s\_i^a}\land \textcolor{red}{s\_j^a})$$ XOR-ed her random bit $$\textcolor{red}r$$, and <mark style="color:green;">Bob</mark> sets his AND gate output as $$(\textcolor{green}{s\_i^b}\land \textcolor{green}{s\_j^b})$$ XOR-ed the OT result $$\textcolor{red}r\oplus\bm((\textcolor{red}{s\_i^a}\land \textcolor{green}{s\_j^b})\oplus(\textcolor{green}{s\_i^b}\land \textcolor{red}{s\_j^a})\bm)$$ he received. Therefore, as seen below, if the results of both parties’s AND gates are now XOR-ed together for the final logical total, the random bit $$\textcolor{red}r$$ is cancelled out, and $$(\textcolor{red}i\land\textcolor{green}j)$$ is successfully computed.

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2FA2Kld11jzih9RPtmdisA%2Fimage.png?alt=media&#x26;token=08775123-d9dd-46f8-a591-ee0e26ace98c" alt=""><figcaption><p>A single AND gate implemented in 2-party GMW</p></figcaption></figure>

## Boolean GMW Protocol Summary <a href="#a7fc" id="a7fc"></a>

Thus, the whole process of GMW can be summed up as follows:

1. All parties share their input bits’ secret shares with each other.
2. All parties compute the circuit separately.\
   a. If a XOR gate is met, each party XORs their own input shares.\
   b. If an AND gate is met, each party communicates with all other parties with 1-out-of-4 OT and XORs the results with the AND of their own input shares.
3. Once all parties are finished computing the circuit, the end results of each party are all XOR-ed together for the final multi-party computation result.

This step-by-step process holds even when GMW is implemented for $$n$$-parties (where $$n \geq 2$$).

## $$n$$-parties Boolean GMW <a href="#id-36eb" id="id-36eb"></a>

Let’s view how the steps would look for the $$n$$-party version of GMW.

### Section 1. <a href="#id-4890" id="id-4890"></a>

> *"All parties share their input bits’ secret shares with each other."*

Here, we follow the same process of how <mark style="color:red;">Alice</mark> and <mark style="color:green;">Bob</mark> shared their secret bit shares with each other.

Given a random input bit $$b$$ known by Party 1 ($$P\_1$$), $$P\_1$$ creates $$n-1$$ random bit shares $$s\_b^2,s\_b^3, \dots,s\_b^{n-1},s\_b^n$$ and sends these to the other parties $$P\_2,P\_3, \dots ,P\_{n-1},P\_n$$. Subsequently, $$P\_1$$ creates their own bit share $$s\_b^1$$ such that $$b=s\_b^1\oplus s\_b^2\oplus s\_b^3\oplus \cdots \oplus s\_b^{n-1}\oplus s\_b^n$$.

This bit sharing process is thus done for all input bits from all parties, ensuring that every party holds a share of an input bit in order to compute the circuit individually.

Our diagrams will now extend on our 2-party example and add in <mark style="color:purple;">Carol</mark> as a 3rd party to <mark style="color:red;">Alice</mark> and <mark style="color:green;">Bob</mark>.

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2FDH7Ml528IkIWNo5wo5EN%2Fimage.png?alt=media&#x26;token=a6f08962-6196-46e0-a859-5f3e2505ac12" alt=""><figcaption><p>A single boolean gate implemented across n parties <mark style="color:red;">Alice</mark>, <mark style="color:green;">Bob</mark>, <mark style="color:purple;">Carol</mark>,...</p></figcaption></figure>

### Section 2a.

> "If a XOR gate is met, each party XORs their own input shares."

Indeed, like the 2-party explanation, each party will XOR their own shares together for their personal XOR operation result. Subsequently, if all parties’ results are XOR-ed together, the final XOR multi-party computation result is revealed.

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2FWYDF1bLMBeqwylDu8yQf%2Fimage.png?alt=media&#x26;token=0908290e-90b8-4d15-aeee-f7a3fd736a06" alt=""><figcaption><p>A single XOR gate implemented in <span class="math">n</span>-parties GMW</p></figcaption></figure>

### Section 2b.

> "If an AND gate is met, each party communicates with all other parties with 1-out-of-4 OT and XORs the results with the AND of their own input shares."

Our logical equivalence statement used in the 2-party version can be generalized to the following (inspiration from [here](https://securecomputation.org/docs/ch3-fundamentalprotocols.pdf)):

$$
\begin{align\*}
k &= (\textcolor{red}{i} \land \textcolor{green}{j}) \\
  &= (\textcolor{red}{s\_i^a} \oplus \textcolor{green}{s\_i^b} \oplus \textcolor{blueviolet}{s\_i^c} \oplus \cdots)\land (\textcolor{red}{s\_j^a} \oplus \textcolor{green}{s\_j^b} \oplus \textcolor{blueviolet}{s\_j^c} \oplus \cdots) \\
  &= \left( \bigoplus\_{x}^n ({s\_i^x} \land {s\_j^x}) \right)\oplus \left( \bigoplus\_{x \neq y} ({s\_i^x} \land {s\_j^y}) \right)\\
  &= \underline{(\textcolor{red}{s\_i^a} \land \textcolor{red}{s\_j^a})
}\oplus (\textcolor{red}{s\_i^a} \land \textcolor{green}{s\_j^b})
\oplus (\textcolor{red}{s\_i^a} \land \textcolor{blueviolet}{s\_j^c})
\oplus \cdots
\oplus (\textcolor{green}{s\_i^b} \land \textcolor{red}{s\_j^a})
\oplus \underline{(\textcolor{green}{s\_i^b} \land \textcolor{green}{s\_j^b})}
\oplus (\textcolor{green}{s\_i^b} \land \textcolor{blueviolet}{s\_j^c})
\oplus \cdots
\oplus (\textcolor{blueviolet}{s\_i^c} \land \textcolor{red}{s\_j^a})
\oplus (\textcolor{blueviolet}{s\_i^c} \land \textcolor{green}{s\_j^b})
\oplus \underline{(\textcolor{blueviolet}{s\_i^c} \land \textcolor{blueviolet}{s\_j^c})}
\oplus \cdots
\end{align\*}
$$

As with our 2-party example, we can see that for the last statement, the sections underlined can be computed by an individual party on their own (“...AND of their own input shares”), while the sections not underlined require communication between multiple parties. More specifically, we can see that the latter sections can be grouped together like so:

$$
\left((\textcolor{red}{s\_i^a}\land \textcolor{green}{s\_j^b})\oplus(\textcolor{green}{s\_i^b}\land \textcolor{red}{s\_j^a})\right)\oplus\left((\textcolor{green}{s\_i^b}\land \textcolor{blueviolet}{s\_j^c})\oplus(\textcolor{blueviolet}{s\_i^c}\land \textcolor{green}{s\_j^b})\right)\oplus\left((\textcolor{red}{s\_i^a}\land \textcolor{blueviolet}{s\_j^c})\oplus(\textcolor{blueviolet}{s\_i^c}\land \textcolor{red}{s\_j^a})\right)\oplus\cdots
$$

The first portion $$(\textcolor{red}{s\_i^a}\land \textcolor{green}{s\_j^b})\oplus(\textcolor{green}{s\_i^b}\land \textcolor{red}{s\_j^a})$$ is the same statement used for OT between <mark style="color:red;">Alice</mark> and <mark style="color:green;">Bob</mark> in our 2-party example. Subsequently, $$(\textcolor{green}{s\_i^b}\land \textcolor{blueviolet}{s\_j^c})\oplus(\textcolor{blueviolet}{s\_i^c}\land \textcolor{green}{s\_j^b})$$ requires OT between <mark style="color:green;">Bob</mark> and <mark style="color:purple;">Carol</mark>, while $$(\textcolor{red}{s\_i^a}\land \textcolor{blueviolet}{s\_j^c})\oplus(\textcolor{blueviolet}{s\_i^c}\land \textcolor{red}{s\_j^a})$$ requires OT between <mark style="color:red;">Alice</mark> and <mark style="color:purple;">Carol</mark> (“...each party communicates with all other parties with 1-out-of-4 OT…”).

Therefore, the final AND result between $$n$$-parties will be each parties’ individual calculations XOR-ed with all OT results with all other parties. Since displaying all OT pairs between all parties proves difficult through a diagram, I’ve shown only 3 parties instead in the following figure:

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2FwPC4FfPwNg60AkVcwJiw%2Fimage.png?alt=media&#x26;token=a495888a-9729-43f4-a942-1e6ad887fea2" alt=""><figcaption><p>A single AND gate implemented for 3-party GMW</p></figcaption></figure>

### Total AND Gate Costs

Going on a slight tangent, let’s think of the communication cost between parties for a whole circuit. Remember that XOR gates don’t have any communication cost.

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2Fw62vuo7WjFfiEb0M7xqJ%2Fimage.png?alt=media&#x26;token=3cf616d6-d280-41d6-85bf-a7fa10665d09" alt=""><figcaption><p>Example circuit with XOR and AND gates</p></figcaption></figure>

Since all AND gates at the same level can be run in parallel (such as AND gates 1 and 2 in the figure above), yet all AND gates in succession must be run in order (as in AND gate 1 must be computed before AND gate 3 in the figure above), the total number of rounds of communication between parties equals the depth of the circuit in terms of AND gates (depth = 2 in the figure above). Additionally, each AND gate requires $$C\_2^n = \frac{n(n-1)}{2}$$ total OT processes to take place (total number of unique party pairs). This means that in total, there are (depth of the circuit in terms of AND gates) $$\times \frac{n(n-1)}{2}$$ total OTs occurring in a given circuit, a significant communication cost for a circuit with many AND gates.

### Section 3.

> "Once all parties are finished computing the circuit, the end results of each party are all XOR-ed together for the final multi-party computation result."

As explained with this sentence, the final results of the circuit for every party are XOR-ed for the total result. Note that this means each party does not expose their intermediate results to the other parties.

## Arithmetic Circuits

While I showed the boolean version of GMW, this protocol also works for **arithmetic circuits**. Instead of XOR and AND gates, arithmetic circuits use **addition** and **multiplication** gates. Additionally, while the secret shares for an input $$b$$ are calculated as $$b=s\_b^1\oplus s\_b^2\oplus s\_b^3\oplus\cdots\oplus s\_b^{n-1}\oplus s\_b^n$$ for $$n$$ parties for the boolean version, for the arithmetic version, $$b$$ equals $$s\_b^1+ s\_b^2+ s\_b^3+ \cdots + s\_b^{n-1}+ s\_b^n$$. Therefore, the addition operation will become free (like how XOR gates are free) and the multiplication operation requires communication between parties (similar to AND gates).

## Conclusion <a href="#id-4f71" id="id-4f71"></a>

In total, GMW stands as a notable $$n$$-party MPC protocol based around the concept of secret shares with free XOR gates and costly AND gates. Communication between parties must occur during the start of the protocol, at every AND gate, and at the end of the circuit computation.

> Written by [Ashley Jeong](https://app.gitbook.com/u/PNJ4Qqiz7kSxSs58UIaauk95AO43 "mention") of Fractalyze