According to one embodiment of the invention, there is provided an information recording and reproducing apparatus which records information in a recording medium and reproduces information recorded in the recording medium, the information recording and reproducing apparatus includes a first recording section which records in the recording medium an encrypted encryption key aggregate where at least one encryption key for encrypting each of a plurality of pieces of information has been encrypted and registered and information encrypted using the encryption key, a second recording section which records encrypted first private key information used to encrypt or decrypt the encryption key into the recording medium and which, if the encrypted encryption key aggregate has not been recorded in the recording medium, records the first private key information into the recording medium only when the encrypted encryption key aggregate is recorded in the recording medium.