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.