# Why do we use addition and multiplication in GMW protocol

So i'm reading about secure computation and the GMW protocol.

I don't understand why the protocol evaluates the addition and the multiplication ?

Why not just the multiplication ?

I didn't find any information about the OT used in this protocol. Is this a basic one like Rabin's or not ?

## 1 Answer

Any efficiently computable function can be represented by a circuit containing XOR gates and AND gates - AND gates alone would not suffice (but NAND gates would). The standard practice in secure computation is to use this {XOR, AND} basis to represent functions, since evaluating a XOR is often very cheap (it only involves cheap local operations, and no communication).

In GMW, a 1-out-of-4 OT is used to evaluate the AND gates (as I said above, XOR gates only require local computation - i.e., XORing the corresponding shares). This is the standard OT, i.e., not Rabin OT: the sender has 4 messages $$(m_i)_{i\leq 4}$$, and the receiver with input $$j \in \{1,2,3,4\}$$ learns $$m_j$$ without learning anything else; $$j$$ remains hidden to the sender.

(note that such an OT can be constructed from the Rabin OT, and conversely, Rabin OT can be constructed from this standard OT - so although their functionality differ, they are essentially "equivalent" in terms of what they allow to do).