⚛️ quantum physics

A Simple and Efficient One-Shot Signature Scheme

Este artigo apresenta um novo, simples e eficiente esquema de assinatura de tiro único que melhora significativamente a construção de Shmueli-Zhandry ao reduzir os tamanhos de chave e assinatura de complexidade cúbica para quadrática, alcançando correção perfeita e permitindo a compressibilidade forte de assinaturas para aplicações de correção e recuperação de trabalhos recentes relacionados.

Autores originais: Andrew Huang, Vinod Vaikuntanathan

Publicado 2026-07-28

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Andrew Huang, Vinod Vaikuntanathan

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um mundo onde as regras da física permitem a criação de um tipo muito especial de trava digital. No nosso mundo atual, se você tem uma chave para um cofre, pode abri-lo quantas vezes quiser. Mas no estranho reino quântico da criptografia do futuro, cientistas descobriram uma maneira de criar uma chave de "uso único". Pense nisso como um bilhete mágico que se autodestrói. Você pode usar esse bilhete para abrir uma porta e provar que esteve lá, mas no momento em que o utiliza, o bilhete se transforma em pó. Você não pode usá-lo novamente e não pode fazer uma cópia dele para usar depois. Isso não é apenas um truque de mágica legal; é uma ferramenta poderosa que pode levar a dinheiro digital inquebrável, certificados de poder quântico inimitáveis e até uma maneira de queimar segredos digitais para que eles nunca possam ser recuperados.

Por muito tempo, construir essas "assinaturas de uso único" foi como tentar construir um arranha-céu feito de palitos de dente. Era teoricamente possível, mas os designs eram incrivelmente desajeitados, exigindo quantidades massivas de memória quântica (como uma biblioteca de livros apenas para assinar uma única letra) e levavam muito tempo para funcionar. Um avanço recente mostrou que era possível, mas as "chaves" resultantes eram enormes e o processo era lento. Agora, um novo artigo de Andrew Huang e Vinod Vaikuntanathan, do MIT, trouxe um redesign elegante e eficiente. Eles descobriram como construir esses bilhetes digitais autodestrutivos usando muito menos espaço e tempo, tornando toda a ideia prática para o uso no mundo real.

O Bilhete Autodestrutivo

O artigo aborda um problema na criptografia quântica chamado "Assinaturas de Uso Único" (OSS - One-Shot Signatures). Para entender a conquista, imagine que você é um espião tentando enviar uma mensagem secreta. Na versão antiga e desajeitada desse jogo de espião, a "assinatura" (a prova de que você enviou a mensagem) era como uma mochila gigante e pesada. Se você quisesse assinar um bilhete curto, tinha que carregar uma mochila cheia de $\Theta(\lambda^4)$ qubits (o equivalente quântico de bits). Se quisesse assinar uma mensagem mais longa, a mochila ficava ainda maior, e o processo de assinatura era lento e complicado, muitas vezes exigindo que o espião realizasse uma dança complexa de medições quânticas apenas para conseguir realizar o trabalho.

Os autores deste artigo dizem: "Podemos fazer melhor". Eles projetaram um novo sistema simplificado onde a "mochila" é muito menor. Em vez de uma carga massiva de $\Theta(\lambda^4)$ qubits, o novo esquema deles precisa de apenas uma mochila de $\Theta(\lambda^2)$ qubits. Isso é uma redução enorme de tamanho. Além disso, as assinaturas que eles produzem também são menores, encolhendo de $\Theta(\lambda^3)$ bits para $\Theta(\lambda^2)$ bits.

Como Eles Fizeram: O Truque da "Imagem"

O método anterior, criado por Shmueli e Zhandry, era como tentar encontrar uma agulha específica em um palheiro procurando pelo palha (a pré-imagem). Era um pouco como tentar adivinhar uma senha trabalhando de trás para frente a partir do resultado embaralhado, o que exigia muito tentativa e erro e muito "rebobinamento" quântico (tentar repetidamente até acertar). Esse processo era ineficiente e às vezes falhava em produzir uma assinatura válida, o que significava que o espião poderia ficar preso com um bilhete inútil.

