⚛️ quantum physics

Constant-Rate Certified Deletion

Este artigo apresenta um framework unificado que atualiza uma ampla classe de primitivas criptográficas para suportar exclusão certificada de taxa constante no modelo plano sem suposições adicionais, alcançando as primeiras construções desse tipo que preservam a segurança eterna e permitem verificabilidade pública sob suposições de dureza padrão.

Autores originais: Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada

Publicado 2026-10-05

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada

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

No mundo digital moderno, o direito ao esquecimento é um conceito jurídico que exige mais do que apenas deletar um arquivo; requer prova de que os dados foram verdadeiramente apagados. Este é um desafio fundamental porque a informação clássica, como uma mensagem de texto ou uma foto, pode ser copiada infinitamente. Mesmo que um arquivo seja trancado com um código secreto, um avanço futuro na computação ou uma chave vazada poderiam permitir que um adversário o desbloqueasse e recuperasse o conteúdo original. A única maneira de garantir que os dados foram apagados é confiar nas leis da física, especificamente nas estranhas regras da mecânica quântica. No reino quântico, a informação se comporta de forma diferente: ela não pode ser copiada perfeitamente, e o ato de medi-la inevitavelmente a perturba. Essa natureza destrutiva oferece uma oportunidade única: se um pedaço de dado estiver armazenado em um estado quântico, pode-se forçar um usuário a medi-lo de uma determinada maneira para provar que o destruiu, deixando-o sem meios de recuperar a informação original.

Por anos, pesquisadores trabalharam em um método chamado exclusão certificada, que permite que um usuário gere um certificado provando que deletou um segredo. No entanto, um grande obstáculo sempre foi a eficiência. Métodos anteriores exigiam uma quantidade massiva de armazenamento quântico para proteger até mesmo uma pequena quantidade de dados. Para criptografar um único bit de informação, esses esquemas antigos precisavam de um número de partículas quânticas que crescia linearmente com o nível de segurança, tornando o sistema impraticável para mensagens grandes. Era como tentar enviar um cartão-postal, mas precisar de um armazém cheio de contêineres de transporte apenas para proteger a tinta no papel. Essa ineficiência significava que, embora o conceito fosse teoricamente sólido, era pesado demais para ser útil em aplicações do mundo real, como mensagens seguras ou armazenamento em nuvem.

Uma equipe de pesquisadores resolveu agora este problema ao desenvolver um novo framework que alcança a exclusão certificada de taxa constante. Isso significa que a quantidade de armazenamento quântico necessária cresce em proporção direta ao tamanho da mensagem, em vez de explodir com os requisitos de segurança. Em seu novo sistema, o overhead é mínimo; para uma mensagem grande, os dados quânticos necessários são apenas ligeiramente maiores que a própria mensagem, permitindo uma taxa de eficiência que antes era considerada impossível em configurações padrão. Eles alcançaram isso criando um método unificado que funciona para uma ampla variedade de ferramentas criptográficas, incluindo sistemas usados para criptografia de chave pública, acesso baseado em atributos e criptografia totalmente homomórfica, que permite computações em dados criptografados.

Os pesquisadores demonstraram que sua abordagem funciona para dois tipos distintos de codificações quânticas. O primeiro tipo baseia-se em um método semelhante ao famoso protocolo BB84, usado para distribuição de chaves seguras. O segundo tipo utiliza estruturas mais complexas conhecidas como estados de cosseno de subespaço, que permitem recursos mais avançados como delegação cega e licenciamento de software seguro. Em ambos os casos, o novo framework permite que a mensagem seja criptografada e, em seguida, deletada com um certificado que é verificado sem a necessidade de confiar na pessoa que está realizando a exclusão. Crucialmente, essa eficiência é alcançada sem introduzir quaisquer novas suposições não comprovadas sobre a dificuldade de problemas matemáticos; ela se baseia apenas nos mesmos fundamentos que os esquemas criptográficos originais usavam.

Além de tornar o processo mais rápido e leve, a equipe também mostrou como tornar a verificação da exclusão pública. Em muitos cenários de segurança, não basta que apenas o remetente saiba que os dados foram apagados; uma terceira parte ou um auditor público deve ser capaz de verificar a exclusão sem precisar de acesso a chaves secretas. Tentativas anteriores de adicionar esse recurso de verificação pública destruíram os ganhos de eficiência, exigindo uma quantidade linear de dados extras que negava os benefícios. Os pesquisadores superaram isso usando uma técnica envolvendo assinaturas restritas, um tipo de assinatura digital que pode ser verificada por qualquer pessoa, mas só pode ser criada sob condições específicas. Ao combinar isso com seu framework de taxa constante, eles criaram um sistema onde qualquer pessoa pode verificar que os dados foram deletados, e o sistema permanece eficiente o suficiente para lidar com mensagens grandes.

