Integrity from Algebraic Manipulation Detection in Trusted-Repeater QKD Networks

Resumo Técnico: Integridade a partir da Detecção de Manipulação Algébrica em Redes QKD de Repetidores Confiáveis

1. Definição do Problema

A Distribuição de Chaves Quânticas (QKD) permite comunicações seguras sem suposições computacionais, mas é atualmente limitada a curtas distâncias devido a restrições de hardware. Para estender a QKD por longas distâncias, são empregadas redes de repetidores confiáveis, onde links de QKD existem entre nós vizinhos e as mensagens são encaminhadas via um protocolo de retransmissão (descriptografar-recriptografar) entre nós não vizinhos.

Enquanto essas redes estão sendo implantadas, uma lacuna crítica de segurança existe: nenhum protocolo existente fornece garantias prováveis de integridade contra manipulação por adversários externos e nós intermediários corrompidos.

• Confidencialidade é frequentemente alcançada via encaminhamento por múltiplos caminhos e compartilhamento de segredos (por exemplo, dividindo um segredo em partes enviadas por caminhos disjuntos), garantindo que um adversário deva corromper um conjunto "qualificado" de caminhos para aprender o segredo.
• Integridade (a capacidade de detectar se uma mensagem foi adulterada) é inexistente. Soluções existentes, como o protocolo SECOQC, dependem de Códigos de Autenticação de Mensagem (MACs) que exigem chaves idênticas pré-compartilhadas, levando ao raciocínio circular. Outras abordagens usando funções de hash ou checksums falham em fornecer segurança contra adversários computacionalmente ilimitados ou dependem de suposições não comprovadas.

O desafio central é projetar um protocolo que garanta Segurança de Informação Teórica (ITS) para a integridade em um cenário onde os nós intermediários são confiáveis apenas para encaminhar dados, mas podem ser corrompidos, e onde o adversário tem controle total sobre a topologia da rede e a comunicação.

2. Metodologia

Os autores propõem um protocolo que combina códigos de Detecção de Manipulação Algébrica (AMD) com encaminhamento por múltiplos caminhos em redes de repetidores confiáveis.

Componentes Principais:

1. Compartilhamento de Segredos: O remetente (Alice) divide um segredo $s$ em $n$ partes usando um esquema de compartilhamento de segredo linear (ex: compartilhamento aditivo). Essas partes são transmitidas por $n$ caminhos disjuntos até o receptor (Bob).
2. Codificação AMD: Antes de dividir, Alice codifica o segredo usando uma construção de código AMD (baseada em Cramer et al., 2008). Isso mapeia o segredo $s$ para um elemento de grupo de tal forma que qualquer deslocamento algébrico não trivial (manipulação) do valor codificado é detectado com alta probabilidade pelo decodificador.
3. Retransmissão: Cada parte é retransmitida por seu respectivo caminho usando criptografia de One-Time Pad (OTP) com chaves geradas por QKD compartilhadas entre nós adjacentes. Nós intermediários descriptografam e recriptografam os dados.

Fluxo do Protocolo (Listagem 1):

• Alice: Codifica $s$ usando um codificador AMD, divide o resultado em partes $\vec{S}$ e criptografa a primeira parte de cada caminho com a chave QKD local.
• Nós de Retransmissão: Descriptografam o texto cifrado recebido, subtraem a chave recebida, adicionam a chave de saída e encaminham o resultado. Isso efetivamente retransmite a parte enquanto mantém a estrutura aditiva necessária para o esquema de compartilhamento de segredos.
• Bob: Descriptografa as partes finais de todos os caminhos, reconstrói o segredo codificado usando a função de recuperação do compartilhamento de segredos e, finalmente, decodifica usando o decodificador AMD. Se a decodificação falhar (saída $\perp$), Bob rejeita o protocolo, indicando manipulação.

Modelo de Segurança:
Os autores adaptam o modelo de segurança baseado em jogos (Brickell et al., 2007) para o contexto de repetidor confiável. Eles assumem que:

• A topologia da rede é estática.
• O adversário pode corromper um conjunto arbitrário de nós, mas é limitado a um conjão de caminhos não qualificado (ou seja, não consegue reconstruir o segredo).
• O adversário é computacionalmente ilimitado.
• Chaves QKD fornecem privacidade estatística contra informação lateral quântica.

