Resumo Técnico: Como Não Construir Microcrypt

1. Definição do Problema

O campo da criptografia quântica tem se concentrado recentemente na "Microcrypt": a construção de primitivas criptográficas (tais como Estados Pseudorandoms (PRS), Unitárias Pseudorandoms (PRU) e Geradores de Estado Unidirecionais (OWSG)) baseadas em suposições mais fracas que funções unidirecionais (OWF) clássicas. Especificamente, pesquisadores buscam primitivas que permaneçam seguras mesmo contra adversários equipados com um oráculo NP.

Embora várias construções candidatas tenham sido propostas (ex: Estados de Fase Hamiltoniana, ações de grupo IQP e várias arquiteturas Clifford-Monomial-Clifford), houve uma falta de criptoanálise sistemática contra adversários auxiliados por NP. Um desafio central é determinar se essas construções inadvertidamente implicam a existência de funções unidirecionais clássicas, o que as tornaria inadequadas para a Microcrypt. Este artigo aborda a questão: Quais receitas naturais para construir PRS e PRUs falham porque implicam funções unidirecionais ou dureza NP?

2. Metodologia

Os autores desenvolvem dois frameworks técnicos primários para analisar e quebrar construções candidatas:

A. Tomografia de Sombra Auxiliada por NP de Estados Computáveis

Os autores introduzem um algoritmo eficiente para aprender estados quânticos usando um oráculo NP.

• Estados Computáveis: Uma família de estados $\{|\psi_k\rangle\}$ é definida como computável se, dado uma chave $k$, a amplitude e a fase de qualquer termo da base computacional puderem ser computadas classicamente de forma eficiente.
• A Estratégia de Ataque: O algoritmo procede em duas etapas:
  1. Correspondência de Distribuição de Base: Ele mede cópias do estado desconhecido na base computacional para obter um transcrito clássico. Usando um oráculo NP, ele busca por uma chave candidata $k_0$ cuja distribuição de medição prevista maximize a verossimilhança do transcrito observado. Isso recupera uma chave que aproxima a distribuição de magnitude do estado desconhecido.
  2. Extração de Fase via Interferência: Para recuperar a informação de fase (que as medições de base descartam), o algoritmo constrói um "estado de referência" $|\psi_{k_0}^+\rangle$ (o estado de amplitude positiva da chave candidata). Ele então realiza um experimento de interferência controlled-SWAP entre o estado desconhecido e este estado de referência. Isso permite a extração de informação de fase relativa.
  3. Recuperação Final da Chave: O algoritmo coleta amostras desta distribuição de interferência e usa uma segunda consulta NP para encontrar uma chave $h$ que maximize a verossimilhança destas amostras sensíveis à fase.
• Resultado: Para qualquer família de OWSG com estados computáveis, um adversário com um oráculo NP pode inverter o gerador (encontrar uma chave que produz um estado de alta fidelidade) em tempo polinomial.

B. Aprendizado de Unitárias Auxiliado por NP (Ataque CMC)

Os autores desenvolvem um ataque específico contra famílias unitárias da forma $U_k = C_{2,k} M_k C_{1,k}$, onde $C$ são unitárias de Clifford e $M$ é uma camada monomial (permutação com fases).

• A Estratégia: O ataque utiliza medições de par de Bell. Ao preparar um estado de Bell $|\beta_{a,c}\rangle$, aplicar a unitária desconhecida $U$ a ambos os registradores e medir na base de Bell, o adversário obtém restrições de "deslocamento".
• Correção de Clifford: Como as camadas externas são Clifford, o adversário pode computar classicamente como essas camadas permutam os rótulos da base de Bell. Ao "desfazer" as camadas de Clifford classicamente, o problema reduz-se a verificar se os deslocamentos observados são consistentes com a camada monomial do meio $M_k$.
• Consulta NP: O adversário pergunta a um oráculo NP: "Existe uma única chave $h$ e um conjunto de strings testemunhas que explicam todas as restrições de deslocamento observadas?"
• Resultado: Para qualquer construção CMC deste tipo, o oráculo NP pode distinguir a unitária de uma unitária Haar-random com alta probabilidade usando polinomialmente muitas consultas. Além disso, a redução de busca-para-decisão permite que o adversário aprenda a chave.

