Resumo Técnico: Criptoanálise de Códigos de Correção de Erros Pseudorandom Baseados em LDPC

Declaração do Problema

Os Códigos de Erros Pseudorandom (PRCs), introduzidos na CRYPTO 2024, representam uma nova primitiva criptográfica projetada para permitir a marca d'água indetectável para Grandes Modelos de Linguagem (LLMs) e Modelos de Geração de Imagem (GIMs). A principal instanciação de PRCs, conhecida como LDPC-PRC, baseia-se em códigos de Verificação de Paridade de Baixa Densidade (LDPC) e afirma segurança baseada na dificuldade dos problemas de Aprendizado de Paridade com Ruído (LPN) e XOR plantado.

Apesar das fortes garantias assintóticas teóricas, a segurança concreta do LDPC-PRC sob configurações de parâmetros práticas permanece inexplorada. A literatura existente sugere que os PRCs podem ser vulneráveis a ataques de distinção de tempo quase polinomial, mas nenhuma análise rigorosa foi conduzida para quantificar essas vulnerabilidades em cenários de implantação do mundo real. Esta lacuna deixa a indetectabilidade e a robustez dos esquemas de marca d'água baseados em PRC não verificadas contra adversários práticos.

Metodologia

Este trabalho apresenta a primeira criptoanálise concreta de LDPC-PRC, focando em dois esquemas específicos de marca d'água: $\Pi_{LLM}$ (para geração de texto) e $\Pi_{GIM}$ (para geração de imagem). Os autores propõem três novos ataques visando a indetectabilidade e a robustez do esquema, analisando sua complexidade sob configurações de parâmetros realistas derivadas de modelos de estado da arte (DeepSeek e Stable Diffusion).

1. Novos Ataques Criptográficos

Os autores projetam três ataques com objetivos variados:

• Ataque-I (Recuperação Parcial da Chave Secreta): Este ataque visa a propriedade de indetectabilidade. Ao adaptar algoritmos de Decodificação de Conjunto de Informação (ISD) usando uma abordagem de Meet-in-the-Middle (MITM), o adversário recupera um subconjunto dos vetores de linha da chave secreta a partir da chave pública. Esses vetores recuperados permitem que o adversário distinga entre palavras de código codificadas por PRC e vetores aleatórios com probabilidade esmagadora, quebrando efetivamente a indetectabilidade.
• Ataque-II (Distinguidor de Chave Fraca): Este ataque explora uma vulnerabilidade no procedimento de geração de chaves ($KeyGen$). Os autores observam que, nas implementações atuais, a matriz da chave pública $G$ pode conter linhas idênticas com probabilidade não desprezível (uma "chave fraca"). Um adversário pode detectar essas não-uniformidades estatísticas para distinguir conteúdo com marca d'água de ruído aleatório em tempo linear, contornando a necessidade de uma recuperação de chave complexa.
• Ataque-III (Ataque de Sobreposição de Ruído): Este ataque visa a propriedade de robustez. Ao recuperar o vetor de ruído Bernoulli original $e$ via Decodificação de Síndrome, um adversário constrói um vetor de sobreposição malicioso $e'$. Este vetor é projetado de tal forma que, quando adicionado à palavra de código, o peso total do ruído excede o limiar de correção do decodificador, causando falha na decodificação (remoção da marca d'água). Crucialmente, este ataque explora a lacuna entre os limites teóricos de ruído e as taxas de ruído concretas observadas em implementações práticas.

2. Análise de Complexidade Concreta

Os autores analisam a complexidade de tempo e de dados desses ataques usando conjuntos de parâmetros específicos para $\Pi_{LLM}$ e $\Pi_{GIM}$. Eles derivam limites teóricos (Teoremas 1–3) e os validam contra parâmetros concretos, calculando os níveis de segurança de bits (ex: $2^{46}$, $2^{60}$) em vez de depender apenas de notação assintótica.

3. Avaliação no Mundo Real

