Key exchange method, key exchange system, key distribution device, communication device, and program

Abstract

Plurality of users share a common key while permitting dynamic member change and computational complexity required for key exchange is reduced. The first key generation unit computes Rand cbased on a twisted pseudo-random function. A session ID generation unit generates sid based on a target-collision resistant hash function and transmits (sid, R, R) to communication devices U. A second key generation unit of a representative communication device Ucomputes Tbased on a pseudo-random function. A second key generation unit of general communication devices Ucomputes Tbased on the pseudo-random function. A third key generation unit computes k' based on the twisted pseudo-random function and computes T′with respect to each j. A session key generation unit of the general communication devices Ucomputes Kand k. The session key generation unit generates a common key Kbased on the pseudo-random function.