Group key exchanges with failures

A computer program element comprising program code means for performing 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 (di, ei) according to a public key encryption scheme, and broadcasting the public key (ei) to each other participating network device (A, B, C);
• choosing a local contribution value (yi) from a multiplicative group (Gq) of size q;
• in each case of receiving a public key (ej) from one of the other participating network devices (A, B, C), encrypting the local contribution value (yi) under the received public key (ej) to an encrypted contribution value (yij) and sending in reply to the one of the other participating network devices (A, B, C) the encrypted contribution value (yij);
• receiving at least n−t−1 encrypted contribution values (yji) and deriving decrypted contribution values (yj) by applying the private key (di);
• deriving a blinded session key (bski) from the decrypted contribution values (yj) and the local contribution value (yi), wherein deriving the blinded session key (bski) comprises:
• deriving a first sequence of at least n−t participating network devices (E1, E2, E3) 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 (yji) have been received;
• deriving a second sequence of at least n−t contribution values (yi1, yi2, yi3), where the m'th contribution value (yim) is the local contribution value (yi) of the m'th participating network device (Em);
• computing a third sequence of at least n−t quotients (q1, q2, q3) where the m'th quotient (qm) is defined as the m'th contribution value (yim) divided by the m+1 modulo n−t'th contribution value (yim+1 mod q);
• and
• defining the blinded session key (bski) as the first sequence and the third sequence;
• agreeing on one of the blinded session keys (bskj) by using an agreement protocol;
• and
• deriving the session key (sk) from the agreed-on blinded session key (bskj) by applying one of the decrypted contribution values (yj) and the contribution value (yi), wherein deriving the session key (sk) comprises:
• deriving an un-blinding value (u) as the local contribution value (yj) of the k'th participating network device (Ek) defined by the agreed-on blinded session key (bskj), 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 (qk+m mod n−t) defined by the agreed-on blinded session key (bskj);
• 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).

A computer program product stored on a computer usable medium, comprising computer readable program means for causing a computer to perform 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 (di, ei) according to a public key encryption scheme, and broadcasting the public key (ei) to each other participating network device (A, B, C);
• choosing a local contribution value (yi) from a multiplicative group (Gq) of size q;
• in each case of receiving a public key (ej) from one of the other participating network devices (A, B, C), encrypting the local contribution value (yi) under the received public key (ej) to an encrypted contribution value (yij) and sending in reply to the one of the other participating network devices (A, B, C) the encrypted contribution value (yij);
• receiving at least n−t−1 encrypted contribution values (yji) and deriving decrypted contribution values (yj) by applying the private key (di);
• deriving a blinded session key (bski) from the decrypted contribution values (yj) and the local contribution value (yi), wherein deriving the blinded session key (bski) comprises:
• deriving a first sequence of at least n−t participating network devices (E1, E2, E3) 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 (yji) have been received;
• deriving a second sequence of at least n−t contribution values (yi1, yi2, yi3), where the m'th contribution value (yim) is the local contribution value (yi) of the m'th participating network device (Em);
• computing a third sequence of at least n−t quotients (q1, q2, q3) where the m'th quotient (qm) is defined as the m'th contribution value (yim) divided by the m+1 modulo n−t'th contribution value (yim+1 mod q);
• and
• defining the blinded session key (bski) as the first sequence and the third sequence;
• agreeing on one of the blinded session keys (bskj) by using an agreement protocol;
• and
• deriving the session key (sk) from the agreed-on blinded session key (bskj) by applying one of the decrypted contribution values (yj) and the contribution value (yi), wherein deriving the session key (sk) comprises:
• deriving an un-blinding value (u) as the local contribution value (yj) of the k'th participating network device (Ek) defined by the agreed-on blinded session key (bskj), 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 (qk+m mod n−t) defined by the agreed-on blinded session key (bskj);
• 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).