“En criptografía, un objetivo principal es crear primitivas criptográficas con seguridad demostrable. En algunos casos, se encuentra que los protocolos criptográficos tienen seguridad teórica de la información; el pad de una sola vez es un ejemplo común. Sin embargo, la seguridad teórica de la información no siempre se puede lograr; En tales casos, los criptógrafos recurren a la seguridad computacional. Hablando en términos generales, esto significa que estos sistemas son seguros suponiendo que cualquier adversario esté limitado computacionalmente , ya que todos los adversarios están en la práctica. Debido a que la dureza de un problema es difícil de probar, en la práctica se supone que ciertos problemas son difíciles ”[1].
El problema de factorización de grandes semiprimes es solo uno de los muchos supuestos de dureza computacional Es muy famoso por su relación con el criptosistema RSA, que es probablemente el criptosistema más utilizado para la criptografía de clave pública en la actualidad, gracias a su eficacia.
Otro supuesto de dureza computacional muy popular es el problema de logaritmo discreto (DLP) , y hay muchos sistemas criptográficos basados en el DLP. Recientemente, el DLP se ha aplicado a los grupos de curvas elípticas, y esta aplicación ha ganado más popularidad en la última década porque las curvas elípticas permiten construir sistemas criptográficos realmente ligeros con una seguridad comparable a RSA.
- ¿Cómo podemos convertir eventos de la vida real (como cambiar el clima) en ecuaciones matemáticas? ¿Se pueden usar las matemáticas para predecir el resultado de eventos tan complejos?
- ¿Cuál es la matemática detrás del procesamiento del lenguaje natural?
- ¿Cuál es actualmente el campo más avanzado o más avanzado de las matemáticas?
- ¿Cómo es ser un estudiante graduado en matemáticas en Stanford?
- ¿Cómo fue su experiencia al aprender geometría algebraica?
Tanto el problema de factorización como el problema de registro discreto se han estudiado durante un tiempo y parecen ser realmente seguros, ya que no se ha descubierto ningún algoritmo de tiempo polinómico para computadoras clásicas que los rompa.
Sin embargo, si se va a construir una computadora cuántica de rendimiento, será mejor que arrojemos a la basura nuestros dos hermosos supuestos de dureza computacional: el Algoritmo de Shor [2] es un algoritmo cuántico descubierto en 1994 para la factorización de enteros, y se ejecuta en tiempo polinómico . Además, este algoritmo se puede adaptar para resolver polinómicamente DLP en una computadora cuántica.
La única garantía que permite a todo el mundo seguir usando sistemas criptográficos basados en la factorización de enteros o DLP es que la investigación en computadoras cuánticas se encuentra en una etapa primitiva, relativamente a la seguridad de, por ejemplo, un sistema criptográfico RSA. En 2017, IBM anunció haber creado un procesador cuántico de 16 qbit [3], que todavía es demasiado débil para romper cualquier criptosistema real.
Pero los criptógrafos nunca se sienten seguros, y es por eso que hoy en día se está estudiando un nuevo campo de criptografía: la criptografía post-cuántica [4] . Este tema es el estudio de criptosistemas clásicos que se basan en supuestos de dureza que se consideran seguros incluso contra un ataque de una computadora cuántica. Uno de estos supuestos es, por ejemplo, el problema de vector más corto (o problema de red ) en el que se basa el criptosistema NTRU [5].
Notas al pie
[1] Supuesto de dureza computacional – Wikipedia
[2] Algoritmo de Shor – Wikipedia
[3] Computación cuántica – Wikipedia
[4] Criptografía post-cuántica – Wikipedia
[5] NTRUEncrypt – Wikipedia
