Paper 2015/132

Homomorphic Computation of Edit Distance

Jung Hee Cheon, Miran Kim, and Kristin Lauter

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Workshop on Encrypted Computing and Applied Homomorphic Cryptography
Keywords
Edit distanceHomomorphic encryptionArithmetic circuit.
Contact author(s)
alfks500 @ snu ac kr
History
2015-03-04: revised
2015-02-26: received
See all versions
Short URL
https://ia.cr/2015/132
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/132,
      author = {Jung Hee Cheon and Miran Kim and Kristin Lauter},
      title = {Homomorphic Computation of Edit Distance},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/132},
      year = {2015},
      url = {https://eprint.iacr.org/2015/132}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.