1
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.