Secret key backup is safely implemented even if a role base access structure in which the access structure is specified using roles is used. An all combination generating unit 107 obtains a backup participating user list 201 which is a list of backup participating users and a list of validated roles validated by the users, and a role base access structure 202 which is a combination of specified roles by which a secret key 205 can be restored, and generates an all combination extracted result which is all combinations of restoration enabling users of the secret key by applying users described in the backup participating user list 201 to the specified role. A same user/role deleting unit 108, etc. deletes a combination showing the same user redundantly, etc. from the all combination extracted result, a general access structure secret distributing unit 114 generates fragments of secret key from the secret key, and distributes the fragments of secret key to the combinations of users from which the redundancy is removed.