Malleability of transformations on the ciphertext in noisy Quantum public key encryption

Resumo Técnico: Maleabilidade de Transformações no Texto Cifrado em Criptografia de Chave Pública Quântica com Ruído

Definição do Problema
Este artigo aborda o desafio de formular rigorosamente a "segurança eterna" (everlasting security) para Criptografia de Chave Pública Quântica (QPKE) e Distribuição de Chaves Quânticas (QKD) na presença de ruído. Embora o trabalho anterior de Malavolta e Walter [3] tenha estabelecido um arcabouço para a segurança eterna em um cenário sem ruído — demonstrando que a segurança pode ser alcançada após apenas duas rodadas de interação entre Alice e Bob — este trabalho investiga como a introdução de ruído afeta os limiares de segurança do protocolo. Especificamente, o artigo explora a relação entre a maleabilidade das transformações do texto cifrado e a segurança do protocolo quando o ruído é injetado nas operações criptográficas. O problema central é generalizar a função de negligibilidade (que quantifica a vantagem do adversário) do caso ideal sem ruído para um cenário com ruído, utilizando suposições relativas à maleabilidade das transformações de texto simples e de texto cifrado.

Metodologia
Os autores empregam uma combinação de Teoria da Informação Quântica e Criptografia Abstrata para analisar o protocolo QPKE-QKD com ruído. A metodologia é estruturada em torno dos seguintes componentes principais:

1. Injeção de Ruído via Maleabilidade: O artigo adapta o conceito de maleabilidade, originalmente introduzido por Maurer e Tackmann [9] para comparar protocolos "autentique depois cifre" (authenticate then encrypt) e "cifre depois autentique" (encrypt then authenticate). Os autores definem transformações ruidosas no espaço do texto simples caracterizadas por três probabilidades de erro: erro de encaminhamento (forwarding error), erro de deleção (deleting error) e erro de reconstrução (reconstruction error). Esses erros são usados para modelar o impacto do ruído no texto cifrado.
2. Distância de Traço e Lema da Medição Suave (GML): Uma ferramenta técnica central é a adaptação do Lema da Medição Suave (Gentle Measurement Lemma - GML) da Teoria da Informação Quântica [18]. Os autores utilizam este lema para estabelecer um limite superior na distância de traço entre dois estados quânticos (representando os experimentos real e ideal) com base em um limite inferior do traço de um operador específico. Isso permite a generalização da função de negligibilidade na presença de ruído.
3. Máquinas de Tempo Polinomial Quântico Ruidoso (NQPT): O artigo formaliza o cenário ruidoso definindo máquinas de Tempo Polinomial Quântico Ruidoso (NQPT) e mapas CPTP (Preservadores de Traço Completamente Positivos) Ruidosos. Esses objetos substituem seus equivalentes sem ruído para modelar o comportamento de Alice, Bob e do adversário (Eve) sob condições de ruído.
4. Operadores de Projeção e Decomposição de Estado: A análise envolve a construção de operadores de projeção ruidosos ($\tilde{\Pi}$) que incorporam termos de ruído (ex: $|\sigma + \text{ruído}\rangle$) no operador de projeção padrão $\Pi$ usado no protocolo QPKE-QKD sem ruído. Os autores derivam limites superiores para a distância de traço comparando as razões entre operadores de projeção ruidosos e sem ruído, operações de traço, e estados ket/bra.
5. Abordagem Teórica de Recursos: O artigo utiliza o arcabouço de teoria de recursos de [9], definindo segurança e disponibilidade em termos da indistinguibilidade de recursos construídos por protocolos. Isso inclui a análise da composição de protocolos e da indistinguibilidade de experimentos híbridos.

Principais Contribuições

