When Alice Goes Bad: Byzantine Secret Sharing

When Alice Goes Bad: Byzantine Secret Sharing

We need to start building systems which are fault-tolerant, and where we assume that sometimes our systems give us errors, or can be faulty, or that they have been taken over by a malicious agent. This will give us Byzantine Fault Tolerance (BFT) in our processing and decision-making. For example, let’s say we are processing a transaction, and have four checkers for the validity of the transaction. If we had one checker, then it may have an error or could be compromised by a hacker. But if we have four, then if three of the checkers were good, we would have an election, and take the majority vote. A checker which loses these elections may then be faulty or is compromised.

A perfect way of keeping things secure and creating resilience is to use Shamir Secret Sharing (SSS), and where we can distribute a secret, and then allow any n-from-m to recover the secret. In this way, Bob, Alice, Carol and Dave can share a secret, and then any three of them can come together and recreate the share. This means we also have resilience in that one might not want to share — or have lost their secret — and we will still be able to recover it. But, what happens when Alice goes bad, can we recreate the shares between Bob, Carol and Dave, so that Alice cannot rebuild the secret? Well, yes! For this, we use Proactive Secret Shares (PSS), but first I’ll explain Shamir’s Secret Shares (SSS), and then outline PSS.

Shamir’s Secret Shares

With secret sharing, we take a secret value and then share it with others. For example, we might have a share for Bob, Alice, Carol and Dave and then for three of them to come together to bring their shares together. First, we generate a polynomial, and which has a secret value. In the following example, we have a quadratic equation of f(x)=2x² -2x + 5 [here]. The secret could be stored at f(0) (the red line), and where we give Bob their y value for x=1 (f(1) — the purple line), Carol the value at x=2 (f(2) — the blue line), Dave the value at x=3 (f(3) — the green line) and Alice the value at x=4 (f(4) — the outer blue line). With the values of their own, they cannot recover f(0), but if we have three of the values, we can recover it:

For an any-3-from-4, we can use a quadratic equation, such as f(x)=20x²−2x+10, and where the value of 10 is the secret. Bob then gets the value of f(x) when x=1. This can be defined as f(1). Carol gets f(2), Dave gets f(3) and Alice gets f(4). The secret value is thus f(0). They then each know a point on the quadratic equation, and three of them can bring them back to recover the secret. In this case, we will generate a random polynomial of ax²+bx+secret, and then distribute the shares to Bob, Alice, Carol and Dave. Finally, we will recover the secret from three of these shares (Bob, Carol and Dave) [here]:

import numpy as np
import random
import sys

a = random.randint(20,20)
b = random.randint(-20,20)
secret = 10

if (len(sys.argv)>1):
 secret=int(sys.argv[1])

seq = [a,b,secret]
f = np.poly1d(seq)
print ("Secret equation:\n",f)

print ("\nSecret: ",f(0))
print ("Bob: ",f(1))
print ("Carol: ",f(2))
print ("Dave: ",f(3))
print ("Alice: ",f(4))

x=[1,2,3]
y=[f(1),f(2),f(3)]
res=np.polyfit(x,y,2)
print ("\nSecret equation: ",res)
print ("Secret: ",int(round(res[2],0)))

The brilliance of the Numpy library comes to the fore here, as we can take the form of seq = [3,5,7] and generate a polynomial of 3x² + 5x + 7. A sample run with a secret of 10 and a secret equation of 20x²-19x+10 is [here]:

Secret equation:
     2
20 x - 19 x + 10

Secret:  10
Bob:  11
Carol:  52
Dave:  133
Alice:  254

Secret equation:  [ 20. -19.  10.]
Secret:  10

In this case, Bob, Carol and Dave bring their shares back to recover the secret. It is not possible for only two of them to recover the secret, as we need three points on a quadratic equation, to recover the equation. But, let’s say that Alice goes bad, and now Bob, Carol and Dave want to regenerate their secrets, without Alice getting involved.

