Method and system for enhancing network security using a multilateral authorization mechanism

• US 7,136,489 B1
• Filed: 09/12/2002
• Issued: 11/14/2006
• Est. Priority Date: 09/12/2002
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Madhusudhana, Honnuduke S., Nagaraj, Shishir, Tripathi, Aridaman
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Pich, Ponnoreay
• Application Number:
  US10/242,176
• Time in Patent Office: 1,524 Days
• Field of Search: None
• US Class Current: 380/277
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

A method and system is provided for implementing a multilateral authorization quorum in a computer network. The authorization quorum comprises a total number of stakeholders out of which a threshold number of stakeholders can provide a multilateral authorization. To implement this multilateral authorization quorum, one or more access sets is first determined, each containing the threshold number of stakeholders. Since the stakeholders split a quorum private key, the shares of the quorum private key for each stakeholder in all access sets are determined. The shares of the private key held by the stakeholders in any one access set add up to a number directly related to the private key. One or more secret keys of the stakeholders are further determined for each access set. One or more polynomials for the access sets are then generated by using the shares of the private key and the secret keys thereof, wherein the private key is thus split among the stakeholders of the multilateral authorization quorum. Such a multilateral authorization quorum is ready to be used for making approvals for predetermined transactions.

Claims

1. A method for implementing a multilateral authorization quorum in a computer network, the multilateral authorization quorum comprising a total number of stakeholders out of which a threshold number of stakeholders can provide a multilateral authorization, the stakeholders sharing a quorum private key, the method comprising:

determining one or more access sets, each containing the threshold number of stakeholders;

determining a share of the quorum private key held by each stakeholder in all of the one or more access sets, wherein the shares of the quorum private key held by the stakeholders in any one of the one or more access sets add up to a number directly related to the quorum private key, wherein the quorum private key is split among the stakeholders of the multilateral authorization quorum, thereby forming the multilateral authorization quorum;

determining one or more secret keys of the stakeholders for each of the one or more access sets; and

generating one or more broadcast polynomials for each of the one or more access sets using the shares of the quorum private key and the one or more secret keys thereof;

wherein the threshold number of stakeholders in the multilateral authorization quorum collectively generate a collective signature for a message in the computer network utilizing a Guillou-Quisquater public key security system, comprising;

computing a value R=r^E(mod N) wherein r is a random number between 1 and integer N, and E denotes a public exponent thereof;

computing t=H (M, R) (mod E), wherein M represents the message being signed by the stakeholders and H(M, R) is a one-way hash function;

computing J′

such that J′

*(J_SIGN)^t*r′

^E≡

1 (mod N), wherein r′

is a random number and 1<

r′

<

N and J_SIGN is the public key for the collective signature;

sending J′ and

a selected polynomial B(x) to all stakeholders in a selected access set;

computing a partial result j′

^Sk (mod N) by each stakeholder, wherein S_k=B(Z′

_k)(0≦

k<

K), Z′

_k denotes the secret key held by each stakeholder; and

computing an intermediate value T as T=r*r′

*J′

*Π

_{k=1 to K} J′

^Sk(mod N),

wherein a three-tuple <

M, t, T>

constitutes the collective signature of the threshold number of stakeholders.

2. The method of claim 1 wherein the shares of quorum private keys S_i and a quorum private key D bear a mathematical relation Σ

(0≦

i<

K) Si≡

D−

1 (mod λ

(N)), wherein 0≦

i<

K, and K represents the threshold number, wherein λ

(N) is a Carmichael function of two strong primes p and q and N=p*q.

3. The method of claim 2 wherein the quorum private key D correlates with a public key E of the multilateral authorization quorum by a mathematical relation:

E*D≡

1 mod λ

(N).

4. The method of claim 2 wherein a first one of the one or more broadcast polynomials for an access set A_i is mathematically represented as B_Ai(x)=Σ

<sub>(0≦

i<

K)</sub>C_iΠ

<sub>(0≦

j<

M and j∉

Ai)</sub>(Z_i−

Z_j)Π

<sub>(j≠

i and jε

Ai)</sub>(x−

Z_j)(mod λ

(N)) wherein C_i=B_Ai(Z_i)/Π

