¿Cuál es el problema de la red dura? Un hilo 🧵

La criptografía basada en redes se basa en un desafío central: encontrar una solución vectorial corta s para un sistema de ecuaciones lineales módulo un entero q (normalmente una potencia prima o prima). Esto se llama problema SIS (Solución Entera Corta), simple en forma pero considerado difícil contra ataques cuánticos/clásicos.

Existen dos versiones principales: la forma inhomogénea usada como función unidireccional f_A(s) = A * s mod q en esquemas de compromiso, donde resolvemos A * s = t (mod q) dado A y el objetivo t...

... y el problema homogéneo del SIS, que pide encontrar un corto s tal que A * s = 0 (mod q) para una matriz aleatoria A.

El esquema de compromiso está garantizado como vinculante gracias a la dureza del SIS. Si A * s = t = A * s', entonces A * (s - s') = 0, lo que significa que encontrar un s' diferente resuelve el problema SIS homogéneo difícil.

La cortadez de s (norma pequeña) es esencial. Sin acotar s, las soluciones son triviales usando álgebra lineal clásica. Esta restricción normativa sustenta la naturaleza difícil de resolver del SIS, incluso frente a ordenadores cuánticos.

El resultado de Ajtai de 1996 relacionó la dificultad del problema SIS con la resolución de problemas de red en el peor caso, formando una base para las suposiciones post-criptografía cuántica.

El problema del SIS permite la compresión de un vector secreto grande s (dimensión M) a un compromiso más corto t. La matriz A tiene dimensiones N x M, donde N suele estar ligado al parámetro de seguridad, lo que la hace atractiva para pruebas de conocimiento cero que requieren concisión.

En conjunto, el SIS es fácil de afirmar pero extremadamente difícil de resolver, desempeñando un papel fundamental en compromisos, pruebas de conocimiento cero y seguridad post-cuántica más amplia.