A storing information generation apparatus obtains registration information and an identifier capable of identifying the registration information, to generate a first individual key from the common key and the identifier, and to generate storing information obtained by linearly converting the registration information using the common key and the first individual key. A matching information concealment apparatus obtains matching information to generate concealed matching information concealing the matching information using an encryption key. A concealed similarity calculation apparatus calculates a concealed similarity from the storing information and the concealed matching information. A decryption apparatus generates a second individual key from the common key and the identifier, and calculates a similarity between the registration information and the matching information from the concealed similarity, a decryption key corresponding to the encryption key, the common key, and the second individual key.