Qual é o Problema da Rede Dura? Um tópico 🧵

A criptografia baseada em redes depende de um desafio central: encontrar uma solução de vetor curto s para um sistema de equações lineares módulo um inteiro q (geralmente um primo ou potência de primo). Isso é chamado de problema SIS (Solução de Inteiro Curto), simples em forma, mas considerado difícil contra ataques quânticos/clássicos.

Existem duas versões principais: a forma inhomogénea utilizada como a função unidirecional f_A(s) = A * s mod q em esquemas de compromisso, onde resolvemos A * s = t (mod q) dado A e o alvo t...

...e o problema homogéneo SIS, que pede para encontrar um s curto tal que A * s = 0 (mod q) para uma matriz A aleatória.

O esquema de compromisso é garantido como vinculativo pela dificuldade do SIS. Se A * s = t = A * s', então A * (s - s') = 0, o que significa que encontrar um s' diferente resolve o difícil problema homogéneo do SIS.

A brevidade de s (norma pequena) é essencial. Sem limitar s, as soluções são triviais usando álgebra linear clássica. Esta restrição de norma fundamenta a natureza difícil de resolver do SIS, mesmo contra computadores quânticos.

O resultado de Ajtai de 1996 conectou a dificuldade do problema SIS à resolução de problemas de rede no pior caso, formando uma base para as suposições da criptografia pós-quântica.

O problema SIS permite a compressão de um grande vetor secreto s (dimensão M) para um compromisso mais curto t. A matriz A tem dimensões N x M, onde N está tipicamente ligado ao parâmetro de segurança, tornando-a atraente para provas de conhecimento zero que necessitam de concisão.

Tomados em conjunto, o SIS é fácil de enunciar, mas extremamente difícil de resolver, desempenhando um papel fundamental em compromissos, provas de conhecimento zero e na segurança pós-quântica mais ampla.