SecureED: Secure Multiparty Edit Distance for Genomic Sequences
Authors: Jiahui Gao (Arizona State University), Yagaagowtham Palanikumar (Arizona State University), Dimitris Mouris (Nillion), Duong Nguyen (Arizona State University), Ni Trieu (Arizona State University)
Volume: 2025
Issue: 2
Pages: 479–493
DOI: https://doi.org/10.56553/popets-2025-0072
Abstract: DNA edit distance (ED) measures the minimum number of single nucleotide insertions, substitutions, or deletions required to convert a DNA sequence into another. ED has broad applications in healthcare such as sequence alignment, genome assembly, functional annotation, and drug discovery. Privacy-preserving computation is essential in this context to protect sensitive genomic data. Nonetheless, the existing secure DNA edit distance solutions lack efficiency when handling large data sequences or resort to approximations and fail to accurately compute the metric. In this work, we introduce ScureED, a protocol that tackles these limitations, resulting in a significant performance enhancement of approximately 2-24 times compared to existing methods. Our protocol computes a secure ED between two genomes, each comprising 1,000 letters, in just a few seconds. The underlying technique of our protocol is a novel approach that transforms the established approximate matching technique (i.e., the Ukkonen algorithm) into exact matching, exploiting the inherent similarity in human DNA to achieve cost-effectiveness. Furthermore, we introduce various optimizations tailored for secure computation in scenarios with a limited input domain, such as DNA sequences composed solely of the four nucleotide letters.
Keywords: applied cryptography, dynamic programming, DNA matching, edit distance, genomics, multiparty computation
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