<sub>(0≦

j<

M and j≠

i)</sub>(Z_i−

Z_j) (mod λ

(N)/2), where M represents the total number of stakeholders and Z_i represents the secret key of the i-th stakeholder.

5. The method of claim 1 further comprising verifying that the quorum private key and the shares of the quorum private key held by the threshold number of stakeholders have not been tampered with.

6. The method of claim 5 wherein the verifying further includes:

providing a test value T corresponding to a broadcast polynomial B(x), the test value T being represented by T≡

t^E (mod N) for the access set, wherein t is a predetermined number and E represents a public key of the multilateral authorization quorum and N is a predetermined integer;

sending T and the broadcast polynomial B(x) to the stakeholders of the access set;

computing a partial result value T^Sk (mod N) by each stakeholder, wherein S_k=B(Z′

_k), and Z′

_k is the secret key held by each stakeholder;

computing a value T′

wherein T′

=TΠ

_{k=1 to K} T^Sk (mod N); and

verifying that T′

=t,

wherein if T′

equals t, the shares of the quorum private key held by the threshold number of stakeholders have not been tampered with.

7. The method of claim 1 further comprising providing an authorization utilizing the one or more broadcast polynomials and the secret keys held by the stakeholders.

8. The method of claim 7 further comprising:

selecting at least one of the one or more broadcast polynomials based on the access set for which it was generated; and

conducting one or more threshold cryptographic computations utilizing the at least one of the one or more broadcast polynomials and the secret keys.

9. The method of claim 7 wherein the multilateral authorization quorum is used for enrolling a new user in the computer network utilizing a Guillou-Quisquater public key security system, the enrolling requires approvals from the threshold number of stakeholders.

10. The method of claim 9 further comprising:

generating, by the new user, a public key J based on one or more predetermined parameters;

computing a value R=r^E(mod N) wherein r is a random number between 1 and integer N, and E denotes a public exponent thereof;

computing a value J′

such that R*J*J′

≡

1 (mod N);

wherein J denotes the public key chosen by the new user;

sending J′ and

a selected broadcast polynomial B(x) to all stakeholders in an access set;

computing a partial result j′

^Sk (mod N) by each stakeholder, wherein S_k=B(Z′

_k)(0≦

k<

K), Z′

_k denotes the secret key held by each stakeholder;

computing B′

=J′

*Π

<sub>k−

1 to</sub> K J′

^Sk (mod N);

sending B′

to the new user; and

computing a distinctive share B=B′

*r (mod N) as a quorum private key for the new user corresponding to the public key J.

11. The method of claim 1 further comprising verifying the generated collective signature.

12. The method of claim 1 further comprising adding at least one new stakeholder to the multilateral authorization quorum by generating new polynomials for added access sets.

13. The method of claim 12 wherein the generating includes, for the added access sets:

selecting a secret key for the at least one new stakeholder;

reselecting the shares of the quorum private key for all stakeholders to satisfy the condition that, for each access set, D−

1 (mod λ

(N)), wherein D represents the quorum private key and λ

(N) represents a predetermined modulus; and

recalculating the one or more polynomials using the shares of the quorum private key and the selected secret keys.

14. A computer program product for implementing a multilateral authorization quorum in a computer network, the multilateral authorization quorum comprising a total number of stakeholders out of which a threshold number of stakeholders can provide a multilateral authorization, the stakeholders sharing a quorum private key, the computer program product stored on a computer-readable medium and comprising instructions for:

determining one or more access sets, each containing the threshold number of stakeholders;

determining a share of the quorum private key held by each stakeholder in all of the one or more access sets, wherein the shares of the quorum private key held by the stakeholders in any one of the one or more access sets add up to a number directly related to the quorum private key, wherein the quorum private key is split among the stakeholders of the multilateral authorization quorum, thereby forming the multilateral authorization quorum;

determining one or more secret keys of the stakeholders for each of the one or more access sets; and

generating one or more broadcast polynomials for each of the one or more access sets using the shares of the quorum private key and the one or more secret keys thereof,

wherein the multilateral authorization quorum is used for enrolling a new user in the computer network utilizing a Guillou-Quisquater public key security system, the enrolling requires approvals from the threshold number of stakeholders, the computer program product further comprising instructions for;

