Estudio e emplementación de un esquema de PSI (Private Set Intersection) descentralizado

Abstract

El matemático estadounidense Leonard Dickson (1874-1954) expresó en su época: ”Thank God that number theory is unsullied by any application”. Sin embargo, lo que Dickson no pudo prever en su momento es que con la llegada de las computadoras, la teoría de números encontraría aplicaciones de gran relevancia en dicho campo. Una de las áreas donde está se manifiesta de manera notable es en el campo de la criptografía, donde la teoría de números juega un papel fundamental en el diseño y la seguridad de los sistemas criptográficos. Uno de estos esquemas, los PSI (Private Set Intersection), son sistemas criptográficos de gran relevancia en la actualidad. Estos hacen uso de técnicas de encriptación homomórfica para abordar un problema emergente: la necesidad de que dos entidades sin confianza mutua puedan encontrar la intersección de dos conjuntos de datos sin exponer información adicional. Este tipo de técnicas encuentra aplicación en campos como la publicidad, medicina o el descubrimiento de contactos mutuos sin revelar información sensible. Recientemente, se han propuesto extensiones de estos protocolos para múltiples entidades, como grupos de usuarios, en una red social segura o en sistemas de mensajería. En este trabajo, se estudiará la implementación de sistemas clásicos con criptosistema homomórficos como el de Paillier, así como propuestas más recientes como el de Damgard-Jurik. Se comparará su rendimiento utilizando métricas como el tamaño de los mensajes para un nivel de seguridad dado, así como el tamaño de las claves definidas.

The American mathematician Leonard Dickson (1874-1954) expressed in his time: ”Thank God that number theory is unsullied by any application.”However, what Dickson could not foresee at the time is that with the arrival of computers, number theory would find highly relevant applications in this field. One of the areas where this manifests itself notably is in the field of cryptography, where number theory plays a fundamental role in the design and security of cryptographic systems. One of these schemes, PSI (Private Set Intersection), are cryptographic systems of great relevance today. These make use of homomorphic encryption techniques to address an emerging problem: the need for two entities without mutual trust to be able to find the intersection of two data sets without exposing additional information. This type of technique finds application in fields such as advertising, medicine or the discovery of mutual contacts without revealing sensitive information. Recently, extensions of these protocols have been proposed for multiple entities, such as groups of users in a secure social network or in messaging systems. In this work, the implementation of classical systems using homomorphic cryptosystems such as Paillier will be studied, as well as more recent proposals such as Damgard-Jurik. Their performance will be compared using metrics such as message size for a given security level, as well as the size of the defined keys.