An authenticated device 200 includes a memory unit 220 to store at least one algorithm identifier and at least one encryption key identifier, a transmitting unit 212 to transmit at least one algorithm identifier and at least one encryption key identifier stored by the memory unit 220 to an authenticating device 100, a receiving unit 211 to receive a prescribed algorithm identifier and a prescribed encryption key identifier selected from among at least one algorithm identifier and at least one encryption key identifier transmitted by the transmitting unit 212 from the authenticating device 100, and an authentication processing unit 296 to perform an authentication process with the authenticating device 100 based on the prescribed algorithm identifier and the prescribed encryption key identifier received by the receiving unit 211.