# Lecture 3

## XOR Secret Sharing Scheme

### Basic blocks:
The basic blocks reqiured for defining the protocol are as follows:

- Consider a b-bit secret.
- Consider a dealer D and n-parties $P_1,\dots,P_n$
- Consider a secret sharing algorithm Share(b) and reconstruction algorithm/function $Rec(b1,\dots,bn)$.

### Distribution and reconstruction:
- WRITE: The dealer D runs a secret sharing algorithm Share(b) and distributes the shares $b_1,\dots,b_n$ respectively to each of $P_1,\dots,P_n$ secretly, such that none of them can compute $'b'$ on their own.
- READ: Is the reconstruction algorithm/function using which we can reconstruct the secret-b by XORing the secret shares $b_1,\dots,b_n$

### Secrecy:
Even if a party Pi is malicious, the share it has looks random and uncorrelated to the actual secret. So, it cannot possibly divulge any information about the secret-b.

### MPC protocol realizing:
The function F depicted above is the ideal F realized by XOR-secret sharing

Refer the following handwritten notes/diagram from the class:

#### Note from the lecture:
An ideal adversary can learn i/p and o/p of the corrupted party.
We use the idea of the sampling random bits. (thats how we achieve secrecy here).
Each adversary $P_i$ can compute $Z_i$ locally, but every other $Z_j$ of other Parties look random to it

## t-out-n Secret Sharing Scheme over F:

Explanation of few items:
- F is the Field
- PPT is a Probabilistic Polynomial Time Function.
- t-out-n -> Meaning that we need atleast t samples out of n total samples to reconstruct/compute the secret.

Considering a subset R of samples out of total n samples, enough to reconstruct the secret S.(needs t samples)

### t-privacy:
The cardinality of 'T' is less than the threshold 't'

#### Indistinguishibility of shares:
As long as we receive a subset R of a secret S,(cardinality less than threshold), We cannot distinguish if R belongs to S or of another secret S'

### t-reconstruction:
If we have enough elements in R (cardinality > t), we can reconstruct the secret S.

## Linear SSS over F
- [S] -> a share of S with respect to party i
- the scalar used for multiplication is chosen from the field.
- Locally, all parties do scalar mult. of their share parts.

#### Linearity
Sum and scalar mult as local and coordinated operations

## XOR Secret Sharing Scheme
#### Linearity:

## GMW protocol:
This is a classical MPC protocol of Goldreich, Micali, and Wigderson (GMW), which uses a boolean-circuit representation for the function being computed and is secure against a semi-honest adversary controlling any number of corrupted parties. The basic, semi-honest protocol, uses Oblivious Transfer to execute the boolean gates.

GMW protocol extensively uses OT

^ Thanks to the linearity of the of SS

While an only NAND circuit is complete, a XOR gate circuit is not enough. We need a sub-protocol to handle multiplication

### Addition is easy:
A party with input $x ∈ \{0, 1\}$ chooses uniform bits x1, . . . , xn subject to
the constraint that $x = x_1 ⊕\dots ⊕ x_n$ It then sends xi to party Pi.
similiarly, there is another input y = y1 ⊕ · · · ⊕ yn. It then sends yi to party Pi.

Say $z = x ⊕ y$

in that case $( ⊕x_i ) ⊕ (⊕y_i)$
=> $⊕ (x_i ⊕ y_i)$ which can be computed locally at each party Pi independent of others.

### Multiplication is not:

Local computation is not possible like previous case.

for n=2: Multiplication protocol can be achieved by a 1-out-of-4 OT as follows

clarification for table above:
considering : $z = x . y$
=> $(z1⊕z2) = (x1⊕x2).(y1⊕y2)$ $=>$ $(z1⊕z2)⊕z1 = z2 = (x1⊕x2).(y1⊕y2) ⊕ z1$

However, for n>2 , it will be not be a simple OT:

for n>2:

Although each Pi can compute the first part locally on its own, it must collaborate with Pj to calculate the shares xi·yj ⊕ xj·yi

### Multiplication Protocol for n>2 in the OT-Hybrid world

Consider the sampling of inputs as following:



At the end of the Protocol , each Pi has an n-out of-n share of (x*y).

From what we already have:

#### Correctness:
We need to show:

X-oring the output of each party gives the mult. of the xoring of each parties share

By definition of the multiplication protocol above: 

=> 

We need to show : 

explanation for above step:
$i\neq j$ would include all permutations of i and j (example $(i = 2 ,j=1), (i=1,j=2),... )$ like tuples.

however,
$\{i,j\}$ is a set, order of the elements doesnt matter. so, $\{i,j\} = \{j,i\}$ , so $\{1,2\} = \{2,1\}$

hence the expansion.

#### Complexity:
GMW is inefficient

the round complexity of the GMW protocol is high. All AND gates
at the same level can be computed by the parties in parallel, but AND gates at different levels
must be computed sequentially.

GMW is not so good as it depends on the number of rounds of OT.