US5907618A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for verifiably providing key recovery information in a cryptographic system
Assignee: International Business Machines Corp
•
Filing: 1997-01-03
•
Granted: 1999-05-25
•
Expires: 2017-01-03
Abstract
Abstract A method and apparatus for verifiably providing key recovery information to one or more trustees in a cryptographic communication system having a sender and a receiver Each communicating party has its own Diffie-Hellman key pair comprising a secret value and corresponding public value, as does each trustee The sender non-interactively generates from its own secret value and the public value held by the receiver a first shared Diffie-Hellman key pair comprising a first shared secret value, shared with the receiver but not with any trustee, and a corresponding public value. For each trustee, the sender then non-interactively generates an additional shared secret value, shared with the receiver and the trustee, from the first shared secret value and the public value corresponding to the secret value held by the trustee. The sender uses the additional shared secret value to encrypt recovery information for each trustee, which is transmitted to the receiver along with the encrypted message. Each trustee can decrypt its recovery information by regenerating its additional shared secret value from its own secret value and the public value of the first shared Diffie-Hellman key pair. The receiver can verify the correctness of the recovery information for each trustee by decrypting the information using the additional shared secret value for that trustee, without having to recreate the recovery information or perform computationally expensive public key operations.
Inventors
- 👤 Rosario Gennaro
- 👤 Paul Ashley Karger
- 👤 Stephen Michael Matyas, Jr.
- 👤 Mohammad Peyravian
- 👤 David Robert Safford
- 👤 Nevenko Zunic
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 12:59
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/08; H04L9/0816; H04L9/0838; H04L9/0841; H04L9/0894
Claims Analysis
Total Claims: 65
Claim 1
Independent Claim
194 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee, said trustee holding a secret value from which a corresponding public value is generated, a method for making said recovery information available to said trustee, wherein said sender performs the steps of: generating a first shared public value from said first shared secret value; generating an additional shared secret value from said first shared secret value and the public value generated from the secret value held by said trustee, encrypting said recovery information using said additional shared secret value generated for said trustee; and transmitting said encrypted recovery information to said receiver via said communications channel, said trustee being able to decrypt said recovery information by regenerating said additional shared secret value from said first shared public value and the secret value held by said trustee.
Claim 2
Dependent Claim
194 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee, said trustee holding a secret value from which a corresponding public value is generated, a method for making said recovery information available to said trustee, wherein said sender performs the steps of: generating a first shared public value from said first shared secret value; generating an additional shared secret value from said first shared secret value and the public value generated from the secret value held by said trustee, encrypting said recovery information using said additional shared secret value generated for said trustee; and transmitting said encrypted recovery information to said receiver via said communications channel, said trustee being able to decrypt said recovery information by regenerating said additional shared secret value from said first shared public value and the secret value held by said trustee.
Claim 3
Dependent Claim
14 words
The method of claim 1 in which said encryption key is a session key.
Claim 4
Dependent Claim
51 words
The method of claim 1 in which said sender and said receiver hold respective secret values from which corresponding public values are generated, said first shared secret value being generated from said secret value held by said sender and the public value generated from the secret value held by said receiver.
Claim 5
Dependent Claim
47 words
The method of claim 3 in which said first shared secret value is generated as: u=g.sup.xy mod p, where x is the secret value held by said sender, y is the secret value held by said receiver, p is a prime modulus, and g is a generator.
Claim 6
Dependent Claim
25 words
The method of claim 1 in which said sender performs the further step of: transmitting said encrypted data to said receiver via said communications channel.
Claim 7
Dependent Claim
27 words
The method of claim 1 in which said sender performs the further step of: transmitting said first shared public value to said receiver via said communications channel.
Claim 8
Dependent Claim
37 words
The method of claim 1 in which said first shared public value is generated as g u mod p, where u is said first shared secret value, p is a prime modulus, and g is a generator.
Claim 9
Dependent Claim
45 words
The method of claim 7 in which said additional shared secret value is generated as v=g.sup.au mod p, where a is the secret value held by said trustee, u is said first shared secret value, p is said prime modulus, and g is said generator.
Claim 10
Dependent Claim
14 words
The method of claim 1 in which said recovery information comprises said encryption key.
Claim 11
Dependent Claim
56 words
The method of claim 1 in which said system has a plurality of trustees, each of which is provided with recovery information and holds a secret value from which a corresponding public value is generated, said steps of generating an additional shared secret value and encrypting said recovery information being performed for each of said trustees.
Claim 12
Dependent Claim
36 words
The method of claim 10 in which said encryption key is split into shares that may be combined to regenerate said encryption key, each of said trustees being provided one of said shares as recovery information.
Claim 13
Dependent Claim
23 words
The method of claim 1 in which said system has one or more trustees for each of a plurality of key recovery jurisdictions.
Claim 14
Dependent Claim
48 words
The method of claim 1 in which said recovery information is generated independently of said encryption key, said sender performing the further steps of: generating additional recovery information as a function of said encryption key; and transmitting said additional recovery information to said receiver via said communications channel.
Claim 15
Dependent Claim
40 words
The method of claim 1 in which said sender performs the further steps of: encrypting said encryption key using a key-encrypting key generated from said recovery information; and transmitting said encrypted encryption key to said receiver via said communications channel.
Claim 16
Dependent Claim
45 words
The method of claim 14 in which said encryption key is one of a plurality of encryption keys, each of which has a corresponding key-encrypting key that is generated as a function of said recovery information and information that is specific to the encryption key.
Claim 17
Dependent Claim
40 words
The method of claim 14 in which said system has a plurality of trustees, each of which is provided with recovery information from which a different key-encrypting key is generated, said encryption key being multiply encrypted with said key-encrypting keys.
Claim 18
Dependent Claim
56 words
The method of claim 1 in which said receiver performs the steps of: receiving said encrypted recovery information; generating said additional shared secret value from said first shared secret value and said public value generated from said secret value held by said trustee; and decrypting said encrypted recovery information using a said additional shared secret value.
Claim 19
Dependent Claim
45 words
The method of claim 17 in which said sender performs the further step of transmitting said encrypted data to said receiver via said communications channel, said receiver performing the further steps of: receiving said encrypted data; and decrypting said encrypted data using said encryption key.
Claim 20
Dependent Claim
17 words
The method of claim 18 in which said receiver obtains said encryption key using said recovery information.
Claim 21
Dependent Claim
44 words
The method of claim 18 in which said step of decrypting said encrypted data comprises the steps of: determining whether said encrypted recovery information was correctly decrypted; and decrypting said encrypted data only if it is determined that said recovery information was correctly encrypted.
Claim 22
Dependent Claim
37 words
The method of claim 20 in which said encrypted recovery information includes a message authentication code, said step of determining whether said encrypted recovery information was correctly decrypted comprising the step of testing said message authentication code.
Claim 23
Dependent Claim
51 words
The method of claim 1 in which said trustee performs the steps of: receiving said encrypted recovery information; generating said additional shared secret value from said first shared public value and said secret value held by said trustee; and decrypting said encrypted recovery information using said regenerated additional shared secret value.
Claim 24
Dependent Claim
19 words
The method of claim 1 in which said recovery information comprises non-key-specific recovery information usable to recover other keys.
Claim 25
Dependent Claim
20 words
The method of claim 23 in which said sender caches said recovery information for use in recovering said other keys.
Claim 26
Dependent Claim
32 words
The method of claim 23 in which said sender also generates and transmits to said receiver key-dependent recovery information used in conjunction with said non-key-specific recovery information to recover said encryption key.
Claim 27
Dependent Claim
43 words
The method of claim 25 in which said key-dependent recovery information is generated by generating a key-specific recovery value from said non-key-specific recovery information and key-specific recovery information and generating said key-dependent recovery information from said key-specific recovery value and said encryption key.
Claim 28
Dependent Claim
23 words
The method of claim 26 in which said key-dependent recovery information is generated by encrypting said encryption key with said key-specific recovery value.
Claim 29
Dependent Claim
26 words
A program storage device readable by a machines tangibly embodying a program of instructions executable by the machine to perform the method steps of claim 1.
Claim 30
Dependent Claim
187 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channels said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said a trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, a method for regenerating said recovery information for said receiver, wherein said receiver performs the steps of: receiving said encrypted recovery information; generating said additional shared secret value from said first shared secret value and said public value generated from said secret value held by said trustee; and decrypting said encrypted recovery information using said additional shared secret value.
Claim 31
Dependent Claim
187 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channels said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said a trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, a method for regenerating said recovery information for said receiver, wherein said receiver performs the steps of: receiving said encrypted recovery information; generating said additional shared secret value from said first shared secret value and said public value generated from said secret value held by said trustee; and decrypting said encrypted recovery information using said additional shared secret value.
Claim 32
Dependent Claim
27 words
The method of claim 29 in which said receiver performs the further steps of: receiving said encrypted data; and decrypting said encrypted data using said encryption key.
Claim 33
Dependent Claim
18 words
The method of claim 30 in which said receiver regenerates said encryption key using said decrypted recovery information.
Claim 34
Dependent Claim
20 words
The method of claim 31 in which said decrypted recovery information comprises non-key-specific recovery information usable to recover other keys.
Claim 35
Dependent Claim
21 words
The method of claim 32 in which said receiver caches said decrypted recovery information for use in recovering said other keys.
Claim 36
Dependent Claim
43 words
The method of claim 32 in which said sender also transmits key-dependent recovery information used in conjunction with said non-key-specific recovery information to recover said encryption keys said receiver regenerating said encryption key from said key-dependent recovery information and said non-key-specific recovery information.
Claim 37
Dependent Claim
81 words
The method of claim 34 in which said key-dependent recovery information is generated by generating a key-specific recovery value from said non-key-specific recovery information and key-specific recovery information and generating said key-dependent recovery information from said key-specific recovery value and said encryption keys said receiver regenerating said encryption key by: regenerating said key-specific recovery value from said non-key-specific recovery information and said key-specific recovery information; and regenerating said encryption key from said regenerated key-specific recovery value and said key-dependent recovery information.
Claim 38
Dependent Claim
41 words
The method of claim 35 in which said key-dependent recovery information is generated by encrypting said encryption key with said key-specific recovery value, said receiver regenerating said encryption key by decrypting said key-dependent recovery information using said regenerated key-specific recovery value.
Claim 39
Dependent Claim
44 words
The method of claim 30 in which said step of decrypting said encrypted data comprises the steps of: determining whether said encrypted recovery information was correctly decrypted; and decrypting said encrypted data only if it is determined that said recovery information was correctly encrypted.
Claim 40
Dependent Claim
37 words
The method of claim 37 in which said encrypted recovery information includes a message authentication code, said step of determining whether said encrypted recovery information was correctly decrypted comprising the step of testing said message authentication code.
Claim 41
Dependent Claim
51 words
The method of claim 29 in which said sender and said receiver hold respective secret values from which corresponding public values are generated, said first shared secret value being generated from said secret value held by said sender and the public value generated from the secret value held by said receiver.
Claim 42
Dependent Claim
47 words
The method of claim 39 in which said first shared secret value is generated as: u=g.sup.xy mod p, where x is the secret value held by said sender, y is the secret value held by said receiver, p is a prime modulus, and g is a generator.
Claim 43
Dependent Claim
37 words
The method of claim 29 in which said first shared public value is generated as g u mod p, where u is said first shared secret value, p is a prime modulus, and g is a generator.
Claim 44
Dependent Claim
45 words
The method of claim 41 in which said additional shared secret value is generated as v=g.sup.au mod p, where a is the secret value held by said trustee, u is said first shared secret value, p is said prime modulus, and g is said generator.
Claim 45
Dependent Claim
26 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps of claim 29.
Claim 46
Dependent Claim
188 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, a method for regenerating said recovery information for said trustee, wherein said trustee performs the steps of: receiving said encrypted recovery information and said first shared public value; regenerating said additional shared secret value from said first shared public value and said secret value held by said trustee; and decrypting said encrypted recovery information using said regenerated additional shared secret value.
Claim 47
Dependent Claim
188 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, a method for regenerating said recovery information for said trustee, wherein said trustee performs the steps of: receiving said encrypted recovery information and said first shared public value; regenerating said additional shared secret value from said first shared public value and said secret value held by said trustee; and decrypting said encrypted recovery information using said regenerated additional shared secret value.
Claim 48
Dependent Claim
29 words
The method of claim 44 in which said trustee receives said encrypted recovery information and said first shared public value from a party seeking recovery of said encryption key.
Claim 49
Dependent Claim
37 words
The method of claim 44 in which said first shared public value is generated as g u mod p, where u is said first shared secret value, p is a prime modulus, and g is a generator.
Claim 50
Dependent Claim
45 words
The method of claim 46 in which said additional shared secret value is generated as v=g.sup.au mod p, where a is the secret value held by said trustee, u is said first shared secret value, p is said prime modulus, and g is said generator.
Claim 51
Dependent Claim
28 words
The method of claim 44 in which said trustee performs the further step of: revealing said decrypted recovery information to a party seeking recovery of said encryption key.
Claim 52
Dependent Claim
36 words
The method of claim 44 in which said trustee performs the further step of: generating a recovery value from said decrypted recovery information; revealing said recovery value to a party seeking recovery of said encryption key.
Claim 53
Dependent Claim
30 words
The method of claim 44 in which said recovery value is generated as a one-way function of said decrypted recovery information and additional recovery information specific to said encryption key.
Claim 54
Dependent Claim
23 words
The method of claim 44 in which said trustee receives said additional recovery information from a party seeking recovery of said encryption key.
Claim 55
Dependent Claim
20 words
The method of claim 44 in which said decrypted recovery information comprises non-key-specific recovery information usable to recover other keys.
Claim 56
Dependent Claim
21 words
The method of claim 52 in which said trustee caches said decrypted recovery information for use in recovering said other keys.
Claim 57
Dependent Claim
81 words
The method of claim 52 in which said sender also transmits key-dependent recovery information used in conjunction with said non-key-specific recovery information to recover said encryption key, said key-dependent recovery information being generated by generating a key-specific recovery value from said non-key-specific recovery information and key-specific recovery information and a generating said key-dependent recovery information from said key-specific recovery value and said encryption key, said trustee regenerating said key-specific recovery value from said non-key-specific recovery information and said key-specific recovery information.
Claim 58
Dependent Claim
30 words
The method of claim 54 in which said trustee presents said key-specific recovery value to a party seeking recovery of said encryption key while not revealing said non-key-specific recovery information.
Claim 59
Dependent Claim
26 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps of claim 44.
Claim 60
Dependent Claim
200 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said a trustee, said trustee holding a secret value from which a corresponding public value is generated, apparatus associated with said sender for making said recovery information available to said trustee, comprising: means for generating a first shared public value from said first shared secret value; means for generating an additional shared secret value from said first shared secret value and the public value generated from the secret value held by said trustee, means for encrypting said recovery information using said additional shared secret value generated for said trustee; and means for transmitting said encrypted recovery information to said receiver via said communications channel, said trustee being able to decrypt said recovery information by regenerating said additional shared secret value from said first shared public value and the secret value held by said trustee.
Claim 61
Dependent Claim
200 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said a trustee, said trustee holding a secret value from which a corresponding public value is generated, apparatus associated with said sender for making said recovery information available to said trustee, comprising: means for generating a first shared public value from said first shared secret value; means for generating an additional shared secret value from said first shared secret value and the public value generated from the secret value held by said trustee, means for encrypting said recovery information using said additional shared secret value generated for said trustee; and means for transmitting said encrypted recovery information to said receiver via said communications channel, said trustee being able to decrypt said recovery information by regenerating said additional shared secret value from said first shared public value and the secret value held by said trustee.
Claim 62
Dependent Claim
188 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, apparatus within said receiver for regenerating said recovery information for said receiver, comprising: means for receiving said encrypted recovery information; means for generating said additional shared secret value from said first shared secret value and said public value generated from said secret value held by said trustee; and means for decrypting said encrypted recovery information using said additional shared secret value.
Claim 63
Dependent Claim
188 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, apparatus within said receiver for regenerating said recovery information for said receiver, comprising: means for receiving said encrypted recovery information; means for generating said additional shared secret value from said first shared secret value and said public value generated from said secret value held by said trustee; and means for decrypting said encrypted recovery information using said additional shared secret value.
Claim 64
Dependent Claim
191 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, apparatus associated with said trustee for regenerating said recovery information for said trustee, comprising: means for receiving said encrypted recovery information and said first shared public value; means for regenerating said additional shared secret value from said first shared public value and said secret value held by said trustee; and means for decrypting said encrypted recovery information using said regenerated additional shared secret value.
Claim 65
Dependent Claim
191 words
In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, apparatus associated with said trustee for regenerating said recovery information for said trustee, comprising: means for receiving said encrypted recovery information and said first shared public value; means for regenerating said additional shared secret value from said first shared public value and said secret value held by said trustee; and means for decrypting said encrypted recovery information using said regenerated additional shared secret value.
References Cited (Backward Citations)
US4200770A
Cited
US5276737A
Cited
US5315658A
Cited
US5276737B1
Cited
US5315658B1
Cited
US5557765A
Cited
US5796830A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-24 | 2002-11-23 | 2003-05-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-24 | 2006-11-23 | 2007-05-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-24 | 2010-11-23 | 2011-05-25 | $7700.00 | Window Closed / Lapsed |