3. Contribuições Principais e Resultados

A. Invertendo OWSGs Computáveis

O artigo prova que todas as famílias de OWSG com estados computáveis são invertíveis em BQPNP (Tempo Polinomial Quântico com acesso a um oráculo NP).

• Implicação para Funções Unidirecionais: Se um OWSG não é apenas computável, mas também amostrável (significando que se pode amostrar eficientemente de forma clássica a partir da distribuição de medição do estado dada a chave), então a existência de tal OWSG implica a existência de uma função unidirecional clássica.
• Quebras Específicas: Este resultado quebra a segurança de:
  • Estados de Fase Hamiltoniana (HPS): Anteriormente conjecturadas para depender de suposições mais fracas que OWF, os autores mostram que elas implicam OWFs.
  • Estados de Ação de Grupo IQP: As suposições de dureza propostas por Morimae e Xagawa são mostradas para implicar OWFs.

B. Quebrando Unitárias Pseudorandoms (PRUs)

O artigo demonstra que muitas arquiteturas de PRU proeminentes são inseguras contra adversários auxiliados por NP:

• PFC e C2PFC1: Construções envolvendo uma camada de permutação/fase entre Cliffords (ex: $C_2 P F C_1$) podem ser distinguidas de Haar random e aprendidas.
• LRFC e Variantes Bloqueadas: Várias construções Luby-Rackoff com extremidades de Clifford são quebradas.
• Generalização: O ataque se aplica a qualquer família de unitárias onde a camada "do meio" é monomial e as extremidades são Cliffords descritíveis eficientemente.

C. Identificação de Candidatos Sobreviventes

O artigo lista explicitamente construções para as quais suas técnicas atuais não fornecem um ataque, observando que estas permanecem caminhos plausíveis (embora não provados) para a Microcrypt. Estas incluem:

• Caminhadas completas de PRSS (Pseudorandom State Scrambler) com muitos ciclos de mistura.
• Caminhadas longas de Kac.
• Construções com blocos sobrepostos ou Cliffords intermediários entre camadas monomiais (ex: a terceira forma de LRFC bloqueada).
• Dinâmica de Hamiltoniana de base oculta.

4. Significância e Alegações

Os autores posicionam este trabalho como o estabelecimento de "guardrails" (proteções) para o campo da Microcrypt. Suas principais alegações são:

1. Criptoanálise Sistemática: Eles vão além de ataques ad-hoc para fornecer uma metodologia geral (tomografia de sombra auxiliada por NP e análise CMC) para avaliar candidatos de criptografia quântica.
2. Resultados de Não-Existência (No-Go Results): Eles demonstram que uma grande classe de construções "naturais" — especificamente aquelas que dependem de amplitudes computáveis ou arquiteturas Clifford-Monomial-Clifford — não podem realizar Microcrypt porque inadvertidamente implicam funções unidirecionais clássicas ou são quebradas por oráculos NP.
3. Direção para Pesquisa Futura: Ao identificar quais arquiteturas falham, o artigo estreita o espaço de busca para primitivas viáveis de Microcrypt. Sugere que construções futuras devem provavelmente depender de suposições plausivelmente fora da classe de complexidade NP e evitar os padrões estruturais específicos (amplitudes computáveis, formas simples de Clifford-Monomial-Clifford) que os autores mostraram serem vulneráveis.

O artigo conclui que, embora o cenário da Microcrypt ainda esteja aberto, os "frutos baixos" das construções de estados computáveis e amostráveis, bem como as arquiteturas unitárias CMC padrão, foram descartados como candidatos para criptografia sem funções unidirecionais.