Patent US5469507A successfully refreshed from Google Patents.
US5469507A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Secure communication and computation in an insecure environment
Assignee: International Business Machines Corp
•
Filing: 1994-03-01
•
Granted: 1995-11-21
•
Expires: 2014-03-01
Abstract
Abstract A mechanism which secures the communication and computation between processors in an insecure distributed environment implements efficient "compilers" for a protocol between processors. The protocol is one that assures some input-output relation when executed by processors which are not all trusted but with secret and authenticated communication links between every two processors. This protocol is transformed by a compiler into a protocol that guarantees essentially the same input-output relations in the presence of (the same type of) insecure processors and insecure communication links. Additionally, a method maintains secret values for a sequence of periods, each secret value being shared by two or more processors for one or several periods, where the processors are connected by a communication network. Another mechanism establishes different cryptographic keys established for each period of communication. Essentially, the effect of exposures is contained to the period in which they occur, or to a minimal number of following periods, and the effect of exposures is contained to the processors exposed. At each period a processor is called nonfaulty if the adversary does not control it. A processor is called secure at a given period if it is non-faulty and also has a secret key, unknown to the adversary.
Inventors
- 👤 Ran Canetti
- 👤 Amir Herzberg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 16:48
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/002; H04L9/004; H04L9/08; H04L9/0891; H04L9/32; H04L9/3247; H04L2209/00; H04L2209/80
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
156 words
A method for securing the communication and distributed computation between and among processors connected by a communication network, said method maintaining secret values for a sequence of periods, each secret value shared by two or more processors for one or several periods and comprising the steps of: securely storing secret values in each processor; calculating in each processor, at the end of a period, messages to be sent to other processors as a function of values held in said processor at that time; transferring said messages to said processors by means of said communication network; calculating in each processor new secret values as a function of messages received from said processors; and periodically replacing the secret values by selecting at random public and private keys of a public-key cyrptosystem; signing the public key with the old secret value stored in the processor; and sending the signed public key to other processors connected to said communication network.
Claim 2
Independent Claim
156 words
A method for securing the communication and distributed computation between and among processors connected by a communication network, said method maintaining secret values for a sequence of periods, each secret value shared by two or more processors for one or several periods and comprising the steps of: securely storing secret values in each processor; calculating in each processor, at the end of a period, messages to be sent to other processors as a function of values held in said processor at that time; transferring said messages to said processors by means of said communication network; calculating in each processor new secret values as a function of messages received from said processors; and periodically replacing the secret values by selecting at random public and private keys of a public-key cyrptosystem; signing the public key with the old secret value stored in the processor; and sending the signed public key to other processors connected to said communication network.
Claim 3
Dependent Claim
28 words
The method recited in claim 1 wherein the messages received from the other processors are signed, further comprising the step of verifying the signatures of the received messages.
Claim 4
Independent Claim
126 words
A method for securing the communication and distributed computation in a distributed dam processing system comprising a plurality of processors connected by a communication network, said method maintaining secret values for a sequence of periods, each secret value shared by two or more processors for one or several periods and comprising the steps of: each processor P i selecting in each round new public and private keys, and broadcasting the public key; broadcasting by each processor P j the vector v j of all public keys received in this round; verifying by each processor the received vectors v j ; issuing a warning if the step of verifying fails; and erasing at each processor old private keys and writing the new private key in secure storage.
Claim 5
Independent Claim
126 words
A method for securing the communication and distributed computation in a distributed dam processing system comprising a plurality of processors connected by a communication network, said method maintaining secret values for a sequence of periods, each secret value shared by two or more processors for one or several periods and comprising the steps of: each processor P i selecting in each round new public and private keys, and broadcasting the public key; broadcasting by each processor P j the vector v j of all public keys received in this round; verifying by each processor the received vectors v j ; issuing a warning if the step of verifying fails; and erasing at each processor old private keys and writing the new private key in secure storage.
Claim 6
Dependent Claim
25 words
The method of claim 3 further comprising the step of generating by each pair of processors a fresh session key using the new public keys.
Claim 7
Dependent Claim
88 words
The method of claim 4 further comprising the steps of: storing the old private key in a secure storage in the processor; storing the new private key in a first register the new public key in a second register section; accessing the secure storage for the old private key to sign the fresh session key held in said first register; exchanging the signed session keys between said pair of processors; and verifying at each processor the received signed session key using old public keys from a previous session.
Claim 8
Dependent Claim
48 words
The method of claim 3 further comprising the step of echoing by each processor P j the public key received from each of the other processors Pi, signed using the old session key of P i and P j , back to the sending processor, P i .
Claim 9
Dependent Claim
110 words
The method of claim 3 wherein the step of selecting new private and public keys by each processor P i is performed by using a random number generator and a public/private key generator, said method further comprising the steps of: storing the old private key in a secure storage in the processor; storing the new private key in a first register and the new public key in a second register; accessing the secure storage for the old private key to sign the new public key held in said first register; and receiving the signed new public keys broadcast by processors P j and temporarily storing the received new public keys.
Claim 10
Dependent Claim
54 words
The method recited in claim 7 further comprising the steps of: storing the old public keys in a third register; accessing the old public keys stored in said third register; and verifying the signatures of the received new public keys from processors P j using the old public keys accessed from said third register.
Claim 11
Dependent Claim
67 words
The method of claim 8 wherein all public keys broadcast by each processor P j , together with the new public key of processor P i , form a vector v i , further comprising the steps of: signing the vector v i using the old private key of the processor P j ; and broadcasting the signed vector v i to the processors P j .
Claim 12
Dependent Claim
43 words
The method recited in claim 9 further comprising the steps of: receiving the vectors v j broadcast by processors P j and temporarily storing the received vectors v j in a fifth register; and verifying the signatures of said vectors v j .
Claim 13
Dependent Claim
127 words
The method of claim 9 further comprising the steps of: receiving and temporarily storing the signed vectors v j from the processors P j ; storing the old public keys of all the processors in a third register; accessing said third register to verify the signatures of the received new public keys from processors P j ; temporarily holding the verified new public keys in a fourth register; accessing said fourth register to read the new public keys from processors P j and, together with the new public key for processor P i held in said first register, forming a vector v i ; signing the vector v i using the old private key stored in the secure storage; and broadcasting the signed vector v i .
Claim 14
Independent Claim
257 words
A method of maintaining secret keys shared between pairs of processors v and v' in distributed processing system comprising n processors connected by a communication network in the presence of a mobile, transient adversary that occasionally breaks into processors of the distributed processing system, each pair of processors communicating directly using a dedicated communication link of the communication network, said method comprising the steps of: at the beginning of each period i, sending by each processor v to each processor v' a table of n 2 values denoted X v ,v' (u,u')[i], for processor pairs u,u'=1,. . . ,n; computing by each processor v each pair of values X v ,v' (u,u')[i], X v ,u' (u, v')[i] by first computing a pseudo-random offset R as a function of v, v', u, and u', and then setting, by each processor v, X v ,v' (u,u')[i] as a function of v, v', u, u', and i; and computing a new key K v'u' (i) by processor v' as an exclusive 0R of all the X v ,v' (u,u') values received from different sources v and with different u values, whereby the keys resulting from this computation are completely unknown to an attacker, even if this attacker has complete control over all processors, except u',v' during period i and some u,v during period i-1, provided that K u ,v (i-1) and K v ,u (i-1) were also completely unknown to the attacker, and that the links (v',v) and (u',u) were non-faulty during the overlap between period i and period i-1.
Claim 15
Independent Claim
257 words
A method of maintaining secret keys shared between pairs of processors v and v' in distributed processing system comprising n processors connected by a communication network in the presence of a mobile, transient adversary that occasionally breaks into processors of the distributed processing system, each pair of processors communicating directly using a dedicated communication link of the communication network, said method comprising the steps of: at the beginning of each period i, sending by each processor v to each processor v' a table of n 2 values denoted X v ,v' (u,u')[i], for processor pairs u,u'=1,. . . ,n; computing by each processor v each pair of values X v ,v' (u,u')[i], X v ,u' (u, v')[i] by first computing a pseudo-random offset R as a function of v, v', u, and u', and then setting, by each processor v, X v ,v' (u,u')[i] as a function of v, v', u, u', and i; and computing a new key K v'u' (i) by processor v' as an exclusive 0R of all the X v ,v' (u,u') values received from different sources v and with different u values, whereby the keys resulting from this computation are completely unknown to an attacker, even if this attacker has complete control over all processors, except u',v' during period i and some u,v during period i-1, provided that K u ,v (i-1) and K v ,u (i-1) were also completely unknown to the attacker, and that the links (v',v) and (u',u) were non-faulty during the overlap between period i and period i-1.
Claim 16
Dependent Claim
19 words
The method recited in claim 12 wherein u'<v' and the pseudo-random offset R is computed as: R.sub.v,v' (u,u')=f.sub.Kv,u(i-1) (u,v',u').
Claim 17
Dependent Claim
32 words
The method recited in claim 13 wherein processor v sets X v ,v' (u,u')[i] as a function of v, v', u, u', and i as: ##EQU5## where (⊕) represents the combination operation.
Claim 18
Dependent Claim
32 words
The method recited in claim 14 wherein the new key K v'u' (i) is computed by processor v' as an exclusive OR of all the X v ,v' (u,u') values as: ##EQU6##
References Cited (Backward Citations)
US4956863A
Cited
US5159633A
Cited
JPH0522283A
Cited
US5200999A
Cited
US5241599A
Cited
US5371794A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-11-20 | 1999-05-22 | 1999-11-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-11-20 | 2003-05-22 | 2003-11-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-11-20 | 2007-05-22 | 2007-11-21 | $7700.00 | Window Closed / Lapsed |