Abstract by anuja a sonalker on Asymmetric Key Distribution

3.8 Key Share Reuse 
In the classical secret sharing scheme[1], k shares are created for k servers, any t out of 
which can combine to form the coalition. This scheme does not have enough randomness 
in the key shares its possesses as the key space used here is not very large. The secret 
sharing scheme used here generates t shares for every possible combination of t-out-of-k 
servers. In other words, the Trusted Dealer would create an 2-D array of private-key 
shares of the order of 
C
k
t
x ( t +1 ). Let us consider the previous example to fully 
understand the concept of key share generation. Thus, 21 sets (
C
7
5
sets) were computed 
and a 2-D array of order 21x 6 key shares was created. Though this increases randomness 
in the available key space, it adds a large computation overhead to the key generation 
process. We therefore look for a way to reuse the number of key shares to be generated 
by sharing some of the private key shares with certain peers such that the security aspect 
is not lost or compromised[13]. Fig. 3.4(a) shows how key shares can be reused. Let us 
consider the previous example with the same array of key shares and the exact same 
setup, but by reusing key shares. Key share reuse reduces the existing number of sets 
from 
C
k
t
to {
C
k
t
div (k-t+1) +
C
k
t
mod (k-t+1)}, which can be up to 
1
+
−
t
k
C
k
t
if
C
k
t
mod (k-t+1) = 0. In this example, the total number of sets created was reduced from 
21 (without reuse) to 
1
5
7
21
+
−
= 
3
21
= 7 with key share reuse. 
In this case, the total number of sets the TD would need to generate would now be 7 
which is a 66% decrease in computation cost in key share generation alone. The figures 
below demonstrate how the private key shares are intelligently combined to reduce the 
number of required sets. In the first set, 5 key shares are distributed to any five of the 
seven share servers, namely, S
1, 
S
2, 
S
3,
S
4 
and S
5 
. Since 2 servers were not given any 
shares, they can be provided with the one of the already dealt shares (d
1 
- d
5
) in the next 
set and leaving out the share server who received that share in the previous set. Thus, in 
Set 2, d
2
was dealt to S
6 
and S
2 
left out of the combination. In Set 3, d
1 
was dealt to S
7 
and 
S
1 
left out of the coalition. Keys can only be reused as many times as there are servers in 

---

31 
excess of the threshold. Since here there are only two servers in excess of the threshold, 
keys can be reused only twice after they initially distributed. Fig 3.4(b) is a concise way 
of representing the array shown in Fig 3.4(a). In key share reuse, care must be taken to 
ensure that no server gets two different shares for the same coalition i.e., from the same 
set. 
S
1
S
2
S
3
S
4
S
5
S
6
S
7
SS 
S
1
S
2
S
3
S
4
S
5
S
6
S
7
SS 
1 d
1
d
2
d
3
d
4
d
5
- - 
d
ss
2 d
1
- d
3
d
4
d
5
d
2
- 
d
ss
1 d
1
d
2
d
3
d
4
d
5
d
2
d
1
d
ss
3 - d
2
d
3
d
4
d
5
- d
1
d
ss
4 
d
10
- - d
6
d
7
d
8
d
9
d
ss
2 d
10
d
8
d
9
d
6
d
7
d
8
d
9
d
ss
5 
d
10
- d
9
d
6
d
7
d
8
- 
d
ss
: : : : : : : : 
: 
: : : : : : : : : 
21 d
31
d
32
- - d
33
d
34
d
35
d
ss
⇒
7 d
31
d
32
d
31
d
32
d
33
d
34
d
35
d
ss