Huang e Vaikuntanathan inverteram o roteiro. Em vez de procurar a agulha na palha, eles decidiram procurar a palha na agulha. Em sua nova construção, a "assinatura" é encontrada diretamente na "imagem" da função. Eles usam um algoritmo de busca quântica inteligente (busca de Grover) para encontrar o caminho certo através dos dados. Essa abordagem é como ter um mapa que leva diretamente ao tesouro, em vez de cavar aleatoriamente. Como eles estão procurando no lugar certo, o processo é de "perfeição absoluta". Isso significa que, toda vez que você tenta assinar uma mensagem, o sistema garante que funcionará. Não há chance de falha, não há momentos de "ops, o bilhete não funcionou".

Por Que Isso Importa: O Fogo Quântico

O artigo não se limita a construir mochilas menores. Eles mostram que suas assinaturas eficientes podem ser usadas para construir algo chamado "Fogo Quântico". Imagine que você tem um documento digital que deseja compartilhar com um amigo, mas quer garantir que, assim que ele ler o documento, este seja instantânea e permanentemente destruído, e que ninguém possa jamais fazer uma cópia dele. Este é o conceito de "Fogo Quântico".

As tentativas anteriores de construir esse fogo dependiam das antigas e desajeitadas assinaturas. Os autores apontam que o método antigo tinha um defeito fatal: não era "incompressível". Em termos simples, um hacker poderia pegar as antigas e volumosas assinaturas e comprimi-las em um arquivo minúsculo que ainda conteria informação suficiente para forjar novas assinaturas mais tarde. Era como um fogo que poderia ser apagado e reacendido.

O novo esquema corrige isso. Como suas assinaturas são estruturadas de forma diferente, elas são "incompressíveis". Você não pode encolhê-las sem perder a capacidade de verificá-las. Isso significa que o "Fogo Quântico" que eles constroem é real e confiável. Uma vez que o segredo digital é queimado, ele permanece queimado. Eles também usam isso para corrigir um erro em um artigo recente de Çakan, Goyal e Shmueli, recuperando a capacidade de criar esses segredos digitais seguros e impossíveis de copiar.

O Ponto Principal

Os autores provaram que é possível criar um esquema de assinatura de uso único que é:

Eficiente: Usa significativamente menos memória quântica ( $\Theta(\lambda^2)$ qubits) e produz assinaturas menores ( $\Theta(\lambda^2)$ bits) em comparação com o melhor anterior ( $\Theta(\lambda^4)$ e $\Theta(\lambda^3)$ ).
Simples: Evita os circuitos quânticos complexos de múltiplas etapas que tornavam o método antigo lento e difícil de entender.
Perfeito: Funciona todas as vezes, com zero chance de falha.
Seguro: Impede que hackers comprimam os dados para trapacear o sistema, permitindo a criação de "Fogo Quântico" e outras ferramentas de segurança avançadas.

Embora o artigo observe que ainda há espaço para melhorias (talvez tornando as chaves ainda menores no futuro), eles conseguiram mover a linha de chegada de "teoricamente possível, mas impraticável" para "eficiente e pronto para a próxima geração de segurança quântica". Eles transformaram um tijolo clunky e autodestrutivo em uma pena elegante e autodestrutiva.

Resumo Técnico: Um Esquema de Assinatura de Tiro Único Simples e Eficiente

Declaração do Problema

Assinaturas de tiro único (OSS - one-shot signatures) são um primitivo criptográfico quântico único que permite a um usuário gerar uma chave de verificação pública ($pk$) e um estado de assinatura quântica secreto ( $|sk\rangle$ ). O estado de assinatura permite a produção de uma assinatura válida para exatamente uma mensagem de escolha do usuário; ao assinar, o estado "autodestrói-se", impedindo a geração de uma segunda assinatura. Embora o OSS implique primitivos poderosos como dinheiro quântico, quantum lightning e quantum fire, construir esses elementos de forma eficiente tem sido um desafio.

O avanço recente de Shmueli e Zhandry (SZ) [SZ25] forneceu a primeira construção de OSS. No entanto, seu esquema sofre de ineficiências significativas:

