Key exchange method and key exchange system

A key exchange system comprising:

• a key distribution device S;
• and
• n+k pieces (here, n is an integer which is 2 or larger and k is an integer which is 1 or larger) of communication devices Ui (i=1, . . . , n+k), wherein
• ∥ is a concatenation operator,
• U1 is one piece of representative communication device which is selected from the communication devices U1, Un, Un+1, . . . , Un+k,
• the key distribution device S includes
• a storage which stores a secret key skS for public key encryption and secret strings stS and st′S of the key distribution device S,
• a session ID generation unit which receives (Ri, ci) from the communication devices Ui (i=1, n, . . . , n+k), receives ci from the communication devices Ui (i=2, . . . , n−1), generates sid by using c1, . . . , cn+k based on a target-collision resistant hash function, and transmits, to the communication devices Ui, (sid, Ri−1) with respect to i=1, 2, sid with respect to i=3, . . . , n−2, (sid, Ri+1) with respect to i=n−1, n, and (sid, Ri−1, Ri+1) with respect to i=n+1, . . . , n+k (here, R0=Rn+K, Rn+k+1=R1), and
• a third key generation unit which receives (T1, T′) from the representative communication device U1, receives (ki, si, Ti) from the communication device Ui (i=2, n−1, . . . , n+k), receives (ki, si) from the communication devices Ui (i=3, . . . , n−2), generates ks by using the secret strings stS and st′S based on a twisted pseudo-random function, computes k′ by an exclusive OR of k2, . . . , kn+k, ks, computes T′i by an exclusive OR of T1, . . . , Ti−1 with respect to i=2, . . . , n+k (here, Ti is nil with respect to i=3, . . . , n−1), transmits k′ to the representative communication device U1, and transmits (k′, T′i, T′) to the communication devices Ui (i=2, . . . , n+k), and
• the communication devices Ui (i=1, . . . , n+k) include
• a storage which stores a secret key ski for public key encryption and secret strings sti and st′i of the communication devices Ui and further stores information r generated in a session established by the communication devices U1, . . . , Un with respect to i=1, . . . , n,
• a first key generation unit which generates ri, ki, and si by using the secret strings sti and st′i based on the twisted pseudo-random function, computes Ri=gri and ci=gkihsi, and transmits (Ri, ci) to the key distribution device S with respect to i=1, n, . . . , n+k, and generates ki and si by using the secret strings sti and st′i based on the twisted pseudo-random function, computes ci=gkihsi, and transmits ci to the key distribution device S with respect to i=2, . . . , n−1,
• a second key generation unit which receives (sid, Rn+k) from the key distribution device S, generates K1l by using (sid, Rn+kr1) based on the pseudo-random function, generates K1r by using (sid, gr1r) based on the pseudo-random function, computes T1 by an exclusive OR of K1l and K1r, computes T′ by an exclusive OR of K1l and k1∥s1, and transmits (T1, T′) to the key distribution device S with respect to i=1, receives (sid, R1) from the key distribution device S, generates K2l by using (sid, R1r) based on the pseudo-random function, generates K2r by using (sid, gr) based on the pseudo-random function, computes T2 by an exclusive OR of K2l and K2r, and transmits (k2, s2, T2) to the key distribution device S with respect to i=2, receives sid from the key distribution device S and transmits (ki, si) to the key distribution device S with respect to i=3, . . . , n−2, receives (sid, Rn) from the key distribution device S, generates Kn−1l by using (sid, gr) based on the pseudo-random function, generates Kn−1r by using (sid, Rnr) based on the pseudo-random function, computes Tn−1 by an exclusive OR of Kn−1l and Kn−1r, and transmits (kn−1, sn−1, Tn−1) to the key distribution device S with respect to i=n−1, receives (sid, Rn+1) from the key distribution device S, generates Knl by using (sid, Rnr) based on the pseudo-random function, generates Knr by using (sid, Rn+1rn) based on the pseudo-random function, computes Tn by an exclusive OR of Knl and Knr, and transmits (kn, sn, Tn) to the key distribution device S with respect to i=n, and receives (sid, Ri−1, Ri+1) from the key distribution device S, generates Kil by using (sid, Ri−1ri) based on the pseudo-random function, generates Kir by using (sid, Ri+1ri) based on the pseudo-random function, computes Ti by an exclusive OR of Kil and Kir, and transmits (ki, si, Ti) to the key distribution device S with respect to i=n+1, . . . , n+k, and
• a session key generation unit which receives k′ from the key distribution device S and generates a common key K2 by using sid and an exclusive OR of k′ and k1 based on the pseudo-random function with respect to i=1, receives (k′, T′i, T′) from the key distribution device S, computes K1l by an exclusive OR of T′i and Kil, computes k1∥s1 by an exclusive OR of T′ and K1l, and generates the common key K2 by using sid and the exclusive OR of k′ and k1 based on the pseudo-random function with respect to i=2, n, . . . , n+k, and receives (k′, T′i, T′) from the key distribution device S, computes K1l by an exclusive OR of T′i and gr, computes k1∥s1 by an exclusive OR of T′ and K1l, and generates the common key K2 by using sid and the exclusive OR of k′ and k1 based on the pseudo-random function with respect to i=3, . . . , n−1.

