Qual é o problema da rede dura? Um fio condutor 🧵

A criptografia baseada em rede depende de um desafio central: encontrar uma solução vetorial curta s para um sistema de equações lineares módulo um inteiro q (geralmente uma potência prima ou prima). Isso é chamado de problema SIS (Solução Inteira Curta), simples na forma, mas acreditado como forte contra ataques quânticos/clássicos.

Existem duas versões principais: a forma inhomogênea usada como 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 do SIS, que busca encontrar um curto s tal que A * s = 0 (mod q) para uma matriz aleatória A.

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

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

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

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

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