Assinatura Bit a Bit: A construção SZ assina inerentemente mensagens um bit por vez. Para assinar uma mensagem de $\lambda$ bits, o esquema requer repetição paralela, levando a um aumento linear nos tamanhos de chave e assinatura.
Amplificação Complexa: Para alcançar segurança forte, o SZ baseia-se na redução de Dall'Agnol e Spooner (DS) [DS22], que utiliza circuitos complexos de rewinding quântico ou Transformada de Valor Singular Quântica (QSVT) (especificamente algoritmos de projeções alternadas/estilo Marriott-Watrous). Isso introduz um overhead adicional de $\Theta(\lambda)$ no tamanho da chave de assinatura.
Correção Imperfeita: O esquema SZ possui um erro de correção negligenciável, o que significa que o algoritmo de assinatura pode falhar em produzir uma assinatura válida.
Custos de Recursos: No modelo de oráculo, o esquema SZ resulta em chaves de assinatura de tamanho $\Theta(\lambda^4)$ qubits e assinaturas de tamanho $\Theta(\lambda^3)$ bits. No modelo plano (plain model), esses parâmetros são ainda maiores.

Além disso, um trabalho subsequente por Çakan, Goyal e Shmueli (CGS) [C¸GS25] tentou usar OSS para construir "public-key quantum fire", mas baseou-se em uma propriedade de incompressibilidade que o esquema SZ não satisfaz.

Metodologia

Este trabalho propõe uma nova construção direta de assinaturas de tiro único que evita as reduções complexas e as repetições paralelas exigidas por abordagens anteriores. A metodologia central envolve uma mudança fundamental na forma como a assinatura é gerada:

1. Construção Direta via Busca de Grover

Em vez da abordagem SZ, que busca um pré-imagem de uma função de hash começando com um bit específico (exigindo amplificação complexa para lidar com o problema da "vinculação de soma" ou sum-binding), este trabalho busca uma assinatura na imagem de uma função.

A Configuração: O esquema utiliza uma permutação aleatória $\Pi$ e uma família de subespaços definidos por matrizes $\mathbf{A}_y$ e vetores $\mathbf{b}_y$ . O estado de assinatura $|sk\rangle$ é uma superposição uniforme sobre um subespaço afim (coset) definido por esses parâmetros.
O Processo de Assinatura: Para assinar um bit $b$ , o algoritmo não procura por um pré-imagem começando com $b$ . Em vez disso, utiliza um algoritmo de busca de Grover para transformar o estado de superposição inicial em um estado onde os vetores do coset possuem um prefixo específico $b$ em sua imagem sob uma função auxiliar $\mathcal{P}$ .
Uso de Oráculo: O algoritmo de assinatura aplica iterativamente dois oráculos de reflexão:
1. Um oráculo de fase que marca estados onde o prefixo da imagem corresponde ao bit da mensagem.
2. Um oráculo dual $\mathcal{D}$ que reflete através do dual do subespaço.
  Ao iterar este processo $\ell$ vezes ( $\ell$ é o comprimento da mensagem), o algoritmo rotaciona o estado para uma superposição de assinaturas válidas para toda a mensagem. A medição deste estado produz uma assinatura válida.

2. Garantindo Correção Perfeita

Os autores abordam a questão da correção imperfeita projetando cuidadosamente a amostragem da matriz $\mathbf{A}_y$ . Eles garantem que a primeira coluna de $\mathbf{A}_y$ seja não nula, garantindo que, para qualquer chave pública $y$ , o coset contenha vetores começando com 0 e 1. Essa garantia estrutural assegura que a busca de Grover sempre tenha sucesso, alcançando correção perfeita (probabilidade 1).

3. Lidando com Mensagens de Comprimento Polinomial

Em vez de repetir o esquema de bit único $\lambda$ vezes (o que causa o aumento de $\lambda$ ), o esquema assina toda a mensagem de $\lambda$ bits em um único tiro, comprimindo as $\lambda$ assinaturas em uma única assinatura de tamanho $\Theta(\lambda^2)$ . Para comprimentos polinomiais arbitrários, uma transformação padrão de hash-and-sign é aplicada.

