Resumo Técnico: Assinaturas Digitais com Sombras Clássicas em Computadores Quânticos de Curto Prazo

Enunciado do Problema

Esquemas tradicionais de assinatura digital dependem da existência de funções de via única (OWFs), como o fatoração de inteiros (RSA) ou problemas baseados em redes (LWE). Essas suposições são vulneráveis a computadores quânticos tolerantes a falhas (ex: algoritmo de Shor) e são objeto de pesquisa contínua quanto à sua segurança contra adversários quânticos. Embora a mecânica quântica ofereça primitivas criptográficas alternativas fundamentadas em leis físicas em vez de dureza matemática, as propostas existentes para assinaturas digitais quânticas (QDS) geralmente exigem a transmissão e o armazenamento coerente de estados quânticos como chaves públicas. Essa dependência de comunicação quântica de baixo ruído e memória quântica de longa duração torna as propostas atuais impraticáveis para dispositivos quânticos de curto prazo.

O desafio central abordado neste trabalho é a realização de um esquema de assinatura digital quântica que:

1. Não dependa de OWFs ou da existência de funções de via única.
2. Opere utilizando apenas comunicação clássica, eliminando a necessidade de memória quântica ou transmissão quântica de chaves públicas.
3. Seja viável em hardware quântico de escala intermediária ruidosa (NISQ) de curto prazo.

Metodologia

Conceito Central: Sombras Clássicas como Chaves Públicas

Os autores propõem um esquema de assinatura onde as chaves públicas não são estados quânticos, mas sombras clássicas de estados quânticos.

• Chave Secreta: Dois circuitos quânticos aleatórios, $C_0$ e $C_1$.
• Chave Pública: Sombras clássicas, $S(|C_0\rangle)$ e $S(|C_1\rangle)$, geradas através da realização de medições aleatórias nos estados $|C_b\rangle = C_b|0\rangle$.
• Assinatura: Para assinar um bit $b$, o remetente revela a descrição clássica do circuito $C_b$.
• Verificação: O receptor utiliza as sombras públicas e o circuito revelado para verificar se o circuito $C_b$ produz um estado consistente com as sombras públicas. Isso é realizado via um protocolo de sobreposição de sombras (shadow overlap protocol).

Suposição de Segurança: Não-Aprendizado Computacional (CNL)

A segurança do esquema repousa na conjectura de Não-Aprendizado Computacional (CNL) a partir de sombras. Esta conjectura postula que é computacionalmente inviável para um adversário aprender a descrição de um circuito quântico aleatório dado apenas suas sombras clássicas (amostras de medições aleatorizadas de comprimento polinomial).

• Esta suposição é distinta e mais fraca do que a conjectura padrão de "não-aprendizado a partir de estados", pois as sombras são derivadas de cópias de estados via medições simples.
• O artigo fornece evidência teórica de que algoritmos de aprendizado existentes (ex: baseados em inversão local ou argumentos de cone de luz) falham em aprender esses circuitos sob as restrições do protocolo (aprendizado adequado, geometria arbitrária e acesso exclusivo via sombras).
• Os autores demonstram uma separação entre o tempo necessário para verificar uma assinatura (exponencial em $n$, mas viável para o verificador) e o tempo necessário para aprender (simular/falsificar) o circuito (exponencialmente mais difícil), criando um hiato de segurança.

Inovações Técnicas

Para tornar o esquema viável em hardware ruidoso, os autores introduzem duas melhorias técnicas fundamentais:

1. Protocolo de Sobreposição de Sombras Melhorado: Eles modificam protocolos de sobreposição de sombras existentes (baseados na Ref. [30]) utilizando circuitos Clifford aleatórios em subconjuntos de qubits, em vez de apenas medições Pauli aleatórias. Isso reduz o "tempo de relaxação" ($\tau$) da cadeia de Markov de certificação e diminui a variância do estimador, melhorando significativamente a tolerância ao ruído e reduzendo a complexidade de amostragem necessária para a certificação.
2. Detecção de Erros Quânticos (QED): Para superar a infidelidade do hardware, os autores empregam um código de detecção de erros Iceberg multi-bloco.
   • O código Iceberg codifica $k$ qubits lógicos em $k+2$ qubits físicos.
   • Eles utilizam o fixamento de gauge (gauge fixing) para promover certos operadores lógicos a estabilizadores, criando qubits "proxy" que permitem a paralelização de portas lógicas de qubit único, reduzindo assim a profundidade do circuito e os erros de memória.
   • Esta abordagem alcança um desempenho "além do ponto de equilíbrio" (beyond-break-even), onde a fidelidade codificada excede a fidelidade não codificada, apesar do overhead.

Principais Resultados

Evidência Teórica

• Dificuldade de Aprendizado: Os autores mostram que algoritmos conhecidos para aprender circuitos rasos falham em satisfazer as condições necessárias (aprendizado adequado, geometria arbitrária, acesso exclusivo via sombras) para quebrar o esquema.
• Hiato de Segurança: Eles provam que, para conjuntos específicos de circuitos (designs aproximados), a complexidade de tempo para um adversário aprender o circuito via polinômios de baixo grau ou treinamento variacional é exponencialmente maior do que o tempo necessário para a verificação. Especificamente, mostram que o treinamento variacional requer um número exponencial de consultas para atingir a fidelidade alvo para as profundidades de circuito utilizadas.

Demonstração Experimental

Os autores implementaram o protocolo no processador de íons aprisionados Quantinuum H2 (56 qubits físicos).

• Parâmetros do Circuito: Eles geraram sombras para estados de 32 qubits usando circuitos aleatórios com $\ge 80$ portas lógicas de dois qubits (correspondendo a $\ge 582$ portas físicas de dois qubits).
• Fidelidade: Utilizando o código Iceberg multi-bloco com fixamento de gauge, alcançaram uma fidelidade certificada de $0,90 \pm 0,01$ com 17.316 amostras.
• Prova de Conceito: O experimento demonstrou com sucesso a capacidade de distinguir entre um signatário honesto e um adversário. Os autores calcularam que aumentar o tamanho da amostra por um fator de 19,5 (para ~340k amostras) seria suficiente para atingir um parâmetro de segurança onde a probabilidade de um adversário computacionalmente limitado falsificar a assinatura seja desprezível ($< 10^{-5}$).

Significância e Alegações

O artigo afirma demonstrar a viabilidade de curto prazo de assinaturas digitais quânticas que não dependem de OWFs ou de comunicação quântica.

• Independência de OWFs: O esquema fundamenta a segurança na dificuldade física de aprender processos quânticos, oferecendo uma rota para a criptografia que permanece segura mesmo se as OWFs não existirem.
• Compatibilidade com NISM: Ao utilizar sombras clássicas e códigos de detecção de erros em vez de correção de erros completa, o protocolo opera dentro das capacidades do hardware quântico ruidoso atual.
• Primitiva Fundamental: O trabalho estabelece uma ligação entre assinaturas digitais quânticas e quebra-cabeças de via única (one-way puzzles), uma primitiva que permite a construção de outras primitivas criptográficas quânticas (como compromissos de bits não interativos) sem assumir a existência de OWFs.

Os autores enfatizam que, embora a demonstração atual seja uma prova de conceito para uma assinatura de um único bit, as primitivas subjacentes (certificação de sobreposição de sombra e detecção de erro) são escaláveis. Eles observam que estender isso para mensagens de múltiplos bits é possível utilizando códigos de correção de erros clássicos para reduzir os custos de verificação, e que aumentar o tamanho do circuito restauraria a segurança contra potenciais avanços futuros em algoritmos de aprendizado.