Post-Quantum Sanitizable Signatures from McEliece-Based Chameleon Hashing

1. O Problema

As assinaturas sanitizáveis permitem que um signatário delegue a um "sanitizador" autorizado a capacidade de modificar blocos específicos de um documento assinado (como dados pessoais em registros médicos ou datas de validade em certificados) sem invalidar a assinatura digital. No entanto, a maioria das esquemas existentes baseia-se em primitivas criptográficas clássicas (RSA, Logaritmo Discreto, emparelhamentos), que são vulneráveis a ataques de computadores quânticos (algoritmo de Shor).

Embora existam propostas recentes baseadas em reticulados (lattices) para assinaturas sanitizáveis pós-quânticas, elas ainda dependem do Modelo de Oráculo Aleatório (ROM) para a resistência a colisões do hash camaleão e não oferecem transparência perfeita. Até o momento, não existia uma solução baseada em códigos (code-based) para assinaturas sanitizáveis pós-quânticas.

2. Metodologia

Os autores propõem o primeiro esquema de assinatura sanitizável pós-quântico baseado em códigos de Goppa (assumindo a dificuldade do problema de Decodificação de Síndrome - SD). A construção central é uma função hash camaleão derivada do sistema criptográfico de McEliece.

• Hash Camaleão McEliece: A função hash é definida como $H(m, r) = (G(m) \oplus r) \cdot H_{pub}^T$, onde:
  • $m$ é a mensagem.
  • $r$ é um vetor aleatório (randomizador) com peso de Hamming limitado.
  • $G$ é uma função hash modelada como um Oráculo Aleatório (implementada como SHA-3).
  • $H_{pub}$ é a matriz de verificação de paridade pública do código de Goppa.
• Prevenção de Colisões Triviais: Sem o pré-processamento $G(m)$, um hash linear seria vulnerável a colisões triviais. O uso do oráculo aleatório $G$ torna a inversão necessária para encontrar colisões sem a trapdoor computacionalmente inviável.
• Mecanismo de Sanitização: O sanitizador possui a chave secreta (trapdoor) do código de Goppa. Para modificar um bloco de mensagem, ele usa o algoritmo de decodificação de Patterson para encontrar um novo vetor aleatório $r'$ que, combinado com a nova mensagem, produza o mesmo valor de hash que a mensagem original, mantendo a assinatura válida.
• Estrutura da Assinatura: O esquema utiliza duas instâncias independentes de hash camaleão (uma para blocos imutáveis e outra para blocos admissíveis) encadeadas. A assinatura final é gerada sobre o resumo (digest) final usando um esquema de assinatura baseado em reticulados (Dilithium2) para garantir a integridade global.

3. Principais Contribuições

1. Primeiro Esquema Baseado em Códigos: Estabelecimento do primeiro esquema de assinatura sanitizável pós-quântico transparente baseado em suposições de códigos (McEliece).
2. Hash Camaleão Seguro no ROM: Definição de um hash camaleão onde a resistência a colisões depende da dificuldade do problema de Decodificação de Síndrome (SD) no Modelo de Oráculo Aleatório.
3. Transparência Perfeita ($\delta = 0$): Uma inovação crucial é a restrição de que o signatário deve amostrar randomizadores com peso de Hamming exatamente igual a $t$. Como a decodificação de Patterson (usada pelo sanitizador) também retorna vetores de peso exatamente $t$, as distribuições de assinaturas "frescas" e "sanitizadas" são estatisticamente indistinguíveis. Isso garante transparência perfeita, eliminando qualquer vantagem para um adversário tentar distinguir quem assinou o documento.
4. Análise de Segurança Rigorosa: Provas formais de:
   • Inforgeabilidade Existencial (EUF-CMA): Baseada na dificuldade do SD.
   • Imutabilidade: Garante que o sanitizador não pode alterar blocos fora da máscara de admissibilidade.
   • Transparência: Limites matemáticos precisos para a distância estatística entre as assinaturas.

4. Resultados e Desempenho

Os autores implementaram um protótipo em Python e realizaram benchmarks com parâmetros do NIST (Categoria 1, segurança pós-quântica de ~128 bits).

• Parâmetros: $n = 3488$, $k = 2720$, $t = 64$.
• Tamanho das Chaves: A chave pública é de aproximadamente 655,3 KB (devido às duas matrizes de verificação de paridade). Embora grande, é menor que a solução baseada em reticulados comparável (~850 KB).
• Tamanho da Assinatura: Para 10 blocos ($L=10$), a assinatura tem cerca de 6,75 KB.
• Tempo de Execução:
  • A assinatura e verificação crescem linearmente com o número de blocos.
  • O tempo teórico de decodificação de Patterson para modificar um bloco é de aproximadamente 8 ms.
  • O protótipo em Python mostrou tempos maiores devido à falta de um decodificador de Patterson otimizado (usando busca aleatória), mas os dados teóricos validam a viabilidade prática.
• Comparação: O esquema oferece chaves públicas menores e transparência perfeita em comparação com a única alternativa pós-quântica anterior baseada em reticulados (Clermont et al.), embora a assinatura seja ligeiramente maior.

5. Significância e Aplicações

Este trabalho preenche uma lacuna crítica na criptografia pós-quântica, oferecendo uma alternativa robusta baseada em códigos para a gestão de dados sensíveis em um futuro quântico.

• Segurança Conservadora: Baseia-se no problema de Decodificação de Síndrome, estudado há mais de 45 anos, oferecendo uma fundação de segurança mais madura e conservadora do que problemas baseados em reticulados (como LWE), que têm apenas ~15 anos de estudo.
• Aplicações Práticas:
  • Registros Médicos: Permite a remoção de identificadores de pacientes de registros assinados por médicos sem quebrar a assinatura, garantindo privacidade e integridade a longo prazo.
  • Certificados X.509: Atualização de datas de validade mantendo outras informações imutáveis.
  • Cadeia de Suprimentos: Sanitização de dados comerciais sensíveis em documentos logísticos.
• Limitações: O esquema requer o Modelo de Oráculo Aleatório para a resistência a colisões do hash e não oferece "isenção de exposição" (exposure-freeness), o que significa que um observador com acesso a pares de colisões poderia, teoricamente, extrair informações sobre a trapdoor após muitas sanitizações. Além disso, o tamanho das chaves públicas ainda é significativo para dispositivos com recursos limitados (IoT), embora seja competitivo entre soluções pós-quânticas.

Em resumo, o artigo apresenta uma solução teoricamente sólida e praticamente viável para assinaturas sanitizáveis pós-quânticas, destacando-se pela transparência perfeita alcançada através de uma restrição algorítmica simples no processo de assinatura.