Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM

Resumo Técnico: Impossibilidade de Acordo de Chave Perfeitamente Completo de Múltiplos Ciclos no QROM

Enunciado do Problema
Este artigo aborda os limites fundamentais do Acordo de Chave Quântica (QKA) dentro do Modelo de Oráculo Aleatório Quântico (QROM). Especificamente, investiga se duas partes, Alice e Bob, podem estabelecer uma chave secreta compartilhada com completude perfeita (probabilidade 1) usando apenas comunicação clássica, enquanto realizam computações quânticas locais e fazem consultas quânticas a um oráculo aleatório. O cenário é o modelo de Computação Quântica com Comunicação Clássica (QCCC). A questão central é se tais protocolos podem ser seguros contra um espião passivo que observa o transcrito clássico e tem acesso ao mesmo oráculo, assumindo que o protocolo é construído a partir de funções de sentido único (OWFs) quânticamente seguras de maneira black-box.

Trabalhos anteriores estabeleceram separações para protocolos clássicos e casos quânticos específicos, mas lacunas permaneciam para protocolos QCCC gerais de múltiplos ciclos. Notadamente, Austrin et al. (CRYPTO 22) forneceram um ataque de consulta polinomial sob uma "Conjectura de Compatibilidade Polinomial" não comprovada, enquanto Li et al. (CRYPTO 26) resolveram o caso para protocolos de dois ciclos incondicionalmente. Este artigo busca fechar a lacuna para protocolos de ciclos arbitrários sem depender de conjecturas não comprovadas.

Metodologia
Os autores empregam uma combinação de teoria de complexidade de consulta quântica, análise de polinômios sobre funções booleanas e complexidade de árvore de decisão para construir um ataque incondicional. A metodologia central procede da seguinte forma:

1. Fatoração Polinomial das Probabilidades do Transcrito:
   Ao fixar o transcrito clássico completo $t$ e a tabela de verdade do oráculo $z$, mostra-se que a probabilidade de Alice e Bob produzirem chaves específicas $a$ e $b$ fatoriza em $A_{t,a}(z) \cdot B_{t,b}(z)$. Aqui, $A$ e $B$ são funções não negativas que representam as probabilidades de execução local de Alice e Bob, respectivamente.

   • Usando o método polinomial quântico (especificamente o Lema 2.2 de [BBC+01]), os autores limitam os graus dessas funções: $\deg(A_{t,a}) \le 2q_A$ e $\deg(B_{t,b}) \le 2q_B$, onde $q_A$ e $q_B$ são o número de consultas quânticas feitas pelas partes honestas.

2. Suportes de Chaves Disjuntos via Completude Perfeita:
   A condição de completude perfeita ($Pr[K_A = K_B] = 1$) implica que, para qualquer transcrito válido $t$ e oráculo $z$, o produto $A_{t,k}(z)B_{t,\ell}(z)$ deve ser zero para todas as chaves distintas $k \neq \ell$.

   • Definindo $C_{t,k}(z) = A_{t,k}(z)B_{t,k}(z)$, os autores demonstram que os suportes desses polinômios são pairwise disjuntos no cubo booleano $\{0,1\}^N$.
   • Essa disjunção, combinada com o fato de que um polinômio multilinear não nulo de grau $d$ deve ser não nulo em pelo menos $2^{N-d}$ pontos (Lema 2.1), limita o número de chaves candidatas $|K_t|$ a no máximo $2^d$, onde $d = 2(q_A + q_B)$.

3. Árvore de Decisão para Polinômios Disjuntos:
   A contribuição técnica crítica é um procedimento determinístico (Lema 3.5) para identificar qual de dois polinômios de suporte disjunto, $p$ e $q$, é não nulo em um oráculo $z$ específico, dada a promessa de que um deles é não nulo.

   • O procedimento utiliza uma árvore de decisão recursiva. Em cada etapa, identifica-se um conjunto de $O(d^3)$ bits do oráculo tal que consultá-los determina a resposta ou reduz estritamente o grau de um dos polinômios.
   • Esta redução baseia-se em uma desigualdade de Markov discreta (Lema 2.3) aplicada a um polinômio $r$ derivado da diferença dos quadrados das entradas.
   • A profundidade desta árvore de decisão é mostrada como sendo $O(d^4)$.

4. Estratégia de Busca Binária:
   O espião realiza uma busca binária balanceada sobre o conjunto de chaves candidatas $K_t$ (tamanho $\le 2^d$). Em cada nível, o conjunto de candidatos é dividido em duas metades, e as somas dos polinômios correspondentes ($P$ e $Q$) são formadas. Como os suportes são disjuntos, exatamente um de $P(z)$ ou $Q(z)$ é não nulo. A árvore de decisão do passo 3 é usada para determinar qual metade contém a chave correta.

   • Com no máximo $d$ níveis de busca binária e $O(d^4)$ consultas por nível, a complexidade de consulta total é $O(d^5)$.

Principais Contribuições e Resultados

• Impossibilidade Incondicional: O artigo prova que é impossível construir protocolos de acordo de chave QCCC de ciclos finitos e com completude perfeita a partir de funções de sentido único (OWFs) quânticamente seguras de maneira black-box no QROM. Este resultado é incondicional, removendo a "Conjectura de Compatibilidade Polinomial" exigida pelo trabalho anterior [ACC+22].
• Limite de Complexidade de Consulta: Os autores constroem um espião que recupera a chave compartilhada com probabilidade 1 usando $O((q_A + q_B)^5)$ consultas de oráculo clássicas.
  • Este limite é independente do número de rodadas de comunicação, do comprimento do transcrito, do comprimento da chave e do tamanho do domínio do oráculo.
  • Crucialmente, embora as partes honestas possam usar consultas de superposição, o espião requer apenas consultas clássicas.
• Generalização: O resultado generaliza as descobertas anteriores sobre protocolos de dois ciclos [LLLL26] para ciclos arbitrários e permite que as partes mantenham estados quânticos arbitrários entre as etapas de comunicação, um cenário não coberto por resultados incondicionais prévios.

Significância e Alegações
O artigo afirma fornecer uma resposta negativa definitiva à segurança de QKA de múltiplos ciclos e com completude perfeita no QROM.

• Impacto Teórico: Estabelece uma separação black-box estrita entre funções de sentido único quânticamente seguras e acordo de chave de completude perfeita no cenário QCCC.
• Avanço Metodológico: A prova introduz uma aplicação inovadora de redução de grau de polinômio e complexidade de árvore de decisão ao problema de recuperação de chave, lidando especificamente com o caso onde as partes honestas usam superposição quântica, mas o atacante é restrito a consultas clássicas.
• Limitações: Os autores declaram explicitamente que a prova depende da completude perfeita. Estender este resultado para protocolos com completude imperfeita (onde as partes podem falhar em concordar com alguma pequena probabilidade) exigiria ideias significativamente diferentes e não é coberto por este trabalho.
• Atribuição: O artigo observa que o núcleo da prova foi descoberto pelo GPT-5.6 Sol Ultra em uma única conversa, com os autores humanos responsáveis pela verificação, refinamento e a exposição final.

Em resumo, o artigo demonstra que, no QROM, a combinação de comunicação clássica e completude perfeita é insuficiente para proteger o acordo de chave de um espião clássico eficiente, independentemente do número de ciclos ou da complexidade das computações quânticas locais.