Patent ID: 7444514

Claim:
A method for generating a session key (sk) on demand in a network among n participating network devices (A, B, C, D) with up to t faulty devices, wherein t<n/2, the method comprising each participating network device (D): choosing a private and public key (d i , e i ) according to a public key encryption scheme, and broadcasting the public key (e i ) to each other participating network device (A, B, C); choosing a local contribution value (y i ) from a multiplicative group (G q ) of size q; in each case of receiving a public key (e j ) from one of the other participating network devices (A, B, C), encrypting the local contribution value (y i ) under the received public key (e j ) to an encrypted contribution value (y ij ) and sending in reply to the one of the other participating network devices (A, B, C) the encrypted contribution value (y ij ); receiving at least n−t−1 encrypted contribution values (y ji ) and deriving decrypted contribution values (y j ) by applying the private key (d i ); deriving a blinded session key (bsk i ) from the decrypted contribution values (y j ) and the local contribution value (y i ), wherein deriving the blinded session key (bsk i ) comprises: deriving a first sequence of at least n−t participating network devices (E 1 , E 2 , E 3 ) comprising the local participating network device (D) and the participating network devices (A, B) from which the at least n−t−1 encrypted contribution values (y ji ) have been received; deriving a second sequence of at least n−t contribution values (y i1 , Y i2 , Y i3 ), where the m'th contribution value (y im ) is the local contribution value (y i ) of the m'th participating network device (E m ); computing a third sequence of at least n−t quotients (q 1 , q 2 , q 3 ) where the m'th quotient (q m ) is defined as the m'th contribution value (y im ) divided by the m+1 modulo n−t'th contribution value (y im+1 mod q ); and defining the blinded session key (bsk i ) as the first sequence and the third sequence; agreeing on one of the blinded session keys (bsk j ) by using an agreement protocol; and deriving the session key (sk) from the agreed-on blinded session key (bsk j ) by applying one of the decrypted contribution values (y j ) and the contribution value (y i ), wherein deriving the session key (sk) comprises: deriving an un-blinding value (u) as the local contribution value (y j ) of the k'th participating network device (E k ) defined by the agreed-on blinded session key (bsk j ), where k is arbitrary; deriving a fourth sequence of at least n−t modified quotients (q′ 1 , q′ 2 , q′ 3 ), where the m'th modified quotient (q′ m ) is defined as the m'th power of the k+m modulo n−t'th quotient (q k+m mod n−t ) defined by the agreed-on blinded session key (bsk j ); and deriving the session key (sk) as the product of the modified quotients (q′ 1 , q′ 2 , q′ 3 ) multiplied with the n−t'th power of the un-blinding value (u).