CINXE.COM
SecurED: Secure Multiparty Edit Distance for Genomic Sequences
<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no"> <link href="/css/dist/css/bootstrap.min.css" rel="stylesheet"> <title>SecurED: Secure Multiparty Edit Distance for Genomic Sequences</title> <link rel="stylesheet" href="/css/eprint.css?v=10"> <style> a.toggle-open:after { content:' -'; font-weight: 800; } a.toggle-closed:after { content: " ›"; font-weight: 800; } .paper-abstract { white-space: pre-wrap; } #metadata dt { margin-top: 1rem; } #metadata dt + dd { /* gap between dt and first dd */ margin-top: .75rem; } #metadata dd { margin-left: 2rem; } #metadata dd.keywords { padding-bottom: .5rem; } span.authorName { margin-top: .5rem; font-style: italic; } </style> <script> MathJax = { tex: { inlineMath: [['$', '$'], ['\\(', '\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEnvironments: false }, loader: { load: [ "ui/safe", "ui/lazy", ], }, options: { safeOptions: { allow: { URLs: "none", classes: "safe", cssIDs: "safe", styles: "safe", }, }, } }; </script> <script id="MathJax-script" async src="/js/mathjax/tex-chtml.js"></script> <meta name="citation_title" content="SecurED: Secure Multiparty Edit Distance for Genomic Sequences"> <meta name="citation_author" content="Jiahui Gao"> <meta name="citation_author" content="Yagaagowtham Palanikuma"> <meta name="citation_author" content="Dimitris Mouris"> <meta name="citation_author" content="Duong Tung Nguyen"> <meta name="citation_author" content="Ni Trieu"> <meta name="citation_journal_title" content="Cryptology ePrint Archive"> <meta name="citation_publication_date" content="2025"> <meta name="citation_pdf_url" content="https://eprint.iacr.org/2025/500.pdf"> <meta property="og:image" content="https://eprint.iacr.org/img/iacrlogo.png"/> <meta property="og:image:alt" content="IACR logo"/> <meta property="og:url" content="https://eprint.iacr.org/2025/500"> <meta property="og:site_name" content="IACR Cryptology ePrint Archive" /> <meta property="og:type" content="article" /> <meta property="og:title" content="SecurED: Secure Multiparty Edit Distance for Genomic Sequences" /> <meta property="og:description" content="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 secureED, 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." /> <meta property="article:section" content="PROTOCOLS" /> <meta property="article:modified_time" content="2025-03-18T00:06:15+00:00" /> <meta property="article:published_time" content="2025-03-16T23:09:02+00:00" /> <meta property="article:tag" content="Applied Cryptography" /> <meta property="article:tag" content="Dynamic Programming" /> <meta property="article:tag" content="DNA Matching" /> <meta property="article:tag" content="Edit Distance" /> <meta property="article:tag" content="Genomics" /> <meta property="article:tag" content="Multiparty Computation" /> </head> <body> <noscript> <h1 class="text-center">What a lovely hat</h1> <h4 class="text-center">Is it made out of <a href="https://iacr.org/tinfoil.html">tin foil</a>?</h4> </noscript> <div class="fixed-top" id="topNavbar"> <nav class="navbar navbar-custom navbar-expand-lg"> <div class="container px-0 justify-content-between justify-content-lg-evenly"> <div class="order-0 align-items-center d-flex"> <button class="navbar-toggler btnNoOutline" type="button" data-bs-toggle="collapse" data-bs-target="#navbarContent" aria-controls="navbarContent" aria-expanded="false"> <span class="icon-bar top-bar"></span> <span class="icon-bar middle-bar"></span> <span class="icon-bar bottom-bar"></span> </button> <a class="d-none me-5 d-lg-inline" href="https://iacr.org/"><img class="iacrlogo" src="/img/iacrlogo_small.png" alt="IACR Logo" style="max-width:6rem;"></a> </div> <a class="ePrintname order-1" href="/"> <span class="longNavName">Cryptology ePrint Archive</span> </a> <div class="collapse navbar-collapse order-3" id="navbarContent"> <ul class="navbar-nav me-auto ms-2 mb-2 mb-lg-0 justify-content-end w-100"> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> Papers </a> <ul class="dropdown-menu me-3" aria-labelledby="navbarDropdown"> <span class="text-dark mx-3" style="white-space:nowrap;">Updates from the last:</span> <li><a class="dropdown-item ps-custom" href="/days/7">7 days</a></li> <li><a class="dropdown-item ps-custom" href="/days/31">31 days</a></li> <li><a class="dropdown-item ps-custom" href="/days/183">6 months</a></li> <li><a class="dropdown-item ps-custom" href="/days/365">365 days</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/byyear">Listing by year</a></li> <li><a class="dropdown-item" href="/complete">All papers</a></li> <li><a class="dropdown-item" href="/complete/compact">Compact view</a></li> <li><a class="dropdown-item" href="https://www.iacr.org/news/subscribe">Subscribe</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/citation.html">How to cite</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/rss">Harvesting metadata</a></li> </ul> </li> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="submissionsDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> Submissions </a> <ul class="dropdown-menu me-3" aria-labelledby="submissionsDropdown"> <li><a class="dropdown-item" href="/submit">Submit a paper</a></li> <li><a class="dropdown-item" href="/revise">Revise or withdraw a paper</a></li> <li><a class="dropdown-item" href="/operations.html">Acceptance and publishing conditions</a></li> </ul> </li> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="aboutDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> About </a> <ul class="dropdown-menu me-3" aria-labelledby="aboutDropdown"> <li><a class="dropdown-item" href="/about.html">Goals and history</a></li> <li><a class="dropdown-item" href="/news.html">News</a></li> <li><a class="dropdown-item" href="/stats">Statistics</a></li> <li><a class="dropdown-item" href="/contact.html">Contact</a></li> </ul> </li> </ul> </div> <div class="dropdown ps-md-2 text-right order-2 order-lg-last"> <button class="btn btnNoOutline" type="button" id="dropdownMenuButton1" data-bs-toggle="dropdown" aria-expanded="false"> <img src="/img/search.svg" class="searchIcon" alt="Search Button"/> </button> <div id="searchDd" class="dropdown-menu dropdown-menu-end p-0" aria-labelledby="dropdownMenuButton1"> <form action="/search" method="GET"> <div class="input-group"> <input id="searchbox" name="q" type="search" class="form-control" autocomplete="off"> <button class="btn btn-secondary border input-group-append ml-2"> Search </button> </div> </form> <div class="ms-2 p-1 d-none"><a href="/search">Advanced search</a></div> </div> </div> </div> </nav> </div> <main id="eprintContent" class="container px-3 py-4 p-md-4"> <div class="row mt-4"> <div class="col-md-7 col-lg-8 pe-md-5"> <h4>Paper 2025/500</h4> <h3 class="mb-3">SecurED: Secure Multiparty Edit Distance for Genomic Sequences</h3> <div class="author"><span class="authorName">Jiahui Gao</span><span class="affiliation">, Arizona State University</span></div> <div class="author"><span class="authorName">Yagaagowtham Palanikuma</span><span class="affiliation">, Arizona State University</span></div> <div class="author"><span class="authorName">Dimitris Mouris</span><a class="ms-1" target="_blank" href="https://orcid.org/0000-0002-2601-203X"><img class="align-baseline orcidIcon" src="/img/orcid.svg"></a><span class="affiliation">, Nillion</span></div> <div class="author"><span class="authorName">Duong Tung Nguyen</span><span class="affiliation">, Arizona State University</span></div> <div class="author"><span class="authorName">Ni Trieu</span><span class="affiliation">, Arizona State University</span></div> <h5 class="mt-3">Abstract</h5> <p style="white-space: pre-wrap;">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 secureED, 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.</p> </div> <div id="metadata" class="col-md-5 col-lg-4 ps-md-5 mt-4 mt-md-0"> <h5>Metadata</h5> <dl> <dt> Available format(s) </dt> <dd> <a class="btn btn-sm btn-outline-dark" href="/2025/500.pdf"> <img class="icon" src="/img/file-pdf.svg">PDF</a> </dd> <dt>Category</dt> <dd><a href="/search?category=PROTOCOLS"><small class="badge category category-PROTOCOLS">Cryptographic protocols</small></a></dd> <dt>Publication info</dt> <dd>Published elsewhere. PoPETs 2025</dd> <dt>DOI</dt> <dd><a href="https://doi.org/10.56553/popets-2025-0072" target="_blank" class="ms-1">10.56553/popets-2025-0072 <img src="/img/open-outline.svg" style="height:1.25rem;"></a></dd> <dt>Keywords</dt> <dd class="keywords"><a href="/search?q=Applied%20Cryptography" class="me-2 badge bg-secondary keyword">Applied Cryptography</a><a href="/search?q=Dynamic%20Programming" class="me-2 badge bg-secondary keyword">Dynamic Programming</a><a href="/search?q=DNA%20Matching" class="me-2 badge bg-secondary keyword">DNA Matching</a><a href="/search?q=Edit%20Distance" class="me-2 badge bg-secondary keyword">Edit Distance</a><a href="/search?q=Genomics" class="me-2 badge bg-secondary keyword">Genomics</a><a href="/search?q=Multiparty%20Computation" class="me-2 badge bg-secondary keyword">Multiparty Computation</a></dd> <dt>Contact author(s)</dt> <dd><span class="font-monospace"> jgao76<span class="obfuscate"> @ </span>asu edu<br>ypalanik<span class="obfuscate"> @ </span>asu edu<br>dimitris<span class="obfuscate"> @ </span>nillion com<br>duongnt<span class="obfuscate"> @ </span>asu edu<br>nitrieu<span class="obfuscate"> @ </span>asu edu </span> </dd> <dt>History</dt> <dd>2025-03-18: revised</dd> <dd>2025-03-16: received</dd> <dd><a rel="nofollow" href="/archive/versions/2025/500">See all versions</a></dd> <dt>Short URL</dt> <dd><a href="https://ia.cr/2025/500">https://ia.cr/2025/500</a></dd> <dt>License</dt> <dd><a rel="license" target="_blank" href="https://creativecommons.org/licenses/by/4.0/"> <img class="licenseImg" src="/img/license/CC_BY.svg" alt="Creative Commons Attribution" title="Creative Commons Attribution"><br> <small>CC BY</small> </a> </dd> </dl> </div> </div> <p class="mt-4"><strong>BibTeX</strong> <button id="bibcopy" class="ms-2 btn btn-sm btn-outline-dark" aria-label="Copy to clipboard" onclick="copyBibtex()"> <img src="/img/copy-outline.svg" class="icon">Copy to clipboard</button></p> <pre id="bibtex"> @misc{cryptoeprint:2025/500, author = {Jiahui Gao and Yagaagowtham Palanikuma and Dimitris Mouris and Duong Tung Nguyen and Ni Trieu}, title = {{SecurED}: Secure Multiparty Edit Distance for Genomic Sequences}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/500}, year = {2025}, doi = {10.56553/popets-2025-0072}, url = {https://eprint.iacr.org/2025/500} } </pre> <script> var bibcopy; function triggerTooltip() { console.log('setting tooltip'); } window.onload = triggerTooltip; function copyBibtex() { let range = document.createRange(); range.selectNode(document.getElementById('bibtex')); window.getSelection().removeAllRanges(); window.getSelection().addRange(range); document.execCommand('copy'); window.getSelection().removeAllRanges(); let bibcopy = document.getElementById('bibcopy'); let copyTooltip = new bootstrap.Tooltip(bibcopy, {trigger: 'manual', title: 'Copied!'}); copyTooltip.show(); setTimeout(function() { copyTooltip.dispose(); }, 2000); } </script> </main> <div class="container-fluid mt-auto" id="eprintFooter"> <a href="https://iacr.org/"> <img id="iacrlogo" src="/img/iacrlogo_small.png" class="img-fluid d-block mx-auto" alt="IACR Logo"> </a> <div class="colorDiv"></div> <div class="alert alert-success w-75 mx-auto"> Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content. </div> </div> <script src="/css/bootstrap/js/bootstrap.bundle.min.js"></script> <script> var topNavbar = document.getElementById('topNavbar'); if (topNavbar) { document.addEventListener('scroll', function(e) { if (window.scrollY > 100) { topNavbar.classList.add('scrolled'); } else { topNavbar.classList.remove('scrolled'); } }) } </script> </body> </html>