Abstract by anuja a sonalker on Asymmetric Key Distribution

 
2.6 How threshold schemes work 
Threshold schemes according to Shamir [1] could be explained thus for a system with 
threshold of two as an example. If there are three servers, two out of which are required 
for a successful signature, we can imagine all the three shares to be part of an x-y plane 
where the co-ordinates (0,S) represent the signature. S1, S2, S3 are the shares of the 
individual servers. 
(0,S) 
S1 
y2 
S2 (x2, y2) 
S3 
x2 
Fig 2.1: Shamir’s Secret Sharing 
According to Shamir [1][4], the secret always lies on the y-axis. We start with the point 
(0,S) on the y axis which is the combined share. If a random line is drawn from that point 
in the positive x-y plane, and three random points are picked on it, it can be observed that 
a minimum of two points on this line are needed to arrive at (0,S) successfully. Any 

---

14 
number of points less than this minimum, in this case a single point, would mean infinite 
number of lines through it, and it would be impossible to retrieve the secret point (0,S) 
from just the single point. This minimum is known as the threshold of the system. If the 
scheme used more than three shares, there would be more points on the line and yet any 
two would be enough to deduce S. Similarly we can visualize geometric figures for 
higher orders of threshold. For a threshold of three, the line would become a parabolic 
curve (curve of degree 2) where any three points would be enough to deduce S. 
2.7 Threshold RSA 
To protect the RSA private key, it is split up into a number of pieces and distributed to 
every server. The private key, d, now looks like this: 
d = d
1 
+ d
2
+ d
3 
+ d
4 
+……+ d
k
, where k is the number of pieces the key is divided into. 
It is also the total number of servers in the system. If t is the threshold of this system, then 
the fault tolerance of the system is k-t.
Now, instead of a single key creating a single signature, we have any t private-key shares 
creating t signature shares. These individual shares are further combined to form the 
signed certificate.
Thus, S
i
= M
d
i
mod N for any t servers. 
Then, S =
Π
S
i ,
where i is in the range of [1 , k]. 
=> S = (S
1 
· S
2 
·....
S
t 
) mod N = ( M
d
1
· M
d
2
· …. · M
d
t
) mod N 
Thus a valid signature is created without having to recreate d at any location . 
And M = (S
e
) mod N.

---

15