3. Principais Contribuições

1. Primeiro Protocolo de Integridade Provável: Este trabalho apresenta o primeiro protocolo que provadamente fornece tanto confidencialidade quanto integridade em redes QKD de repetidores confiáveis contra adversários computacionalmente ilimitados.
2. Definição de Robustez de Deslocamento ($\delta$-shift-robustness): Os autores introduzem uma nova noção de segurança chamada $\delta$-shift-robustness. Diferente do compartilhamento de segredo robusto padrão onde um acionista honesto recupera o segredo, esta definição considera a recuperação externa (Bob), onde o adversário pode induzir deslocamentos em partes não corrompidas através da maleabilidade da criptografia OTP.
3. Prova de Segurança Formal: Os autores provam que seu protocolo alcança:
   • Confidencialidade: Limitada por $n\ell\epsilon$ (onde $n$ é o número de caminhos, $\ell$ é o comprimento do caminho, $\epsilon$ é a privacidade da QKD).
   • Integridade: Limitada por $n\ell\epsilon + \delta$, onde $\delta$ é a probabilidade de detecção de manipulação do código AMD.
4. Overhead Ótimo: O protocolo alcança o overhead ótimo para robustez forte ($2 \log(1/\delta)$ bits) ao retransmitir mensagens arbitrárias.
5. Eficiência: O protocolo é não interativo (Alice envia, Bob recebe) e requer apenas $n\ell$ mensagens não autenticadas entre vizinhos, superando soluções interativas como o SECOQC.

4. Resultados

• Garantias Teóricas: O protocolo é provado seguro através de uma sequência de jogos. O primeiro salto de jogo substitui as chaves QKD por elementos aleatórios uniformes (indistinguíveis com probabilidade $n\ell\epsilon$). O segundo salto reduz a garantia de integridade para a segurança do esquema de compartilhamento de segredo robusto ao deslocamento (probabilidade $\delta$).
• Implementação: Os autores fornecem uma implementação concreta demonstrando que o método é eficiente. Para um campo de tamanho $q$, a codificação mapeia um valor para $F^d \times F \times F$, e o compartilhamento de segredo aditivo não adiciona overhead.
• Comparação: Ao contrário do protocolo SECOQC, que depende de raciocínio circular para MACs e permite a identificação de trapaceiros (o que os autores mostram que pode ser quebrado via manipulação algébrica), este protocolo prioriza a integridade provável sem suposições circulares.

5. Significância e Alegações

O artigo afirma preencher uma lacuna crítica na segurança de redes QKD implantadas. Embora a confidencialidade seja frequentemente assumida via encaminhamento por múltiplos caminhos, a integridade tem sido uma vulnerabilidade não abordada. Os autores afirmam que seu protocolo é o primeiro a fornecer integridade provável neste cenário específico.

Limitações e Suposições:
Os autores são modestos quanto à praticidade de seu modelo atual:

• Topologia Estática: O protocolo assume uma topologia de rede fixa e chaves fixas. Ele não suporta atualmente redes dinâmicas onde caminhos ou endpoints mudam, o que limita a flexibilidade de implantação imediata no mundo real.
• Autenticação de Nó: O protocolo assume que a autenticação de nós é tratada pela natureza estática da rede ou por um mecanismo externo. Ele não resolve o problema de autenticar endpoints em uma rede dinâmica e parcialmente confiável.
• Sem Identificação de Trapaceiro: Ao contrário de algumas propostas anteriores, este protocolo detecta a manipulação, mas não identifica qual nó intermediário foi malicioso.

Direções Futuras:
Os autores identificam três vias específicas para trabalhos futuros:

1. Investigar famílias de diferenças externas para alcançar robustez fraca com tamanho de tag mínimo, o que é suficiente para o encaminhamento de chaves.
2. Desenvolver um protocolo que possa identificar trapaceiros (nós maliciosos) em vez de apenas detectar a manipulação.
3. Estender o modelo de repetidor confiável para representar redes dinâmicas, indo além das suposições estáticas necessárias para a prova atual.