Quantum Oracle Distribution Switching and its Applications to Fully Anonymous Ring Signatures

Título: Alternância de Distribuição de Oracle Quântico e suas Aplicações a Assinaturas em Anel Totalmente Anônimas

Autores: Marvin Beckmann e Christian Majenz (DTU - Universidade Técnica da Dinamarca)

---

1. Problema e Motivação

As assinaturas em anel (Ring Signatures - RSS) são primitivas criptográficas que permitem a um membro de um grupo assinar uma mensagem em nome do grupo sem revelar sua identidade. Elas são componentes essenciais para protocolos de troca de chaves autenticadas e negáveis (DAKE), como o protocolo Signal (usado no WhatsApp, Signal, etc.), que requerem anonimato total mesmo sob exposição completa das chaves.

O problema central abordado neste trabalho é a segurança pós-quântica (PQ) dessas construções.

• Atualmente, as principais construções de RSS usadas para DAKEs conformes ao Signal (como Erebor, MayoRS, Gandalf e FalconRS) são provadas seguras apenas no Modelo de Oracle Aleatório Clássico (ROM).
• No cenário pós-quântico, a segurança deve ser provada no Modelo de Oracle Aleatório Quântico (QROM), onde o adversário tem acesso quântico ao oráculo (pode fazer superposições de consultas).
• Muitas provas clássicas dependem de técnicas (como reprogramação de oráculos ou uso de Divergência de Rényi) que não se traduzem diretamente para o QROM ou falham devido a ataques quânticos específicos (como o algoritmo de Deutsch-Jozsa).

O objetivo do trabalho é fornecer provas de segurança no QROM para duas famílias principais de RSS: as baseadas no framework AOS (transformação de protocolos $\Sigma$) e as baseadas em armadilhas de anel (Ring Trapdoors).

---

2. Metodologia e Contribuições Técnicas

Os autores desenvolvem novas ferramentas teóricas para analisar a indistinguibilidade de oráculos no QROM e aplicam-nas a construções de assinaturas.

A. Alternância de Distribuição de Oracle Quântico (Quantum Oracle Distribution Switching)

Esta é a contribuição teórica fundamental do artigo. Os autores estudam a indistinguibilidade de um algoritmo quântico que interage com um oráculo cujas saídas são amostradas independentemente de uma distribuição $P$ versus uma distribuição $Q$.

1. Limites Baseados em Distância Estatística:

   • Eles provam um limite explícito e apertado para a distância estatística entre as distribuições de saída de um algoritmo que faz $q$ consultas quânticas a oráculos com distribuições subjacentes $P$ e $Q$.
   • O limite é da ordem de $O(q\sqrt{\epsilon})$, onde $\epsilon$ é a distância estatística entre $P$ e $Q$. Isso melhora limites anteriores e é provado usando a técnica de Oracle Comprimido (Compressed Oracle).

2. Falha da Divergência de Rényi para Substituição Total:

   • No modelo clássico, a Divergência de Rényi permite limites multiplicativos para a probabilidade de sucesso de um adversário.
   • Os autores demonstram que, no QROM, não é possível substituir a distribuição inteira de um oráculo por outra usando apenas a Divergência de Rényi para obter limites multiplicativos.
   • Contraexemplo: Eles constroem um cenário onde um adversário usa o Algoritmo de Deutsch-Jozsa para distinguir duas distribuições com uma razão de probabilidades de sucesso que cresce exponencialmente com o tamanho do domínio, tornando qualquer limite multiplicativo impossível.

3. Solução Parcial (Reprogramação Adaptativa):

   • Embora a substituição total falhe, eles mostram que é possível usar a Divergência de Rényi se apenas um número limitado de posições do oráculo for reprogramado (re-amostrado).
   • Isso é crucial para a segurança de assinaturas, onde apenas as entradas usadas durante a geração de assinaturas precisam ser reprogramadas, não todo o oráculo.

B. Assinaturas em Anel Baseadas em RPSF (Ring Preimage Sampleable Functions)

Os autores formalizam uma nova primitiva chamada RPSF (generalizando as funções de amostragem de pré-imagem - PSFs) para capturar construções como Gandalf e FalconRS.

