A communication device includes: a first subscriber identification unit that stores first subscriber identification unit identification information associated with user identification information; and a communication unit that communicates with another communication device, the other communication device including a second subscriber identification unit that stores second subscriber identification unit identification information associated with user identification information. The first subscriber identification unit includes: a key memory unit that records a pair of a public key certificate and a secret key, the pair being shared with the second subscriber identification unit; a public key certificate generation unit that generates, using the secret key recorded in the key memory unit, a “first public key certificate comprising the first subscriber identification unit identification information or the user identification information associated with the first subscriber identification unit identification information”; and a secret key memory unit that records a secret key paired with the first public key certificate.