Withdrawability in Fiat-Shamir with aborts constructions

Resumo Técnico: Retratabilidade em Construções de Fiat–Shamir com Abortos

Definição do Problema
As assinaturas digitais tradicionalmente proporcionam permanência; uma vez gerada, uma assinatura não pode ser revogada sem comprometer a chave privada do signatário ou invalidar outras assinaturas. Essa limitação impõe desafios em ambientes dinâmicos, como contratos inteligentes de blockchain, votação eletrônica descentralizada e serviços de custódia, onde os participantes podem precisar revogar compromissos baseados em mudanças de condições. Liu, Baek e Susilo [LBS23] introduziram as "assinaturas retráteis" (withdrawable signatures), um primitivo que permite ao signatário gerar uma assinatura verificável apenas por um verificador designado, que pode posteriormente ser transformada em uma assinatura publicamente verificável. No entanto, sua construção baseia-se em suposições clássicas (Logaritmo Discreto, Diffie-Hellman) vulneráveis a ataques quânticos.

O desafio abordado neste artigo é estender o conceito de assinaturas retráteis para o cenário pós-quântico, especificamente dentro do paradigma Fiat–Shamir com abortos. Este paradigma é a base de esquemas de assinatura pós-quântica líderes, como Dilithium (ML-DSA) e HAETAE. Existe um obstáculo estrutural específico: a construção original de Liu–Baek–Susilo depende de um segredo compartilhado Diffie-Hellman "gratuito" para alcançar a ambiguidade entre signatário/verificador e a designação simultaneamente. A criptografia baseada em redes (lattice-based) carece de um análogo barato e eficiente para este segredo compartilhado, necessitando de uma nova abordagem arquitetônica.

Metodologia
O artigo propõe uma construção abstrata geral para assinaturas retráteis baseada no paradigma Fiat–Shamir com abortos, seguida de uma instanciação concreta.

1. Construção Abstrata:
   Os autores definem um framework composto por cinco algoritmos: KeyGen, WSign (assinatura retrátil), WSVerify (verificação retrátil), Confirm e CVerify.

   • Mecanismo Central: O esquema utiliza um prova de OR de dois agentes (two-party) de Fiat–Shamir com abortos. A assinatura retrátil consiste em dois ramos: um gerado pelo signatário (usando sua chave secreta) e outro simulado pelo signatário para mimetizar o ramo do verificador.
   • Ambiguidade: Como tanto o signatário quanto o verificador designado podem gerar um ramo válido (o signatário ao simular o verificador, e o verificador ao simular o signatário), a origem da assinatura é indistinguível para terceiros.
   • Confirmação: Para tornar a assinatura publicamente verificável, o signatário executa o algoritmo Confirm, que gera uma assinatura comum e ordinária sobre a mensagem, o conjunto de chaves públicas e a própria assinatura retrátil. Isso vincula a assinatura retrátil à identidade do signatário sem exigir a re-derivação de aleatoriedade compartilhada (o que é inviável em sistemas de rede baseados em lattice de Fiat–Shamir com abortos devido à amostragem de rejeição).

2. Variante de Verificador Designado Forte (SDVS):
   Para garantir que a assinatura retrátil não seja publicamente verificável (correspondendo ao modelo de Liu–Baek–Susilo), os autores criptografam o núcleo público da assinatura usando um esquema de Criptografia de Chave Pública (PKE) (especificamente, a criptografia module-LWE CPA-segura subjacente ao ML-KEM/Kyber).

   • A assinatura é criptografada tanto para a chave pública do verificador designado quanto para a chave pública do signatário. Isso permite que o verificador decifre e verifique, e permite que o signatário decifre e realize a operação Confirm de forma sem estado (stateless).
   • Esta abordagem substitui o segredo compartilhado Diffie-Hellman por criptografia explícita, reconhecendo que o Intercâmbio de Chaves Não Interativo (NIKE) baseado em redes é atualmente muito ineficiente para este propósito.

3. Instanciação Concreta:
   O framework abstrato é instanciado usando uma construção no-hint, full-$t$ do tipo Dilithium.

   • Os autores utilizam uma variante do Dilithium que não utiliza "dicas" (hints, a divisão $t_1$/$t_0$), garantindo que o simulador para a prova de conhecimento zero seja perfeito ($\varepsilon_{zk} = 0$).
   • Essa escolha simplifica as provas de segurança, particularmente para a propriedade de retratabilidade, evitando os pequenos erros estatísticos associados a esquemas com hints.

Principais Contribuições

• Framework Geral: O artigo introduz a primeira construção abstrata para assinaturas retráteis baseada no paradigma Fiat–Shamir com abortos, preenchendo a lacuna entre o modelo de Liu–Baek–Susilo e a criptografia de redes pós-quântica.
• Provas de Segurança:
  • Não-falsificabilidade: O esquema é provado não-falsificável sob corrupção interna (onde o adversário possui a chave secreta do verificador) no Modelo de Oráculo Aleatório Quântico (QROM). A prova reduz-se à segurança EUF-CMA do esquema de assinatura de rede subjacente (suposições SelfTargetMSIS/MSIS).
  • Retratabilidade: O esquema é provado retrátil, o que significa que um adversário não consegue distinguir se uma assinatura foi gerada pelo signatário ou pelo verificador designado. Para a instanciação no-hint, esta propriedade é estatística (informacional) com $\varepsilon_{zk} = 0$, baseando-se no conhecimento zero de honesto-verificador perfeito (naHVZK) do esquema de identificação subjacente e na min-entropia dos compromissos.
• Adaptação às Restrições Pós-Quânticas: O artigo aborda explicitamente a falta de um segredo compartilhado Diffie-Hellman baseado em redes. Ele demonstra que a designação pode ser alcançada via Criptografia de Chave Pública (PKE) em vez de NIKE, e que a ambiguidade do signatário pode ser alcançada via provas de OR em vez de simetria algébrica.

Resultados

• Segurança Concreta: Para a instanciação no-hint do Dilithium, o artigo fornece limites de segurança concretos. A vantagem de não-falsificabilidade é limitada pela segurança do esquema subjacente mais um termo negligenciável relacionado à programação do oráculo aleatório ($2^{-1024}$). A vantagem de retratabilidade é limitada por $1/2$ mais um termo estatístico negligenciável, alcançando efetivamente a ambiguidade perfeita para o verificador designado no caso no-hint.
• Comparação: Os autores fornecem uma comparação detalhada com o esquema de Liu–Baek–Susilo (Tabela 2). Embora a construção de redes exija material de chave adicional (chaves de criptografia) e resulte em assinaturas maiores (devido ao overhead de criptografia), ela ganha duas propriedades significativas: a assinatura retrátil é pseudorandom (escondendo sua existência de terceiros) e a não-transferibilidade contra o verificador designado é perfeita (estatística) em vez de computacional.

Significância
O artigo afirma ser uma adaptação necessária do primitivo de assinatura retrátil para a era pós-quântica. Estabelece que a retratabilidade é alcançável na criptografia baseada em redes sem depender de análogos de Diffie-Hellman baseados em redes que são ineficientes ou inexistentes. Ao separar os mecanismos de designação (criptografia) e ambiguidade (provas de OR), os autores fornecem uma construção robusta e provadamente segura que mantém as propriedades de segurança dos esquemas subjacentes, como o Dilithium, enquanto adiciona a flexibilidade crítica da revogação de assinaturas. O trabalho sugere que estas construções podem aumentar a resistência quântica em sistemas de blockchain onde a revogação de transações é desejável, mas tradicionalmente difícil de implementar.