La teoría combinatoria de grupos y la teoría de gráficas han sido utilizadas con diversos fines en criptografía, tanto para la resolución de problemas difíciles, como para la propuesta de protocolos criptográficos. Perteneciente a la teoría combinatoria de grupos, el problema de la palabra es considerado uno de los problemas más dificiles de resolver y generalmente es irresoluble de manera algorítmica. Dada una presentación de un grupo G = hC;Ri, donde C es un conjunto de generadores y R un conjunto de relaciones, el problema de la palabra consiste en decidir si dos palabras α; β ∈ C son equivalentes o no. El problema de la palabra es soluble de manera algorítmica en el caso de los grupos de Coxeter. Gracias a esto, la estructura abstracta de tal grupo se puede representar mediante una gráca de Cayley. Sea G la gráfica de Cayley de un grupo de Coxeter donde el problema de la palabra es intratable, con tal gráfica se puede realizar la definición de protocolos de identificación del tipo reto-respuesta. Así pues, un protocolo puede consistir en la selección aleatoria de un árbol T extraído de G y su conjunto de hojas H(T), donde T será una clave privada asociada a una cierta identidad, digamos un probador, y H(T) será una clave pública dada a conocer a un verificador que desee comprobar la identidad del probador. Entonces, a partir de H(T), el verificador puede plantear retos al probador para comprobar si este posee o no la correspondiente clave T. En esta tesis se presenta un estudio que muestra algunos de los grupos de Coxeter más adecuados para realizar la construcción de tales gráficas. De igual forma se presentan algunos mecanismos que permiten la selección aleatoria de árboles a partir de gráficas de Cayley, incluso sin la necesidad de la construcción de toda la gráfica, lo cual resalta por el hecho de que en la mayoría de los casos tales gráficas son de crecimiento exponencial. Finalmente, se proponen dos protocolos de identificación del tipo reto-respuesta que utilizan dichos fundamentos y se muestra el nivel de seguridad en términos de bits que estos protocolos pueden ofrecer.
Palabras clave: Gráficas de Cayley, grupos de Coxeter, problema de la palabra, protocolos de identificación reto-respuesta, selección aleatoria de árboles.
Abstract
Combinatorial group theory and graph theory have been used for several purposes in cryptography, for instance to solve dificult problems and to propose cryptographic protocols. On combinatorial group theory, the word problem is considered one of the most dificult problems to solve and in general it is algorithmically unsolvable. Given a presentation of a group G = hC;Ri, where C is a set of generators and R is a set of relations, the word problem consists on deciding whether two words α; β ∈ C are equivalent or not. The word problem is algorithmically solvable in the case of Coxeter groups. Hence, the abstract structure of such a group may be represented by a Cayley graph. Let G be the Cayley graph of a Coxeter group where the word problem is intractable. Identification challenge-response protocols can be defined using Cayley graphs as the basis of their construction. Thus, a protocol may consist of two agents: a prover and a verifier. For a randomly selected tree T extracted from G and its set of leaves H(T) the tree T can be considered as the private key of the prover and H(T) as his public key. The public key is given to the verifier who wants to check the identity of the prover. Given H(T), the verifier may pose challenges to the prover to establish whether he does or does not possess the corresponding key T. In this thesis we show some Coxeter groups suitable for building such graphs. Likewise, we show some mechanisms allowing random selection of trees from Cayley graphs, even without building the entire graph, which highlight the fact that in most cases these have exponential growth. Finally, two identification challenge-response protocols are proposed using these concepts and we show the safety level in terms of bits that these protocols can provide.
Key words: Cayley graphs, Coxeter groups, word problem, identification challengeresponse protocols, random selection trees.