O trabalho fornece uma solução unificada que atualiza uma ampla classe de primitivas criptográficas para suportar esta exclusão verificável de alta eficiência. Pela primeira vez, é possível ter um sistema onde os dados quânticos necessários para proteger uma mensagem são aproximadamente do mesmo tamanho da própria mensagem, mantendo a garantia de que os dados podem ser provadamente apagados. Este avanço remove o overhead significativo que anteriormente tornava a exclusão certificada impraticável, abrindo as portas para que esses recursos quânticos-seguros sejam integrados em futuras tecnologias de preservação de privacidade. Os pesquisadores provaram que esses resultados se mantêm mesmo contra adversários com poder computacional ilimitado, desde que o certificado de exclusão seja verificado com sucesso, garantindo que os dados sumam para sempre de uma forma que sistemas clássicos jamais poderiam alcançar.

Resumo Técnico: Exclusão Certificada de Taxa Constante

1. Definição do Problema

O artigo aborda o desafio fundamental da Exclusão Certificada (CD - Certified Deletion) na criptografia. A CD permite que um usuário prove a um terceiro que excluiu um dado, mesmo que esse dado tenha sido previamente criptografado. Isso é motivado pelo "direito ao esquecimento" em regulamentações de privacidade (ex: GDPR).

No mundo clássico, a CD é impossível porque a informação clássica pode ser copiada arbitrariamente; um adversário poderia reter uma cópia do texto cifrado e decifrá-lo posteriormente se a chave secreta fosse vazada. A informação quântica oferece uma solução por meio do teorema da não-clonagem e do princípio da incerteza, que impedem um adversário de copiar um estado e medi-lo em duas bases incompatíveis simultaneamente.

No entanto, as construções de CD existentes no modelo puro (sem oráculos aleatórios) sofrem de uma ineficiência crítica: exigem um número linear de qubits ( $\Theta(\lambda)$ ) para criptografar um único bit clássico. Isso resulta em um custo de comunicação total de $\Theta(n\lambda)$ para uma mensagem de $n$ bits, gerando uma taxa subconstante ( $O(\log \lambda)/\Theta(\lambda)$ ). A principal barreira para alcançar a taxa constante de CD (onde o número de qubits é proporcional ao tamanho da mensagem, $O(n)$ ) é a técnica de prova utilizada em trabalhos anteriores (especificamente [BK23]), que depende de "adivinhar" toda a string da mensagem para retardar a dependência do conteúdo real da mensagem. Este passo de adivinhação incorre em uma perda de segurança exponencial em relação ao comprimento da mensagem, tornando-o inviável para mensagens longas.

2. Metodologia

Os autores propõem um framework unificado para superar a barreira da perda de segurança exponencial, permitindo a CD de taxa constante para duas classes amplas de primitivas: aquelas baseadas em estados BB84 e aquelas baseadas em estados de cosset de subespaço.

Inovações Técnicas Centrais

Adivinhação Posição-a-Posição com Extratores Lineares:
Em vez de adivinhar toda a string da mensagem (o que causa perda exponencial), os autores empregam uma estratégia de adivinhação posição-a-posição. Eles substituem o simples extrator XOR (usado em [BK23]) por um extrator linear de alta taxa baseado em um código de Distância Máxima Separável (MDS) sobre um corpo finito $\mathbb{F}$ .
- A mensagem $m$ é mascarada usando um mapa linear $R$ aplicado a um estado quântico, mais um pad aleatório $r$ .
- A prova de segurança procede adivinhando um elemento de campo da mensagem por vez. Para evitar que o adversário obtenha informações sobre as partes não adivinhadas, os autores introduzem um novo pad aleatório $r$ que realiza o one-time pad computacional do vazamento dos bits restantes da mensagem.
Amostragem Diferida e Purificação:
Para restaurar o argumento de "cut-and-choose" no cenário de taxa constante, os autores diferem a amostragem da string de base $\theta$ (ou dos parâmetros do subespaço) até depois que o adversário emite seu certificado de exclusão.
- Eles utilizam técnicas de purificação para tratar o estado quântico como um par EPR emaranhado entre o desafiante e o adversário.
- Ao introduzir o pad aleatório $r$ , eles podem adiar a escolha de $\theta$ sem alterar a distribuição conjunta da visão do adversário. Isso permite que o desafiante meça o estado na base correta apenas após verificar o certificado, garantindo que o adversário tenha efetivamente medido na base errada para os bits relevantes.
Predicados Verificáveis Eficientemente:
Um passo crucial da prova é transferir o argumento de segurança de um "mundo ideal" (onde a criptografia é trivial) para o "mundo real" (onde a criptografia depende de suposições computacionais). Os autores definem um predicado verificável eficientemente que verifica se o estado residual do adversário satisfaz uma condição estrutural específica (ex: ser próximo de um estado onde os erros são esparsos).
- Para estados BB84, isso envolve aplicar uma transformada de Fourier e usar a capacidade de correção de erros do código MDS para recuperar o vetor de erro.
- Para estados de cosset de subespaço, eles utilizam uma estratégia de purificação inteligente que separa o vazamento da parte emaranhada do estado, contornando os problemas de emaranhamento que prejudicaram tentativas anteriores de aplicar essa técnica a estados de cosset.
Verificabilidade Pública via Assinaturas Restritas:
Para alcançar a Exclusão Verificável Publicamente (PVD - Publicly Verifiable Deletion) sem sacrificar a taxa constante, os autores incorporam Assinaturas Restritas (CS - Constrained Signatures) baseadas na suposição Shortest Integer Solution (SIS).
- Em vez de assinar qubits individuais (o que adicionaria um overhead linear), eles assinam toda a superposição do estado quântico de forma coerente.
- Eles utilizam uma chave de assinatura restrita associada a um predicado que verifica se uma string pertence ao conjunto válido definido pela codificação quântica (ex: $T_{x,\theta}$ ).
- Ao aproveitar a privacidade de função das CS e funções de hash 4-vezes independentes (para simular um oráculo aleatório), eles garantem que a assinatura da superposição não vaze informações sobre a mensagem ou base subjacente, mantendo um tamanho de assinatura polinomial no parâmetro de segurança $\lambda$ , mas independente do comprimento da mensagem $n$ .

