Exponential implementation in SMPC

[LaRiffle]

Suggestion to implement exp in SMPC

The interest of this is to allow computation of functions which derive of exponentials like sigmoid.

Let's say you share the tensor x in x0 and x1. You want to compute exp(x).
But exp(x) = exp(x0 + x1) = exp(x0) * exp(x1).
So you can compute locally exp(x0) and exp(x1), and additively share these values, perform an encrypted mul and then you obtain shares of exp(x0) * exp(x1) = exp(x).

[kamathhrishi]

Guess I will take this up :)

[andrelmfarias]

@LaRiffle please notice that when doing operations in SMPC we are working with fixed_precision tensors. Exponential is not defined for fixed_precision tensors, we would need a polynomial approximation or other numerical methods that require several computations (including division which is really slow now)... 😞

[LaRiffle]

Why it won't work:

x = torch.tensor([[3, 4]])
x_sh = x.share(alice, bob, crypto_provider=crypto_provider)

x0, x1 = x_sh.child.child['alice'], x_sh.child.child['bob']
x0 = x0.float()
x1 = x1.float()

exp_x0, exp_x1 = [torch.exp(x0), torch.exp(x1)]
print(alice._objects[exp_x0.id_at_location], bob._objects[exp_x1.id_at_location])

output

(tensor([[inf, inf]]), tensor([[inf, inf]]))

Computers are so weak.

[LaRiffle]

Ok so let's not give up here!

Claim 1

If I can compute privately exp of a bit then I'm good for any exp(integer)

Idea:

e = torch.exp(torch.tensor(1.))
# this...
e**5
# can be written
e**(1*2**2 + 0*2**1 + 1*2**0)
# or also
(e**1)**(2**2) * (e**0)**(2**1) * (e**1)**(2**0)

Claim 2

I can compute privately exp of a single bit

# Take a bit (0 or 1, here 0 for example)and share it in a *binary* field
x = torch.tensor([0])
x_sh = x.share(alice, bob, crypto_provider=crypto_provider, field=2)

# Access shares
x0, x1 = x_sh.child.child['alice'], x_sh.child.child['bob']
x0 = x0.float()
x1 = x1.float()
print(alice._objects[x0.id_at_location], bob._objects[x1.id_at_location])

# Compute privately the wrap field bit, which decrypts to 1 iff x0+x1 >= 2  
x0_sh = x0.fix_precision().share(alice, bob, crypto_provider=charlie).get()
x1_sh = x1.fix_precision().share(alice, bob, crypto_provider=charlie).get()
wrap_field = x0_sh * x1_sh 

# Compute exp of shares
exp_x0, exp_x1 = [torch.exp(x0), torch.exp(x1)]
alice._objects[exp_x0.id_at_location], bob._objects[exp_x1.id_at_location]

# Share the exp of shares
exp_x0_sh = exp_x0.fix_precision().share(alice, bob, crypto_provider=charlie).get()
exp_x1_sh = exp_x1.fix_precision().share(alice, bob, crypto_provider=charlie).get()

# Apply exp(x0 + x1) =  exp(x0) *  exp(x1) formula + a wrapping correction if needed
one = torch.tensor([1.]).fix_precision()
inv_exp_field_size = torch.exp(-torch.tensor([2.])).fix_precision()

exp_sh = exp_x0_sh * exp_x1_sh * (wrap_field * (inv_exp_field_size - one) + one)

# Open and get 1.0
exp_sh.get().float_prec()

Now, how practical is this is another question...
From my first implem, the price to pay should be around 1.5s for a float value, which can be amortized when using vectors

[mortendahl]

@LaRiffle I suggest you take a look in the SCALE-MAMBA documentation. Note that some of those protocols might be slower versions that are used to support any n, and hence there may be better protocols for the two-party case.

[andrelmfarias]

@mortendahl we were discussing SCALE-MAMBA last week, @LaRiffle and I were thinking about trying to "hook" it for some MPC operations...

[mortendahl]

@andrelmfarias @LaRiffle not sure I understand what you mean by hooking here..?

[andrelmfarias]

We were thinking that maybe we could "hook" some operations from their github repository: https://github.com/KULeuven-COSIC/SCALE-MAMBA

To use their protocols without needing to implement them ourselves in PySyft.

I don't know if it's clear...