Departamento de Computación

Esta tesis se centra en el estudio riguroso de la seguridad demostrable en criptografía, con un enfoque particular en los códigos de autenticación de mensajes (MAC). La tesis se erige sobre una base sólida de conceptos teóricos provenientes de la probabilidad, la teoría de la información y la criptografía simétrica. Estos fundamentos proporcionan el marco necesario para abordar los temas centrales de la investigación. Asimismo, se realiza un estudio exhaustivo de los cifradores por bloques entonables, que son considerados la piedra angular de muchos sistemas criptográficos modernos. Se introduce el concepto de oráculo como una herramienta teórica para modelar la interacción entre un adversario y un sistema criptográfico. Se define formalmente el concepto de familia de funciones, que es fundamental para las funciones pseudoaleatorias y las estrategias que pueden emplear los adversarios para distinguirlas de funciones verdaderamente aleatorias. Se presta especial interés en el concepto de seguridad incondicional, que se basa en la teoría de la información y no depende de supuestos computacionales. Adicionalmente, se explica con alto grado de detalle la técnica de los coeficientes H, una herramienta poderosa para demostrar la seguridad de construcciones criptográficas. Se ofrecen demostraciones rigurosas de los teoremas principales y se generaliza la definición de transcrito bueno, proporcionando así una medida de seguridad para cualquier sistema probabilíıstico. Por último, se muestra la aplicación de la técnica H al análisis del esquema ZMAC, un MAC basado en cifradores por bloques entonables. Se identifican las propiedades de seguridad de ZMAC y se demuestra su resistencia a diversos tipos de ataques. Además, se proponen mejoras para optimizar la eficiencia computacional de ZMAC sin comprometer su seguridad.

Abstract

This dissertation delves into a rigorous examination of provable security in cryptography, with a particular focus on Message Authentication Codes (MAC). The thesis is grounded in a solid foundation of theoretical concepts drawn from probability theory, information theory, and symmetric cryptography. These underpinnings provide the necessary framework to address the core research topics. Furthermore, a comprehensive study of block ciphers, which are widely regarded as the cornerstone of many modern cryptographic systems, is undertaken. The concept of an oracle is introduced as a theoretical tool to model the interaction between an adversary and a cryptographic system. The concept of a function family is formally defined, which is fundamental to understanding pseudorandom functions and the strategies adversaries may employ to distinguish them from truly random functions. Particular attention is paid to the notion of unconditional security, which is grounded in information theory and independent of computational assumptions. Furthermore, the thesis provides a highly detailed explanation of the H-coefficient technique, a powerful tool for proving the security of cryptographic constructions. Rigorous proofs of the main theorems are presented, and the definition of a good transcript is generalized, providing a security measure for any probabilistic system. Finally, the application of the H-coefficient technique to the analysis of the ZMAC scheme, a MAC based on block ciphers, is demonstrated. The security properties of ZMAC are identified, and its resistance to various attacks is proven. Additionally, improvements are proposed to optimize the computational efficiency of ZMAC without compromising its security.