Abstract by anuja a sonalker on Asymmetric Key Distribution

Table 3.1: Typical key share splitting for a single set for a private-key. 
key SetCount Z 
index priv_share 
d[index] key New 
Z 
1000 1 279 0 163 163 837 170 
837 1 170 1 157 157 
680 
535 
680 1 535 2 145 145 
535 
197 
535 1 197 3 141 141 
394 
251 
394 1 251 4 143 143 
251 
126 
251 1 126 5 xxxx 
xxxx 
xxxx 
xxxx 

---

29 
We begin with a key size of 1000 and as we progress through the algorithm, each new 
modulus creates a share of the key. This process continues till the required number of 
share server shares is created. Once the required number of shares is created (as seen in 
row 6), further splitting of the key is stopped and the remaining share is allotted to the 
special server. Thus, share servers S1 to S5 would be allotted d[0] to d[4] and d[5] to 
Special Server. 
If there are k Share Servers, any t out of which can combine to form a legitimate 
signature along with the compulsory share from the Special Server, the Trusted Dealer 
would need to split the private-key d into t +1 shares for each possible combination of the 
t-out-of-k Share Servers. In short, the Trusted Dealer would generate an array of key 
shares for every possible combination of Share Servers in the system and a compulsory 
share for the Special Server for each of the combinations. This introduces more 
randomness in the private-key share generation than the original threshold scheme 
proposed by Shamir[1] since there are more combinations of key shares with each 
participant. It enables the servers to use different private shares for different 
combinations of Share Server coalitions. This way, the Trusted Dealer would need to 
create 
C
k
t
sets of t+1 shares to accommodate all the possible combinations, which could 
be a computationally expensive process if k is comparatively larger than t. This overhead 
can be reduced by intelligent reuse of key shares among certain servers without 
compromising on the secrecy aspect of the private-key shares. 
For example, If the Trusted Dealer had to generate the private keys for a scenario where 
there was a 5-out-of-7 secret sharing among the Share Servers, then he would need to 
generate 
C
k
t
= 
C
7
5
= 21 different sets of 6 private shares which would be a 
computationally heavy task. By intelligent reuse of key shares, the burden on the Trusted 
Dealer is reduced by a factor up to (k-t+1).

---

30