El creciente uso de dispositivos electrónicos potentes y la disponibilidad de redes de comunicación que proporcionan conectividad ubicua y de alto rendimiento, permite a diversas aplicaciones digitales transmitir grandes volúmenes de datos en períodos breves de tiempo. En muchas ocasiones, los datos transmitidos requieren de un canal de comunicación protegido mediante procedimientos confiables de autenticación y privacidad basados en esquemas criptográficos. Para su implementación, estos esquemas consideran problemas matemáticos que son difíciles de resolver. Aunque existe una numerosa cantidad de algoritmos criptográficos, sólo unos cuantos son utilizados en el mundo real, como lo son el conocido procedimiento de Rivest-Shamir-Ademan (RSA), y el Estándar de Firma Digital (DSS por sus siglas en inglés), debido principalmente a su resistencia y fácil implementación. Estos algoritmos son la base de varias técnicas de firma digital y protocolos de autenticación e identificación que se utilizan comúnmente en comercio electrónico, transacciones bancarias y servicios gubernamentales, entre otros. Aunado a esto, su uso ha aumentado debido a la introducción de nuevas aplicaciones, como la autenticación multifactorial y las criptodivisas. El rápido desarrollo de técnicas de criptoanálisis y el auge de la computación cuántica ponen en peligro estas medidas de seguridad, siendo la amenaza más alarmante la existencia de un algoritmo capaz de resolver eficientemente el problema de la factorización, siempre que la construcción de una computadora cuántica sea posible. Estas implicaciones sugieren que deben estudiarse y desarrollarse nuevos mecanismos de seguridad ante la posible materialización de estas amenazas. Recientemente, las pruebas de conocimiento nulo han sido consideradas como una alternativa a los protocolos de autenticación e identificación existentes, siendo la mayor ventaja que estos protocolos se basan en problemas que aún no han sido resueltos por algoritmos cuánticos. Además de los servicios de autenticación e identificación, tecnologías novedosas como el blockchain y las criptodivisas, que requieren servicios de anonimato, han mostrado las capacidades de las pruebas de conocimiento nulo: una técnica fiable para demostrar el conocimiento de datos específicos sin revelar detalles; por ejemplo, para demostrar que una cuenta tiene suficiente crédito para comprar un artículo sin conocer el saldo exacto. También se ha manifestado interés en dicha tecnología para la autenticación en el almacenamiento en la nube y en el Internet de las cosas, fomentando el desarrollo de estos protocolos.
En esta tesis nos centramos en la dificultad de encontrar isomorfismos de diseños combinatorios, específicamente sistemas de ternas de Steiner. Se realiza un estudio exhaustivo de las herramientas más importantes para probar isomorfismo. Además, se revelan algunas mejoras de estas técnicas y, con base a las observaciones de dicho análisis, se caracterizan instancias difíciles, las cuales comprenden los elementos básicos para una variedad de protocolos de conocimiento nulo.
Abstract
The increasing use of powerful electronic devices and the availability of communication networks that provide ubiquitous and high performance connectivity, allow digital applications to transmit huge volumes of data in short periods of time. In many cases, the data transmitted requires a communication channel protected by reliable authentication and privacy procedures based on cryptographic schemes. For their implementation, these schemes consider mathematical problems that are difficult to solve. Although several cryptographic algorithms exist, only a few of them are used in real world applications, such as the well-known Rivest-Shamir-Adleman procedure (RSA), and the Digital Signature Standard (DSS), mainly due to their robustness and easy implementation. These algorithms are the basis of several digital signature techniques, and authentication and identification protocols that are commonly used in e-commerce, banking transactions and government services, among others. In addition, their use has increased due to the introduction of new applications, such as multi-factor authentication and cryptocurrencies. The rapid development of cryptanalysis techniques and quantum computers jeopardizes these security measures, the most alarming threat being the existence of an algorithm capable of efficiently solving the factorization problem, whenever the construction of a quantum computer is possible. These implications suggest that new security measures should be studied and developed in view of the possible materialization of these threats. Recently, zero-knowledge tests have been considered as an alternative to existing authentication and identification protocols, the major advantage being that these protocols are based on problems that have not yet been solved by quantum algorithms. In addition to authentication and identification services, novel technologies such as blockchain and cryptocurrencies, which require anonymity services, have shown the capabilities of zero-knowledge proofs: a reliable technique to demonstrate knowledge of specific data without revealing details; for example, to demonstrate that an account has enough credit to purchase an item without knowing the exact balance. Interest has also been expressed in such technology for authentication in cloud storage and on the Internet of Things, encouraging the development of these protocols.
In this thesis we focus on the difficulty of finding isomorphisms of combinatorial designs, specifically of Steiner triple systems. An exhaustive study of the most important tools for testing isomorphism is carried out. In addition, some improvements of these techniques are revealed and, based on the observations of this analysis, difficult instances are characterized, which comprise the basic elements for a variety of zero-knowledge protocols.