generating, by the new user, a public key J based on one or more predetermined parameters;

computing a value R=r^E(mod N) wherein r is a random number between 1 and integer N, and E denotes a public exponent thereof;

computing a value J′

such that R*J*J′

≡

1 (mod N);

wherein J denotes the public key chosen by the new user;

sending J′ and

a selected broadcast polynomial B(x) to all stakeholders in an access set;

computing a partial result J′

^Sk(mod N) by each stakeholder, wherein S_k=B(Z′

_k)(0≦

k<

K), Z′

_k denotes the secret key held by each stakeholder;

computing B′

=J′

*Π

_{k=1 to K} J′

^Sk (mod N);

sending B′

to the new user; and

computing a distinctive share B=B′

*r (mod N) as a private key for the new user corresponding to the public key J.

15. The computer program product of claim 14 wherein the shares of the private keys S_i and the private key D bears a mathematically relation Σ

(0≦

i<

K) Si≡

D−

1 (mod λ

(N)), wherein 0≦

i<

K, and K represents the threshold number, wherein λ

(N) is a Carmichael function of two strong primes p and q and N=p*q.

16. The computer program product of claim 15 wherein the quorum private key D correlates with a public key E of the multilateral authorization quorum by a mathematical relation:

E*D≡

1 mod λ

(N).

17. The computer program product of claim 15 wherein a first one of the one or more broadcast polynomials for an access set A_i is mathematically represented as B_Ai(x)=Σ

<sub>(0≦

i<

K)</sub>C_iΠ

<sub>(0≦

j<

M and j∉

Ai)</sub>(Z_i−

Z_j)Π

<sub>(j≠

i and jε

Ai)</sub>(x−

Z_j)(mod λ

(N)) wherein C_i=B_Ai(Z_i)/Π

<sub>(0≦

j<

M ad j≠

i)</sub>(Z_i−

Z_j) (mod λ

(N)/2), where M represents the total number of stakeholders and Z_i represents the secret key of the i-th stakeholder.

18. The computer program product of claim 14 further comprising instructions for verifying that the quorum private key and the shares of the quorum private key held by the threshold number of stakeholders have not been tampered with.

19. The computer program product of claim 18 wherein the instructions for verifying further include:

providing a test value T corresponding to a broadcast polynomial B(x), the test value T being represented by T=t^E (mod N) for the access set, wherein t is a predetermined number and E represents a public key of the multilateral authorization quorum and N is a predetermined integer;

sending T and the broadcast polynomial B(x) to the stakeholders of the access set;

computing a partial result value T^Sk(mod N) by each stakeholder, wherein S_k=B(Z′

_k), and Z′

_k is the secret key held by each stakeholder;

computing a value T′

wherein T′

=T*Π

_{k=1 to K} T^Sk (mod N); and

verifying that T′

=t,

wherein if T′

equals t, the shares of the quorum private key held by the threshold number of stakeholders have not been tampered with.

20. The computer program product of claim 14 further comprising instructions for providing an authorization utilizing the one or more broadcast polynomials and the secret keys held by the stakeholders.

21. The computer program product of claim 20 further comprising instructions for:

selecting at least one of the one or more broadcast polynomials based on the access set for which it was generated; and

conducting one or more threshold cryptographic computations utilizing the at least one of the one or more broadcast polynomials and the secret keys.

22. The computer program product of claim 20, wherein the threshold number of stakeholders in the multilateral authorization quorum collectively generate a collective signature for a message in the computer network utilizing a Guillou-Quisquater public key security system, comprising instructions for:

computing a value R=r^E(mod N) wherein r is a random number between 1 and integer N, and E denotes a public exponent thereof;

computing t=H (M, R)(mod E), wherein M represents the message being signed by the stakeholders and H(M, R) is a one-way hash function;

computing J′

such that J′

*(J_SIGN)^t*r′

^E≡

1 (mod N), wherein r′

is a random number and 1<

r′

<

N and J_SIGN is the public key for the collective signature;

sending J′ and

a selected polynomial B(x) to all stakeholders in a selected access set;

computing a partial result j′

^Sk(mod N) by each stakeholder, wherein S_k=B(Z′

_k)(0≦

k<

K), Z′

