Efficient hybrid public key signature scheme

• US 6,701,434 B1
• Filed: 05/07/1999
• Issued: 03/02/2004
• Est. Priority Date: 05/07/1999
• Status: Active Grant

• Current Assignee: eBay Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Rohatgi, Pankaj
• Primary Examiner(s): Jean, Frantz B.
• Assistant Examiner(s): Arani, Taghi T
• Application Number:
  US09/307,493
• Time in Patent Office: 1,761 Days
• Field of Search: 380/277, 380/28, 380/30, 380/46, 713/168, 713/177, 713/170, 713/156, 713/179, 705/37
• US Class Current: 713/168
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823

Abstract

Methods, apparatus and computer products provide solutions to the problem caused by the slow speed of public key signature algorithms. The solutions also solve problems of packet authentication for multicast and other scenarios requiring fast, compact digital signatures. Security guarantees required for packet authentication are provided in a way that can handle multiple independent flows, produces authentication fields of fixed size, works in the fully unreliable setting, does not require any packet delays and has the additional property of being able to withstand and smooth over irregular processor loading and bursty packet output rate. One aspect of the present invention uses a hybrid approach consisting of the signer creating a certificate for the public key of an efficient k-time signature scheme using a regular signature key. The signer then signing up to k messages with the private key corresponding to k-time public key. The time consumed to compute a public key signature is amortized over k signatures. These and other aspects are provided in a signature scheme wherein a commitment is employed.

Claims

1. A method for generating a signature for a message, the method comprising:

employing a public/private key pair in which the private key includes at least one enhancing key and the public key includes a TCR commitment to said at least one enhancing key;

obtaining an opening string,

opening the TCR-commitment to said enhancing key with the opening string,

forming a function of the message and the private key, and

forming a signature comprising the function and the opening string.

2. A method as recited in claim 1, wherein the opening string includes the enhancing key.

3. A method as recited in claim 1, further comprising combining the signature with the message to form a signed message.

4. A method as recited in claim 3, wherein the step of combining comprises including the message in the signature.

5. A method as recited in claim 1, wherein the signed message includes a certificate.

11. A method as recited in claim 1, wherein the TCR-commitment is a regular-commitment.

12. A method as recited in claim 1 further comprising employing the signature in a commitment based signature scheme.

13. A method as recited in claim 12, wherein the step of employing the commitment based signature scheme is implemented for a 36-time key pair embodiment.

14. A method as recited in claim 12, wherein the step of employing includes using cryptographic primitives having more than 80 bit security.

15. A method as recited in claim 12, wherein the step of employing includes using a SHA-1 hash algorithm.

16. A method as recited in claim 12, further comprising the step of verifying a purported signature.

19. A method as recited in claim 16, further comprising combining the signature with the internal message to form a signed message.

20. A method as recited in claim 19, wherein the signed message includes a certificate.

70. A method as recited in claim 1, further comprising steps of a 36-time signature scheme.

6. A method comprising:

receiving a signed message having an internal message, a signature, and a commitment opening string, and

authenticating the internal message employing a public key from a public/private key pair in which the public key includes a TCR-commitment to an enhancing key and the private key includes at least one enhancing key.

7. A method as recited in claim 6, further including the step of extracting the internal message from the signed message.

8. A method as recited in claim 7, which further includes the step of extracting the opening string from the signed message and verifying the validity of the opening string with respect of the TCR-commitment made to an enhancing string in the public key.

9. A method as recited in claim 8, further comprising verifying validity of the opening string with respect to the TCR-commitment by a computing function using a certificate for the public key.

10. A method as recited in claim 6, further comprising the step of extracting the signature from the signed message.

17. A method for generating a signature for an internal message, the method comprising:

employing a private key which includes at least one enhancing key and which is paired with a public key which includes a commitment to said enhancing key;

opening the commitment to said enhancing key and obtaining an opening string,

forming a function of the internal message and the private key, and

forming the signature comprising the function and the opening string.

18. A method as recited in claim 17, wherein the opening string includes the enhancing key.

21. A method for a signer to generate key pairs for a signature scheme, the method comprising:

generating k 1-time key pairs;

constructing an authentication tree based on a collision resistant hash function using the k, 1-time public keys of the key pairs thus generated to form a k-time public key; and

signing a root of the tree with a long-term signature key to form a certificate for the k-time key pair,

wherein it least one of the k 1-time key pairs includes an embedded commitment.

22. A method as recited in claim 21, wherein the long-term signature key is a key certified by a certification authority.

23. A method as recited in claim 21, where the step of generating employs a Lamport scheme.

