Paper 2023/1201

Privacy-preserving edit distance computation using secret-sharing two-party computation

Hernán Darío Vanegas Madrigal
Daniel Cabarcas Jaramillo
Diego F. Aranha, Aarhus University

The edit distance is a metric widely used in genomics to measure the similarity of two DNA chains. Motivated by privacy concerns, we propose a 2PC protocol to compute the edit distance while preserving the privacy of the inputs. Since the edit distance algorithm can be expressed as a mixed-circuit computation, our approach uses protocols based on secret-sharing schemes like Tinier and SPD$\mathbb{Z}_{2^k}$; and also daBits to perform domain conversion and edaBits to perform arithmetic comparisons. We modify the Wagner-Fischer edit distance algorithm, aiming at reducing the number of rounds of the protocol, and achieve a flexible protocol with a trade-off between rounds and multiplications. We implement our proposal in the MP-SPDZ framework, and our experiments show that it reduces the execution time respectively by 81\% and 54\% for passive and active security with respect to a baseline implementation in a LAN. The experiments also show that our protocol reduces traffic by two orders of magnitude compared to a BMR-MASCOT implementation.

Available format(s)
Publication info
Published elsewhere. LATINCRYPT 2023
Edit distancesecure MPCsecret-sharing schemes
Contact author(s)
hdvanegasm @ unal edu co
dcabarc @ unal edu co
dfaranha @ cs au dk
2023-08-10: approved
2023-08-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hernán Darío Vanegas Madrigal and Daniel Cabarcas Jaramillo and Diego F. Aranha},
      title = {Privacy-preserving edit distance computation using secret-sharing two-party computation},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1201},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.