# Additive Secret Sharing

Author: 
- Carlos Salgado - [email](mailto:csalgado@uwo.ca) - [linkedin](https://www.linkedin.com/in/eng-socd/) - [github](https://github.com/socd06)

## Additive Secret Sharing
Additive Secret Sharing is a mechanism to share data among parties and to perform computation on it. 



## Sharing
A secret `s` is uniformly split into `n` shares, one per shareholder (also known as worker, node, user or party) using some randomness `r`, also known as some **very high random prime** number `Q`. 

$ F_s (s, r, n) = ( s_1, s_2, ..., s_n ) $

## Reconstruction
`s` can be reconstructed (decrypted) by adding up **all the shares** and taking the [*modulo*](https://en.wikipedia.org/wiki/Modulo_operation) of the random prime number `Q`, used to encrypt the shares originally. 

$ s = ( \: \sum \limits _{i=1} ^n s_i \: ) \; mod \; Q $

## 32-bit Integer Secrets
A secret is the data or message that a party wants to secure. In additive secret sharing, secrets (and therefore, shares) must be members of a fixed [finite field](https://en.wikipedia.org/wiki/Finite_field). Particularly, the literature mentions shares should be members of the $ {\mathbb{Z}_{2^{32}}} $ [ring](https://en.wikipedia.org/wiki/Ring_(mathematics)), which is the [ring of integers](https://en.wikipedia.org/wiki/Ring_of_integers) that fit within [32-bits](https://en.wikipedia.org/wiki/32-bit_computing).  



Rings are [sets](https://en.wikipedia.org/wiki/Set_(mathematics)) with two operations, addition and multiplication, which allow the rationale of secret sharing and reconstruction to work. 

Plainly, secrets and secret shares **must** be integers within -2,147,483,647 to +2,147,483,647

## Governance
Additive secret sharing provides shared governance. The threshold `t` to reconstruct `s` is equal to `n`, which means **no party can recover the data** alone because all the shares are required to decrypt the secret *(t = n)*. This scheme allows us to do computation on the shares while each shareholder is only aware of their **own** share.

### [Quiz] Find the secret `s`

In practice, we use a **very high prime number** Q to add a **big deal of uniform randomness** to our shares. Here we will use a very small Q, so you can try to solve the quiz without programming yet. 

Let $ s_1 = 10 \; and \; s_2 = 74 \; and \; Q = 59 $

What is the original secret `s`? Fill the ____ space below with your answer.
Try **not** to use a calculator or programming.


```python
# Run this cell to import the quizzes
from quiz import q0, q1, q2
```


```python
# run to check your answer
q0.check(___)
```


```python
# Uncomment the line below to see a hint
# q0.hint
```


```python
# Uncomment the line below to see the solution
# q0.solution
```

### [Quiz] Find the final share s<sub>2</sub>

Using a small `Q` to facilitate calculation (it needs to be a **very high prime number** in production), let 

$ s = 7, n = 2 $ with $ Q = 59 $ and $ s_1 = 9 $
plugged in on the secret reconstruction equation, find the final share s<sub>2</sub>.

Fill the ____ space below with your answer. Feel free to implement the equation in a new cell or use whatever tool you'd like (e.g. a calculator), it's your call.  


```python
# Fill the ____ space below with your answer
final_share = 

# run to check your answer
q1.check(final_share)
```


```python
# Uncomment the line below to see a hint
# q1.hint
```


```python
# Uncomment the line below to see the solution
# q1.solution
```

## In Practice
Just as an educational example, we can generate a list of prime numbers using [sympy](https://www.sympy.org/en/index.html)


```python
# Verify we have all the tools we need to run the notebook
!pip install -r requirements.txt
```


```python
import sympy

# An arbitrary constant, feel free to play with it
CONST = 999

BIT_DEPTH = 31

# Range start
start = 2**BIT_DEPTH-CONST

# Maximum in Z2**32 ring
end = 2**BIT_DEPTH 

prime_lst = list(sympy.primerange(start,end+1))

print("Prime numbers in range: " , prime_lst)
```

And **randomly** choose one every time using [NumPy](https://numpy.org/devdocs/contents.html)'s [randint](https://numpy.org/doc/stable/reference/random/generated/numpy.random.randint.html)


```python
from numpy.random import randint

Q = prime_lst[randint(len(prime_lst))]
Q
```

As an additional note, the [Secrets module](https://docs.python.org/3/library/secrets.html), introduced in Python 3.6, provides randomness as secure as your operating system.


```python
import secrets 
  
Q = secrets.choice(prime_lst)
Q
```

## The Final Share and 2-party Additive Secret Sharing

Knowing that $ s_n = Q - (\;  \sum \limits _{i=1} ^{n-1} s_i \; mod \; Q \; ) + s $

How do we implement 2-party ($ n=2 $) additive secret sharing using Python? 

Keep reading and fing out!


```python
def dual_share(s, r):
    '''
    s = secret
    r = randomness
    '''
    share_lst = list()
    share_lst.append(randint(0,r))
        
    final_share = r - (share_lst[0] % r) + s
    
    share_lst.append(final_share)
        
    return share_lst
```


```python
# Let's generate a couple of shares
secret = 5 

dual_shares = dual_share(secret, Q)
dual_shares
```

Now go back to the previous cell and **run it again**. Notice anything?

...

...

... 

See it yet? The shares are never the same because they are **randomly generated**.

Now let's implement the reconstruction (or decryption) function.


```python
def decrypt(shares, r):
    '''
    shares = iterable made of additive secret shares
    r = randomness
    '''
    return sum(shares) % r
```


```python
# And let's decrypt our secret for the first time
decrypt(dual_shares, Q)
```

## Exercise: Implement n-party additive secret sharing 
Fill the function below with your code.


```python
def n_share(s, r, n):
    '''
    s = secret
    r = randomness
    n = number of nodes, workers or participants    
    
    returns a tuple of n-shares
    '''
    # replace with your code
    pass            
```


```python
five_shares = n_share(s=686,r=Q,n=5)
five_shares

# run this cell to check your solution
q2.check(decrypt(five_shares, Q))
```


```python
# Uncomment the line below to see a hint
# q2.hint
```


```python
# Uncomment the line below to see the solution
# q2.solution
```

## Addition
Given two shared values $a$ and $b$, a party $P_i$ can compute the added shares as:
$ c_i = ( a_i + b_i ) \; mod \; Q$

In Python, we can implement this type of addition like this:


```python
def addition(a, b, r):
    '''
    a = iterable of the same length of b
    b = iterable of the same length of a
    r = randomness AKA randomly generated very high prime number 
    '''
    c = list()
    
    for i in range(len(a)):
        c.append((a[i] + b[i]) % r)
        
    return tuple(c)
```

Considering Alice and Bob are our parties, with secrets $s_a$ and $s_b$ to be shared (2-way) and wanting to compute addition.

Let $s_a = 5 $ and $s_b = 11 $

Alice's shares would be something like:


```python
# Alice's secret
sa = 5 

alice_shares = dual_share(sa, Q)
alice_shares
```

While Bob's shares would be


```python
# Bob's secret
sb = 11

bob_shares = dual_share(sb, Q)
bob_shares
```


```python
secret_sum = addition(alice_shares, bob_shares, Q)
secret_sum
```

Doesn't make a lot of sense, does it?

Secret shares must only reveal information about their secrets when they are all combined. Otherwise all data must be hidden, which defines the **privacy** property. 

These are still secret shares so there is one more step to get the sum of the original secrets. 


```python
decrypt(secret_sum, Q)
```

Et Voilà!

## Public (scalar) Multiplication
Given a list of shared values $a$ and a **scalar** $b$, a party $P_i$ can compute the multiplied shares as:
$ c_i = a_i \times b \; mod \; Q$

In Python, we can implement this type of multiplication like this:


```python
def public_mul(a, b, r):
    '''
    a = iterable of the same length of b
    b = scalar to multiply a by
    r = randomness AKA randomly generated very high prime number 
    '''
    c = list()
    
    for i in range(len(a)):
        c.append((a[i] * b) % r)
        
    return tuple(c)
```

Let's say another party wants to multiply Alice's shares by the **scalar** value of 3. 


```python
alice_times3 = public_mul(alice_shares, 3, Q)
```

Then we can decrypt (with Alice's permission) to double check we did multiply what we intended.


```python
decrypt(alice_times3,Q)
```

And this is `True` because Alice's secret $sa = 5$, remember?


```python
decrypt(alice_times3,Q) == sa * 3
```

## PyTorch + PySyft implementation
Now that you know how additive secret sharing works under the hood, let's see how we can leverage PyTorch and PySyft to do it for us.


```python
import torch
import syft as sy
hook = sy.TorchHook(torch)
```

Let's say Alice, Bob and Charlie are all enrolled on the **Foundations of Privacy** course and we, as instructors, want to know on average, how far in the course they are. We don't want to breach their privacy so each percentage of completion will be their own secret (a, b and c). 

For educational purposes, we will define our parties (nodes, workers, etc) using `VirtualWorker` PySyft objects.


```python
alice = sy.VirtualWorker(hook, id="alice")
bob = sy.VirtualWorker(hook, id="bob")
charlie = sy.VirtualWorker(hook, id="charlie")
```

We also need a "secure worker", also known as the `Crypto Provider` to provide us with random prime numbers.


```python
secure_worker = sy.VirtualWorker(hook, "secure_worker")
```

We define our secrets using `torch.tensor` PyTorch tensor objects and we `Additive Share` them with our fellow workers.


```python
# Let a, b and c be our students' completion percentage
a = torch.tensor([35])
b = torch.tensor([77])
c = torch.tensor([10])
```


```python
# And we additive share with our parties
a = a.share(alice, bob, charlie, crypto_provider=secure_worker)
b = b.share(alice, bob, charlie, crypto_provider=secure_worker)
c = c.share(alice, bob, charlie, crypto_provider=secure_worker)
```


```python
# And we compute the mean of our tensor
mean = torch.mean(torch.stack(list([a,b,c])))
mean
```

Also, see that the object type is **[AdditiveSharingTensor]**.
For this example, we can decrypt our computation result using the get() method


```python
decrypted_mean = mean.get()
decrypted_mean
```

And get the scalar using the item() method (Only works for 1-dimensional tensors).


```python
scalar_mean = decrypted_mean.item()
scalar_mean
```

Now, the average completion should actually be 40 and $ \frac{1}{3} $ (or 40.6666666666... ) but this is something we will learn about in the next lessons.

Let’s now tackle private multiplication!

cb10273e7d8cbf1c9915a4422be9b24d2401a1dc
ipynb
Jupyter Notebook
Foundations_of_Private_Computation/Secure_multiparty_computation/Additive Secret Sharing.ipynb
gonzalo-munillag/Private_AI_OpenMined
c23da9cc1c914d10646a0c0bc1a2497fe2cbaaca
MIT
2021-01-06T16:49:22.000Z
2021-02-19T05:34:27.000Z
Foundations_of_Private_Computation/Secure_multiparty_computation/Additive Secret Sharing.ipynb
gonzalo-munillag/Private_AI_OpenMined
c23da9cc1c914d10646a0c0bc1a2497fe2cbaaca
MIT
Foundations_of_Private_Computation/Secure_multiparty_computation/Additive Secret Sharing.ipynb
gonzalo-munillag/Private_AI_OpenMined
c23da9cc1c914d10646a0c0bc1a2497fe2cbaaca
MIT
Qwen/Qwen-72B
1. YES
2. YES