Abstract by anuja a sonalker on Asymmetric Key Distribution

(a) 
(b) 
Fig 3.4: Reduction in Key Space and computation overhead using key share reuse. 
At the end of the Key generation process, for a 3-out-of 5 threshold, the Trusted Dealer’s 
table of key shares would look as follows. 
 
S
1
 
S
2
 
S
3
 
S
4
 
S
5
 
S
t+1 
(Special 
Server) 
Combination 1 
d
1
d
2
d
3
- - 
d
ss1
Combination 2 
d
1
- d
3
d
2
- 
d
ss2
Combination 3 
: 
d
2
d
3
: d
1
d
ss3
: 
: : : : : 
: 
Combination C
*
: : : : : 
: 
Fig 3.5: Typical Trusted Dealer table after Key generation 
* C = 
1
+
−
t
k
C
k
t
due to key share reuse.
 

---

32 
3.9 Example: 
Scenario: Let k = 7 be the total number of share servers in the setup. If the number of 
share servers required to participate was predetermined as 5, then, as per the algorithm, 
the Special Server would be dealt a private-key share equivalent to a series of k-t+1 
shares by the Trusted Dealer and each Share Servers would be dealt a private share. 
During certificate signing, say, a random coalition sequence of Servers 2, 3, 5, 6, 7 was 
generated, then the Special Server would receive five signed shares of the hash of the 
message M, from the respective share servers.
As per the dynamic combination of share servers in this round of certificate signing, the 
Special Server selects his key share (corresponding to 2_3_5_6_7) using the numerical 
lookup 23567 and computes his signature share. This share is equivalent to the signing of 
k-t+1 = 3 individual shares. He multiplies all the signature shares he received to obtain 
the complete signed certificate S. He then uses the public exponent, e, on the signature S 
and matches it with the message to verify that the correct shares have been applied. 
Here, we can see that no combination of compromised servers would be able to get the 
message signed. Even if the 7 Share Servers maliciously try to utilize the private shares 
they possess in order to generate the Special Servers signature share, they would not be 
able to for two reasons:
1.) The size of the key being so large, and given the number of threshold servers, the 
total number of possible combinations they would need to try would be so time-
intensive an operation that the attack would become too late to do any good. 
2.) Though the total number of shares being used here is six, it is equivalent to 
virtually increasing the threshold to 8. Since there are only seven share servers, 
they cannot combine to form the equivalent of eight shares. 
Thus, we have the same effect as that achieved by a higher threshold by having 
almost half the threshold and without forgoing security. Thus we maintain that the 
malicious intending servers will never be able to leave out the Special Server in any 
successful transaction. 

---

33