Optimizing Secure Edit Distance Computation for Genomic Sequences via SMC Frameworks

The rapid advancement of genomic sequencing has generated an enormous amount of data, allowing the development of personalized medicine and advanced biomedical research. However, the highly sensitive nature of genomic information poses significant privacy risks, as an individual can be uniquely identified from as few as 75 Single Nucleotide Polymorphisms (SNPs). To protect privacy of genomic data, it is possible to deploy Secure Multiparty Computation (SMC) techniques, that offer a promising solution by allowing collaborative analysis on encrypted data without revealing the underlying sequences. Recently, the speed of SMC protocols has significantly increased over time and today a combination of cryptographic, protocol, network and hardware optimizations, enables their application in important contexts and applications, to solve several real-life problems \cite{PragmaticSMPC}. In this paper, we evaluate and consider several optimizations for the computation of the Edit Distance used for genomic sequence alignment within the SMC framework. We implement and compare the performance of algorithms such as Wagner-Fischer, Ukkonen, and Damerau-Levenshtein using two distinct SMC paradigms: Garbled Circuits (via the EMP Toolkit) and Secret Sharing (via the Sequre framework). Our findings highlight the technical challenges of adapting complex algorithms to secure environments, particularly regarding data-oblivious control flow and secret memory access. Experimental results demonstrate that the Sequre framework achieves an average performance improvement of approximately 43\% in computation time compared to the EMP Toolkit across various sequence lengths. This research provides a practical foundation for secure genomic data analysis, balancing the needs of precision medicine with the fundamental right to protect privacy of genomic data.