_k denotes the secret key held by each stakeholder; and

computing an intermediate value T as T=r*r′

*J′

*Π

_{k=1 to K} J′

^Sk(mod N),

wherein a three-tuple <

M, t, T>

constitutes the collective signature of the threshold number of stakeholders.

23. The computer program product of claim 22 further comprising instructions for verifying the generated collective signature.

24. The computer program product of claim 14 further comprising adding at least one new stakeholder to the multilateral authorization quorum by generating new polynomials for added access sets.

25. The computer program product of claim 24 wherein the instructions for generating includes, for the added access sets, instructions for:

selecting a secret key for the at least one new stakeholder;

reselecting the shares of the quorum private key for all stakeholders to satisfy the condition that, for each access set, D−

1 (mod λ

(N)), wherein D represents the quorum private key and λ

(N) represents a predetermined modulus; and

recalculating the one or more polynomials using the shares of the quorum private key and the selected secret keys.

26. A system for implementing a multilateral authorization quorum in a computer network, the multilateral authorization quorum comprising a total number of stakeholders out of which a threshold number of stakeholders can provide a multilateral authorization, the stakeholders sharing a quorum private key, the system comprising:

a key share management center for determining one or more access sets, each containing the threshold number of stakeholders;

for determining a share of the quorum private key held by each stakeholder in all of the one or more access sets, wherein the shares of the quorum private key held by the stakeholders in any one of the one or more access sets add up to a number directly related to the quorum private key; and

for determining one or more secret keys of the stakeholders for each of the one or more access sets; and

wherein the key share management center contains at least one memory,

wherein the key share management center generates one or more broadcast polynomials for each of the one or more access sets using the shares of the quorum private key and the one or more secret keys thereof,

wherein the threshold number of stakeholders in the multilateral authorization quorum collectively generate a collective signature for a message in the computer network utilizing a Guillou-Quisquater public key security system, the system further comprising means for;

computing a value R=r^E(mod N) wherein r is a random number between 1 and integer N, and E denotes a public exponent thereof;

computing t=H(M, R)(mod E), wherein M represents the message being signed by the stakeholders and H(M, R) is a one-way hash function;

computing J′

such that J′

*(J_SIGN)^t*r′

^E≡

1 (mod N), wherein r′

is a random number and 1<

r′

<

N and J_SIGN is the public key for the collective signature;

sending J′ and

a selected polynomial B(x) to all stakeholders in a selected access set;

computing a partial result J′

^Sk(mod N) by each stakeholder, wherein S_k=B(Z′

_k)(0≦

k<

K), Z′

_k denotes the secret key held by each stakeholder; and

computing an intermediate value T as T=r*r′

*J′

*Π

k=1 to K J′

^Sk(mod N),

wherein a three-tuple <

M, t, T>

constitutes the collective signature of the threshold number of stakeholders.

27. The system of claim 26 wherein the shares of quorum private keys S_i and a quorum private key D bear a mathematical relation Σ

(0≦

i<

K) Si≡

D−

1 (mod λ

(N)), wherein 0≦

i<

K, and K represents the threshold number, wherein λ

(N) is a Carmichael function of two strong primes p and q and N=p*q.

28. The system of claim 27 wherein the quorum private key D correlates with a public key E of the multilateral authorization quorum by a mathematical relation:

E*D≡

1 mod λ

(N).

29. The system of claim 27 wherein a first one of the one or more broadcast polynomials for an access set A_i is mathematically represented as B_Ai(x)=Σ

<sub>(0≦

i<

K)</sub>CiΠ

<sub>(0≦

j<

M and j∉

Ai)</sub>(Z_i−

Z_j)Π

<sub>(j≠

i and jε

Ai)</sub>(x−

Z_j)(mod λ

(N)) wherein C_i=B_Ai(Z_i)/Π

<sub>(0≦

j<

M and j≠

i)</sub>(Z_i−

Z_j)(mod λ

(N)/2), where M represents the total number of stakeholders and Z_i represents the secret key of the i-th stakeholder.

30. The system of claim 27 further comprising means for verifying that the quorum private key and the shares of the quorum private key held by the threshold number of stakeholders have not been tampered with.

