Simultaneous Approximation for Lattice-Based Cryptography

Resumo Técnico: Aproximação Simultânea para Criptografia Baseada em Retículos

1. O Problema e o Contexto

A criptografia baseada em retículos (lattices) é uma das principais candidatas para a segurança pós-quântica, oferecendo reduções de caso médio para pior caso e suporte a esquemas de criptografia homomórfica. No entanto, implementações ingênuas exigem chaves públicas grandes, o que é um gargalo para a eficiência.

Para mitigar isso, foram propostas estruturas especiais, como retículos ideais, que permitem chaves menores. Contudo, retículos ideais não garantem que seus problemas sejam tão difíceis quanto os de retículos gerais, e algoritmos específicos já demonstraram vulnerabilidades em certas instâncias.

O objetivo deste trabalho é investigar uma nova classe de retículos chamada Retículos de Aproximação Simultânea (SA - Simultaneous Approximation). O autor busca definir problemas nesses retículos que sejam:

1. Capazes de permitir chaves menores (devido à representação compacta).
2. Tão difíceis quanto os problemas gerais em retículos arbitrários (garantia de segurança).

2. Definições e Novos Problemas

O artigo define um retículo SA de dimensão $n$ como aquele gerado pelas colunas da matriz identidade $I_n$ e um vetor $x \in \mathbb{Q}^n$. Isso permite descrever o retículo com $n+1$ inteiros, em vez dos $n^2$ necessários para um retículo geral.

O autor introduz dois novos problemas relacionados a resolver problemas clássicos de retículos dentro desse contexto restrito:

• SIAP ($\gamma$) - Problema de Aproximação Independente Curta: Uma versão do Shortest Independent Vectors Problem (SIVP) em retículos SA. O objetivo é encontrar $n$ vetores independentes $b_1, \dots, b_n \in \mathbb{Z}$ tais que os vetores $\{b_i x\}$ (parte fracionária) sejam linearmente independentes e tenham norma limitada por $\gamma \lambda_n$.
• CAP ($\gamma$) - Problema de Aproximação Mais Próxima: Uma versão do Closest Vector Problem (CVP) em retículos SA. O objetivo é encontrar $b_0 \in \mathbb{Z}$ tal que a distância entre $\{b_0 x - t\}$ e a origem seja minimizada dentro de um fator $\gamma$.

O problema SAP ($\gamma$) (Aproximação Simultânea) já era conhecido como equivalente ao SVP (Shortest Vector Problem) em retículos SA, mas este trabalho estende a equivalência para SIVP e CVP.

3. Metodologia

A abordagem central do artigo é construir reduções determinísticas de tempo polinomial que preservam a dimensão e o "gap" (fator de aproximação) entre os problemas gerais (SVP, SIVP, CVP) e suas contrapartes em retículos SA (SAP, SIAP, CAP).

Algoritmo Chave (Algoritmo 1): Aproximação de um Retículo Geral por um Retículo SA
O núcleo da metodologia é um algoritmo que transforma um retículo geral $L = M\mathbb{Z}^n$ em um retículo SA aproximado.

1. Construção: O algoritmo gera uma matriz $\tilde{M} = c \cdot \text{adj}(M) + A$, onde $c$ é um escalar grande e $A$ é uma matriz de perturbação com entradas pequenas.
2. Garantia de Geração: O algoritmo ajusta iterativamente as entradas de $A$ para garantir que as colunas de $\tilde{M}$ e um vetor $b$ gerem $\mathbb{Z}^n$. Isso é feito assegurando que determinantes de submatrizes sejam coprimos (usando o Teorema de Bézout e a função de Jacobsthal).
3. Mapeamento: Se $\tilde{M}$ e $b$ geram $\mathbb{Z}^n$, então $M\tilde{M}$ e $M b$ geram o retículo original $L$. O vetor $x$ do retículo SA é derivado de $(c \cdot \det(M) I_n + MA)^{-1} M b$.
4. Inflação Inteira: O algoritmo controla rigorosamente o crescimento das entradas inteiras (inflação) durante o processo de perturbação e inversão, garantindo que o tamanho dos números permaneça polinomial.

4. Contribuições Principais e Resultados

• Teorema 1.1 (Reduções Preservadoras): O autor prova que os Algoritmos 2, 3 e 4 realizam reduções determinísticas de tempo polinomial de SVP$_\gamma$, SIVP$_\gamma$ e CVP$_\gamma$ para SAP$_\gamma$, SIAP$_\gamma$ e CAP$_\gamma$, respectivamente.

  • A complexidade de tempo é $O(n^5 \log^3(nk))$.
  • O tamanho da entrada é escalado por $O(n^2 \log(n))$.
  • Preservação do Gap: As reduções mantêm o fator de aproximação $\gamma$, o que é crucial para a segurança.

• Teorema 1.2 (Dureza NP):

  • SIAP$_\gamma$ e CAP$_\gamma$ são NP-difíceis para qualquer constante $\gamma$ sob as normas $\ell_1, \ell_2$ ou $\ell_\infty$.
  • SAP$_\gamma$ é NP-difícil sob a norma $\ell_\infty$ para qualquer $\gamma$, e sob reduções aleatórias para $\ell_1$ ou $\ell_2$ com $\gamma < 2$ ou $\gamma < 2^{1/2}$.
  • Implicação: Resolver problemas em retículos SA é tão difícil quanto em retículos gerais, superando a principal desvantagem dos retículos ideais.

• Otimização da Inflação Inteira (Seção 3.4):

  • O trabalho demonstra que a inflação inteira (crescimento do tamanho dos números) obtida é ótima.
  • O autor prova que qualquer algoritmo que produza uma inflação sub-quadrática (menor que $O(n^2)$) permitiria uma aproximação sub-exponencial para vetores curtos, o que quebraria a segurança dos retículos. Portanto, a bound $O(n^2 \log(nk))$ alcançada é o melhor possível sem comprometer a segurança.

5. Significado e Impacto

1. Segurança Garantida com Eficiência: Este trabalho estabelece que os retículos SA são uma base promissora para criptografia pós-quântica. Eles oferecem a vantagem de chaves menores (devido à representação compacta de $n+1$ inteiros) sem sacrificar a dureza do problema subjacente, ao contrário dos retículos ideais.
2. Novos Problemas para Criptografia: A definição de SIAP e CAP fornece novos problemas matemáticos que podem ser usados para construir esquemas criptográficos (como chaves públicas ou assinaturas) com garantias teóricas de segurança baseadas no pior caso.
3. Limites Teóricos: Ao provar a otimalidade da inflação inteira, o artigo define os limites fundamentais para a eficiência de esquemas baseados em aproximação simultânea, evitando tentativas fúteis de buscar reduções mais eficientes que violariam a segurança.

Em resumo, o artigo valida teoricamente o uso de retículos de Aproximação Simultânea como uma alternativa viável e segura aos retículos ideais, oferecendo um caminho para sistemas criptográficos mais eficientes em termos de tamanho de chave, mantendo a resistência contra ataques quânticos e clássicos.