Post-Quantum Security of Block Cipher Constructions

Resumo Técnico: Segurança Pós-Quântica de Construções de Cifras de Bloco

Autores: Gorjan Alagic, Chen Bai, Christian Majenz e Kaiyan Shi.
Contexto: Este trabalho estabelece as fundações teóricas para a análise de segurança pós-quântica de cifras de bloco e suas construções associadas, preenchendo uma lacuna significativa na literatura, onde a segurança simétrica pós-quântica é menos explorada do que a assimétrica.

---

1. O Problema

Embora o impacto da computação quântica na criptografia de chave pública (devido ao algoritmo de Shor) seja bem compreendido, o cenário para a criptografia de chave simétrica (especificamente cifras de bloco) permanece em grande parte inexplorado.

• Risco Atual: Não existem ataques quânticos "dramáticos" conhecidos contra esquemas simétricos atualmente implantados (como AES), mas a falta de provas rigorosas de segurança impede a seleção precisa de parâmetros.
• Limitação das Práticas Atuais: A prática comum é simplesmente dobrar o tamanho da chave para mitigar o ataque de busca de Grover. No entanto, resultados recentes indicam que isso pode ser excessivo em alguns casos ou insuficiente em outros, especialmente quando se consideram ataques híbridos (clássico + quântico) e modelos de oráculo ideais.
• Desafio Técnico: Provar segurança em um cenário onde o adversário possui um computador quântico e acesso quântico ao oráculo da cifra ideal (Modelo de Cifra Ideal Quântica - QICM), enquanto as construções (modos de operação) são acessadas classicamente.

2. Metodologia e Técnicas Principais

Os autores desenvolvem novas técnicas para provar segurança no Modelo de Cifra Ideal Quântica (QICM), onde o adversário pode fazer consultas quânticas (em superposição) à cifra ideal subjacente, mas as construções derivadas (como FX ou LRW) são consultadas classicamente.

A. Lema de Resampling para Cifras Ideais (Ideal Cipher Resampling)

A contribuição técnica central é um novo Lema de Resampling (Reamostragem) adaptado para o modelo de cifra ideal.

• Funcionamento: O lema quantifica a capacidade de um adversário quântico de detectar modificações locais em uma cifra ideal (por exemplo, trocar dois valores de saída para um chave específica) sem ter feito consultas suficientes para "tocar" nesses pontos.
• Diferencial: Levas anteriores de resampling aplicavam-se apenas a funções aleatórias ou permutações aleatórias. Este trabalho generaliza a técnica para o modelo de cifra ideal, permitindo provar que o adversário não consegue distinguir entre a cifra real e uma versão modificada (idealizada) a menos que realize um número massivo de consultas quânticas.
• Aplicação: Esta técnica é combinada com um argumento de híbrido (hybrid argument) para substituir consultas clássicas a uma construção por consultas a uma permutação aleatória, passo a passo.

B. Abordagem Híbrida (Hybrid Technique)

Os autores utilizam uma sequência de experimentos híbridos onde:

1. Começa-se com o mundo real (construção usando a cifra real).
2. Substitui-se gradualmente as consultas clássicas por uma permutação aleatória.
3. Para evitar argumentos circulares (onde o adversário precisaria saber a chave para distinguir), o método modifica a cifra ideal subjacente em pontos específicos e "reseta" essas modificações posteriormente, usando o Lema de Resampling para garantir que o adversário não detectou a mudança.

3. Principais Contribuições e Resultados

O artigo fornece as primeiras provas de segurança pós-quântica para várias construções fundamentais:

A. Esquema de Extensão de Chave FX

• Construção: Transforma uma cifra de bloco $E$ com chave $m$ em uma cifra com chave mais longa ($m+2n$) usando o esquema $FX(x) = E_{k_0}(x \oplus k_1) \oplus k_2$.
• Resultado: Prova de segurança no QICM com limites de vantagem de distinção estritos (tight).
• Limites: A vantagem do adversário é limitada por termos que envolvem $q_C$ (consultas clássicas) e $q_Q$ (consultas quânticas), especificamente da ordem de $q_C\sqrt{q_Q} \cdot 2^{-(m+n)/2}$.
• Aplicação: Estabelece a segurança pós-quântica para os cifras leves PRINCE e PRIDE, que são baseadas em variantes do FX.

B. Cifras de Bloco com Tweak (Tweakable Block Ciphers)

• Construções: LRW (Liskov-Rivest-Wagner) e XEX2 (base do padrão XTS-AES para criptografia de disco).
• Resultado: Provas de segurança tanto no modelo padrão quanto no QICM.
• Novidade: O limite de segurança para LRW inclui um termo adicional ($6q_C^2 \cdot 2^{-n}$) que corresponde a ataques de colisão clássicos, além dos termos quânticos. Para XEX2, o limite é derivado e mostra segurança robusta contra ataques quânticos completos de recuperação de chave.

C. Modos de Operação de Cifras de Bloco

• Teorema de Elevação (Lifting Theorem): Os autores provam um teorema geral que permite "elevar" a segurança clássica de modos de operação (como CBC, CTR, GCM, CMAC) para o cenário pós-quântico.
• Mecanismo: A segurança pós-quântica de um modo é limitada pela soma da segurança pós-quântica da cifra de bloco subjacente (como um SPRP) e a segurança informação-teórica do modo quando usado com uma permutação aleatória.
• Resultado: Isso implica que a maioria dos modos de operação usados na internet segura (incluindo GCM e GCM-SST) mantém sua segurança pós-quântica, desde que a cifra de bloco subjacente seja segura.

4. Análise de Tightness (Ajuste dos Limites)

Os autores demonstram que seus limites são tight (apertados), ou seja, correspondem à complexidade dos melhores ataques conhecidos:

• Ataques Clássicos: Limitados por colisões de aniversário ($O(2^{n/2})$).
• Ataques Quânticos (Grover): Busca de chave em $O(2^{m/2})$.
• Ataques Híbridos (Offline-Simon e BHT): Ataques que combinam consultas clássicas e quânticas (como o ataque Offline-Simon) atingem exatamente os limites teóricos estabelecidos nas provas (ex: trade-off $q_C \cdot q_Q^2 \approx 2^{m+n}$).

5. Significado e Impacto

• Fundação Teórica: Este trabalho fornece a primeira estrutura rigorosa para analisar a segurança de cifras de bloco contra adversários quânticos, indo além de heurísticas como "dobrar a chave".
• Validação de Padrões: Confirma que construções amplamente utilizadas, como o esquema FX (usado em PRINCE/PRIDE) e o modo XTS-AES (usado em criptografia de disco), possuem garantias de segurança formais no cenário pós-quântico.
• Guia para Parâmetros: Os limites exatos fornecidos permitem que os projetistas de sistemas escolham tamanhos de chave e blocos otimizados para a era pós-quântica, evitando superproteção (custo computacional desnecessário) ou subproteção (vulnerabilidade real).
• Modelo Realista: Ao considerar o modelo onde o adversário tem acesso quântico à cifra ideal, mas as construções são acessadas classicamente (Modelo Q1), o trabalho reflete com precisão a realidade de implementações onde o hardware de criptografia é clássico, mas o atacante possui capacidade quântica.

Em suma, o artigo transforma a segurança simétrica pós-quântica de um campo baseado em suposições para uma disciplina com provas formais e limites de segurança rigorosos.