FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG

Este artigo apresenta o primeiro esquema de ML-DSA (FIPS 204) com limite que utiliza um DKG de nonce baseado em Shamir para garantir privacidade das partes sem suposições computacionais, permitindo assinaturas padrão de 3,3 KB e relaxando os requisitos de honestidade em perfis coordenados.

O essencial

Imagine que você tem um cofre digital extremamente seguro (o ML-DSA, que é o novo padrão de segurança contra computadores quânticos) que protege os segredos mais valiosos da internet. O problema é que, para abrir esse cofre, você precisa de uma única chave. Se essa chave for roubada ou perdida, tudo acaba.

A solução tradicional é dividir a chave em pedaços e dar para várias pessoas (um esquema de "limite" ou threshold). Mas, até agora, fazer isso com a nova tecnologia quântica era como tentar montar um quebra-cabeça gigante com peças que não se encaixavam: ou a segurança era fraca, ou o processo era tão lento que ninguém usava, ou o formato final não era reconhecido pelos sistemas existentes.

Este artigo, escrito por Leo Kao, apresenta uma nova maneira de fazer isso: "Assinaturas de Limite ML-DSA via DKG de Nonce Shamir". Vamos traduzir isso para o português do dia a dia usando analogias.

1. O Problema: O "Cofre" que exige muitos guardas

Pense no ML-DSA como um cofre que só abre se você digitar uma senha correta. Para proteger essa senha, você divide o trabalho entre 5 guardas (por exemplo), mas só precisa de 3 para abrir o cofre.

• O desafio antigo: Quando os guardas tentam combinar suas partes da senha, o "barulho" (matemática complexa) gerado por essa combinação tornava a senha final muito grande (como tentar passar um elefante por um buraco de rato) ou exigia que todos os guardas estivessem online ao mesmo tempo, sincronizados como um coral, o que é difícil na prática.

2. A Grande Ideia: A "Chave Mestra" e o "Ruído Branco"

O autor propõe duas técnicas principais para resolver isso:

A. O "Nonces" (Números de Uso Único) como um Quebra-Cabeça Compartilhado

Na criptografia, antes de assinar, você precisa gerar um número aleatório único (chamado de nonce). Se esse número vazar, sua chave secreta é roubada.

• A técnica antiga: Cada guarda gerava seu próprio número e tentava somar. Isso criava um "número final" que não era perfeitamente aleatório, deixando uma pequena brecha de segurança.
• A nova técnica (Shamir Nonce DKG): Imagine que os guardas não geram números separados. Em vez disso, eles criam juntos uma única "fita de música" (polinômio) onde a melodia principal é o número secreto.
  • Cada guarda segura apenas um "pedaço" da fita.
  • O segredo é que, mesmo que um guarda mal-intencionado veja os pedaços dos outros, ele não consegue ouvir a melodia completa. É como se o guarda honesto tivesse um "segredo extra" (uma entropia condicional) que é 5 vezes maior que a própria chave.
  • Resultado: Eles conseguem gerar o número aleatório juntos sem que ninguém precise confiar em ninguém, e sem que o número final fique "viciado" ou previsível.

B. As "Máscaras de Cancelamento" (Pairwise-Canceling Masks)

Imagine que os guardas precisam somar seus pedaços para formar a assinatura final. Se eles apenas somarem, o "barulho" matemático (os coeficientes de Lagrange) fica gigante e quebra o formato padrão.

• A solução: Eles usam "máscaras". Cada guarda adiciona um ruído aleatório à sua parte, mas esse ruído foi combinado com o ruído do vizinho de forma que, quando todos somam, os ruídos se cancelam perfeitamente.
  • É como se cada guarda tivesse um pedaço de papel branco e um pedaço de papel preto. Quando eles juntam tudo, o preto e o branco se anulam, deixando apenas a mensagem original limpa.
  • Isso permite que a assinatura final tenha exatamente o mesmo tamanho e formato (3,3 KB) que uma assinatura feita por uma única pessoa. O sistema de verificação externo nem percebe que foi feito por um grupo!

3. Os Três Perfis de Uso (Como aplicar na vida real)

O artigo não é apenas teoria; ele oferece três maneiras de usar isso, dependendo de quanto você confia nas pessoas ou máquinas:

1. Perfil P1 (O "Guarda-Costas" de Confiança):

   • Imagine que você tem um cofre blindado (um TEE/HSM) que é inviolável. Um coordenador dentro desse cofre faz a parte mais difícil de checar se a assinatura está correta.
   • Vantagem: É o mais rápido (5,8 ms).
   • Desvantagem: Você precisa confiar que o cofre blindado não tem falhas.

2. Perfil P2 (A "Reunião Democrática" Total):

   • Ninguém confia em ninguém. Todos os guardas conversam entre si usando criptografia avançada (MPC) para fazer os cálculos sem revelar nada.
   • Vantagem: Não precisa de cofres blindados ou confiança em hardware. É puramente matemático.
   • Desvantagem: É um pouco mais lento (21,5 ms) e exige mais rodadas de conversa entre os guardas.

