An encrypted text matching system comprising: means for generating first auxiliary data and second auxiliary data (16, 303), respectively, which are for verification of matching between a first encrypted text that is obtained by encrypting at least one of a plurality of data segments into which input data is divided by segmenting means and that is registered with a storage device and a second encrypted text that is obtained by encrypting at least one of a plurality of data segments into which input data to be matched is divided by segmenting means, the verification being performed by using a Hamming distance between plaintexts; and means for taking a difference between the first encrypted text and the second encrypted text, and determining whether a Hamming distance between plaintexts that corresponds to the difference between the first encrypted text and the second encrypted text is equal to or less than a predetermined certain value by using the first auxiliary data and the second auxiliary data, wherein the encrypted text is a result of an exclusive OR operation between a code word, which is obtained by encoding a key for encrypting the plaintext of the data segment of the input data with an error-correcting code having linearity, and the plaintext, and wherein the system is configured to calculate each of the first auxiliary data and the second auxiliary data that are related to the first encrypted text and the second encrypted text, respectively, based on an exclusive OR between an inner product of the corresponding key and a constant, and an output of a cryptographic hash function for a bit string that is based on the corresponding encrypted text. means for generating first auxiliary data and second auxiliary data (16, 303), respectively, which are for verification of matching between a first encrypted text that is obtained by encrypting at least one of a plurality of data segments into which input data is divided by segmenting means and that is registered with a storage device and a second encrypted text that is obtained by encrypting at least one of a plurality of data segments into which input data to be matched is divided by segmenting means, the verification being performed by using a Hamming distance between plaintexts; and means for taking a difference between the first encrypted text and the second encrypted text, and determining whether a Hamming distance between plaintexts that corresponds to the difference between the first encrypted text and the second encrypted text is equal to or less than a predetermined certain value by using the first auxiliary data and the second auxiliary data, wherein the encrypted text is a result of an exclusive OR operation between a code word, which is obtained by encoding a key for encrypting the plaintext of the data segment of the input data with an error-correcting code having linearity, and the plaintext, and wherein the system is configured to calculate each of the first auxiliary data and the second auxiliary data that are related to the first encrypted text and the second encrypted text, respectively, based on an exclusive OR between an inner product of the corresponding key and a constant, and an output of a cryptographic hash function for a bit string that is based on the corresponding encrypted text.