• Formalização da Segurança Eterna com Ruído: O artigo define a "segurança eterna" para um protocolo QPKE com ruído (Definição 37), estabelecendo que a distância de traço entre experimentos híbridos ruidosos é limitada por uma função de negligibilidade dependente do parâmetro de segurança ruidoso $\lambda'$.
• Generalização da Função de Negligibilidade: Os autores derivam uma relação entre a distância de traço no cenário com ruído e a função de negligibilidade $NEGL(\lambda')$. Eles demonstram que, sob suposições específicas sobre o ruído, a função de negligibilidade no cenário com ruído relaciona-se com um limiar de segurança mais alto em comparação ao caso sem ruído.
• Limites de Distância de Traço via GML: Uma principal contribuição técnica é a derivação de um limite superior para a distância de traço usando o Lema da Medição Suave. Os autores mostram que:
  $$Td(\tilde{Exp}, Exp) \lesssim \sqrt{NEGL(\lambda' - \lambda)}$$
  Isso é alcançado ao provar um limite inferior para o traço de um operador específico envolvendo a diferença entre estados ruidosos e sem ruído ($\tilde{\rho} - \tau$).
• Suposições de Maleabilidade: O trabalho vincula explicitamente a segurança do protocolo à maleabilidade das transformações do texto cifrado. Ele quantifica como as probabilidades de erro de encaminhamento, deleção e reconstrução das transformações ruidosas se relacionam com a lacuna do limiar de segurança entre os protocolos sem ruído ($\lambda$) e com ruído ($\lambda'$).
• Compensações de Tempo de Execução Computacional: O artigo analisa as compensações (trade-offs) entre o tempo de execução computacional de protocolos ruidosos versus sem ruído (codificação, decodificação e geração de chaves). Sugere-se que, se o tempo de execução do protocolo com ruído for significativamente maior, a lacuna do limiar de segurança $\lambda' - \lambda$ escala de uma maneira específica, potencialmente relacionada a funções exponenciais ou polinomiais da diferença de tempo de execução.

Resultados

• Teorema Principal: O artigo prova que, para um protocolo QPKE-QKD com ruído que satisfaz condições de correção, a distância de traço entre os experimentos híbridos ruidosos (inicializados com bits 0 e 1) é limitada pela função de negligibilidade do parâmetro de segurança ruidoso:
  $$Td(\tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 1), \tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 0)) \lesssim NEGL(\lambda')$$
• Corolário sobre Funções de Vantagem: Os autores mostram que as funções de vantagem ruidosas para diferentes experimentos híbridos ($\tilde{Adv}(0), \tilde{Adv}(1), \tilde{Adv}(2)$) são todas limitadas pela mesma função de negligibilidade $NEGL(\lambda')$, confirmando a consistência da definição de segurança entre diferentes configurações experimentais.
• Limite Inferior do Traço: O artigo fornece uma derivação detalhada mostrando que o traço de um operador específico envolvendo a diferença entre estados ruidosos e sem ruído é limitado inferiormente por uma constante vezes o inverso da função de negligência, o que é um pré-requisito para aplicar o Lema da Medição Suave.

Significância e Alegações
O artigo afirma fornecer um arcabouço matemático rigoroso para estender a noção de segurança eterna para a Criptografia de Chave Pública Quântica com ruído. Ao adaptar o Lema da Medição Suave, os autores demonstram que as garantias de segurança do protocolo sem ruído podem ser generalizadas para o cenário com ruído, desde que o ruído seja caracterizado através de suposições de maleabilidade nas transformações do texto cifrado.

Os autores enfatizam que, embora a introdução de ruído geralmente leve a um limiar de segurança mais alto (implicando uma garantia de segurança potencialmente mais fraca em termos do parâmetro $\lambda'$), os limites derivados permitem uma comparação quantitativa entre protocolos ruidosos e sem ruído. O trabalho é apresentado como um passo teórico inicial, observando que, embora os requisitos para segurança incondicional e eterna sejam difíceis de realizar experimentalmente, o arcabouço proposto oferece um ponto de partida valioso para analisar as limitações da computação quântica com ruído em contextos criptográficos. O artigo conclui sugerindo que os cálculos derivados para limitar a distância de traço poderiam ser examinados futuramente em cenários centrados em abordagens de teoria dos jogos, embora não proponha implementações experimentais específicas ou aplicações imediatas além da análise teórica.