¿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 de vector corto s a un sistema de ecuaciones lineales módulo un entero q (generalmente un primo o una potencia de primo). Esto se llama el problema SIS (Solución de Entero Corto), simple en forma pero considerado difícil frente a ataques cuánticos/clásicos.

Hay dos versiones principales: la forma inhomogénea utilizada como la 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 SIS, que pide encontrar un s corto tal que A * s = 0 (mod q) para una matriz A aleatoria.

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

La brevedad de s (norma pequeña) es esencial. Sin limitar s, las soluciones son triviales utilizando álgebra lineal clásica. Esta restricción de norma subyace a la naturaleza difícil de resolver de SIS, incluso contra computadoras cuánticas.

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

El problema SIS permite la compresión de un gran vector secreto s (dimensión M) a un compromiso más corto t. La matriz A tiene dimensiones N x M, donde N está típicamente relacionado con el parámetro de seguridad, lo que la hace atractiva para pruebas de conocimiento cero que necesitan concisión.

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