Similarity calculation system, similarity calculation apparatus, similarity calculation method, and similarity calculation program

A similarity calculation apparatus calculating a distance between a first vector stored while being encrypted and a second vector entered from an input terminal, the similarity calculation apparatus:

• transmitting to the input terminal a ciphertext of each element of the first vector and a weighted distance table with respect to combinations of possible values of the elements of the first vector and possible values of the elements of the second vector;
• having the input terminal refer to the weighted distance table to calculate a ciphertext of element distances for all combinations of the value of a single element of the second vector and possible values of elements of the first vector corresponding to the single element and receiving from the input terminal a ciphertext of the sum of the element distances calculated for each element of the second vector using additive homomorphic encryption;
• and
• extracting the distance between the first and the second vectors from the ciphertext of the sum,
• wherein a plurality of the first vectors are stored in the similarity calculation apparatus and the distances between the first and the second vectors are calculated for all the first vectors, and
• wherein the similarity calculation apparatus selects from the plurality of the first vectors stored in the similarity calculation apparatus the one having the shortest distance to the second vector and transmits the values linked to the selected first vector to the input terminal.

A similarity calculation method calculating a distance between a first vector encrypted and stored in a similarity calculation apparatus and a second vector entered from an input terminal, wherein

• the similarity calculation apparatus transmits to the input terminal a ciphertext of each element of the first vector and a weighted distance table with respect to combinations of possible values of the elements of the first vector and possible values of the elements of the second vector,
• the input terminal refers to the weighted distance table to calculate a ciphertext of element distances for all combinations of the value of a single element of the second vector and possible values of elements of the first vector corresponding to the single element, calculates a ciphertext of the sum of the element distances for each element of the second vector using additive homomorphic encryption, and transmits the ciphertext of the sum to the similarity calculation apparatus, and
• the similarity calculation apparatus extracts the distance between the first and the second vectors from the ciphertext of the sum,
• wherein a plurality of the first vectors are stored in the similarity calculation apparatus and the distances between the first and the second vectors are calculated for all the first vectors, and
• wherein the method further comprises the similarity calculation apparatus selecting from the plurality of the first vectors stored in the similarity calculation apparatus the one having the shortest distance to the second vector and transmitting the values linked to the selected first vector to the input terminal.

A non-transient computer readable medium storing similarity calculation program causing a computer to calculate a distance between a first vector stored while being encrypted and a second vector entered from an input terminal, the similarity calculation program:

• transmitting to the input terminal a ciphertext of each element of the first vector and a weighted distance table with respect to combinations of possible values of the elements of the first vector and possible values of the elements of the second vector;
• having the input terminal refer to the weighted distance table to calculate a ciphertext of element distances for all combinations of the value of a single element of the second vector and possible values of elements of the first vector corresponding to the single element and receiving from the input terminal a ciphertext of the sum of the element distances calculated for each element of the second vector using additive homomorphic encryption;
• and
• extracting the distance between the first and the second vectors from the ciphertext of the sum,
• wherein a plurality of the first vectors are stored in the similarity calculation apparatus and the distances between the first and the second vectors are calculated for all the first vectors, and
• wherein the similarity calculation program further causes the computer to select from the plurality of the first vectors stored in the similarity calculation apparatus the one having the shortest distance to the second vector and transmit the values linked to the selected first vector to the input terminal.