Method for privacy-preserving computation of edit distance of symbol sequences
US8625782B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 9, 2010 |
| Grant date | Jan 7, 2014 |
| Priority date | — |
| Expiry date | Aug 5, 2032 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L2209/50
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
Embodiments of the invention discloses a system and 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. The method determines recursively a current element of the matrix as an encryption of a minimum of a first element, a second element, and a third element to produce the dynamic programming solution, 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; and selects the dynamic programming solution as the encrypted edit distance, wherein steps of the method are performed by a first processor and a second processor.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.