Patent ID: 8625782

Claim:
A method for determining an encrypted edit distance as an encryption of a minimum cost of transformation of a first sequence into a second sequence based on an insertion cost, a deletion cost, and a substitution cost, comprising steps of: formulating the minimum cost as a dynamic programming solution of a matrix, wherein elements of the matrix are determined recursively based on values of previously determined elements; determining a current element of the matrix as an encryption of a minimum of a first element, a second element, and a third element, wherein the first element represents the insertion cost, the second element represents the deletion cost, and the third element represents the substitution costs, and wherein the current element, the first element, the second element, and the third element are homomorphically encrypted with a public key; determining the current element using a minimum-finding method, wherein the minimum-finding method is configured to determine an encryption of a minimum of numbers in homomorphically encrypted form; determining, for each of the first element, the second element, and the third element, an encrypted summation producing a set of encrypted summations, wherein the encrypted summation is determined according to ξ r′ i (μ a i +α)=(ξ r i ( a i )) μ ξ r 0 (α), wherein i=1, 2, . . . L, and L=3, μ is a scaling constant and α is an integer shift selected at random, r i , r 0 are encryption coefficients selected at random, an encryption coefficient r′ i =r i r 0 , and ξ(.) is an encryption function; transmitting from the second processor to the first processor the set of encrypted summations, wherein the first processor is configured to decrypt, the encrypted summation using a private key, to determine a minimum from the set of encrypted summations, and to encrypt the minimum with the public key to produce the current element; and receiving by the second processor the current element transmitted from the first processor; repeating the determining recursively to produce the dynamic programming solution; selecting the dynamic programming solution as the encrypted edit distance, wherein steps of the method are performed by a first processor and a second processor, such that the first sequence is stored only at a memory connected to the first processor and is kept private from the second processor, and the second sequence is stored only at a memory connected to the second processor and is kept private from the first processor; providing the public key to the first processor and to the second processor; providing a private key only to the first processor; transmitting the encrypted edit distance to the first processor; and decrypting the encrypted edit distance with the private key, wherein a distribution of computational tasks and computational complexity between the first and second processors is unequal, wherein the method is performed in the first and second processors.