24. A method as recited in claim 21, wherein the step of constructing includes forming a binary tree with the k 1-time public keys at leaves of the tree, and giving each interior node in the tree values which are collision resistant hashes of children nodes of said each interior node.

25. A method as recited in claim 24, wherein the collision resistant hashes employ SHA-1.

26. A method to generate k-time key pairs for a signature scheme, the method comprising:

generating k 1-time key pairs;

constructing an TCR authentication tree based on a target collision resistant hash function using k 1-time public keys of the key pairs thus generated to form a k-time public key; and

signing a root of the tree combined with TCR-keys used to build the TCR tree, with a long-term signature key of a signer to form a certificate for at least one of the k-time key pairs.

27. A method as recited in claim 26, wherein the step of generating includes k 1-time key pairs that have a public key with an embedded commitment to an enhancing key, and have a private key which includes an enhancing key.

28. A method as recited in claim 26, further comprising storing the generated key pairs and each certificate.

29. A method as recited in claim 26, further comprising storing the TCR tree.

30. A method as recited in claim 26, further comprising storing intermediate values obtained during the step of generating.

31. A method as recited in claim 26, wherein each certificate formed in the step of signing forms a signature and the signature includes information being signed by the signature.

32. A method as recited in claim 31, further comprising extracting the information from the signature.

33. A method as recited in claim 31, further comprising verifying the signature.

34. A method for signing at least one arbitrary message, employing a k-time key pair generated as recited in claim 27, the method of signing comprising:

choosing a unique key pair taken from said 1-time key pairs;

computing a TCR hash function of said at least one arbitrary message using the enhancing key corresponding to the unique 1-time key;

computing a 1-time signature on an output of said TCR hash function;

a commitment opening string to the commitment included within a public key of the unique 1-time key; and

forming a signature comprised of the 1-time signature, the commitment opening string.

35. A method as recited in claim 34, further comprising the step of creating ancillary information for identifying and authenticating the unique 1-time public key within the certificate for the k-time public key;

and

including said ancillary information in the signature.

36. A method for verifying a signature on an arbitrary message, wherein the signature is formed according to method recited in claim 34, the method of verifying comprising:

obtaining a authentic copy of the 1-time public key associated with said signature;

extracting the commitment opening string from said signature;

deriving the enhancing key using the commitment opening string;

computing a TCR hash function for the arbitrary message using said enhancing key;

verifying the commitment opening string with respect to the commitment embedded in the 1-time public key; and

verifying the 1-time signature which signed an output of said TCR hash function with respect to the 1-time public key.

37. A method as recited in claim 36, wherein the step of deriving the enhancing key from the commitment opening string includes applying an identity transformation to the commitment opening string.

38. A method as recited in claim 35, wherein the step of verifying the commitment opening string includes computing a function on the 1-time public key and the commitment opening string.

39. A method as recited in claim 35, wherein the step of verifying the 1-time signature includes applying a function on the 1-time signature on said output of the TCR hash function and on said 1-time public key.

40. A method for verifying a signature on an arbitrary message, wherein the signature is formed according to the method recited in claim 35, the method for verifying comprising:

obtaining a certificate for the k-time public key associated with said signature;

verifying the certificate using a long term public key of the signer to authenticate the k-time public key;

extracting the commitment opening string from said signature and using the opening string to derive the enhancing key;

computing a TCR hash function on said message using said enhancing key;

verifying the commitment opening string with respect to a commitment embedded in one of the 1-time public keys within the k-time public key;

verifying the 1-time signature on a output of said TCR hash function with respect to one of the 1-time public keys embedded within the k-time public key; and

validating the ancillary information with respect to the authenticated k-time public key to authenticate the 1-time public key associated with said signature.

41. A method as recited in claim 40, wherein the step of verifying the certificate is performed only once for k uses of the k-time key.

42. A method as recited in claim 39, wherein the step of validating the ancillary information includes the step of partially reconstructing the TCR-tree used to create the k-time public key.

43. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing generation of a signature for a message, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

employing a public/private key pair in which the private key includes at least one enhancing key and the public key includes a TCR commitment to said at least one enhancing key;

obtaining an opening string,

opening the TCR-commitment to said enhancing key with the opening string,

forming a function of the message and the private key, and

forming a signature comprising the function and the opening string.

44. An article of manufacture as recited in claim 43, wherein the opening string includes the enhancing key.

45. An article of manufacture as recited in claim 43, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect combining the signature with the message to form a signed message.

46. An article of manufacture as recited in claim 45, wherein the step of combining comprises including the message in the signature.

47. An article of manufacture as recited in claim 43, wherein the signed message includes a certificate.

48. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

receiving a signed message having an internal message, a signature, and a commitment opening string, and

authenticating the internal message employing a public key from a public/private key pair in which the public key includes a TCR-commitment to an enhancing key and the private key includes at least one enhancing key.

49. An article of manufacture as recited in claim 48, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect extracting the internal message from the signed message.

50. An article of manufacture as recited in claim 49, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect extracting the opening string from the signed message and verifying the validity of the opening string with respect of the TCR-commitment made to an enhancing string in the public key.

51. An article of manufacture as recited in claim 50, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect verifying validity of the opening string with respect to the TCR-commitment by a computing function using a certificate for the public key.

52. An article of manufacture as recited in claim 48, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect the step of extracting the signature from the signed message.

53. An article of manufacture as recited in claim 51, wherein the TCR-commitment is a regular commitment.

54. An article of manufacture as recited in claim 51, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect employing the signature in an enhanced commitment based signature scheme.

55. An article of manufacture as recited in claim 51, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect verifying a purported signature.

56. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a generation of a signature for an internal message, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect:

generating a signature for an internal message employing a private key which includes at least one enhancing key and which is paired with a public key which includes a commitment to said enhancing key;

opening the commitment to said enhancing key and obtaining an opening string;

forming a function of the internal message and the private key; and

forming the signature comprising the function and the opening string.

57. A computer program product as recited in claim 56, wherein the opening string includes the enhancing key.

58. A computer program product as recited in claim 56, the computer readable program code means in said computer program product further comprising computer readable program code means for causing a computer to effect combining the signature with the internal message to form a signed message.

59. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for a signer to generate key pairs for a signature scheme, said method steps comprising:

generating k 1-time key pairs;

constructing an authentication tree based on a collision resistant hash function using the k, 1-time public keys of the key pairs thus generated to form a k-time public key; and

signing a root of the tree with a long-term signature key to form a certificate for the k-time key pair;

wherein at least one of the k 1-time key pairs includes an embedded commitment.

60. A program storage device readable by machine as recited in claim 59, wherein the step of generating employs a Merkle scheme.

61. A program storage device readable by machine as recited in claim 59, wherein the step of constructing includes forming a binary tree with the k 1-time public keys at leaves of the tree, and giving each interior node in the tree values which are collision resistant hashes of children nodes of said each interior node.

71. A program storage device readable by machine as recited in claim 61, wherein the collision resistant hashes employ MD-5.

62. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for generating k-time key pairs for a signature scheme, said method steps comprising:

generating k 1-time key pairs;

constructing an TCR authentication tree based on a target collision resistant hash function using k 1-time public keys of the key pairs thus generated to form a k-time public key; and

signing a root of the tree combined with TCR-keys used to build the TCR tree, with a long-term signature key of a signer to form a certificate for at least one of the k-time key pairs.

63. A program storage device readable by machine as recited in claim 62, wherein the step of generating includes k 1-time key pairs that have a public key with an embedded commitment to an enhancing key, and have a private key which includes an enhancing key.

64. A program storage device readable by machine as recited in claim 62, said method steps further comprising storing the generated key pairs and each certificate.

65. A program storage device readable by machine as recited in claim 62, said method steps further comprising storing intermediate values obtained during the step of generating.

66. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for signing at least one arbitrary message,

employing a k-time key pair generated as recited in claim 63, said method steps for signing comprising:

choosing a unique key pair taken from said 1-time key pairs;

computing a TCR hash function of said at least one arbitrary message using the enhancing key corresponding to the unique 1-time key;

computing a 1-time signature on an output of said TCR hash function;

computing a commitment opening string to the commitment included within a public key of the unique 1-time key; and

forming a signature comprised of the 1-time signature, the commitment opening string.

67. A program storage device readable by machine as recited in claim 66, said method steps further comprising the steps of creating ancillary information for identifying and authenticating the unique 1-time public key within the certificate for the k-time public key;

and

including the ancillary information in the signature.

68. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for verifying a signature on an arbitrary message, wherein the signature is formed according to method recited in claim 66, said method steps for verifying comprising:

obtaining a authentic copy of the 1-time public key associated with said signature;

extracting the commitment opening string from said signature;

deriving the enhancing key using the commitment opening string;

computing a TCR hash function for the arbitrary message using said enhancing key;

verifying the commitment opening string with respect to the commitment embedded in the 1-time public key; and

verifying the 1-time signature which signed an output of said TCR hash function with respect to the 1-time public key.

69. A program storage device readable by machine as recited in claim 62, wherein the signature scheme is a 36-time signature scheme.