Experimental asymmetric relativistic zero-knowledge proofs with unconditional security

Este artigo apresenta um protocolo de prova de conhecimento zero relativístico assimétrico, eficiente e experimentalmente verificado, que alcança segurança incondicional contra ataques quânticos ao alavancar a relatividade especial e a não localidade quântica, superando, assim, a complexidade de rodadas impraticável de abordagens simétricas anteriores.

O essencial

O Panorama Geral: Provando que Você Sabe um Segredo Sem Contá-lo

Imagine que você tem o mapa secreto de um tesouro e quer convencer um guarda cético de que você realmente possui o mapa. Você não quer mostrar o mapa a ele (porque ele pode roubá-lo), e não quer dizer a ele onde o tesouro está. Você apenas quer provar: "Eu conheço o caminho".

No mundo digital, isso é chamado de Prova de Conhecimento Zero (Zero-Knowledge Proof - ZKP). É o truque de mágica que permite provar quem você é ou que possui dinheiro suficiente para uma transação, sem revelar sua senha ou seu saldo bancário.

O Problema: O Monstro Quântico

Por décadas, esses truques de mágica digitais dependeram de enigmas matemáticos que eram difíceis para humanos resolverem, mas fáceis para computadores. No entanto, cientistas estão construindo Computadores Quânticos, que são como monstros supervelozes. Esses monstros podem resolver esses antigos enigmas matemáticos quase instantaneamente, quebrando a segurança de nossas atuais fechaduras digitais.

Precisamos de um novo tipo de fechadura que não dependa de enigmas matemáticos. Precisamos de uma fechadura baseada nas leis da física.

A Solução: A Fechadura da "Velocidade da Luz"

Este artigo apresenta um novo tipo de prova chamada Prova de Conhecimento Zero Relativística. Em vez de depender de matemática difícil, ela depende da Velocidade da Luz.

A Analogia: O Dragão de Duas Cabeças
Imagine que você tem um dragão com duas cabeças (vamos chamá-las de Cabeça A e Cabeça B). Você quer provar a um juiz que o dragão é real, mas não pode deixar as cabeças conversarem entre si.

• O juiz fica longe da Cabeça A.
• Outro juiz fica longe da Cabeça B.
• A distância é tão grande que mesmo um feixe de luz (a coisa mais rápida do universo) não consegue viajar da Cabeça A para a Cabeça B no tempo necessário para responder a uma pergunta.

Como a Cabeça A e a Cabeça B não conseguem se comunicar rápido o suficiente para coordenar uma mentira, elas são forçadas a dizer a verdade. Se tentarem trapacear, as leis da física (especificamente, que nada viaja mais rápido que a luz) as pegam.

O Que Esta Equipe Fez

Os pesquisadores construíram uma versão funcional desta prova de "Velocidade da Luz". Veja como eles a melhoraram:

1. O Jeito Antigo Era Muito Lento: Tentativas anteriores desta prova do "dragão de duas cabeças" eram como tentar resolver um labirinto gigante caminhando por cada caminho um por um. Se o mapa (o grafo) fosse grande, levaria milhares de anos para terminar a prova. Era teoricamente possível, mas praticamente inútil.
2. O Novo Jeito é Rápido: A equipe projetou uma versão assimétrica mais inteligente. Pense nisso como ter uma das cabeças do dragão fazendo todo o trabalho pesado enquanto a outra apenas observa.
   • O Resultado: Eles reduziram o tempo necessário de "milhares de anos" para 0,22 segundos.
   • O Custo: Eles usaram um pouco mais de "aleatoriedade" (como embaralhar um baralho de cartas mais vezes), mas a quantidade total de dados usada ainda era pequena o suficiente para caber em um disco rígido moderno (cerca de 430 MB).

O Experimento

Para provar que isso funciona no mundo real, eles montaram um experimento na Universidade de Nanjing:

• Eles colocaram dois computadores (as "cabeças") em edifícios diferentes a 300 metros de distância.
• Usaram lasers de alta velocidade e relógios de GPS para garantir que os computadores não pudessem conversar entre si mais rápido que a luz.
• Pediram aos computadores para provarem que sabiam como colorir um mapa complexo com apenas três cores (um clássico enigma matemático) sem mostrar as cores.
• O Resultado: Os computadores completaram toda a prova em 0,22 segundos.

Por Que Isso Importa

O artigo afirma que este é um grande passo à frente porque:

