Efficient Secure Computation of Edit Distance on Genomic Data

Genetic data are the most sensitive information for a person, containing many specific features that uniquely determine an individual and also make it possible to trace relationships with other people or evaluate the pre- disposition to particular diseases. For this reason, any processing of genetic data should be carefully performed and any threat to their privacy properly considered. A very important computation in medical and public health domains involves the evaluation of the edit distance between human genomes, that can eventually lead to a better diagnosis of several diseases. To maintain the privacy of the genetic data, it is possible to apply secure computation protocols and then, in this context, the improvement of the computational performance of such techniques is a key factor for real-world application scenarios. In this paper we focus on the application of the garbling circuit technique for the computation of the edit dis- tance, showing its efficiency. We apply the technique considering four different algorithms and compare their performances to the best previous results found in literature. We show that the Ukkonen algorithm with gener- alized cut-off is the one that performed better among the considered algorithms, reporting some experimental results obtained considering datasets composed of both randomly generated and real genomic strings