US 5,469,507 A · Secure communication and computation in an insecure environment

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.

Claims15

Dependent claims

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.

6 more elements

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.sup.2 values denoted X.sub.v,v' (u,u')[i], for processor pairs u,u'=1,. . . ,n;
computing by each processor v each pair of values X.sub.v,v' (u,u')[i], X.sub.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.sub.v,v' (u,u')[i] as a function of v, v', u, u', and i;
and
computing a new key K.sub.v'u' (i) by processor v' as an exclusive 0R of all the X.sub.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.sub.u,v (i-1) and K.sub.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.

1 more element

Dependencies are inferred from the claim text.

Secure communication and computation in an insecure environment

Life of this patent

Secure communication and computation in an insecure environment

Life of this patent

Abstract

Claims15