A key exchange method for a case where, in a key exchange system which includes a key distribution device S and n pieces (here, n is an integer which is 2 or larger) of communication devices Ui (i=1, . . . , n), communication devices Uj1, . . . , Ujm leave from a session established by communication devices U1, . . . , Un, in which

• R={Uj1, . . . , Ujm} is a subset of {U1, . . . , Un} and N={Uj1−1, Uj1+1, . . . , Ujm−1, Ujm+1} is a subset of {U1, . . . , Un},
• ∥ is a concatenation operator,
• U1 (εN) is one piece of representative communication device which is selected from N,
• a secret key skS for public key encryption and secret strings stS and st′S of the key distribution device S are stored in a storage of the key distribution device S, and a secret key ski for public key encryption and secret strings sti and st′i of the communication devices Ui and information Hil and Hir generated in the session established by the communication devices U1, . . . , Un are stored in a storage of the communication devices Ui (i=1, . . . , n), the key exchange method comprising:
• a first key generation step in which the communication devices Ui (εN) generate ri, ki, and si by using the secret strings sti and st′i based on a twisted pseudo-random function, compute Ri=gri and ci=gkihsi, and transmit (Ri, ci) to the key distribution device S, and the communication devices Ui (ε({U1, . . . , Un}−R)−N) generate ki and si by using the secret strings sti and st′i based on the twisted pseudo-random function, compute ci=gkihsi, and transmit ci to the key distribution device S;
• a session ID generation step in which the key distribution device S generates sid by using {ci|i satisfies U1ε{U1, . . . , Un}−R} based on a target-collision resistant hash function and transmits, to the communication devices Ui, (sid, Rj) with respect to i which satisfies UiεN and Ui+1εR (here, j is a minimum index which satisfies UjεN and j>i), (sid, Rj′) with respect to i which satisfies UiεN and Ui−1εRt (here, j′ is a maximum index which satisfies Uj′εN and j′<i), and sid with respect to i which satisfies Uiε({U1, . . . , Un}−R)−N;
• a second key generations step in which the representative communication device U1 generates K1l by using (sid, Rn−1r1) based on a pseudo-random function, generates K1r by using (sid, R3r1) based on the pseudo-random function, computes T1 by an exclusive OR of K1l and K1r, computes T′ by an exclusive OR of K1l and k1∥s1, and transmits (T1, T′) to the key distribution device S in a case where Uj=U3 and Uj′=Un−1 are satisfied, generates K1l by using (sid, Rn−1r1) based on the pseudo-random function, generates K1r by using (sid, H1r) based on the pseudo-random function, computes T1 by the exclusive OR of K1l and K1r, computes T′ by the exclusive OR of K1l and k1∥s1, and transmits (T1, T′) to the key distribution device S in a case where Uj′=Un−1 and U2εN are satisfied, and generates K1l by using (sid, H1l) based on the pseudo-random function, generates K1r by using (sid, R3r1) based on the pseudo-random function, computes T1 by the exclusive OR of K1l and K1r, computes T′ by the exclusive OR of K1l and K1∥s1, and transmits (T1, T′) to the key distribution device S in a case where Uj=U3 and UnεN are satisfied, the communication devices Ui (i satisfies UiεN and Ui+1εR (here, i is not 1)) generate Kil by using (sid, Hil) based on the pseudo-random function, generate Kir by using (sid, Rjri) based on the pseudo-random function, compute Ti by an exclusive OR of Kil and Kir, and transmit (ki, si, Ti) to the key distribution device S, the communication devices Ui (i satisfies UiεN and Ui−1εR (here, i is not 1)) generate Kil by using (sid, Rjri) based on the pseudo-random function, generate Kir by using (sid, Hir) based on the pseudo-random function, compute Ti by the exclusive OR of Kil and Kir, and transmit (ki, si, Ti) to the key distribution device S, and the communication devices Ui (i satisfies Uiε({U1, . . . , Un}−R)−N (here, i is not 1)) generate Kil by using (sid, Hil) based on the pseudo-random function, generate Kir by using (sid, Hir) based on the pseudo-random function, compute Ti by the exclusive OR of Kil and Kir, and transmit (ki, si, Ti) to the key distribution device S;
• a third key generation step in which the key distribution device S generates ks by using the secret strings stS and st′S based on the twisted pseudo-random function, computes k′ by an exclusive OR of {ki|i satisfies Uiε({U1, . . . , Un}−R)−{U1}} and ks, computes T′i by an exclusive OR of T1, . . . , Tj, . . . , Ti−1 with respect to i which satisfies Uiε{U1, . . . , Un}−R (here, Tj is nil with respect to j which satisfies USER), transmits k′ to the representative communication device U1, and transmits (k′, T′i, T′) to the communication devices Ui (ε({U1, . . . , Un}−R)−{U1});
• a first session key generation step in which the communication devices Ui (ε({U1, . . . , Un}−R)−{U1}) compute K1l by an exclusive OR of T′i and Kil and compute k1∥s1 by an exclusive OR of T′ and K1l;
• and
• a second session key generation step in which the communication devices Ui (ε{U1, . . . , Un}−R) generate the common key K2 by using sid and the exclusive OR of k′ and k1 based on the pseudo-random function.