31. The system of claim 30 wherein the means for verifying further includes means for:

providing a test value T corresponding to a broadcast polynomial B(x), the test value T being represented by T=t^E(mod N) for the access set, wherein t is a predetermined number and E represents a public key of the multilateral authorization quorum and N is a predetermined integer;

sending T and the broadcast polynomial B(x) to the stakeholders of the access set;

computing a partial result value T^Sk(mod N) by each stakeholder, wherein S_k=B(Z′

_k), and Z′

_k is the secret key held by each stakeholder;

computing a value T′

wherein T′

=T*Π

_{k=1 to K} T^Sk(mod N); and

verifying that T′

=t,

wherein if T′

equals t, the shares of the quorum private key held by the threshold number of stakeholders have not been tampered with.

32. The system of claim 26 further comprising means for providing an authorization utilizing the one or more broadcast polynomials and the secret keys held by the stakeholders.

33. The system of claim 32 further comprising means for:

selecting at least one of the one or more broadcast polynomials based on the access set for which it was generated; and

conducting one or more threshold cryptographic computations utilizing the at least one of the one or more broadcast polynomials and the secret keys.

34. The system of claim 32 wherein the multilateral authorization quorum is used for enrolling a new user in the computer network utilizing a Guillou-Quisquater public key security system, the enrolling requires approvals from the threshold number of stakeholders.

35. The system of claim 34 further comprising means for:

generating, by the new user, a public key J based on one or more predetermined parameters;

computing a value R=r^E(mod N) wherein r is a random number between 1 and integer N, and E denotes a public exponent thereof;

computing a value J′

such that R*J*J′

≡

1 (mod N);

wherein J denotes the public key chosen by the new user;

sending J′ and

a selected broadcast polynomial B(x) to all stakeholders in an access set;

computing a partial result J′

^Sk (mod N) by each stakeholder, wherein S_k=B(Z′

_k) (0≦

k<

K), Z′

_k denotes the secret key held by each stakeholder;

computing B′

=J′

*Π

_{k=1 to K} J′

^Sk (mod N);

sending B′

to the new user; and

computing a distinctive share B=B′

*r (mod N) as a private key for the new user corresponding to the public key J.

36. The system of claim 26 further comprising means for verifying the generated collective signature.

37. The system of claim 26 further comprising means for adding at least one new stakeholder to the multilateral authorization quorum by generating new polynomials for added access sets.

38. The system of claim 37 wherein the means for generating includes, for the added access sets:

selecting a secret key for the at least one new stakeholder;

reselecting the shares of the quorum private key for all stakeholders to satisfy the condition that, for each access set, D−

1 (mod λ

(N)), wherein D represents the quorum private key and λ

(N) represents a predetermined modulus; and

recalculating the one or more polynomials using the shares of the quorum private key and the selected secret keys.

39. A method for implementing a multilateral authorization quorum in a computer network, the multilateral authorization quorum comprising a total number of stakeholders out of which a threshold number of stakeholders can provide a multilateral authorization, the stakeholders sharing a quorum private key, the method comprising:

determining one or more access sets, each containing the threshold number of stakeholders;

determining a share of the quorum private key held by each stakeholder in all of the one or more access sets, wherein the shares of the quorum private key held by the stakeholders in any one of the one or more access sets add up to a number directly related to the quorum private key, wherein the quorum private key is split among the stakeholders of the multilateral authorization quorum, thereby forming the multilateral authorization quorum;

determining one or more secret keys of the stakeholders for each of the one or more access sets; and

generating one or more broadcast polynomials for each of the one or more access sets using the shares of the quorum private key and the one or more secret keys thereof,

wherein the multilateral authorization quorum is used for enrolling a new user in the computer network utilizing a Guillou-Quisquater public key security system, the enrolling requires approvals from the threshold number of stakeholders, the method further comprising;

generating, by the new user, a public key J based on one or more predetermined parameters;

computing a value R=r^E(mod N) wherein r is a random number between 1 and integer N, and E denotes a public exponent thereof;

computing a value J′

such that R*J*J′

≡

1 (mod N);

wherein J denotes the public key chosen by the new user;

sending J′ and

a selected broadcast polynomial B(x) to all stakeholders in an access set;