• Construção Genérica: Eles propõem uma construção genérica de RSS a partir de RPSFs.
• Provas de Segurança no QROM:
  • Via Reprogramação Adaptativa: Usando o "sal" (salt) na entrada do hash, eles aplicam a técnica de reprogramação adaptativa (Lemma 7) combinada com a análise de distância estatística e Rényi para provar segurança contra forjamento (SUF-CRA).
  • Via Reduções "History-Free": Eles generalizam a técnica de reduções sem histórico (introduzida por Boneh et al.) para o contexto de assinaturas em anel, provando segurança sem a necessidade de sal, mas com limites ligeiramente diferentes.
  • Anonimato: Provam que a anonimidade (sob exposição total de chaves) é mantida no QROM, utilizando a indistinguibilidade da amostragem de pré-imagem.

C. Assinaturas em Anel AOS (Abe-Ohta-Sakurai)

Para o framework AOS, que transforma protocolos $\Sigma$ em RSSs lineares:

1. Prova Genérica (Measure-and-Reprogram):

   • Eles utilizam a técnica de Medir e Reprogramar (Measure-and-Reprogram) para ordenar as consultas do oráculo.
   • Isso permite reduzir a segurança UF-NRA (Unforgeability under No-Ring Attacks) à segurança de impersonificação do protocolo $\Sigma$ subjacente.
   • Limitação: O limite de segurança decai exponencialmente com o tamanho do anel ($N$), mas é suficiente para o caso prático de anel de tamanho 2 (usado no Signal).

2. Prova Apertada para Protocolos Commit-and-Open (C&O):

   • Para protocolos $\Sigma$ do tipo "Commit-and-Open" (como ZKBoo, ZKB++), eles utilizam técnicas de extração em linha reta (straightline extraction) baseadas em propriedades de banco de dados de oráculos comprimidos.
   • Isso resulta em uma redução multiplicativamente apertada para a segurança do protocolo $\Sigma$, evitando a perda exponencial no tamanho do anel.

---

3. Resultados Principais

1. Provas de Segurança QROM: O trabalho fornece as primeiras provas de segurança no QROM para as duas principais famílias de assinaturas em anel usadas em DAKEs conformes ao Signal (AOS e Trapdoor de Anel).
2. Análise de Falha da Divergência de Rényi: Demonstra-se que a aplicação direta de limites clássicos baseados em Rényi para substituição de oráculos no QROM é inválida, exigindo novas abordagens (como reprogramação parcial).
3. Aplicação ao Falcon: Os autores discutem as implicações para o Falcon (candidato NIST). O uso de Rényi na prova de segurança do Falcon no QROM é questionado, sugerindo que uma análise completa requer o uso de técnicas de reprogramação adaptativa com sal, similar ao proposto para as RSSs.
4. Eficiência: As construções propostas mantêm a eficiência das versões clássicas, com apenas um custo adicional linear ou constante na segurança efetiva devido aos fatores de perda quântica (como o fator $q^2$ em colisões de hash).

---

4. Significado e Impacto

• Segurança Pós-Quântica Realista: O trabalho preenche uma lacuna crítica na criptografia pós-quântica. Sem provas no QROM, protocolos de mensagens seguras baseados em RSSs não podem ser considerados totalmente seguros contra adversários quânticos.
• Validação de Protocolos Existentes: As técnicas desenvolvidas permitem revalidar construções existentes (como Gandalf e Erebor) no modelo quântico, oferecendo garantias de segurança para futuras implementações de sistemas de comunicação seguros.
• Novas Ferramentas Teóricas: A análise detalhada da "Alternância de Distribuição de Oracle" e a demonstração dos limites da Divergência de Rényi no QROM fornecem ferramentas valiosas para a análise de segurança de outras primitivas criptográficas além das assinaturas em anel.
• Direção para Padrões: Os resultados têm implicações diretas para a padronização de criptografia pós-quântica (NIST), especialmente para esquemas de assinatura e troca de chaves que dependem de oráculos aleatórios.

Em resumo, este artigo estabelece a base teórica necessária para garantir que as assinaturas em anel, essenciais para a privacidade em comunicações futuras, permaneçam seguras na era da computação quântica.