Resumo Técnico: Preparação de Estado Remoto Cega ao Eavesdropper e Aplicações à Criptografia de Chave Pública Quântica

1. Definição do Problema

A Preparação de Estado Remoto (RSP - Remote State Preparation) é um primitivo fundamental na criptografia quântica, permitindo que um cliente clássico instrua um servidor quântico a preparar um estado quântico específico usando apenas comunicação clássica. As construções existentes de RSP são centrais para o modelo de Computação Quântica com Comunicação Clássica (QCCC), suportando aplicações como computação delegada, provas de quânticidade e criptografia de chave pública quântica (QPKE).

No entanto, os protocolos de RSP atuais enfrentam duas limitações significativas:

1. Pressupostos Fortes: Todas as construções conhecidas dependem de primitivos criptográficos de "porta dos fundos" (trapdoor), mais notavelmente Funções Livres de Garra com Porta dos Fundos (TCFs - Trapdoor Claw-Free Functions). Essa dependência de trapdoors é um problema aberto importante, uma vez que reduzir os pressupostos criptográficos (por exemplo, para funções de uma via ou estruturas algébricas) continua sendo um objetivo primário na criptografia.
2. Sobrecarga de Segurança: As definições padrão de RSP exigem "cegueira contra o servidor malicioso" (malicious-server blindness), garantindo que o servidor não aprenda nada sobre o estado, mesmo que ele se desvie arbitrariamente do protocolo. Essa noção de segurança forte frequentemente exige protocolos complexos e pressupostos específicos.

O artigo investiga se uma forma mais fraca de RSP ainda pode suportar aplicações criptográficas significativas enquanto admite construções a partir de pressupostos mais fracos e livres de trapdoors. Especificamente, os autores perguntam:

• Podem aplicações úteis ser derivadas de protocolos de RSP com garantias de segurança relaxadas?
• Tais RSPs mais fracas podem ser construídas sem trapdoors?

2. Metodologia e Definições

Preparação de Estado Remoto Cega ao Eavesdropper (EB-RSP)

Os autores introduzem um novo primitivo chamado Preparação de Estado Remoto Cega ao Eavesdropper (EB-RSP). Este relaxa o requisito de cegueira padrão:

• Cegueira Padrão: O provador quântico (servidor) deve não aprender nada sobre o estado preparado, mesmo sendo malicioso.
• Cegueira EB-RSP: O protocolo é cego apenas contra um eavesdropper externo que observa o registro clássico de uma interação honesta entre o verificador e o provador. O próprio provador honesto tem permissão para conhecer o estado que prepara.

Definição Formal: Um protocolo EB-RSP envolve um verificador clássico $V$ e um provador quântico $P$.

• Corretude: $P$ detém um estado $|+\theta\rangle = \frac{1}{\sqrt{2}}(|0\rangle + e^{i\theta}|1\rangle)$ onde $\theta \in \Theta_N = \{k \cdot \frac{2\pi}{N} \mid 0 \le k \le N-1\}$, e $V$ detém a descrição clássica $\theta$.
• Cegueira ao Eavesdropper: Dado o registro da execução honesta, nenhum eavesdropper de tempo polinomial quântico (QPT) pode distinguir o verdadeiro $\theta$ de uma amostra uniformemente aleatória de $\Theta_N$.

Os autores focam especificamente em protocolos EB-RSP de duas mensagens (uma mensagem de $V$, uma de $P$), pois esta estrutura é suficiente para sua principal aplicação.

Pressupostos Criptográficos

O artigo constrói EB-RSP a partir de Ações de Grupo de Uma Via (OWGAs - One-Way Group Actions).

• Ação de Grupo: Um mapa $\star: G \times X \to X$ que satisfaz os axiomas de ação de grupo.
• Livre (Semirregulagem): Uma ação é livre se $g \star x = x$ implica $g = 1$.
• Unidirecionalidade (One-Wayness): Dado $(x, s \star x)$, é computacionalmente difícil para um adversário QPT encontrar $s'$ tal que $s' \star x = s \star x$.
• Distinção Chave: Ao contrário das TCFs, as OWGAs não fornecem inerentemente uma trapdoor para o verificador inverter a função. A construção baseia-se nas propriedades algébricas da ação de grupo para cancelar parâmetros desconhecidos.

3. Principais Contribuições e Resultados

A. Construção de EB-RSP de Duas Mensagens a partir de OWGAs

Os autores apresentam um protocolo concreto de EB-RSP de duas mensagens baseado em OWGAs livres onde $G = \mathbb{Z}_p^\lambda$ para um primo $p$.

Visão Geral do Protocolo:

1. Verificador ($V$): Amostra $x_0 \in X$ e $r, s \in G$. Computa $x_1 = (-s) \star x_0$. Envia $(x_0, x_1, r)$ para $P$.
2. Provador ($P$):
   • Prepara uma superposição sobre $b \in \{0,1\}$ e $g \in G$.
   • Computa $g \star x_b$ em superposição.
   • Mede o registro de saída, colapsando o estado para um estado de "garra" $|0, g_0\rangle + |1, g_0 + s\rangle$ (devido à liberdade da ação).
   • Computa produtos internos com $r$ e aplica Transformadas de Fourier Quânticas (QFT) aos registros.
   • Mede para obter os resultados $g$ e $z$, enviando-os para $V$.
   • Gera o estado $|+\theta\rangle$ onde $\theta = \langle s, z \cdot r + g \rangle \cdot \frac{2\pi}{p}$.
