Lattice-based extended withdrawability

Resumo Técnico: Retirabilidade Estendida Baseada em Lattices

Definição do Problema
Assinaturas digitais tradicionalmente fornecem permanência: uma vez assinada, uma mensagem permanece verificável sob a chave pública do signatário indefinidamente. No entanto, muitas aplicações descentralizadas (por exemplo, acesso por tempo limitado, acordos revogáveis, custódia descentralizada) requerem a capacidade de retirar uma assinatura sem revelar a chave secreta ou invalidar outras assinaturas. Liu, Susilo e Baek introduziram as assinaturas com retirada estendida (EWS - extended withdrawable signatures) para abordar isso, permitindo que uma assinatura seja ambígua entre um conjunto de potenciais signatários até que o verdadeiro signatário a "confirme". Sua construção baseia-se em primitivas de logaritmo discreto (assinaturas de Schnorr e assinaturas 1-de-N).

Este artigo aborda a "lacuna pós-quântica": o algoritmo de Shor quebra a fundação de logaritmo discreto das existentes esquemas EWS. Embora existam assinaturas baseadas em lattices (por exemplo, Dilithium), uma "transcrição literal" da construção de Liu-Susilo-Baek (LSB) para lattices falha devido a obstruções estruturais. Especificamente, o esquema LSB baseia-se na publicação de deslocamentos multiplicativos de chaves públicas para re-randomizar a contribuição do signatário. No cenário de lattices (Fiat-Shamir com abortos), tais deslocamentos assumem a forma $As_1 s_j$, que compartilham um fator comum $As_1$ com a chave pública do signatário $t_i = As_1 + s_2$. Publicar esses deslocamentos vaza a identidade do signatário, quebrando a ambiguidade necessária.

Metodologia
Os autores propõem uma nova construção para EWS baseada em lattices que se afasta da abordagem LSB ao tratar o esquema como uma assinatura de anel reivindicável (Park e Sealfon). Em vez de tentar re-randomizar as chaves públicas de forma clara, a construção separa as duas funções principais da EWS:

1. Ambiguidade: Fornecida por uma assinatura de anel (ring signature) anônima 1-de-N, usada como uma caixa preta.
2. Confirmação: Fornecida pela reivindicação do signatário, consistindo em uma assinatura vinculativa sobre o objeto retirável e a abertura de um compromisso ocultante para o índice do signatário.

A construção opera sobre o paradigma Fiat-Shamir com abortos e baseia-se em três ingredientes modulares:

• Um esquema de assinatura base (por exemplo, um esquema do tipo Dilithium de $t$ total e sem dicas/no-hint).
• Uma assinatura anônima 1-de-N (instanciada via uma prova de 1-para-muitos baseada em lattices).
• Um esquema de compromisso de ocultação e vinculação (estilo Ajtai).

A assinatura retirável $\sigma$ consiste em uma assinatura de anel $\sigma_r$ sobre a mensagem e um compromisso $C$ para o índice do signatário, juntamente com o conjunto de chaves públicas. Para confirmar, o signatário revela a abertura $(i, \rho)$ de $C$ e assina todo o objeto retirável $\langle \mu, \pi, \sigma \rangle$ com sua chave secreta base.

Principais Contribuições

1. Refinamento do Modelo de Segurança: Os autores refinam o modelo de segurança de LSB.

   • Eles substituem a definição de "completude" de LSB para a retirabilidade estendida por um jogo de indistinguibilidade de anonimato-até-reivindicação (Definição 14), capturando explicitamente a garantia de ocultação.
   • Eles introduzem a solidez de reivindicação (Definição 16), garantindo que uma assinatura confirmada se vincule a um índice de signatário único, impedindo que um adversário atribua a mesma assinatura a diferentes membros do anel.
   • Eles formalizam a não-falsificabilidade sob corrupção de insider com um índice alvo fixo, evitando a perda de redução de $q_H$ (consulta de hash) multiplicativa presente na prova de LSB.

2. Construção Genérica: Uma construção genérica de EWS sobre o paradigma Fiat-Shamir com abortos é apresentada. Crucialmente, ela publica nenhum valor derivado do signatário de forma clara. A ambiguidade é derivada puramente das propriedades de conhecimento zero da assinatura de anel, e a rastreabilidade é derivada da propriedade de vinculação do compromisso.

3. Resultado de Impossibilidade: O artigo prova (Proposição 2) que uma transcrição literal de lattice da assinatura 1-de-N de LSB (usando divisão de desafio aditiva) é insegura. No cenário de lattices com desafios esparsos, a probabilidade de um signatário honesto produzir uma divisão de desafio válida é negligenciável ($2^{-\Omega(n)}$), e mesmo que a completude fosse corrigida, a anonimidade falharia porque o transcript simulado não seria indistinguível de um transcript real.

4. Provas de Segurança Completas: Os autores fornecem reduções explícitas baseadas em jogos no Modelo de Oráculo Aleatório Quântico (QROM) para:

   • Corretude: Reduzindo à corretude das primitivas subjacentes.
   • Retirabilidade Estendida: Reduzindo à ocultação do compromisso (Decisional MLWE) e ao anonimato da prova 1-de-N.
   • Não-falsificabilidade: Reduzindo à segurança EUF-CMA da assinatura base (sem reuso/rewinding e sem perda de $q_H$).
   • Solidez de Reivindicação: Reduzindo à vinculação do compromisso (MSIS).

5. Instanciação: O esquema é instanciado usando uma assinatura base do tipo Dilithium de $t$ total e sem dicas e uma prova de 1-para-muitos de lattice estabelecida. O artigo discute escolhas de parâmetros e observa que o HAETAE poderia servir como uma alternativa base.

Resultados
O artigo estabelece que a construção proposta é:

• Correta: Assinaturas honestas verificam com probabilidade esmagadora.
• Retirável Estendida: Um adversário detendo todas as chaves secretas não pode distinguir qual membro de um anel produziu uma assinatura retirável até que o signatário a confirme.
• Não-falsificável: Mesmo com acesso a oráculos de assinatura e às chaves secretas de todos os membros do anel exceto o alvo, um adversário não pode forjar uma assinatura confirmada para uma mensagem nova.
• Sólida: Uma assinatura confirmada não pode ser atribuída a dois signatários diferentes.

A segurança baseia-se em suposições padrão de módulo-lattice: Decisional MLWE, MSIS e SelfTargetMSIS, juntamente com a propriedade de conhecimento zero da prova 1-de-N.

Significância
O artigo afirma sua significância ao fornecer a primeira realização pós-quântica segura de assinaturas com retirada estendida. Ele demonstra que a construção de logaritmo discreto de LSB não pode ser diretamente portada para lattices devido à falta de "re-randomização livre" de valores compartilhados. Ao reformular o problema como uma assinatura de anel reivindicável e utilizar um mecanismo de confirmação baseado em compromisso, os autores alcançam um esquema que é:

• Seguro contra Computação Quântica: Resistente a adversários quânticos via suposições de lattice.
• Publicamente Verificável: Diferente das variantes de verificador designado, qualquer parte pode verificar a assinatura retirável.
• Modular: As provas de segurança dependem apenas das interfaces das primitivas subjacentes, permitindo a substituição de diferentes componentes de lattice (por exemplo, diferentes assinaturas base ou provas de anel) sem re-provar todo o sistema.
• Fiel aos Objetivos Originais: O design preserva os objetivos funcionais e a intuição do esquema LSB original, enquanto corrige suas falhas estruturais no cenário de lattices.