3. Perfil P3+ (O "Trabalho Assíncrono" ou "Human-in-the-Loop"):

   • Imagine que você precisa assinar um documento, mas os guardas estão em fusos horários diferentes ou ocupados.
   • Eles preparam suas partes do "número aleatório" quando estão livres (offline). Quando chega a hora de assinar, eles só precisam responder rapidamente dentro de uma janela de tempo (ex: 5 minutos).
   • Vantagem: É o mais flexível para humanos. Você não precisa esperar todos estarem online ao mesmo tempo.
   • Desvantagem: Requer que pelo menos dois "computadores de confiança" (CPs) estejam honestos.

4. Por que isso é um marco?

• Velocidade: Funciona em milissegundos, rápido o suficiente para uso real em bancos ou carteiras de criptomoedas.
• Segurança: Mantém a segurança contra computadores quânticos e não precisa de suposições computacionais frágeis para proteger a privacidade dos pedaços da chave.
• Compatibilidade: A assinatura final é "byte a byte" igual à assinatura padrão. Os sistemas antigos não precisam ser atualizados para aceitar isso.
• Escalabilidade: Funciona bem mesmo se você tiver 32 guardas (antes, isso era impossível sem quebrar o sistema).

Resumo em uma frase

Este artigo ensina como dividir a "chave mestra" quântica entre várias pessoas de forma que elas possam assinar documentos juntas rapidamente, com segurança total e sem que o sistema externo perceba que não foi uma única pessoa assinando, usando truques matemáticos de "máscaras que se cancelam" e "partes de quebra-cabeça que protegem o segredo".

Resumo técnico

Título: Threshold ML-DSA via Shamir Nonce DKG

Autor: Leo Kao (Codebat Technologies Inc.)
Contexto: Criptografia Pós-Quântica, Assinaturas de Limiar, FIPS 204.

1. O Problema: A Lacuna de Limiar no ML-DSA

Com a padronização do ML-DSA (Module-Lattice-Based Digital Signature Algorithm) pelo NIST como o padrão FIPS 204 para criptografia pós-quântica, há uma necessidade urgente de variantes de assinatura de limiar (threshold signatures). Essas variantes permitem que um grupo de $N$ partes distribua a autoridade de assinatura, onde qualquer subconjunto de $T$ ou mais partes pode gerar uma assinatura válida, sem que coalizões menores de $T$ aprendam nada sobre a chave secreta.

No entanto, a estrutura baseada em reticulados (lattices) do ML-DSA apresenta desafios únicos em comparação com esquemas clássicos (como ECDSA):

• Paradigma Fiat-Shamir com Abortos: A validação da assinatura exige que o vetor de resposta $z = y + c \cdot s_1$ satisfaça uma norma estrita ($\|z\|_\infty < \gamma_1 - \beta$). Em esquemas de limiar, a reconstrução de $z$ envolve coeficientes de Lagrange ($\lambda_i$) que podem ser muito grandes.
• Incompatibilidade de Tamanho: Soluções anteriores para limiares arbitrários ou usavam "noise flooding" (inundação de ruído), que inflava o tamanho da assinatura para ~17 KB (quebrando a compatibilidade com o FIPS 204, que exige ~3.3 KB), ou limitavam o limiar $T$ a valores muito baixos (ex: $T \le 6$) devido ao crescimento exponencial dos coeficientes de reconstrução.
• Privacidade do Nonce: Garantir que as partes não vazem informações sobre o nonce (número aleatório de uso único) usado na assinatura é crítico. Soluções anteriores frequentemente exigiam a suposição de "duas partes honestas" ($|S| \ge T+1$) para garantir privacidade, o que é restritivo.

2. Metodologia e Técnicas Principais

O artigo propõe o primeiro esquema de assinatura de limiar para ML-DSA que atinge privacidade de compartilhamento de nonce baseada em entropia mínima condicional (sem suposições computacionais) com limiares arbitrários, mantendo o tamanho padrão da assinatura.

As duas técnicas principais são:

A. Shamir Nonce DKG (Distributed Key Generation)

Esta é a contribuição central. Em vez de gerar o nonce $y$ de forma uniforme e depois compartilhá-lo, as partes geram o nonce como um compartilhamento de Shamir de grau $(T-1)$ desde o início.

• Estrutura: Cada parte $i$ gera um polinômio de grau $(T-1)$ onde o termo constante é uma contribuição para o nonce e os coeficientes de grau superior são amostrados uniformemente de $R_q$.
• Privacidade Estatística: Como o adversário observa apenas $T-1$ avaliações do polinômio de uma parte honesta, resta um grau de liberdade. Isso atua como um "one-time pad" aproximado. O artigo prova que a entropia mínima condicional do compartilhamento do nonce de uma parte honesta excede 5 vezes a entropia da chave secreta (para conjuntos de assinatura de tamanho até 17), sem depender de suposições computacionais.
• Eficiência de Limiar: Isso permite que conjuntos de assinatura com tamanho mínimo $|S| = T$ (em vez de $T+1$) sejam usados em perfis baseados em coordenadores, eliminando a necessidade de uma parte honesta extra para privacidade.

