US5625692A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for a public key cryptosystem having proactive, robust, and recoverable distributed threshold secret sharing
Assignee: International Business Machines Corp
•
Filing: 1995-01-23
•
Granted: 1997-04-29
•
Expires: 2015-01-23
Abstract
Abstract A proactive threshold secret sharing cryptosystem using a set of servers. The cryptosystem is a threshold cryptosystem, in the sense that service is maintained if at least (k+1) out of n servers are active and honest. The secret signature key is compromised only if the adversary breaks into at least (k+1) servers. It is robust in the sense that the honest servers detect faulty ones and the service is not disrupted. It is recoverable, because if the adversary erases all the local information on the server it compromised, the information can be restored as soon as the server comes back to performing the correct protocol. The method and system has proactiveness, which means that in order to learn the secret, the adversary has to break into (k+1) servers during the same round of the algorithm because the shares of the secret are periodically redistributed and rerandomized. The present invention uses a verifiable secret sharing mechanism to get the security requirements during the update between two rounds. The security of the scheme depends on the assumption of intractability of computing logarithms in a field of a big prime order and the EIGamal signature scheme.
Inventors
- 👤 Amir Herzberg
- 👤 Stanislaw M. Jarecki
- 👤 Hugo M. Krawczyk
- 👤 Marcel M. Yung
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 23:06
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/08; H04L9/0891; H04L9/0816; H04L9/085; H04L9/32; H04L9/3247; H04L9/3252
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
139 words
A method of public key cryptography having proactive, robust and recoverable distributed threshold secret sharing, comprising the steps of: initializing servers linked by a communications network to form keys; synchronizing said servers to operate in discrete rounds having ends; calculating updated keys at said ends of said rounds from messages broadcast on said communications network; verifying said updated keys to form a set of compromised servers; recovering said set of compromised servers; and wherein said step of calculating updated keys at said ends of said rounds from messages broadcast on said communications network comprises the steps of: picking a set of random numbers for each said server; picking a new key for each said server, said new key derived from said set of random numbers; and broadcasting messages derived from said set of random numbers on said communication network.
Claim 2
Independent Claim
139 words
A method of public key cryptography having proactive, robust and recoverable distributed threshold secret sharing, comprising the steps of: initializing servers linked by a communications network to form keys; synchronizing said servers to operate in discrete rounds having ends; calculating updated keys at said ends of said rounds from messages broadcast on said communications network; verifying said updated keys to form a set of compromised servers; recovering said set of compromised servers; and wherein said step of calculating updated keys at said ends of said rounds from messages broadcast on said communications network comprises the steps of: picking a set of random numbers for each said server; picking a new key for each said server, said new key derived from said set of random numbers; and broadcasting messages derived from said set of random numbers on said communication network.
Claim 3
Dependent Claim
62 words
The method of claim 1, wherein said initializing servers linked by a communications network to form keys comprises the steps of: choosing random numbers for each said server; calculating secret values for each said server from said random numbers; calculating private keys for each said server from said secret values; and broadcasting public counterparts of said private keys on said communications network.
Claim 4
Dependent Claim
73 words
The method of claim 1, wherein said verifying said updated keys to form a set of compromised servers comprises the steps of: analyzing said messages broadcast on said communications network to form a set of bad servers; creating a set of accusations corresponding to said set of bad servers; broadcasting said set of accusations on said communications network; and analyzing said broadcasted set of accusations to form an updated set of bad servers.
Claim 5
Dependent Claim
21 words
The method of claim 1, further comprising the step of displaying messages identifying said set of compromised servers on a console.
Claim 6
Dependent Claim
76 words
The method of claim 1, wherein said recovering said set of compromised servers comprises the steps of: installing a new private key in each server in said set of compromised servers; choosing a set of recovery servers from said servers; computing sub-shares for each server in said set of recovery servers; broadcasting messages derived from said sub-shares on said communications network; and verifying said messages derived from said sub-shares received by said set of compromised servers.
Claim 7
Dependent Claim
70 words
The method of claim 5, wherein said choosing a set of recovery servers comprises: choosing a subset of said servers; computing a set of random values for each server in said subset; broadcasting signed messages derived from said set of random values on said communications network; verifying said signed messages to derive a set of bad servers; and eliminating said set of bad servers from said subset of said servers.
Claim 8
Dependent Claim
56 words
The method of claim 1, further comprising the steps of: picking random numbers for each said server; computing first parts of signatures for each said server from said random numbers; broadcasting said first parts of signatures on said communications network; and computing second parts of signatures for each said server from said first parts of signatures.
Claim 9
Dependent Claim
20 words
The method of claim 7, further comprising the step of verifying a message signed with said second parts of signatures.
Claim 10
Dependent Claim
176 words
A data processing system for processing a public key cryptography scheme having proactive, robust and recoverable distributed threshold secret sharing, comprising: servers linked by a communications network; initialization means for initializing said servers to form keys associated with said servers; timing means for synchronizing operation of said servers into discrete rounds having ends; updating means for updating said keys at the end of each round of said discrete rounds to produce updated keys; verification means for verifying said updated keys to form a set of compromised servers; recovery means for recovering said set of compromised servers; and wherein said updating means for updating said keys at the end of each round of said discrete rounds to produce updated keys comprises: random number generating means for generating a set of random numbers, said set of random numbers with each said server; key generating means for generating a new key for each said server from said set of random numbers; and broadcasting means for broadcasting a message on said communications network derived from said set of random numbers.
Claim 11
Dependent Claim
176 words
A data processing system for processing a public key cryptography scheme having proactive, robust and recoverable distributed threshold secret sharing, comprising: servers linked by a communications network; initialization means for initializing said servers to form keys associated with said servers; timing means for synchronizing operation of said servers into discrete rounds having ends; updating means for updating said keys at the end of each round of said discrete rounds to produce updated keys; verification means for verifying said updated keys to form a set of compromised servers; recovery means for recovering said set of compromised servers; and wherein said updating means for updating said keys at the end of each round of said discrete rounds to produce updated keys comprises: random number generating means for generating a set of random numbers, said set of random numbers with each said server; key generating means for generating a new key for each said server from said set of random numbers; and broadcasting means for broadcasting a message on said communications network derived from said set of random numbers.
Claim 12
Dependent Claim
79 words
The data processing system of claim 9, wherein said initialization means comprises: choosing means for choosing a random number for each said server; first calculating means for calculating a secret value for each said server from said random number; second calculating means for calculating a private key and a public counterpart of said private key for each said server from said secret value; broadcasting means for broadcasting said public counterpart of each said private key on said communications network.
Claim 13
Dependent Claim
87 words
The data processing system of claim 9, wherein said verification means for verifying said updated keys to form a set of compromised servers comprises: first analysis means for analyzing messages broadcast on said communications network to form a set of bad servers; accusation means for creating a set of accusations corresponding to said set of bad servers; broadcasting means for broadcasting said set of accusations on said communications network; second analysis means for analyzing said broadcasted set of accusations to form an updated set of bad servers.
Claim 14
Dependent Claim
18 words
The data processing system of claim 9, further comprising display means for displaying said set of compromised servers.
Claim 15
Dependent Claim
87 words
The data processing system of claim 9, wherein said recovery means for recovering said set of compromised servers comprises: selecting means for selecting a set of recovery servers from said servers; computing means for computing a sub-share for each server in said set of recovery servers; broadcasting means for broadcasting messages derived from said sub-share from each server in said set of recovery servers on said communications network; and verification means for verifying said messages derived from each said sub-share received by said set of compromised servers.
Claim 16
Dependent Claim
87 words
The data processing system of claim 13, wherein said selecting means for selecting a set of recovery servers comprises: choosing means for choosing a subset of said servers; computing means for computing a set of random values for each server in said subset; broadcasting means for broadcasting signed messages derived from said set of random values on said communications network; verification means for verifying said signed messages to derive a set of bad servers; and elimination means for eliminating said set of bad servers from said subset.
Claim 17
Dependent Claim
76 words
The data processing system of claim 9, further comprising: random number generation means for generating a set of random numbers for each said server; first computing means for computing first parts of signatures for each said server from said set of random numbers; broadcasting means for broadcasting said first parts of signatures on said communications network; and second computing means for computing second parts of signatures for each said server from said first parts of signatures.
Claim 18
Dependent Claim
21 words
The data processing of claim 15, further comprising verification means for verifying a message signed with said second parts of signatures.
References Cited (Backward Citations)
US4578531A
Cited
US4876716A
Cited
US5175765A
Cited
US5202921A
Cited
US5220606A
Cited
US5375170A
Cited
US5491750A
Cited
US5412723A
Cited
US5469507A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-04-28 | 2000-10-28 | 2001-04-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-04-28 | 2004-10-28 | 2005-04-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-04-28 | 2008-10-28 | 2009-04-29 | $7700.00 | Window Closed / Lapsed |