In a key-insulated cryptosystem according to the present invention, a plurality of external devices are associated with a number of updates of a terminal secret key which has already been updated, and a different piece of secret information is stored in each of the external devices. In addition, a key-updating method in the key-insulated cryptosystem according to the present invention includes steps of: selecting one of the external devices depending on the number of updates of the terminal secret key; and causing the selected external device to generate key-updating information used for updating the terminal secret key based on the number of updates and the stored secret information.