Sumário Técnico: Códigos Pseudorandoms Melhorados a partir de Quebra-cabeças Permutados

Declaração do Problema

A proliferação de conteúdo gerado por IA exige esquemas de marca d'água robustos para identificar a procedência. Trabalhos recentes estabeleceram que os Códigos Pseudorandoms (PRCs) são equivalentes a esquemas de marca d'água com garantias fortes de robustez e qualidade. Um PRC é um esquema de criptografia de chave secreta onde os textos cifrados são computacionalmente indistinguíveis de uma distribuição uniforme (garantindo indetectabilidade/qualidade) e o algoritmo de decodificação tolera uma alta taxa de erros (garantindo robustez).

No entanto, as construções de PRC existentes sofrem de três limitações críticas:

1. Segurança Fraca: Todas as construções anteriores são vulneráveis a ataques de distinção de tempo quase-polinomial. Elas dependem de ocultar estruturas esparsas de $(\log n)$, o que permite ataques de busca por força bruta.
2. Robustez de Alfabeto Limitada: Embora algumas construções lidem com erros de edição, elas exigem um alfabeto de tamanho polinomial. O texto realista (por exemplo, de Grandes Modelos de Linguagem) possui baixa entropia (aprox. 1 bit por palavra), necessitando de um PRC robusto a edições sobre um alfabeto de tamanho constante (idealmente binário).
3. Modelos Adversariais Fracos: Trabalhos anteriores assumem que os adversários são computacionalmente limitados ou carecem da chave de detecção. Não estava claro se os PRCs poderiam permanecer robustos contra adversários computacionalmente ilimitados que possuem a chave de detecção (robustez fortemente adaptativa).

A questão central em aberto era se uma única construção poderia alcançar segurança subexponencial, robustez de edição sobre um alfabeto binário e robustez contra adversários detentores da chave simultaneamente.

Metodologia

1. A Conjectura dos Códigos Permutados

Os autores introduzem uma nova suposição de dureza computacional, a Conjectura dos Códigos Permutados. Esta conjectura postula que uma distribuição de palavras-código "embaralhadas" e ruidosas é computacionalmente indistinguível de uma distribuição uniforme.

A distribuição $D_{n,\Sigma,C,\eta,T}$ é gerada da seguinte forma:

1. Amostra-se uma permutação de índice aleatória $\sigma \in S_n$ e permutações de alfabeto $\pi_1, \dots, \pi_n \in S_\Sigma$.
2. Amostram-se $T$ palavras-código $c_1, \dots, c_T$ uniformemente de um código linear $C \subseteq \Sigma^n$.
3. Para cada palavra-código, permuta-se os índices via $\sigma$ e os símbolos em cada posição via $\pi_j$, resultando em $\hat{c}$.
4. Aplica-se um canal de substituição com taxa de ruído $\eta$ a $\hat{c}$.

Insight Chave: Os autores provam que esta conjectura é implicada pela Conjectura dos Quebra-cabeças Permutados (previamente usada para Recuperação de Informação Privada duplamente eficiente). Eles fornecem evidência estatística de que, para alfabetos de tamanho constante e códigos com alta distância dual, um número logarítmico de amostras é estatisticamente uniforme. Além disso, demonstram que todos os três componentes (permutação de índice, permutação de alfabeto e ruído) são necessários; omitir a permutação de alfabeto (como em uma versão "brinquedo") torna os códigos Reed-Solomon distinguíveis via ataques de polinômio de baixo grau.

2. Construção de PRCs Robustos à Edição

Para alcançar a robustez de edição sobre um alfabeto binário, os autores constroem um PRC baseado em códigos Reed-Solomon Dobrados (FRS).