A key exchange system comprising:

• a key distribution device S;
• and
• n pieces (here, n is an integer which is 2 or larger) of communication devices Ui (i=1, . . . , n), wherein
• R={Uj1, . . . , Ujm} is a subset of {U1, . . . , Un} and N={Uj1−1, Uj1+1, . . . , Ujm−1, Ujm1} is a subset of {U1, . . . , Un},
• ∥ is a concatenation operator,
• U1 (εN) is one piece of representative communication device which is selected from N,
• the key distribution device S includes
• a storage which stores a secret key skS for public key encryption and secret strings stS and st′S of the key distribution device S,
• a session ID generation unit which receives (Ri, ci) from the communication devices Ui (εN), receives ci from the communication devices Ui (ε({U1, . . . , Un}−R)−N), generates sid by using {ci|i satisfies Uiε{U1, . . . , Un}−R} based on a target-collision resistant hash function, and transmits, to the communication devices Ui, (sid, Rj) with respect to i which satisfies UiεN and Ui+1εR (here, j is a minimum index which satisfies UjεN and j>i), (sid, Rj′) with respect to i which satisfies UiεN and Ui−1εR (here, j′ is a maximum index which satisfies Uj′εN and j′<i), and sid with respect to i which satisfies Uiε({U1, . . . , Un}−R)−N, and
• a third key generation unit which receives (T1, T′) from the representative communication device U1, receives (ki, si, Ti) from the communication devices Ui (ε({U1, . . . , Un}−R)−{U1}), generates ks by using the secret strings stS and st′S based on the twisted pseudo-random function, computes k′ by an exclusive OR of {ki|i satisfies Uiε({U1, . . . , Un}−R)−{U1}} and ks, computes T′i by an exclusive OR of T1, . . . , Tj, Ti−1 (here, Tj is nil with respect to j which satisfies UjεR) with respect to i which satisfies Uiε{U1, Un}−R, transmits k′ to the representative communication device U1, and transmits (k′, T′i, T′) to the communication devices Ui (ε({U1, . . . , Un}−R)−{U1}), and
• the communication devices Ui (ε{Ui, . . . , Un}−R) include
• a storage which stores a secret key ski for public key encryption and secret strings sti and st′i of the communication devices Ui and stores information Hil and Hir generated in a session established by the communication devices U1, . . . , Un,
• a first key generation unit which generates ri, ki, and si by using the secret strings sti and st′i based on a twisted pseudo-random function, computes Ri=gri and ci=gkihsi, and transmits (Ri, ci) to the key distribution device S with respect to i which satisfies UiεN, and generates ki and si by using the secret strings sti and st′i based on the twisted pseudo-random function, computes ci=gkihsi, and transmits Ci to the key distribution device S with respect to i which satisfies Uiε({U1, . . . , Un}−R)−N,
• a second key generation unit which, with respect to i=1, receives (sid, R3, Rn−1) from the key distribution device S, generates K1l by using (sid, Rn−1r1) based on the pseudo-random function, generates K1r by using (sid, R3r1) based on the pseudo-random function, computes T1 by an exclusive OR of K1l and K1r, computes T′ by an exclusive OR of K1l and k1∥s1, and transmits (T1, T′) to the key distribution device S in a case where Uj=U3 and Uj′=Un−1 are satisfied, receives (sid, Rn−1) from the key distribution device S, generates K1l by using (sid, Rn−1r1) based on the pseudo-random function, generates K1r by using (sid, H1r) based on the pseudo-random function, computes T1 by the exclusive OR of K1l and K1r, computes T′ by the exclusive OR of K1l and k1∥s1, and transmits (T1, T′) to the key distribution device S in a case where Uj′=Un−1 and U2εN are satisfied, and receives (sid, R3) from the key distribution device S, generates K1l by using (sid, H1l) based on the pseudo-random function, generates K1ir by using (sid, R3r1) based on the pseudo-random function, computes T1 by the exclusive OR of K1l and K1r, computes T′ by the exclusive OR of K1l and k1∥s1, and transmits (T1, T′) to the key distribution device S in a case where Uj=U3 and UnεN are satisfied;
• with respect to i which satisfies UiεN and Ui+1εR (i is not 1), receives (sid, Rj) from the key distribution device S, generates Kil by using (sid, Hil) based on the pseudo-random function, generates Kir by using (sid, Rjri) based on the pseudo-random function, computes Ti by an exclusive OR of Kil and Kir, and transmits (ki, si, Ti) to the key distribution device S;
• with respect to i which satisfies UiεN and Ui−1εR (i is not 1), receives (sid, Rj′) from the key distribution device S, generates Kil by using (sid, Rj′ri) based on the pseudo-random function, generates Kir by using (sid, Hir) based on the pseudo-random function, computes Ti by the exclusive OR of Kil and Kir, and transmits (ki, si, Ti) to the key distribution device S;
• and with respect to i which satisfies Uiε({U1, . . . , Un}−R)−N (i is not 1), receives sid from the key distribution device S, generates Kil by using (sid, Hil) based on the pseudo-random function, generates Kir by using (sid, Hir) based on the pseudo-random function, computes Ti by the exclusive OR of Kil and Kir, and transmits (ki, si, Ti) to the key distribution device S, and
• a session key generation unit which, with respect to i=1, receives k′ from the key distribution device S and generates a common key K2 by using sid and an exclusive OR of k′ and k1 based on the pseudo-random function, and with respect to i which satisfies Uiε({U1, . . . , Un}−R)−{U1}, receives (k′, T′i, T′) from the key distribution device S, computes K1l by an exclusive OR of T′i and Kil, computes k1∥s1 by an exclusive OR of T′ and K1l, and generates the common key K2 by using sid and the exclusive OR of k′ and k1 based on the pseudo-random function.