• É Seguro contra Computação Quântica: Mesmo que um computador quântico tente quebrar o código, ele não pode trapacear porque não pode quebrar as leis da física (a velocidade da luz).
• É Prático: Diferente de versões anteriores que eram lentas demais para serem usadas, esta é rápida o suficiente para uso na vida real, como para garantir transações bancárias online ou votações.
• É Incondicional: Não depende de "achamos que esta matemática é difícil". Depende de "sabemos que a luz tem um limite de velocidade".

Resumo

Os pesquisadores pegaram uma ideia teórica — usar a velocidade da luz para impedir mentirosos — e construíram uma máquina funcional que faz isso em uma fração de segundo. Eles resolveram o problema de ser lento demais fazendo com que um lado do sistema fizesse mais trabalho, o que permitiu que todo o processo fosse incrivelmente rápido e seguro contra futuros computadores quânticos.

Resumo técnico

Resumo Técnico: Provas de Conhecimento Zero Relativísticas Assimétricas Experimentais com Segurança Incondicional

Definição do Problema

As provas de conhecimento zero (ZKPs) são críticas para estabelecer confiança e privacidade em economias digitais, como criptomoedas e contratos inteligentes. No entanto, os protocolos clássicos de ZKP dependem de suposições computacionais (por exemplo, a existência de funções de via única), tornando-os vulneráveis a futuros ataques quânticos. As ZKPs quânticas oferecem uma alternativa potencial, mas enfrentam obstáculos significativos de implementação, incluindo o teorema da não-clonagem, que complica o rewinding quântico, e a impossibilidade de um compromisso de bit quântico incondicionalmente seguro.

As RZKPs (Provas de Conhecimento Zero Relativísticas) surgiram como uma solução ao substituir suposições computacionais pelos princípios da relatividade especial (especificamente o princípio da não-sinalização). Um avanço recente demonstrou uma RZKP simétrica para o problema de coloração de três cores de grafos. Contudo, este protocolo simétrico sofre de ineficiências proibitivas ao garantir a segurança quântica (segurança contra provadores que compartilham emaranhamento quântico). Para alcançar a segurança quântica, o protocolo simétrico exige uma complexidade de rodadas de $O(|E|^4)$ (onde $|E|$ é o número de arestas), levando a tempos de execução inalcançáveis e custos massivos de aleatoriedade para grafos de tamanho realista.

Metodologia

Os autores propõem e implementam experimentalmente um protocolo de GMW ZKP relativístico assimétrico projetado para superar as limitações de eficiência das abordagens simétricas anteriores, mantendo a segurança incondicional contra provadores correlacionados quânticamente.

Design do Protocolo

O protocolo envolve dois pares de provador-verificador ($P_1-V_1$ e $P_2-V_2$) e opera sobre $m$ rodadas interativas para provar que um grafo $G(V, E)$ é colorível com três cores sem revelar a coloração.

1. Preparação: Os provadores $P_1$ e $P_2$ compartilham uma permutação de cores aleatória $\pi$ e um conjunto de valores aleatórios $B = \{b_k\}$.
2. Fase de Consulta: O verificador $V_1$ envia consultas aleatórias $X = \{x_k\}$ para $P_1$.
3. Fase de Compromisso: $P_1$ computa compromissos $A = \{a_k\}$, onde $a_k = x_k \cdot y_k - b_k$ (sendo $y_k$ a cor) e os envia para $V_1$.
4. Fase de Desafio: O verificador $V_2$ seleciona uma aresta aleatória $C = \{i, j\}$ e a envia para $P_2$.
5. Fase de Revelação: $P_2$ revela as cores $Y(C)$ e os valores correspondentes $B(C)$ para $V_2$.
6. Fase de Verificação: Os verificadores checam as restrições relativísticas (garantindo que não haja sinalização entre $P_1$ e $P_2 ao verificar os atrasos de tempo$|t_1 - t_4| < \tau$e$|t_2 - t_3| < \tau$, onde $\tau = d/c$) e a consistência lógica (as cores são distintas e correspondem aos compromissos).

Análise Teórica

Os autores abordam o desafio da segurança quântica. Diferente dos protocolos clássicos onde o compromisso de bit é fortemente vinculativo (strongly binding), os compromissos de bit relativísticos garantem apenas o "vinculamento de soma" (sum-binding). Os autores demonstram que a probabilidade de provadores quânticos maliciosos trapacearem com sucesso em uma aresta inválida é limitada superiormente pelo valor quântico de um jogo não-local CHSH$_{Q(2)}$. Ao relacionar o erro de segurança do protocolo a este jogo, eles derivam um limite superior rigoroso para o erro de segurança quântica $\delta$.