• Codificação: A chave secreta consiste nas permutações e em um one-time pad. Para codificar, uma palavra-código aleatória do código subjacente é permutada, ruidosa, e então um subconjunto de símbolos é selecionado. Crucialmente, cada símbolo selecionado é exibido como uma string binária contendo tanto o valor do símbolo quanto seu índice.
• Decodificação: O decodificador recebe uma string potencialmente corrompida por edições (inserções/deleções). Ele varre todas as substrings de um comprimento específico, tentando "forçar a força bruta" da distância de edição para recuperar pares potenciais de $(índice, símbolo)$. Esses candidatos formam uma lista para cada posição. Um algoritmo de recuperação de lista para o código subjacente é então aplicado a essas listas para recuperar a palavra-código original.
• Mecanismo de Robustez: Ao incluir índices na saída, o decodificador pode recuperar o símbolo correto mesmo se a posição tiver sido deslocada por inserções ou deleções, desde que o número de edições seja limitado. O uso de códigos FRS permite que o sistema tolere uma fração constante de edições mesmo quando o alfabeto é efetivamente binário (via transformação).

3. Transformação de Marca d'Água

Usando o framework estabelecido por Christ e Gunn (CRYPTO '24), os autores transformam seu PRC em um esquema de marca d'água para modelos de linguagem autorregressivos. O esquema gera texto com marca d'água ao enviesar a seleção de tokens em direção aos bits da palavra-código do PRC. A robustez do PRC contra edições traduz-se diretamente na capacidade da marca d'água de sobreviver a modificações adversariais de texto, desde que o modelo possua entropia suficiente por token.

Principais Contribuições e Resultados

1. Nova Construção de PRC com Três Propriedades

O artigo apresenta a primeira construção de PRC que satisfaz simultaneamente:

• Segurança Subexponencial Plausível: Baseada na Conjectura dos Códigos Permutados, que evita as estruturas esparsas vulneráveis a ataques de tempo quase-polinomial.
• Robustez de Edição de Alfabeto Binário: A construção tolera uma taxa constante de edições de pior caso (inserções, deleções, substituições) sobre um alfabeto binário.
• Robustez Fortemente Adaptativa: O esquema permanece robusto mesmo contra adversários que conhecem a chave de detecção e são computacionalmente ilimitados.

2. Garantias Teóricas

• Teorema 5.6: Sob a Conjectura dos Códigos Permutados, existe um PRC de alfabeto binário que é fortemente adaptativo a uma taxa constante de edições com segurança subexponencial.
• Teorema 5.14: Sob uma variante da conjectura para códigos Reed-Solomon Dobrados, existe uma marca d'água de LLM indetectável que é robusta a uma taxa constante de edições ($\tilde{O}(\alpha^7)$) exigindo apenas uma taxa de entropia por token constante $\alpha$. Esta é a primeira marca d'água que é tanto indetectável quanto robusta a edições de pior caso sob restrições de entropia realistas.

3. Criptoanálise e Evidência

• Necessidade da Permutação de Alfabeto: Os autores provam que, sem as permutações de alfabeto, os códigos Reed-Solomon são eficientemente distinguíveis de aleatórios, mesmo com permutações de índice e ruído.
• Ataques Quase-polinomiais em Trabalhos Anteriores: Eles mostram que uma ampla classe de construções de PRC anteriores (aquelas que dependem de estruturas esparsas plantadas ou predicados tolerantes a ruído) são inerentemente vulneráveis a ataques de tempo quase-polinomial.
• Uniformidade Estatística: Eles provam que, para alfabetos de tamanho constante, um pequeno número de palavras-código permutadas são estatisticamente indistinguíveis de uniformes, fornecendo evidência para a validade da conjectura contra distinguidores simples.

Significância

O artigo afirma resolver a tensão entre as três propriedades desejáveis de PRCs que anteriormente eram pensadas como mutuamente exclusivas ou inalcançáveis. Ao formalizar a Conjectura dos Códigos Permutados e alavancar códigos Reed-Solomon Dobrados, os autores fornecem uma base teórica para esquemas de marca d'água que são:

1. Indetectáveis: Indistinguíveis da saída real do modelo de linguagem.
2. Robustos: Capazes de resistir a edições adversariais (inserções/deleções) no texto.
3. Seguros: Resilientes contra atacantes que possuem a chave de detecção, permitindo a verificação pública sem comprometer a robustez.

O trabalho estabelece que alcançar essas propriedades requer ir além das estruturas esparsas e abraçar a dificuldade de distinguir palavras-código permutadas e ruidosas de strings aleatórias. Embora a segurança dependa de uma nova conjectura, os autores fornecem evidências fortes para sua validade e demonstram que ela implica a existência de marcas d'água práticas e robustas para texto gerado por IA.