Based on an encrypted feature vector C (comparison ciphertext) encrypted with a public key pk of a decryption apparatus and an encrypted feature vector C' (target ciphertext) encrypted with the public key pk of the decryption apparatus, and a random number (temporary key) generated by a random number generation unit 303 (temporary key generation unit), an encrypted random similarity degree calculation unit 314 (interim similarity degree ciphertext calculation unit) performs calculation for calculationg a similarity degree in a first stage, with two encrypted feature vectors C and C' kept encrypted, thereby calculating a second challenge C". The decryption apparatus decrypts the second challenge C^ with a secret key sk of the decryption apparatus, and performs calculation for calculating the similarity degree in a second stage with a result of the decryption kept encrypted with the temporary key, thereby calculating a second response Z. A plaintext similarity degree extraction unit 315 (similarity degree calcu