4. Incompressibilidade e Quantum Fire

O artigo identifica uma falha na afirmação de CGS [C¸GS25] de que o esquema SZ satisfaz a "assinatura incompressível forte". O esquema SZ falha nesta propriedade porque o algoritmo de assinatura requer acesso tanto aos oráculos direto quanto inverso ( $\mathcal{P}$ e $\mathcal{P}^{-1}$ ), permitindo que um adversário gere assinaturas para chaves fora de uma lista comprimida.
A nova construção modifica o esquema para que a assinatura exija apenas o oráculo dual $\mathcal{D}$ , enquanto a verificação utiliza um oráculo separado $\mathcal{D}_0$ . Essa separação permite uma prova de incompressibilidade de assinatura forte, recuperando a validade das aplicações de quantum fire propostas por CGS.

Principais Contribuições e Resultados

Melhorias de Eficiência

O artigo alcança reduções significativas na complexidade de recursos comparado à construção SZ:

Tamanho da Chave de Assinatura: Reduzido de $\Theta(\lambda^4)$ qubits para $\Theta(\lambda^2)$ qubits.
Tamanho da Assinatura: Reduzido de $\Theta(\lambda^3)$ bits para $\Theta(\lambda^2)$ bits.
Tamanho da Chave Pública: Reduzido de $\Theta(\lambda^3)$ bits (modelo de oráculo) e $\Theta(\lambda^5)$ bits (modelo plano) para $\Theta(\lambda^2)$ bits (modelo de oráculo) e $\Theta(\lambda^4)$ bits (modelo plano).
Tempo de Execução: O algoritmo de assinatura requer significativamente menos consultas de oráculo, evitando o overhead de $\Theta(\lambda)$ associado a circuitos de QSVT/rewinding.

Segurança e Correção

Correção Perfeita: Ao contrário do SZ, o novo esquema garante que uma assinatura válida seja produzida com probabilidade 1.
Segurança Forte: O esquema alcança inforjabilidade forte, o que significa que é inviável produzir uma assinatura válida para uma mensagem diferente ou para uma assinatura diferente para a mesma mensagem.
Incompressibilidade: O esquema satisfaz a incompressibilidade de assinatura forte, uma propriedade necessária para aplicações avançadas como quantum fire.

Resultados Teóricos

O artigo formaliza essas melhorias em dois teoremas principais:

Teorema 1.1: Estabelece a existência de esquemas de OSS eficientes para mensagens de comprimento polinomial com correção perfeita tanto no modelo de oráculo clássico (incondicionalmente) quanto no modelo plano (assumindo obscuridade de ocultação quântica pós-quântica e LWE).
Teorema 1.2: Demonstra que o novo esquema de OSS incompressível permite a construção de esquemas de public-key quantum fire e key-fire com correção perfeita, corrigindo os erros no trabalho de CGS [C¸GS25].

Significância

O artigo afirma fornecer uma alternativa "simples, direta e eficiente" aos esquemas de assinatura de tiro único de estado da arte. Ao contornar as reduções complexas (DS [DS22]) e as estratégias de repetição paralela usadas em trabalhos anteriores, os autores alcançam uma melhoria quadrática nos tamanhos de chave e assinatura.

A significância deste trabalho é dupla:

Eficiência Prática: Torna os esquemas de assinatura quântica significativamente mais viáveis ao reduzir os requisitos de qubits e bits de escalas quárticas/cúbicas para escalas quadráticas.
Correção Fundamental: Retifica uma lacuna crítica na literatura referente à incompressibilidade de OSS. Ao corrigir a propriedade de incompressibilidade, o artigo valida e possibilita a construção de primitivos de "quantum fire" e relacionados, que anteriormente eram alegados como possíveis, mas dependiam de uma premissa falha sobre o esquema SZ.

Os autores observam que, embora tenham otimizado os parâmetros significativamente, melhorias adicionais para $\Theta(\lambda)$ no modelo de oráculo podem exigir técnicas inteiramente novas, já que o gargalo atual reside na análise do caso livre de dual. Da mesma forma, melhorar os parâmetros do modelo plano permanece como um problema em aberto.