Técnicas criptográficas que se fundamentan en lo impredecible

¿Cómo podemos garantizar que nuestra información está bien protegida? Si alguien intentase acceder a nuestros datos, ¿cómo confiar en que sus ataques serán infructuosos? Lo ideal sería tener una prueba de que todo lo que puede ver son palabras sin sentido, colecciones de ceros y unos arbitrarias, de las que no podrá extraer ninguna información. A esto se dedica la teoría de seguridad demostrable, una rama de la criptografía matemática que busca demostraciones formales que relacionen la dificultad de vulnerar una construcción criptográfica —como las que protegen nuestras transacciones bancarias online— con la de resolver un problema matemático concreto —por ejemplo, la dificultad de factorizar números muy grandes en sus divisores primos—. Demostrar esta relación no es un reto sencillo.

Uno de los objetos esenciales de esta teoría son las llamadas funciones de una vía o funciones one-way. Estas son funciones fáciles de evaluar —es decir, es fácil aplicarlas sobre un objeto dado—, pero para las que hacer el camino inverso —dado un valor, calcular un elemento que la función transforme justamente en ese— es una tarea muy compleja. Un ejemplo clásico de un proceso de este tipo podría ser el basado en la factorización de enteros; dados dos números primos es muy fácil multiplicarlos, pero, dado un número, no se conoce ningún método realmente rápido —ni empleando los ordenadores más potentes— para descomponerlo en el producto de dos números primos (es decir, saber de qué dos números “viene”). Ya con números relativamente pequeños se observa la diferencia de dificultad que hay entre la multiplicación y su proceso inverso: por ejemplo, al considerar los primos 7919 y 541 y su producto, 4.284.179.

Muchos otros problemas matemáticos plantean buenas “candidatas” a funciones de una vía: el cálculo de logaritmos discretos, los problemas de vector más corto en retículos, etc. Sin embargo, ¿cómo podemos asegurar que realmente las funciones resultantes son de una vía? ¿Es posible descartar que, más adelante, alguien encuentre una manera sencilla de revertir los procesos involucrados? Por ejemplo, ¿cómo garantizar que nunca podrá diseñarse un algoritmo eficiente para factorizar enteros con nuevas ideas? ¿Podría ser que en realidad no exista ninguna función de una vía, sino que, para algunas funciones, no hemos encontrado los métodos adecuados?

Los criptógrafos siempre han ansiado resolver el problema general, argumentando de manera irrefutable la existencia de estos objetos. Si se obtuviera este resultado sabríamos que es posible diseñar una cantidad ingente de construcciones criptográficas: generadores pseudoaleatorios, esquemas de cifrado, de firma, de identificación, de compromiso... Si supiéramos que no existen, ninguna de estas construcciones sería del todo segura: en el futuro podría aparecer un método para romperlas. Además, demostrar que hay funciones de una vía daría solución a uno de los llamados problemas del millón de dólares, proporcionando una evidencia de que la clase de complejidad P es distinta de la clase NP.

De momento, nadie ha conseguido resolver el problema, pero Yanyi Liu y Rafael Pass, dos investigadores de la Universidad de Cornell (EE UU), han sido capaces de cuantificar, en cierta medida, lo difícil que es hacerlo. En un trabajo reciente, consiguen cuantificar la dificultad de demostrar la existencia de funciones de una vía, empleando un célebre problema de teoría de complejidad, que trata de la llamada complejidad de Kolmogorov (o K-complejidad). La K-complejidad de una secuencia es la longitud del algoritmo más corto necesario para construirla. Esta noción, introducida en los años sesenta del siglo pasado por el matemático ruso Andrey Kolmogorov, puede interpretarse como una medida de los recursos computacionales que son necesarios para describir cualquier objeto. Permite, por ejemplo, cuantificar la dificultad de detectar patrones en secuencias binarias arbitrarias: cuanto más simple sea el patrón que sigue una secuencia, más baja será su complejidad de Kolmogorov.

El resultado de Liu y Pass involucra además un ingrediente fundamental en criptografía: el tiempo, como factor relevante a la hora de medir la dificultad de una tarea. Esto se refleja a través de una función t, que acota el tiempo de cálculo necesario para describir la secuencia en estudio. Así, la t-complejidad de Kolmogorov es la longitud de un programa capaz de construir cualquier secuencia binaria de cierta longitud, en tiempo acotado por una función t, que depende del tiempo. El resultado de Liu y Pass dice, precisamente, que la existencia de funciones de una vía equivale al hecho de que la t-complejidad de Kolmogorov sea grande, en un cierto sentido.

En consecuencia, solo podemos garantizar que la criptografía actual está sólidamente cimentada si no es posible diseñar un algoritmo infalible para calcular esta complejidad. En otras palabras, si el algoritmo más certero para calcular la t-complejidad de Kolmogorov está condenado a fracasar, al menos en una cantidad no despreciable de secuencias. Es decir, gran parte de nuestra criptografía seguirá valiendo solo si esta complejidad es impredecible.

Liu y Pass han recibido el reconocimiento de la comunidad criptográfica internacional por este resultado, además del prestigioso NSA Best Cybersecurity Research Paper. Sin duda, su trabajo nos acerca un poco más a entender qué tipo de procesos se escabullen del escrutinio de los algoritmos y pueden, por tanto, ayudarnos a mantener a salvo nuestros datos.

María Isabel González Vasco es catedrática de Matemática Aplicada de la Universidad Rey Juan Carlos.

Ágata Timón García-Longoria es coordinadora de la Unidad de Cultura Matemática del ICMAT.

Café y Teoremas es una sección dedicada a las matemáticas y al entorno en el que se crean, coordinado por el Instituto de Ciencias Matemáticas (ICMAT), en la que los investigadores y miembros del centro describen los últimos avances de esta disciplina, comparten puntos de encuentro entre las matemáticas y otras expresiones sociales y culturales y recuerdan a quienes marcaron su desarrollo y supieron transformar café en teoremas. El nombre evoca la definición del matemático húngaro Alfred Rényi: “Un matemático es una máquina que transforma café en teoremas”.

Edición y coordinación: Ágata A. Timón G Longoria (ICMAT).

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aquí para recibir nuestra newsletter semanal.