An authenticating device communicating with a server device includes: a dividing unit that divides secret information into plural secret fragments by a threshold secret sharing scheme; a first generating unit that generates plural cryptographic fragments by encrypting the secret fragments using first plural passwords; a first transmitting unit that transmits the cryptographic fragments to the server device; a first receiving unit that receives the cryptographic fragments from the server device, a second generating unit that generates plural secret fragment candidates by decrypting the cryptographic fragments using second plural passwords; a third generating unit that obtains a verifying information candidate by the threshold secret sharing scheme using a group of the secret fragment candidates; a second transmitting unit that transmits the verifying information candidate to the server device; and a second receiving unit that receives result information of comparing the verifying information candidate with verifying information in the server device.