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

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)=Σ (0≦i<K) C i Π (0≦j<M and j∉Ai) (Z i −Z j )Π (j≠i and jεAi) (x−Z j )(mod λ(N)) wherein C i =B Ai (Z i )/Π (0≦j<M and j≠i) (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′*Π 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.

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)=Σ (0≦i<K) C i Π (0≦j<M and j∉Ai) (Z i −Z j )Π (j≠i and jεAi) (x−Z j )(mod λ(N)) wherein C i =B Ai (Z i )/Π (0≦j<M ad j≠i) (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)=Σ (0≦i<K) CiΠ (0≦j<M and j∉Ai) (Z i −Z j )Π (j≠i and jεAi) (x−Z j )(mod λ(N)) wherein C i =B Ai (Z i )/Π (0≦j<M and j≠i) (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.