Proactive Secret Sharing

With PSS, Bob, Carol and Dave have secrets, and they don’t want them regenerated, as they don’t trust anyone to do it for them. They know that Alice has turned bad, so must leave her out.

With proactive secret shares, Bob, Carol and Dave can regenerate their shares in order to remove Alice from the sharing process. For this, Bob generates a new equation of g(x) and where g(0)=0, Carol generates h(x) and where h(0)=0, and Dave generates k(x) and where k(0)=0. Bob then shares g(2) with Carol and g(3) with Dave, and each of them does the same with their new equations. Thus Carol passes h(1) to Bob, and h(3) to Dave, and Dave passes k(1) to Bob and k(2) to Carol. Bob’s new share value will be f(1)+g(1)+h(1)+k(1). Once the share is over they will have a new sharing equation of f′(x)=f(x)+g(x)+h(x)+k(x), and where f′(0) will generate the secret.

In this case, we use Numpy to generate the polynomial, and also recover it:

import numpy as np
import random
import sys
a = random.randint(20,20)
b = random.randint(-20,20)
secret = 10
if (len(sys.argv)>1):
 secret=int(sys.argv[1])
seq = [a,b,secret]
f = np.poly1d(seq)
print ("Secret equation:\n",f)
print ("\nSecret: ",f(0))
print ("Bob: ",f(1),end=' ')
print ("Carol: ",f(2),end=' ')
print ("Dave: ",f(3),end=' ')
print ("Alice: ",f(4))
g_x = np.poly1d([random.randint(-20,20),random.randint(-20,20),0])
h_x = np.poly1d([random.randint(-20,20),random.randint(-20,20),0])
k_x = np.poly1d([random.randint(-20,20),random.randint(-20,20),0])

print ("\nBob's new secret equation:\n",g_x)
print ("Carol's new secret equation:\n",h_x)
print ("Dave's new secret equation:\n",k_x)
carol_to_bob = h_x(1)
dave_to_bob = k_x(1)
print ("\nBob new value: ",f(1)+g_x(1)+carol_to_bob+dave_to_bob)
bob_to_carol = g_x(2)
dave_to_carol = k_x(2)
print ("Carol new value: ",f(2)+h_x(2)+bob_to_carol+dave_to_carol)

bob_to_dave = g_x(3)
carol_to_dave = h_x(3)
print ("Dave new value: ",f(3)+k_x(3)+bob_to_dave+carol_to_dave)

f_ = f+g_x+h_x+k_x
print ("New secret:\n",f_)
print ("\nSecret: ",f_(0))
print ("Bob: ",f_(1),end=' ')
print ("Carol: ",f_(2),end=' ')
print ("Dave: ",f_(3),end=' ')
x=[1,2,3]
y=[f_(1),f_(2),f_(3)]
res=np.polyfit(x,y,2)
print ("\nSecret equation: ",res)
print ("Secret: ",int(res[2]))

A sample run with a secret of 10 and a secret equation of 20x²+4x+10 is:

Secret equation:
     2
20 x + 4 x + 10

Secret:  10
Bob:  34 Carol:  98 Dave:  202 Alice:  346

Bob's new secret equation:
     2
10 x + 8 x
Carol's new secret equation:
    2
8 x - 17 x
Dave's new secret equation:
      2
-11 x - 11 x

Bob new value:  21
Carol new value:  86
Dave new value:  205
New secret:
     2
27 x - 16 x + 10

Secret:  10
Bob:  21 Carol:  86 Dave:  205 
Secret equation:  [ 27. -16.  10.]
Secret:  10

Conclusions

And there you go. Shamir’s secret-sharing method is one of the most wonderful things I’ve come across, but it suffers from a malicious party being able to trick the others in recovering a secret. With proactive secret sharing, we can remove Alice, and Bob, Carol and Dave, and still protect the secrecy of the store secret, and now get rid of Alice from it. It’s just magic!