Public Key Encryption from High-Corruption Constraint Satisfaction Problems

Título: Criptografia de Chave Pública a partir de Problemas de Satisfação de Restrições (CSPs) com Alta Corrupção

1. O Problema e o Contexto

A criptografia de chave pública (PKE) é um primitivo fundamental, mas suas construções atuais dependem de um número limitado de suposições de dificuldade computacional, principalmente problemas de teoria dos números (que são vulneráveis a computadores quânticos) e problemas de teoria de códigos/lattices. Existe uma necessidade crítica de encontrar novas fontes de dificuldade computacional para construir PKEs que sejam seguras contra ataques quânticos e baseadas em conjecturas diferentes das atuais.

O artigo aborda a construção de um esquema de PKE baseado na intractabilidade de Problemas de Satisfação de Restrições (CSPs) sob condições extremas de alta corrupção. Especificamente, o trabalho considera cenários onde a maioria das restrições (uma fração $1 - o(1)$) é substituída por ruído aleatório, tornando a detecção de uma solução "plantada" (oculta) extremamente difícil.

2. Metodologia e Abordagem

Os autores propõem uma nova abordagem que combina duas conjecturas de dificuldade em CSPs de alta corrupção com uma nova técnica de "plantio de armadilhas" (trapdoors) baseada em grafos de fatores estendidos por rótulos.

A. As Duas Conjecturas de Dificuldade

A segurança do esquema depende da dificuldade de distinguir entre distribuições nulas (aleatórias) e distribuições plantadas em dois tipos de CSPs, ambos com taxas de corrupção de $1 - o(1)$:

1. LARP-CSP (Large Alphabet Random Predicate CSP):

   • Envolve um grafo de fatores que é fortemente expansor (arbitrário, mas com propriedades de expansão).
   • As restrições são definidas por funções aleatórias de um alfabeto grande ($\Sigma$) para outro ($\Gamma$).
   • A maioria das restrições é corrompida (substituída por valores aleatórios).
   • A conjectura afirma que é computacionalmente impossível distinguir se as restrições foram geradas a partir de uma atribuição secreta ou se são puramente aleatórias, mesmo para algoritmos de tamanho polinomial.

2. kXOR Aleatório com Alta Corrupção:

   • Envolve um grafo de fatores escolhido aleatoriamente.
   • As restrições são somas paritárias ($k$-XOR) de variáveis binárias.
   • Assim como no LARP-CSP, a vasta maioria das restrições é corrompida.
   • A conjectura afirma a intractabilidade de distinguir a distribuição plantada da nula neste regime de alta ruído.

B. A Técnica de Plantio de Armadilhas (Trapdoors)

O núcleo da construção é uma nova maneira de esconder uma "armadilha" que permite a descriptografia:

• Grafo de Fatores Estendido por Rótulos: Os autores utilizam a estrutura do grafo de fatores estendido de um CSP para plantar uma armadilha em outro CSP.
• Códigos Corretores de Erros Expansores: Eles constroem um código de correção de erros com uma matriz geradora de baixa densidade e forte expansão. A "armadilha" reside na capacidade de identificar quais linhas da matriz pública correspondem a uma versão "punctured" (furada) do código original, permitindo a recuperação da mensagem.
• Mecanismo de Chave Pública: A chave pública é gerada listando todas as pré-imagens locais de uma instância de LARP-CSP. Isso cria uma matriz que contém, de forma oculta, uma submatriz correspondente ao código de correção de erros subjacente.

C. Construção do Código Corretor

Uma contribuição técnica crucial é a primeira construção uniforme e explícita de um código corretor de erros que:

• Possui uma matriz geradora esparsa e expansora.
• Permite a decodificação eficiente (ou distinção) mesmo quando uma fração $1 - o(1)$ dos bits está corrompida ou apagada.
• Baseia-se em códigos de Reed-Muller de baixa taxa, utilizando algoritmos de decodificação existentes adaptados para este cenário.

3. Principais Resultados

1. Esquema de PKE Semânticamente Seguro:

   • O artigo apresenta o primeiro esquema de PKE que utiliza CSPs de alta corrupção e atinge um nível de segurança quase-exponencial (quasi-exponential), especificamente da ordem de $\exp(2^{\log^{\Omega(1)} \lambda})$.
   • Isso supera significativamente os esquemas anteriores baseados em CSPs de alta corrupção, que eram limitados a segurança quasi-polinomial ($\lambda^{O(\log \lambda)}$) devido a barreiras de força bruta na descriptografia.

2. Construção de Código Expansor Decodificável:

   • Fornecem um algoritmo explícito para gerar matrizes expansoras que são subcódigos de códigos de Reed-Muller, permitindo a distinção de vetores ruidosos com alta taxa de erro.

3. Evidências de Dificuldade (Lower Bounds):

   • Os autores provam uma série de limites inferiores (lower bounds) para apoiar suas conjecturas, excluindo várias classes de ataques naturais:
     • Ataques de Embedding de Baixa Complexidade: Mostram que ataques baseados em circuitos AC0[+] (como os que quebraram geradores pseudoaleatórios de Goldreich em grafos expansores específicos) falham devido à alta entropia das funções aleatórias no LARP-CSP.
     • Algoritmos de Polinômios de Baixo Grau: Demonstram que algoritmos representados por polinômios de grau até $n^{0.99}$ não conseguem distinguir as distribuições.
     • Refutações de Cálculo Polinomial: Provam que refutações do sistema de cálculo polinomial exigem tamanho exponencial ($\exp(n^{0.99})$), indicando resistência contra algoritmos algébricos.

4. Significado e Impacto

• Novas Fundações para PKE: O trabalho expande o horizonte de suposições de dificuldade para a criptografia de chave pública, movendo-se além de problemas de fatoração e lattices para problemas de CSPs em média (average-case).
• Segurança Pós-Quântica: Ao basear-se em problemas de CSPs e códigos, o esquema é resistente a ataques de computadores quânticos (diferente de RSA e ECC).
• Perspectiva "Win-Win": Os autores argumentam que, mesmo que a conjectura seja quebrada no futuro, o processo de tentativa e erro levará a um entendimento mais profundo da complexidade média de problemas NP e das fronteiras entre dificuldade computacional e estatística.
• Superação de Barreiras de Segurança: A capacidade de atingir segurança quase-exponencial (próxima da sub-exponencial) usando CSPs de alta corrupção é um avanço teórico significativo, eliminando a necessidade de algoritmos de descriptografia do tipo "guess-and-check" que limitavam esquemas anteriores.

Conclusão

Este artigo representa um avanço fundamental na criptografia teórica, propondo um esquema de chave pública robusto baseado na dificuldade de resolver CSPs com ruído massivo. Ao introduzir novas técnicas de plantio de armadilhas via grafos de fatores estendidos e provar a resistência contra uma ampla gama de ataques algorítmicos, os autores estabelecem uma nova direção promissora para a construção de primitivas criptográficas seguras no mundo pós-quântico.