Bueno, se trata de supuestos de dureza de varios problemas. Los problemas subyacentes en los que se basan RSA, Diffie-Hellman, etc., están en la dureza de la factorización y el registro discreto. No haré ninguna suposición aunque digas que estás familiarizado con el algoritmo de Shor. Una vez que se construye una computadora cuántica de propósito general, las personas podrán ejecutar el algoritmo de Shor y resolver la factorización en tiempo polinómico.
Los enrejados (actualmente) se basan en una suposición de dureza diferente, que es la dureza de un problema llamado vector más corto (SVP), que esencialmente, dada una base de puntos de red, encuentra el vector más corto (un punto de red) en el espacio. Relacionado está el problema de vector más cercano (CVP), que es que, dado un vector en un espacio, encuentra el punto de red más cercano. Esto se puede reducir a SVP. Unos cuantos problemas más que se usan como una suposición de arnés es aprender con error (LWE), pequeño problema ideal principal, problema de solución entera corta, etc., para lo cual no se conocen algoritmos cuánticos (actualmente). Y debido a la naturaleza de algunos de estos problemas, puede que no haya algoritmos cuánticos.
Sin embargo, eso no significa necesariamente que estos sean seguros. Una de las principales preocupaciones en la investigación sobre criptografía basada en red es proporcionar pruebas de seguridad de caso promedio. También existe una gran dependencia en la reducción de problemas, ya que se utilizan muchas matemáticas polinómicas para acelerar los procedimientos computacionales, podría haber mejores reducciones o reducciones a otros problemas que hacen que las redes sean más fáciles de resolver. Pero, por supuesto, estos también son problemas de nuestros criptosistemas actuales y, sin embargo, confiamos en ellos.
- Cómo diseñar algoritmos que puedan ser utilizados por una computadora cuántica
- Además de D-Wave, ¿hay alguna otra entidad / compañía / organización que haya avanzado en el desarrollo del uso práctico de la computación cuántica?
- ¿Qué piensan los físicos cristianos sobre la teoría de la mecánica cuántica de muchos mundos?
- ¿Se podría usar la decoherencia cuántica para probar si una IA es realmente consciente?
- ¿Estamos descubriendo la física cuántica, o estamos definiendo qué es la física cuántica, cómo funciona y qué es?
Sin embargo, en última instancia, solo estamos eligiendo diferentes problemas difíciles para basar nuestros sistemas.
EDITAR: para responder algunas preguntas adicionales.
1) tamaño de la llave
Usted mencionó que el tamaño de la clave es problemático. Esto no es del todo cierto. Una de las principales razones por las que las redes son tan importantes en la investigación en este momento, es porque se basan en anillos conmutativos y el cifrado / descifrado es un homomorfismo en anillo que permite operaciones homomórficas en datos cifrados. El gran tamaño clave de la mayoría de los sistemas criptográficos centrados en el cifrado totalmente homomórfico es el resultado del único método que se ha utilizado hasta ahora (“arranque” es el término, pero lo odio porque hay muchos usos más relevantes, lo siento Gentry), que usa algo como el problema de suma de subconjuntos para almacenar la clave, y al mismo tiempo convierte un esquema algo homomórfico en un esquema completamente homomórfico.
Sin embargo, el tamaño de la clave para la mayoría de las redes criptográficas en este punto parece estar en el rango de unos cientos de bytes, por lo que, en cierto sentido, es grande.
2) celosías Q-ary
Si observa una red como una [matemática] n [/ matemática] -tupla en el anillo [matemática] \ matemática {Z} ^ n [/ matemática], entonces una retícula [matemática] q [/ matemática] en esto (con respecto a la q elegida) es todos los puntos reticulares tomados módulo [matemáticas] q [/ matemáticas]. En notación:
[matemáticas] (\ mathbb {Z} / (q)) ^ n = \ {(v_1, \ dots, v_n} \ in \ mathbb {Z}: v_1, \ dots, v_n \ in \ mathbb {Z} / q \ mathbb {Z} [/ math]
3) Razones para usar redes en cripto post-cuántico en oposición a otros métodos.
Bueno, las redes están entrando actualmente en un estado de madurez, y parece que tienen potencial para nuevas optimizaciones. Otras opciones, como los esquemas basados en la teoría de codificación (McEliece, etc.), las funciones mutlivariadas no parecen tan maduras o prácticas como lo que hemos encontrado con las redes.
Pero la verdad es que, al igual que la criptografía que tenemos actualmente, es una cuestión de ignorancia por parte del conocimiento humano que no sabemos si hay o no algoritmos cuánticos para redes, códigos Goppa o multivariados. cifrado Estamos eligiendo un pequeño subconjunto de sistemas actualmente investigados con la * creencia * de que son seguros contra ataques cuánticos. Puede o no ser cierto. Pero también es cierto que hay cosas que no se han descubierto incluso sobre la criptografía que usamos actualmente, y podría ser posible romper nuestra criptografía actual en una computadora clásica.