3. Contribuições Principais e Resultados

A. Exclusão Certificada de Taxa Constante para Estados BB84

Os autores estabelecem um teorema para CD baseado em estados BB84 que alcança uma taxa de $(1-\epsilon)$ para qualquer $\epsilon > 0$ constante.

Escopo: Aplica-se a primitivas do tipo "all-or-nothing", incluindo Esquemas de Compromisso (Commitment Schemes), Criptografia de Chave Secreta (SKE), Criptografia de Chave Pública (PKE), Criptografia Baseada em Atributos (ABE), Criptografia Totalmente Homomórfica (FHE), Criptografia de Liberação Temporal (Timed-Release Encryption) e Witness Encryption.
Mecanismo: Utiliza códigos MDS sobre corpos finitos e a técnica de adivinhação posição-a-posição.
Resultado: O custo de comunicação é de $O(n)$ qubits para uma mensagem de $n$ bits, uma melhoria significativa em relação aos $\Theta(n\lambda)$ anteriores.

B. Exclusão Certificada de Taxa Constante para Estados de Cosset de Subespaço

Os autores estendem o framework para estados de cosset de subespaço, alcançando uma taxa de $1/4$ .

Escopo: Aplica-se a primitivas além do "all-or-nothing", incluindo Delegação Cega (Blind Delegation), Leasing de Software Seguro, Criptografia Funcional (FE), Indistinguibilidade de Inputs Diferentes (diO) e CCA-PKE.
Mecanismo: Utiliza uma nova técnica de purificação que evita as barreiras de emaranhamento presentes nas provas baseadas em BB84 quando aplicadas a estados de cosset.
Resultado: Esta é a primeira construção de taxa constante para essas primitivas avançadas no modelo puro.

C. Exclusão Certificada Verificável Publicamente (PVD)

Sob a dureza da suposição SIS, os autores constroem esquemas de PVD que preservam a propriedade de taxa constante.

Significância: Construções de PVD anteriores exigiam overhead linear (destruindo a taxa) ou dependiam de suposições fortes como Indistinguibilidade de Obfuscação (iO).
Resultado: O artigo fornece as primeiras construções de PVD de taxa constante tanto para primitivas baseadas em BB84 quanto em estados de cosset, assumindo apenas SIS.

4. Significância e Alegações

O artigo afirma resolver um problema de longa data na criptografia quântica: construir esquemas de exclusão certificada com taxa constante no modelo puro enquanto mantém a segurança eterna (segurança contra adversários ilimitados após a exclusão).

Superação de Barreiras: O trabalho identifica e supera explicitamente a "barreira da adivinhação" inerente à técnica de prova do [BK23], que anteriormente limitava a CD a comprimentos de mensagem logarítmicos.
Framework Unificado: Fornece um compilador genérico que atualiza uma ampla gama de primitivas criptográficas para suportar CD sem introduzir novas suposições além das necessárias para as primitivas subjacentes (exceto SIS para PVD).
Eficiência Prática: Ao reduzir o overhead de qubits de linear no parâmetro de segurança para um fator constante, os resultados tornam a exclusão certificada teoricamente viável para aplicações de dados em larga escala.
Modéstia: Os autores observam que, embora alcancem taxas constantes, a taxa para estados BB84 é de aproximadamente $1/3$ (ou $1-\epsilon$ com parâmetros desbalanceados) e $1/4$ para estados de cosset, em vez de se aproximar de 1. Eles também reconhecem que seu compilador PVD para estados de cosset de subespaço não se estende atualmente a todas as primitivas "além do all-or-nothing" (como diO ou FE) devido a dificuldades em descomputar coerentemente assinaturas dentro de funcionalidades clássicas, embora funcione para CCA-PKE.

Em resumo, este trabalho demonstra que a exclusão certificada pode ser alcançada com alta eficiência (taxa constante) e fortes garantias de segurança (segurança eterna e verificabilidade pública) usando suposições de reticulados (lattices) padrão, marcando um passo significativo para a praticidade da exclusão de dados quânticos seguros.