Optimal-resilience, proactive, public-key cryptographic system and method

• US 6,035,041 A
• Filed: 04/28/1997
• Issued: 03/07/2000
• Est. Priority Date: 04/28/1997
• Status: Expired due to Term

• Current Assignee: Certco
• Original Assignee: Certco
• Inventors: Frankel, Yair, Yung, Marcel M.
• Primary Examiner(s): Laufer, Pinchus M.
• Application Number:
  US08/842,080
• Time in Patent Office: 1,044 Days
• Field of Search: 380/21, 380/30, 380/45, 380/49, 380/25, 380/28, 380/29
• US Class Current: 380/30
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• 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/3247 involving digital signatures

Abstract

Proactive robust threshold schemes are presented for general "homomorphic-type" public key systems, as well as optimized systems for the RSA function. Proactive security employs dynamic memory refreshing and enables us to tolerate a "mobile adversary" that dynamically corrupts the components of the systems (perhaps all of them) as long as the number of corruptions (faults) is bounded within a time period. The systems are optimal-resilience. Namely they withstand any corruption of minority of servers at any time-period by an active (malicious) adversary (i.e., any subset less than half. Also disclosed are general optimal-resilience public key systems which are "robust threshold" schemes (against stationary adversary), and are extended to "proactive" systems (against the mobile one). The added advantage of proactivization in practical situations is the fact that, in a long-lived threshold system, an adversary has a long time (e.g., years) to break into any t out of the l servers. In contrast, the adversary in a proactive systems has only a short period of time (e.g., a week) to break into any t servers. The model of mobile adversary seems to be crucial to such "long-lived" systems that are expected to span the secure network and electronic commerce infrastructure.

Claims

1. A method of providing a cryptographic service comprising the steps of:

selecting a first function having properties useful for providing the cryptographic service;

re-expressing the first function as a first plurality of alternate functions;

distributing the first plurality of alternate functions to a plurality of distinct, electronic, cryptographic processing apparatus;

during a first operational period, (i) at each of a selected set of cryptographic processing apparatus, electronically applying at least one of the first plurality of alternate functions to a first input message to obtain first partial results, and (ii) combining first partial results to obtain a first final electronic output associated with the input message, said output-being identical to the output that would have been obtained by applying the first function to the input message;

during an update period, (i) generating a second plurality of alternate functions that re-express the first function, and (ii) distributing the second plurality of alternate functions to distinct cryptographic processing apparatus; and

during a second operational period, (i) at each of a selected set of cryptographic processing apparatus, electronically applying at least one of the second plurality of alternate functions to a second input message to obtain second partial results, and (ii) combining second partial results to obtain a second final electronic output associated with the input message, said second output being identical to the output that would have been obtained by applying the first function to the second input message.

2. The method of claim 1 wherein the first function is an RSA function.

3. The method of claim 2 wherein the private key for the RSA function is over a subset of the integers.

4. The method of claim 1 wherein the first function is a cryptographic function having a key drawn from a group for which neither the order nor a multiple of the order is publicly known.

5. The method of claim 1 wherein the first function has a property of share translation.

6. The method of claim 1 wherein the first function has an associated share space and a property that inverses can be computed in the share space.

7. The method of claim 1 wherein the first function has an associated share space and a property that the share space is simulatable.

8. The method of claim 1 wherein each function of the first plurality of alternate functions is based on a generator over a finite field.

9. The method of claim 1 wherein each function of the first plurality of alternate functions is an exponentiation function.

10. The method of claim 1 wherein each function of a plurality of alternate functions is defined over a ring.

11. The method of claim 1 wherein each function of a plurality of alternate functions is defined over a group.

12. The method of claim 1 wherein each function of a plurality of alternate functions is defined over a subset of the integers.

13. The method of claim 1 wherein:

the first function is a cryptographic function having a key; and

the first function has a property that an inverse of the key cannot be computed practicably with publicly known information.

14. The method of claim 1 wherein the cryptographic service is a digital signature service.

15. The method of claim 1 wherein the cryptographic service is an encryption service.

16. The method of claim 1 wherein the cryptographic service is a decryption service.

17. The method of claim 1 wherein the cryptographic service is an authentication service.

18. The method of claim 1 wherein the step of generating a second plurality of alternate functions includes a step of re-expressing at least some of the first plurality of alternate functions as the second plurality of alternate functions.

19. The method of claim 1 wherein the step of generating a second plurality of alternate functions includes a step of rendering the set of cryptographic processing apparatus incapable of applying the first plurality of alternate functions.

20. The method of claim 1 wherein the step of re-expressing the first function as a first plurality of alternate functions includes a step of re-expressing the first function in the form of a t-of-l system, in which l is a number of cryptographic processing apparatus configured to provide partial results, and t is a minimum number of partial results needed to generate a final result that is the same result as would have been obtained by applying the first function to an input message.

21. The method of claim 20 wherein the number l is greater than the number t.

22. The method of claim 20 wherein the step generating a second plurality of alternate functions that re-expresses the first function includes a step of generating re-expression of the first function as a t'"'"' of l'"'"' system, in which l'"'"' is a number of cryptographic processing apparatus configured to provide partial results, and t'"'"' is a minimum number of partial results needed to generate a final result that is the same result as would have been obtained by applying the first function to an input message.

23. The method of claim 22 wherein the number l'"'"' is greater than the number t'"'"'.

24. The method of claim 22 wherein the number t'"'"' is not equal to the number t.

25. The method of claim of claim 22 wherein the number l'"'"' is not equal to the number l.

26. The method of claim 1 wherein the step of generating a second plurality of alternate functions that re-express the first function includes steps of:

re-expressing at least some of the first plurality of alternate functions in the form of a t'"'"'-of-t'"'"' system, and

re-expressing the t'"'"'-of-t'"'"' system in the form of the second plurality of alternate functions.

27. The method of claim 26 wherein the step of re-expressing at least some of the first plurality of alternate functions in the form of t'"'"'-of-t'"'"' system includes steps of:

(1) selecting a number, t'"'"', of cryptographic apparatus, and

(2) communicating information among the t'"'"' cryptographic processing apparatus using a protocol, such that any of the t'"'"' cryptographic apparatus, acting either singly or in concert, can detect whether another of the t'"'"' cromptographic processing apparatus is acting in violation of the protocol.

28. The method of claim 1 wherein any minority of the plurality of apparatus may malfunction arbitrarily.

29. A method of providing a public-key cryptographic service comprising the steps of:

selecting an RSA function having associated public and private keys;

re-expressing the RSA function as a first plurality of alternate functions;

distributing the first plurality of alternate functions to a plurality of distinct, electronic, cryptographic processing apparatus;

during a first operational period, (i) at each of a selected set of cryptographic processing apparatus, electronically applying at least one of the first plurality of alternate functions to a first input message to obtain first partial results, and (ii) combining first partial results to obtain a first final electronic output associated with the first input message, said first output being identical to the output that would have been obtained by applying the RSA function to the first input message;

during an update period, updating the plurality of distinct cryptographic processing apparatus by (i) generating a second plurality of alternate functions that re-express the RSA function, and (ii) distributing the second plurality of alternate functions to distinct cryptographic processing apparatus; and

during a second operational period, (i) at each of a selected set of cryptographic processing apparatus, electronically applying at least one of the second plurality of alternate functions to a second input message to obtain second partial results, and (ii) combining second partial results to obtain a second final electronic output associated with the second input message, said second output being identical to the output that-would have been obtained by applying the RSA function to the second input message.

30. The method of claim 29 wherein the private key for the RSA function is over a subset of the integers.

31. The method of claim 29 wherein each function of the first plurality of alternate functions employs a generator.

32. The method of claim 29 wherein each function of the first plurality of alternate functions is an exponentiation function.

33. The method of claim 29 wherein each function of a plurality of alternate functions is defined over a ring.

34. The method of claim 29 wherein each function of a plurality of alternate functions is defined over a group.

35. The method of claim 29 wherein each function of a plurality of alternate functions is defined over a subset of the integers.

36. The method of claim 29 wherein the step of generating a second plurality of alternate functions includes a step of re-expressing at least some of the first plurality of alternate functions as the second plurality of alternate functions.

37. The method of claim 29 wherein the step of generating a second plurality of alternate functions includes a step of rendering the set of cryptographic processing apparatus incapable of applying the first plurality of alternate functions.

38. The method of claim 29 wherein the step of re-expressing the first function as a first plurality of alternate functions includes a step of re-expressing the first function in the form of a t-of-l system, in which l is a number of cryptographic processing apparatus configured to provide partial results, and t is a minimum number of partial results needed to generate a final result that is the same result as would have been obtained by applying the first function to an input message.

39. The method of claim 38 wherein the number l is greater than the number t.

40. The method of claim 38 wherein the step generating a second plurality of alternate functions that re-expresses the first function includes a step of generating re-expression of the first function as a t'"'"' of l'"'"' system, in which l'"'"' is a number of cryptographic processing apparatus configured to provide partial results, and t'"'"' is a minimum number of partial results needed to generate a final result that is the same result as would have been obtained by applying the first function to an input message.

41. The method of claim 40 wherein the number l'"'"' is greater than the number t'"'"'.

42. The method of claim 40 wherein the number t'"'"' is not equal to the number t.

43. The method of claim of claim 40 wherein the number l'"'"' is not equal to the number l.

44. The method of claim 29 wherein the step of generating a second plurality of alternate functions that re-express the first function includes steps of:

re-expressing at least some of the first plurality of alternate functions in the form of a t'"'"'-of-t'"'"' system, and

re-expressing the t'"'"'-of-t'"'"' system in the form of the second plurality of alternate functions.

45. The method of claim 44 wherein the step of re-expressing at least some of the first plurality of alternate functions in the form of a t'"'"'-of-t'"'"' system includes steps of:

(1) selecting a subset number, t'"'"', of cryptographic processing apparatus, and

(2) communicating information among the t'"'"' cryptographic processing apparatus using a protocol, such that any of the t'"'"' cryptographic processing apparatus, acting either singly or in concert, can detect whether another of the t'"'"' cryptographic processing apparatus is acting in violation of the protocol.

46. The method of claim 29 wherein any minority of the plurality of apparatus may malfunction arbitrarily.

47. A method of providing a cryptographic service comprising the steps of:

selecting a first relation, said relation having properties useful for providing a cryptographic service, in connection with a public key and a private key drawn from a domain for which neither the order nor a multiple of the order is publicly known;

re-expressing the first relation as a first plurality of alternate relations;

distributing the first plurality of alternate relations to a plurality of distinct, electronic, cryptographic processing apparatus;

during a first operational period, (i) at each of a selected set of cryptographic processing apparatus, electronically applying at least one of the first plurality of alternate relations to a first input message to obtain first partial results, and (ii) combining first partial results to obtain a first final electronic output associated with the input message, said first output being a legitimate result that can be processed using one of said public and private keys as if it had been obtained by applying the first relation to the first input message;

during an update period, updating the plurality of distinct cryptographic processing apparatus by (i) generating a second plurality of alternate relations that re-express the first relation, and (ii) distributing the second plurality of alternate relations to distinct cryptographic processing apparatus; and

during a second operational period, (i) at each of a selected set of cryptographic processing apparatus, electronically applying at least one of the second plurality of alternate relations to a second input message to obtain second partial results, and (ii) combining second partial results to obtain a second final electronic output associated with the second input message, said second output being a legitimate result that can be processed using one of said public and private keys as if it had been obtained by applying the first relation to the second input message.

48. The method of claim 47 wherein the first relation has a property of share translation.

49. The method of claim 47 wherein the first relation has an associated share space and a property that inverses can be computed in the share space.

50. The method of claim 47 wherein the first relation has an associated share space and a property that the share space is simulatable.

51. The method of claim 47 wherein each relation of the first plurality of alternate relations is based on a generator over a finite field.

52. The method of claim 47 wherein each relation of the first plurality of alternate relations is an exponentiation relation.

53. The method of claim 47 wherein each relation of a plurality of alternate relations is defined over a ring.

54. The method of claim 47 wherein each relation of a plurality of alternate relations is defined over a group.

55. The method of claim 47 wherein each relation of a plurality of alternate relations is defined over a subset of the integers.

56. The method of claim 47 wherein:

the first relation is a cryptographic relation having a key; and

the first relation has a property that an inverse of the key cannot be computed practicably with publicly known information.

57. The method of claim 47 wherein the cryptographic service is a digital signature service.

58. The method of claim 47 wherein the cryptographic service is an encryption service.

59. The method of claim 47 wherein the cryptographic service is a decryption service.

60. The method of claim 47 wherein the cryptographic service is an authentication service.

61. The method of claim 47 wherein the step of generating a second plurality of alternate relations includes a step of re-expressing at least some of the first plurality of alternate relations as the second plurality of alternate relations.

62. The method of claim 47 wherein the step of generating a second plurality of alternate relations includes a step of rendering the set of cryptographic processing apparatus incapable of applying the first plurality of alternate relations.

63. The method of claim 47 wherein the step of re-expressing the first relation as a first plurality of alternate relations includes a step of re-expressing the first relation in the form of a t-of-l system, in which l is a number of cryptographic processing apparatus configured to provide partial results, and t is a minimum number of partial results needed to generate a final result.

64. The method of claim 63 wherein the number l is greater than the number t.

65. The method of claim 63 wherein the step of generating a second plurality of alternate relations that re-expresses the first relation includes a step of generating re-expression of the first relation as a t'"'"' of l'"'"' system, in which l'"'"' is a number of cryptographic processing apparatus configured to provide partial results, and t'"'"' is a minimum number of partial results needed to generate a final result that is the same result as would have been obtained by applying the first relation to an input message.

66. The method of claim 65 wherein the number l'"'"' is greater than the number t'"'"'.

67. The method of claim 65 wherein the number t'"'"' is not equal to the number t.

68. The method of claim of claim 65 wherein the number l'"'"' is not equal to the number l.

69. The method of claim 47 wherein the step of generating a second plurality of alternate relations that re-express the first relation includes steps of:

re-expressing at least some of the first plurality of alternate relations in the form of a t'"'"'-of-t'"'"' system, and

re-expressing the t'"'"'-of-t'"'"' system in the form of the second plurality of alternate relations.

70. The method of claim 69 wherein the step of re-expressing at least some of the first plurality of alternate relations in the form of a t'"'"'-of-t'"'"' system includes steps of:

(1) selecting a subset number, t'"'"', of cryptographic processing apparatus, and

(2) communicating information among a subset number t'"'"' of cryptographic processing apparatus using a protocol, such that any of the t'"'"' cryptographic processing apparatus, acting either singly or in concert, can detect whether another of the t'"'"' crytographic processing apparatus is acting in violation of the protocol.

71. The method of claim 47 wherein any minority of the plurality of apparatus may malfunction arbitrarily.