A cryptographic communication system includes: a first cryptographic communication apparatus including a first tamper-resistant device configured to store a first key generation function and a first storage unit configured to store first individual information; and a second cryptographic communication apparatus including a second tamper-resistant device configured to store a second key generation function and a second storage unit configured to store second individual information. The first cryptographic communication apparatus generates a twelfth shared key using the first key generation function and the second individual information. The second cryptographic communication apparatus generates a twenty first shared key using the second key generation function and the first individual information.