Para validar ameaças práticas, os autores implementaram $\Pi_{LLM}$ e $\Pi_{GIM}$ no DeepSeek (LLM) e Stable Diffusion (GIM). Eles avaliaram as taxas de sucesso dos ataques e o impacto na qualidade do conteúdo. Notavelmente, descobriram que para $\Pi_{LLM}$, alcançar marcas d'água detectáveis requer alta entropia de tokens, o que degrada severamente a legibilidade do texto, tornando o esquema impraticável para geração de texto de alta qualidade.

Principais Contribuições e Resultados

1. Quebrando a Indetectabilidade

• Ataque-I: Demonstrou que a recuperação parcial da chave secreta é viável. Para $\Pi_{GIM}$, o nível de segurança permanece abaixo de 46 bits em todas as escolhas de parâmetros. Para $\Pi_{LLM}$, o ataque tem sucesso com probabilidade esmagadora.
• Ataque-II: Revelou que chaves fracas ocorrem com quase 100% de probabilidade para parâmetros específicos (ex: $t=3, 4$) em ambos os esquemas LLM e GIM. Isso permite ataques de distinção em tempo polinomial, comprometendo completamente a indetectabilidade nesses regimes.

2. Quebrando a Robustez

• Ataque-III: Provou que o nível de segurança de $\Pi_{LLM}$ não pode exceder 75 bits para $n \le 2^{17}$ sob ataques de sobreposição de ruído. Para $\Pi_{GIM}$, o nível de segurança concreta é inferior a 60 bits devido à baixa taxa de ruído concreta ($\eta \ll \rho$).
• Validação Experimental: No Stable Diffusion, os autores alcançaram taxas de sucesso de remoção de marca d'água de 67% a 96%, dependendo do limite de perturbação ($\delta$), demonstrando que a robustez é facilmente comprometida.

3. Limitações Práticas de $\Pi_{LLM}$

A avaliação no DeepSeek revelou um compromisso fundamental: para satisfazer os limites de correção de erro do LDPC-PRC, o LLM deve gerar tokens de alta entropia (baixa confiança). Isso resulta em textos que são ou indetectáveis (baixa entropia) ou ilegíveis (alta entropia). Consequentemente, os autores concluem que $\Pi_{LLM}$ é impraticável para marca d'água de texto de alta qualidade no mundo real.

4. Defesas Propostas

O artigo propõe três estratégias de mitigação:

• Recomendações de Parâmetros: Aumentar o comprimento do código $n$ e o peso da linha $t$ pode elevar a complexidade do ataque. No entanto, alcançar segurança de 128 bits exige $n > 2^{24}$, o que excede o comprimento máximo de saída dos atuais modelos de estado da arte ($2^{15}$).
• Geração de Chave Revisada: Um algoritmo $KeyGen$ modificado (Algoritmo 2) usando eliminação Gaussiana é proposto para eliminar a probabilidade de gerar chaves fracas, mitigando o Ataque-II.
• Ajustes de Implementação: Para GIMs, sugere-se aumentar o peso do vetor de ruído adicionado para fechar a lacuna entre as taxas de ruído teóricas e concretas, aumentando assim a complexidade do Ataque-III.

Significância e Alegações

O artigo afirma fornecer a primeira avaliação de segurança sistemática de PRCs, preenchendo a lacuna entre a teoria assintótica e a implantação prática. Os autores afirmam que:

1. As Garantias de Segurança são Comprometidas: A segurança reivindicada do LDPC-PRC é insuficiente em todos os regimes praticáveis. Ataques podem detectar marcas d'água com probabilidade esmagadora a custos significativamente menores que 128 bits.
2. Impossibilidade Prática para LLMs: Devido a restrições inerentes aos grandes modelos generativos (especificamente comprimento de saída e entropia de tokens), alcançar segurança de 128 bits para marca d'água de LLM via LDPC-PRC é atualmente impraticável.
3. Necessidade de Avaliação Rigorosa: O trabalho destaca que suposições de dureza teórica (LPN/XOR plantado) não se traduzem automaticamente em segurança concreta quando detalhes específicos de implementação (como heurísticas de geração de chave e taxas de ruído) são considerados.

Os autores concluem que, embora a marca d'água de imagem baseada em PRC possa ainda admitir instâncias práticas com qualidade aceitável, o estado atual dos PRCs para LLMs requer uma reavaliação significativa de parâmetros e estratégias de implementação antes de sua ampla implantação.