Cryptology ePrint Archive: Report 2015/132

Homomorphic Computation of Edit Distance

Jung Hee Cheon and Miran Kim and Kristin Lauter2

Abstract: These days genomic sequence analysis provides a key way of understanding the biology of an organism. However, since these sequences contain much private information, it can be very dangerous to reveal any part of them. It is desirable to protect this sensitive information when performing sequence analysis in public. As a first step in this direction, we present a method to perform the edit distance algorithm on encrypted data to obtain an encrypted result. In our approach, the genomic data owner provides only the encrypted sequence, and the public commercial cloud can perform the sequence analysis without decryption. The result can be decrypted only by the data owner or designated representative holding the decryption key.

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