The client includes a random number generation unit which generates a random number, a concealed information storage unit which stores concealed information generated by concealing registered information and the generated random number using a secret key, and a response computation unit which, on the basis of a challenge transmitted from the server, the collation information input for collation with the registered information, and the concealed information, computes a response corresponding to the challenge and including a concealed index, generated by concealing an index indicating closeness between the registered information and the collation information. The server includes a challenge generation unit which generates the challenge using a public key corresponding to the secret key, and a determination unit which uses the public key and the random number transmitted from the client to determine whether or not the response transmitted from the client corresponds to the challenge.