B. Máscaras de Cancelamento Par a Par (Pairwise-Canceling Masks)

Adaptadas de esquemas ECDSA, essas máscaras são usadas para esconder os valores de compromisso ($W_i$) e as partes de verificação $r_0$ ($V_i$) durante a agregação.

• As partes calculam máscaras baseadas em sementes compartilhadas via PRF (Funções Pseudoaleatórias) de modo que a soma das máscaras seja zero.
• Isso protege a privacidade dos compromissos individuais e impede a recuperação da chave $s_2$ durante a verificação $r_0$, mesmo em cenários de distribuição total.

C. Análise de Distribuição Irwin-Hall

O nonce agregado segue uma distribuição de Irwin-Hall (soma de variáveis uniformes) em vez de uma distribuição uniforme. O artigo realiza uma análise rigorosa de segurança (usando divergência de Rényi e invariância de deslocamento direta) para provar que essa mudança na distribuição introduz uma perda de segurança insignificante (< 0,013 bits por sessão para $|S| \le 33$), resolvendo a "lacuna de escalabilidade" encontrada em trabalhos anteriores.

3. Perfis de Implantação

O protocolo é implementado em três perfis com diferentes suposições de confiança, todos com provas de segurança UC (Universal Composability):

1. Perfil P1 (Assistido por TEE): Utiliza um coordenador em um Ambiente de Execução Confiável (TEE/HSM).
   • Vantagens: 3 rodadas online, baixa latência (~5.8 ms para 3-of-5), privacidade estatística do nonce.
   • Confiança: Requer integridade do TEE.
2. Perfil P2 (Totalmente Distribuído): Não requer hardware confiável; usa Computação Multi-Parte (MPC) baseada em SPDZ e edaBits.
   • Vantagens: Segurança contra maioria desonesta, sem confiança em hardware.
   • Desvantagens: 5 rodadas online, maior latência (~21.5 ms para 3-of-5).
3. Perfil P3+ (Semi-Assíncrono 2PC): Projetado para autorização com intervenção humana. Usa 2PC (Two-Party Computation) leve entre duas partes de computação.
   • Vantagens: Assinantes precalculam nonces offline e respondem dentro de uma janela de tempo (semi-assíncrono). Apenas 2 rodadas lógicas.
   • Confiança: Assumindo que pelo menos 1 das 2 partes de computação é honesta.

4. Resultados e Desempenho

A implementação em Rust demonstra eficiência prática:

• Tamanho da Assinatura: 3.3 KB (idêntico ao ML-DSA de um único signatário, compatível com verificadores FIPS 204 não modificados).
• Latência:
  • P1 (TEE): 4 ms a 60 ms (para limiares de 2-of-3 a 32-of-45).
  • P3+ (2PC): 17 ms a 94 ms.
  • P2 (MPC): 21 ms a 194 ms (variação devido à amostragem de rejeição).
• Taxa de Sucesso: Aproximadamente 21–45% por tentativa (comparável à taxa de 20–25% do ML-DSA de único signatário), graças à concentração da distribuição de Irwin-Hall perto de zero.
• Escalabilidade: O esquema escala de 2-of-3 até 32-of-45 com latência sub-100ms nos perfis P1 e P3+.

5. Contribuições Chave e Significância

• Primeiro Esquema Compatível com FIPS 204: É a primeira solução de limiar para ML-DSA que produz assinaturas de tamanho padrão (3.3 KB) verificáveis por implementações existentes, preenchendo uma lacuna crítica para adoção corporativa e governamental.
• Privacidade Estatística sem Suposições Computacionais: A técnica de Shamir Nonce DKG garante privacidade do nonce baseada puramente em propriedades estatísticas (entropia mínima), eliminando a necessidade de suposições de "duas partes honestas" em perfis coordenados.
• Segurança Comprovada: O artigo fornece provas completas de segurança UC para todos os três perfis e uma análise rigorosa da perda de segurança devido à distribuição de nonces não uniformes, mostrando que a perda é negligenciável (< 0.013 bits por sessão).
• Impacto Prático: Facilita a transição para criptografia pós-quântica em cenários de alta segurança, como custódia de criptomoedas, autoridades certificadoras distribuídas e gerenciamento de chaves empresariais, permitindo a integração com infraestrutura existente sem modificações nos verificadores.

Em resumo, este trabalho resolve o problema fundamental de como realizar assinaturas de limiar seguras e eficientes para o novo padrão de criptografia pós-quântica do NIST, equilibrando segurança, privacidade estatística e compatibilidade prática.