Privacy-preserving edit distance computation using secret-sharing protocols

Abstract

La distancia de edición entre dos cadenas en un alfabeto es el mínimo número de inserciones, borrados y reemplazamientos que se necesitan para transformar una de las cadenas en la otra. Esta métrica es ampliamente utilizada en aplicaciones de la genómica para determinar la similitud de dos cadenas de ADN, lo cual tiene sus usos en estudios médicos y biológicos. A pesar de los beneficios de computar la distancia de edición entre dos cadenas de ADN, existen riesgos a la privacidad como la reidentificación, donde un adversario que posee una cadena de ADN puede extraer información privada de su propietario. Para atender estos riesgos a la privacidad, hemos propuesto un protocolo para dos participantes usando circuitos mixtos mediante esquemas de secreto compartido como Tinier y SPDZ_{2^k} para computar la distancia de edición preservando la privacidad de las cadenas usadas en el cómputo. Además, usamos daBits para realizar conversiones entre dominios, y eda\-Bits para computar comparaciones aritméticas. Nuestro trabajo se enfoca en protocolos cuyo dominio computacional subyacente son anillos de la forma Z_{2^k}. En este trabajo implementamos nuestra propuesta en el framework MP-SDPZ, y mediante una evaluación experimental simulando una red de área local, hemos encontrado que nuestra propuesta alcanza una reducción en el tiempo de ejecución de aproximadamente un 64% en el caso de seguridad activa, y un 78% en el caso de seguridad pasiva con respecto a una implementación tradicional del algoritmo Wagner-Fischer. En los experimentos mostramos que nuestro protocolo tiene una reducción de datos enviados a la red entre un 57-99% aproximadamente en comparación a una implementación usando \textit{garbled circuits}, y una reducción de 40% aproximadamente con respecto a implementaciones que usan encripción homomórfica encontradas en trabajos anteriores. (texto tomado de la fuente)

The edit distance between two strings in an alphabet is the minimum number of insertions, deletions, and replacements that need to be done to transform one of the strings into the other. This metric is widely used in genomic applications to determine the similarity of two DNA chains which has its uses in medical and biological studies. Despite the benefits of computing the edit distance between DNA chains, there are privacy risks like re-identification, where an adversary having a DNA chain can extract private information about its owner. To attend to such privacy concerns, we propose a two-party MPC protocol using mixed-circuit computations through secret-sharing schemes like Tinier and SPDZ_{2^k} to compute the edit distance while preserving the privacy of the DNA chains used as inputs. Also, we use daBits to perform domain conversion and edaBits to perform arithmetic comparisons. Our work focuses on protocols whose underlying computational domains are rings of the form Z_{2^k}. We implement our proposal in the MP-SPDZ framework, and through experimental evaluation simulating a local area network, we show that our proposal reaches a reduction in the execution time of approximately a 64% for active security and 78% for passive security with respect to a traditional implementation of the Wagner-Fischer algorithm. In the experiments, we show that our protocol has a reduction in the data sent of approximately 57-99% compared to a garbled circuit implementation and a reduction of the execution time of approximately 40% with respect to approaches using homomorphic encryption found in previous works.