US5469507A — Secure communication and computation in an insecu…

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##

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

Secure communication and computation in an insecure environment

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag