Contributions to secure multicast and privacy-preserving computations on peer-to-peer networks

Abstract

El termino privacidad engloba un amplio campo de investigacion compuesto por diferentes areas. Esta tesis doctoral se centra en dos de ellas. La primera son las comunicaciones privadas en grupos restringidos, o secure multicast. Un grupo de participantes desea mantener comunicaciones de forma que ningun oyente externo al grupo sea capaz de interpretar la informacion transmitida. Este problema tiene diferentes aplicaciones como servicios pay-per-view en plataformas de streaming multimedia o multiconferencias privadas en el ambito empresarial e incluso militar. La solucion estandar al problema consiste en establecer una clave de cifrado simetrico comun al grupo, llamada session key o clave de sesion, con la cual todos los participantes cifran o descifran la informacion transmitida. Sin embargo, las implicaciones practicas de esta solucion no son triviales por dos motivos: el uso de una misma clave de cifrado durante largo tiempo la hace vulnerable a ataques, y los cambios en la composicion del grupo (un fenomeno conocido como churn), de ocurrir, fuerzan a cambiar la clave despues de cada entrada o salida de participantes. Por ello es necesario refrescar la clave de sesion periodicamente, y en especial despues de cada cambio en la composicion del grupo. El capitulo 1 introduce mas formalmente estos conceptos y da al lector una vision mas amplia del problema. Las propuestas de secure multicast existentes pueden clasificarse en tres categorias dependiendo de como realicen la renovacion de la clave de sesion: centralizadas, descentralizadas y distribuidas. En las primeras, una entidad central, el Key Server o Servidor de Claves, esta a cargo del establecimiento de nuevas claves de sesion y la distribucion a toda la red. Esta es la forma mas sencilla y popular de resolver el problema a cambio de soportar tamanos de grupo limitados. La segunda categoria, las propuestas descentralizadas, es una extension natural de la primera: para conseguir mayores tamanos de grupo los participantes se distribuyen en subgrupos disjuntos, cada uno gestionado por un Servidor de Claves secundario mediante secure multicast centralizado. Finalmente, en las propuestas distribuidas no existe una unica entidad a cargo del proceso de renovacion de claves. En su lugar, todos los participantes colaboran en la generacion del material criptografico cada vez que sea necesario. Los esquemas distribuidos ofrecen por tanto mas fiabilidad al evitar un unico punto de fallo a cambio de una escalabilidad muy limitada. Esta tesis se enfoca hacia la categoria centralizada debido a su importancia como solucion en si misma y como pilar de construcciones descentralizadas. El capitulo 2 realiza una amplia revision del estado del arte, y el capitulo 3 presenta (i) un nuevo esquema centralizado, discute sus propiedades y pone a prueba su rendimiento. Los fundamentos matematicos del esquema se basan principalmente en el Algoritmo Extendido de Euclides, gracias al cual tambien hemos desarrollado (ii) una solucion de autenticacion para los mensajes de renovacion provenientes del Servidor de Claves, y (iii) una prueba de conocimiento cero (zero-knowledge proof) que permite a miembros legales del grupo verificar la legalidad de otros. Los tres esquemas han sido ya objeto de criptoanalisis por parte de otros investigadores, los cuales han hallado algunas vulnerabilidades en el segundo y tercero (autenticacion de mensajes y prueba de conocimiento cero). Sin embargo, el esquema principal de secure multicast sigue siendo seguro a dia de hoy. Mencionaremos las vulnerabilidades encontradas por el criptoanalisis, asi como soluciones propuestas por otro conjunto de investigadores. Dichas soluciones no son merito del autor de esta tesis y se muestran aqui con el unico proposito de dar al lector una perspectiva completa. La segunda parte de esta tesis se centra en computaciones distribuidas con preservacion de privacidad. En este caso, los nodos que conforman una red desean seguir la evolucion de una variable global a la que todo el mundo contribuye. Sin embargo, las contribuciones individuales hechas por cada nodo no deberian ser conocidas por los demas. Un ejemplo tipico, muy ilustrativo, es el Problema de los millonarios: dos millonarios quieren saber quien es mas rico sin revelar la cuantia de sus fortunas. Situaciones similares, especialmente aquellas que involucran un numero indeterminado de participantes y el computo de otras funciones, son utiles a la hora realizar agregacion de datos, calculo de confianza y mineria de datos, operaciones todas de creciente interes. El problema de la preservacion de privacidad en computacion distribuida no es nuevo: existen ya un amplio numero de soluciones. Sin embargo, la mayoria de ellas es aplicable solo a un grupo reducido de participantes y no suelen ser tolerantes a fallos. El autor de esta tesis cree que esas dos caracteristicas van a cobrar mucha importancia con el tiempo debido a la popularizacion de diferentes tipos de redes. Por ejemplo, en redes peer-to-peer los nodos pueden entrar y salir de la red de forma inesperada (tal y como hemos comentado previamente para los escenarios de secure multicast), y los calculos no deberian detenerse o reiniciarse por ello. En redes de sensores (wireless sensor networks) el medio de transmision es propenso a fallos, y tambien los participantes pueden aparecer y desaparecer sin previo aviso. El capitulo 4 repasa de la literatura disponible en este campo. En vista de la importancia de la tolerancia a fallos y al dinamismo de las redes, en el capitulo 5 hemos desarrollado un algoritmo de computo distribuido iterativo con preservacion de privacidad enfocado a redes peer-to-peer que se adapta a ese tipo de situaciones practicas. Nuestro algoritmo sigue un modelo de paso de mensajes asincrono que tolera churn y perdida o retraso de mensajes de forma natural, en oposicion a los algoritmos sincronos. Para demostrarlo, lo comparamos con una propuesta sincrona parecida tomada de la literatura. Creemos que nuestro algoritmo es el primero de este tipo. La literatura en este campo considera dos modelos de adversario a tener en cuenta: semi-honestos y maliciosos. Los primeros analizan cualquier dato a su disposicion para obtener informacion privada de otros participantes, pero se asume que ejecutan el protocolo de forma correcta. De los segundos se espera que lleven a cabo acciones arbitrarias para obtener la informacion privada deseada, tales como enviar mensajes falsos. Nuestro algoritmo tolera adversarios semi-honestos. A modo de resumen de lo anterior, la presente tesis (i) analiza el estado del arte en algoritmos de secure multicast centralizado, (ii) presenta una solucion de secure multicast centralizada con bajos requerimientos computacionales asi como algoritmos complementarios para la autenticacion de los mensajes de refresco y los miembros, (iii) repasa el estado del arte en computacion distribuida con preservacion de privacidad y (iv) presenta un algoritmo iterativo asincrono para computacion distribuida con preservacion de privacidad que tolera churn y fallos en el envio de mensajes.