The random number generating unit 222 randomly generates an integer s. The first ciphertext generating unit 241 generates a first ciphertext C1 by encrypting the plaintext M, based on the integer s. The second ciphertext generating unit 242 generates a second ciphertext C2, based on the integer s and a recipient ID. The third ciphertext generating unit 243 generates a third ciphertext C3, based on the integer s. The hash value calculation unit 244 calculates a hash value H0 by combining the first ciphertext C1, the second ciphertext C2, and the third ciphertext C3. The fourth ciphertext generating unit 245 generates a fourth ciphertext C4, based on the hash value H0. The ciphertext combining unit 246 generates a ciphertext C by combining the first ciphertext C1, the second ciphertext C2, the third ciphertext C3, and the fourth ciphertext C4. Thus, it is possible to provide an ID-based public key cryptographic communication system being secure even when transmitting ciphertexts generated by encrypting the same plaintext to a plurality of recipients.