Implementação Experimental

A equipe implementou um experimento de prova de conceito utilizando:

• Hardware: FPGAs para processamento de baixa latência e servidores de sincronização de tempo GPS de alta precisão (com relógios atômicos) para temporização.
• Configuração: Dois pares de provador-verificador separados por 300 metros (correspondendo a uma separação de tempo $\tau = 1000$ ns).
• Grafo: Um grafo colorível com três cores com $|V| = 588$ vértices e $|E| = 1097$ arestas.
• Execução: O experimento completou todas as rodadas interativas necessárias em aproximadamente 0,22 segundos.

Principais Contribuições

1. Protocolo Assimétrico Eficiente: Os autores projetaram um GMW ZKP relativístico assimétrico que reduz a complexidade de rodadas de $O(|E|^4)$ (em protocolos simétricos anteriores de segurança quântica) para $O(|E|)$. Isso é alcançado através do uso de compromissos de bit relativísticos de dois provadores dentro da estrutura GMW, permitindo que a prova e as verificações de consistência ocorram simultaneamente em uma única rodada.
2. Prova de Segurança Quântica: Eles forneceram uma prova rigorosa de segurança quântica ao relacionar a probabilidade de trapaça de provadores emaranhados ao jogo não-local CHSH$_{Q(2)}$, estabelecendo um limite superior para o erro de segurança sem depender de suposições computacionais.
3. Realização Experimental: Eles executaram com sucesso o protocolo sobre uma separação de 300 metros, demonstrando que o tempo de execução e o custo de aleatoriedade exigidos são viáveis para implantações no mundo real.

Resultados

• Complexidade de Rodadas: O protocolo requer $m = 2k|E|$ rodadas para atingir um erro de segurança de $e^{-k}$. Para os parâmetros experimentais ($|E|=1097, k=100$), isso resultou em aproximadamente $2,2 \times 10^5$ rodadas.
• Tempo de Execução: Todo o experimento foi concluído em 0,22 segundos. Em contraste, o protocolo simétrico anterior [23] teria exigido aproximadamente $6,72 \times 10^4$ anos para atingir o mesmo nível de segurança com o mesmo grafo.
• Custo de Aleatoriedade: O custo total de aleatoriedade para o experimento foi de 430,81 MB. O protocolo simétrico [23] teria exigido aproximadamente $5,92 \times 10^9$ GB (5,92 exabytes) para a mesma tarefa.
• Segurança: As diferenças de tempo $|t_1 - t_4|$ e $|t_2 - t_3|$ foram consistentemente medidas abaixo do limite de 1000 ns, satisfazendo as restrições de não-sinalização relativística, mesmo considerando erros de sincronização de GPS.

Significância e Alegações

O artigo afirma que este trabalho ilustra o potencial poderoso de integrar a relatividade especial com a teoria quântica para criar sistemas de confiança sem necessidade de confiança (trustless) que sejam seguros contra ataques quânticos sem depender de suposições de dureza computacional.

As principais alegações de significância incluem:

• Viabilidade Prática: A redução na complexidade de rodadas de $O(|E|^4)$ para $O(|E|)$ transforma as RZKPs de construtos teóricos em tecnologias praticamente implantáveis para cenários reais envolvendo grafos de tamanho razoável.
• Segurança Incondicional: O protocolo oferece segurança quântica e propriedades de conhecimento zero baseadas puramente no princípio da não-sinalização, tornando-o robusto contra futuros avanços da computação quântica.
• Potencial de Escalabilidade: Embora a natureza assimétrica imponha uma carga computacional maior a um par provador-verificador ($V_1-P_1$), os autores argumentam que o trade-off é necessário para alcançar tempos de execução viáveis. Eles sugerem que o protocolo pode ser implementado em dispositivos cotidianos, como smartphones.
• Aplicações Futuras: Os autores destacam potenciais aplicações em domínios sensíveis à privacidade, como blockchains, contratos inteligentes, votação eletrônica anônima e leilões online. Eles também observam o potencial de estender este framework para Provas de Conhecimento de Conhecimento (ZKPoK) para verificação de identidade.

Os autores permanecem modestos quanto aos desafios de escalabilidade, reconhecendo que a implantação prática em redes de fibra óptica ainda enfrenta obstáculos, como a verificação da posição precisa dos provadores e a gestão de cargas computacionais, que identificam como problemas abertos para pesquisas futuras.