In this paper, we describe how to calculate edit distance on encrypted data with a somewhat homomorphic encryption scheme and analyze its performance. More precisely, given two encrypted sequences of lengths n and m, we show that a somewhat homomorphic scheme of depth O((n + m) log log(n + m)) can evaluate the edit distance algorithm in O(nm log(n + m)) homomorphic computations. In the case of n = m, the depth can be brought down to O(n) using our optimization technique. Finally, we present the estimated performance of the edit distance algorithm and verify it by implementing it for short DNA sequences.
Category / Keywords: Edit distance, Homomorphic encryption, Arithmetic circuit. Original Publication (with minor differences): Workshop on Encrypted Computing and Applied Homomorphic Cryptography Date: received 18 Feb 2015, last revised 3 Mar 2015 Contact author: alfks500 at snu ac kr Available format(s): PDF | BibTeX Citation Version: 20150304:063251 (All versions of this report) Short URL: ia.cr/2015/132