A communication device (100, 300) comprising: cryptosystem selection means (101, 303) configured to: determine whether synchronization accuracy is higher, lower or asynchronous by using predetermined information, the synchronization accuracy representing a frequency of timings at which a cryptosystem used for encryption communication between the communication device (100, 300) and another communication device (100, 300) can be changed in synchronization, select the cryptosystem with lower processing load on cryptographic processing in the encryption communication when the synchronization accuracy is higher, select the cryptosystem with higher processing load on the cryptographic processing in the encryption communication when the synchronization accuracy is lower, and select the cryptosystem with higher processing load on the cryptographic processing in the encryption communication than the cryptosystem at the time when the synchronization accuracy is lower, and set so as not to change the cryptosystem, when the synchronization accuracy is asynchronous; and cryptographic processing means (102, 305) configured to execute at least one of encryption processing and decryption processing on communication data with the another communication device by using the cryptosystem selected. cryptosystem selection means (101, 303) configured to: determine whether synchronization accuracy is higher, lower or asynchronous by using predetermined information, the synchronization accuracy representing a frequency of timings at which a cryptosystem used for encryption communication between the communication device (100, 300) and another communication device (100, 300) can be changed in synchronization, select the cryptosystem with lower processing load on cryptographic processing in the encryption communication when the synchronization accuracy is higher, select the cryptosystem with higher processing load on the cryptographic processing in the encryption communication when the synchronization accuracy is lower, and select the cryptosystem with higher processing load on the cryptographic processing in the encryption communication than the cryptosystem at the time when the synchronization accuracy is lower, and set so as not to change the cryptosystem, when the synchronization accuracy is asynchronous; and determine whether synchronization accuracy is higher, lower or asynchronous by using predetermined information, the synchronization accuracy representing a frequency of timings at which a cryptosystem used for encryption communication between the communication device (100, 300) and another communication device (100, 300) can be changed in synchronization, select the cryptosystem with lower processing load on cryptographic processing in the encryption communication when the synchronization accuracy is higher, select the cryptosystem with higher processing load on the cryptographic processing in the encryption communication when the synchronization accuracy is lower, and select the cryptosystem with higher processing load on the cryptographic processing in the encryption communication than the cryptosystem at the time when the synchronization accuracy is lower, and set so as not to change the cryptosystem, when the synchronization accuracy is asynchronous; and cryptographic processing means (102, 305) configured to execute at least one of encryption processing and decryption processing on communication data with the another communication device by using the cryptosystem selected.