computing a partial result J′

^Sk(mod N) by each stakeholder, wherein S_k=B(Z′

_k)(0≦

k<

K), Z′

_k denotes the secret key held by each stakeholder;

computing B′

=J′

*Π

_{k=1 to K} J′

^Sk(mod N);

sending B′

to the new user; and

computing a distinctive share B=B′

*r (mod N) as a quorum private key for the new user corresponding to the public key J.

40. A computer program product for implementing a multilateral authorization quorum in a computer network, the multilateral authorization quorum comprising a total number of stakeholders out of which a threshold number of stakeholders can provide a multilateral authorization, the stakeholders sharing a quorum private key, the computer program product stored on a computer-readable medium and comprising instructions for:

determining one or more access sets, each containing the threshold number of stakeholders;

determining a share of the quorum private key held by each stakeholder in all of the one or more access sets, wherein the shares of the quorum private key held by the stakeholders in any one of the one or more access sets add up to a number directly related to the quorum private key, wherein the quorum private key is split among the stakeholders of the multilateral authorization quorum, thereby forming the multilateral authorization quorum;

determining one or more secret keys of the stakeholders for each of the one or more access sets; and

generating one or more broadcast polynomials for each of the one or more access sets using the shares of the quorum private key and the one or more secret keys thereof,

wherein the threshold number of stakeholders in the multilateral authorization quorum collectively generate a collective signature for a message in the computer network utilizing a Guillou-Quisquater public key security system, the computer program product further comprising instructions for;

computing a value R=r^E(mod N) wherein r is a random number between 1 and integer N, and E denotes a public exponent thereof;

computing t=H (M, R) (mod E), wherein M represents the message being signed by the stakeholders and H(M, R) is a one-way hash function;

computing J′

such that J′

*(J_SIGN)^t*r′

^E≡

1 (mod N), wherein r′

is a random number and 1<

r′

<

N and J_SIGN is the public key for the collective signature;

sending J′ and

a selected polynomial B(x) to all stakeholders in a selected access set;

computing a partial result J′

^Sk(mod N) by each stakeholder, wherein S_k=B(Z′

_k)(0≦

k<

K), Z′

_k denotes the secret key held by each stakeholder; and

computing an intermediate value T as T=r*r′

*J′

*Π

_{k=1 to K} J′

^Sk(mod N),

wherein a three-tuple <

M, t, T>

constitutes the collective signature of the threshold number of stakeholders.

41. A system for implementing a multilateral authorization quorum in a computer network, the multilateral authorization quorum comprising a total number of stakeholders out of which a threshold number of stakeholders can provide a multilateral authorization, the stakeholders sharing a quorum private key, the system comprising:

a key share management center for determining one or more access sets, each containing the threshold number of stakeholders;

for determining a share of the quorum private key held by each stakeholder in all of the one or more access sets, wherein the shares of the quorum private key held by the stakeholders in any one of the one or more access sets add up to a number directly related to the quorum private key; and

for determining one or more secret keys of the stakeholders for each of the one or more access sets; and

wherein the key share management center contains at least one memory,

wherein the key share management center generates one or more broadcast polynomials for each of the one or more access sets using the shares of the quorum private key and the one or more secret keys thereof,

wherein the multilateral authorization quorum is used for enrolling a new user in the computer network utilizing a Guillou-Quisquater public key security system, the enrolling requires approvals from the threshold number of stakeholders, the system further comprising means for;

generating, by the new user, a public key J based on one or more predetermined parameters;

computing a value R=r^E(mod N) wherein r is a random number between 1 and integer N, and E denotes a public exponent thereof;

computing a value J′

such that R*J*J′

≡

1 (mod N);

wherein J denotes the public key chosen by the new user;

sending J′ and

a selected broadcast polynomial B(x) to all stakeholders in an access set;

computing a partial result J′

^Sk(mod N) by each stakeholder, wherein S_k=B(Z′

_k)(0≦

k<

K), Z′

_k denotes the secret key held by each stakeholder;

computing B′

=J′

*Π

k=1 to K J′

^Sk(mod N);

sending B′

to the new user; and

computing a distinctive share B=B′

*r (mod N) as a private key for the new user corresponding to the public key J.