An apparatus generates first shared information that is shared by the apparatus and a recording medium by performing a first bilateral authentication. The apparatus encrypts overwrite data that is used to erase key information item recorded in the recording medium using the first shared information. Encrypted overwrite data is transferred to the recording medium. Second shared information is generated and shared by the apparatus and the recording medium by performing a second bilateral authentication between them. The apparatus receives data that is encrypted using the second shared information and that has been used by the recording medium for erasing key information. Encrypted data is decrypted using second shared information item and key information recorded in the recording medium is erased when the decrypted data is identical to overwrite data.