3. Verificador ($V$): Computa $\theta$ usando seu segredo $s$ e os recebidos $g, z$.

Significância da Construção:

• Livre de Trapdoor: O verificador não precisa de uma trapdoor para computar $\theta$. Em vez disso, a estrutura algébrica da ação de grupo garante que parâmetros desconhecidos (como $g_0$) se cancelem durante a medição da QFT, deixando apenas termos conhecidos pelo verificador.
• Segurança: A segurança baseia-se no Teorema de Goldreich-Levin Quântico. Como $g$ é uniformemente aleatório e independente da visão do adversário, o termo $\langle s, z \cdot r + g \rangle$ é computacionalmente indistinguível de uniforme, ocultando $\theta$ do eavesdropper.
• Generalização: O protocolo pode ser estendido para $N$ composto (produto de primos distintos) executando sub-rotinas paralelas.

B. Construção de QPKE a partir de EB-RSP

Os autores demonstram que o EB-RSP de duas mensagens é suficiente para construir Criptografia de Chave Pública Quântica (QPKE) com chaves públicas clássicas e textos cifrados quânticos.

Construção (Black-Box):

• KeyGen: Executa a configuração EB-RSP $n$ vezes. A chave pública $pk$ consiste nas primeiras mensagens do verificador; a chave secreta $sk$ consiste nos estados internos do verificador.
• Enc: Para criptografar um bit $b$, o encriptador (atuando como o provador) executa a computação EB-RSP para cada instância de $pk$ para gerar estados $|+\theta_i\rangle$. Eles então aplicam uma unitária $U_b = R_z(b \cdot \lfloor N/2 \rfloor \cdot \frac{2\pi}{N})$ para inverter a fase baseada em $b$. O texto cifrado é o conjunto de estados transformados e as mensagens do provador.
• Dec: O decriptador usa $sk$ para recuperar $\theta_i$, aplica $R_z(-\theta_i)$ para remover a fase e mede na base de Hadamard para recuperar $b$.

Segurança: A segurança IND-CPA da QPKE depende diretamente da cegueira ao eavesdropper do EB-RSP subjacente. Como o eavesdropper não pode distinguir o ângulo aleatório $\theta$ de um uniforme, ele não pode distinguir o estado criptografado (que depende de $\theta + b \cdot \text{shift}$) de um estado aleatório.

C. Adaptação de Protocolos Existentes Baseados em TCF

O artigo observa que as construções de RSP existentes baseadas em TCFs puras (ex: [BKM+25]) podem ser adaptadas para o modelo EB-RSP de duas mensagens. Ao mesclar mensagens e notar que o "bit de subproduto" (byproduct bit) em RSP baseado em TCF é independente do ângulo em execuções honestas, esses protocolos também satisfazem a cegueira ao eavesdropper. Isso resulta em uma segunda construção de QPKE a partir de TCFs puras.

4. Significância e Alegações

O artigo alega a seguinte significância:

1. Primeiro Primitivo do Tipo RSP Livre de Trapdoor: Tanto quanto o conhecimento dos autores, este é o primeiro primitivo do tipo RSP com aplicações criptográficas úteis que não depende de nenhum primitivo de trapdoor. Demonstra que pressupostos algébricos (OWGAs) podem substituir pressupostos de trapdoor para tarefas específicas de RSP.
2. Segurança Mais Fraca, Mesma Utilidade: O trabalho estabelece que a cegueira ao eavesdropper (uma noção de segurança mais fraca que a cegueza contra servidor malicioso) é suficiente para construir QPKE com chaves públicas clássicas. Isso sugere que os requisitos de segurança fortes de RSP padrão podem ser desnecessários para certas aplicações, potencialmente permitindo protocolos mais simples e pressupostos mais fracos.
3. Abordagem Modular: Os autores fornecem uma redução black-box genérica de EB-RSP de duas mensagens para QPKE. Isso separa a construção do primitivo de preparação de estado de sua aplicação em criptografia, permitindo melhorias modulares em qualquer um dos componentes.
4. Passo Fundamental: Embora a construção seja limitada a ações de grupo específicas e ainda não alcance RSP verificável ou RSP contra servidores maliciosos sem trapdoors, ela fornece um "primeiro passo" para reduzir os pressupostos criptográficos que fundamentam esquemas de criptografia quântica.

Limitações e Questões em Aberto:

• A construção atualmente funciona para $N$ sendo um primo ou um produto de primos distintos; estender para potências de primos permanece incerto devido a problemas de corretude com a QFT sobre potências de primos.
• O artigo não afirma construir RSP verificável ou RSP cego contra servidores maliciosos sem trapdoors; ele deixa isso explicitamente como uma direção aberta.
• O esquema de QPKE resultante produz textos cifrados quânticos, não clássicos (ao contrário de algumas construções baseadas em TCF).

Em resumo, o artigo inicia o estudo de uma noção de RSP mais fraca (EB-RSP), constrói-a a partir de ações de grupo de uma via sem trapdoors e prova sua suficiência para construir QPKE, expandindo assim o panorama de pressupostos disponíveis para a criptografia quântica.