Privacy-preserving edit distance computation using secret-sharing protocols

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)

• Autores: Vanegas Madrigal, Hernán Darío
• Fecha de publicación: 2023
• Institución: Universidad Nacional de Colombia
• Repositorio: Universidad Nacional de Colombia
• Idioma: eng
• OAI Identifier: oai:repositorio.unal.edu.co:unal/85504
• Acceso en línea: https://repositorio.unal.edu.co/handle/unal/85504; https://repositorio.unal.edu.co/
• Palabra clave: 510 - Matemáticas::519 - Probabilidades y matemáticas aplicadas; Secure multi-party computation; Edit distance; Secret-sharing; Computación segura de múltiples participantes; Distancia de edición; Secreto compartido; Secreto compartido
• Rights: openAccess
• License: Reconocimiento 4.0 Internacional