Resumo Técnico: A Aritmética Centrada Não é Neutra em Relação ao Vazamento

Declaração do Problema

Em implementações de software de criptografia baseada em reticulados (ex: ML-KEM, ML-DSA), valores sensíveis são protegidos via mascaramento aritmético, onde um segredo é dividido em partes aleatórias que somam o segredo módulo $q$. Embora a operação matemática seja aritmética modular, o armazenamento físico dessas partes exige uma escolha de representação dentro da palavra de máquina. Tipicamente, as partes são armazenadas como resíduos não sinalizados em $[0, q)$ ou como inteiros sinalizados centrados em complemento de dois $[-\lfloor q/2 \rfloor, \lceil q/2 \rceil - 1]$.

Embora ambas as codificações implementem aritmética modular idêntica, elas diferem significamente em sua representação binária. Especificamente, inteiros negativos em complemento de dois exibem extensão de sinal (uns à esquerda), enquanto seus equivalentes não sinalizados não exibem. Trabalhos anteriores exploraram esse efeito de "extensão de sinal" para ataques de canal lateral (ex: preditores de valor absoluto). No entanto, faltava um arcabouço teórico abrangente que caracterizasse como essa escolha de representação afeta o vazamento em todas as ordens de mascaramento, sob ruído finito e para módulos arbitrários. Este artigo aborda a questão fundamental: A aritmética centrada é neutra em relação ao vazamento comparada ao armazenamento não sinalizado?

Metodologia

O artigo emprega uma abordagem matemática rigorosa combinando teoria da probabilidade, análise de Fourier e teoria combinatória de números para modelar o canal de vazamento de canal lateral.

1. Modelagem de Canal de Ruído Finito: O autor modela o vazamento de partes mascaradas como canais de ruído aditivos independentes. Eles derivam a verossimilhança exata da soma mascarada tratando o problema como uma convolução cíclica das distribuições de vazamento de cada parte individual.
2. Análise de Fourier: A análise utiliza a Transformada Discreta de Fourier (DFT) para converter a convolução em um produto no domínio da frequência. Isso permite a derivação de ataques ótimos e a decomposição espectral do vazamento.
3. Minimax de Representação: O estudo avalia diferentes "seções" (representações) de $\mathbb{Z}_q$ minimizando a energia do espectro de vazamento. Isso envolve comparar seções contíguas (não sinalizadas vs. centradas) e livros de códigos binários injetivos arbitrários.
4. Decomposição Espectral: Uma inovação metodológica chave é a decomposição do espectro de vazamento de complemento de dois centrado em termos de extensão de sinal e termos de carry (vai-um), permitindo uma análise assintótica precisa.
5. Validação Algorítmica: Os limites teóricos são verificados através de computações exatas, experimentos sintéticos com parâmetros de tamanho total de ML-KEM e ML-DSA, e análise de traços físicos públicos.

Principais Contribuições

1. Inferência Ótima de Ruído Finito

O artigo estabelece que a verossimilhança completa de uma soma mascarada pode ser computada em tempo quase linear $O(dq \log q)$ usando uma convolução circular avaliada via Transformada Rápida de Fourier (FFT).

• Resultado: Isso fornece uma estratégia de ataque ótima que avalia todas as $q$ hipóteses simultaneamente.
• Condição de Suficiência: O autor deriva uma condição exata sob a qual a estatística de produto comumente usada (multiplicando partes centradas) retém toda a informação de verossimilhança. Eles provam que, para tabelas de vazamento não negativas com um zero único, a estatística de produto é estritamente insuficiente para qualquer módulo $q \ge 2$ e ordem $d \ge 2$ sob ruído finito. A observação completa contém estritamente mais informação (maior divergência KL, divergência de Rényi, etc.) do que a estatística de produto.

2. Leis Minimax de Representação Global

O artigo otimiza a escolha da representação para minimizar o vazamento:

• Vazamento de Primeira Ordem: Entre todas as seções contíguas, o armazenamento não sinalizado ($[0, q)$) é o minimizador único do vazamento de primeira ordem, a menos que o módulo $q$ ocupe a palavra de máquina completa ($q=2^m$), caso em que todas as seções são equivalentes.
• Vazamento de Ordem Superior: A otimalidade do armazenamento não sinalizado não é permanente. O artigo identifica uma "mudança de fase" exata onde, para parâmetros específicos (ex: $q=14, \beta=4$), o armazenamento centrado torna-se o minimizador único para ordens $d \ge 4$, enquanto o não sinalizado é ótimo para ordens menores.
• Lei Lexicográfica: Para qualquer família finita de representações, o minimizador eventual conforme a ordem de mascaramento $d \to \infty$ é determinado pelo espectro de coeficientes de vazamento ordenado lexicograficamente menor.
• Livros de Códigos de Peso Constante: Para codificações binárias arbitrárias, o vazamento desaparece exatamente se, e somente se, o livro de códigos possuir peso de Hamming constante. O artigo fornece um limite de capacidade agudo para a existência de tais livros de códigos ($q \le \binom{\beta}{\lfloor \beta/2 \rfloor}$) e calcula a largura mínima de palavra necessária para os módulos padrão do NIST (ex: $\beta=14$ para $q=3329$).

3. A Lei de Redução Centrada

O resultado teórico central do artigo é uma decomposição espectral exata do vazamento de complemento de dois centrado:

• Decomposição: O espectro de vazamento é dividido em um termo macroscópico de extensão de sinal e um defeito de carry (vai-um) binário.
• Limiar de Dominância: O artigo prova um limiar uniforme agudo: três bits excedentes ($s = \beta - \lceil \log_2 q \rceil \ge 3$) são necessários para que o armazenamento centrado exiba uma magnitude de vazamento estritamente maior que o armazenamento não sinalizado no primeiro modo de Fourier. Especificamente, a condição $D(q, \beta) > 2U(q)$ ocorre se, e somente se, $s \ge 3$.
• Assíntotas: Para largura de excesso fixa, a razão dos coeficientes de vazamento centrado para não sinalizado converge para $s+1$. Para o caso específico de $q=2^m-1$, a razão de vazamento converge para uma constante relacionada à soma das tangentes ($\kappa \approx 1.81$).
• Neutralidade: A aritmética centrada não é neutra em relação ao vazamento. Ela é apenas neutra (equivalente em vazamento ao não sinalizado) no caso exato onde $q=2^m$ e $\beta=m$. Em todos os outros casos, o armazenamento centrado resulta em vazamento estritamente maior no primeiro modo de Fourier (e tipicamente para baixas ordens de mascaramento), embora possa se tornar a representação ótima em ordens muito altas para conjuntos de parâmetros específicos.

4. Robustez e Complexidade de Amostragem

• Raios de Robustez: O artigo define raios de robustez exatos para modelos de peso de Hamming ponderado, mostrando que a separação estrita entre o armazenamento centrado e o não sinalizado se mantém mesmo com variações de sensibilidade de bits, desde que a largura de excesso seja de pelo menos 3.
• Complexidade de Amostragem: Um teste harmônico de confiança exponencial é proposto. O artigo prova que a razão de complexidade de amostragem entre ataques centrados e não sinalados escala como a $2d$-ésima potência da razão de seus coeficientes espectrais. Isso implica que, para ordens de mascaramento mais altas, a penalidade por usar armazenamento centrado (que possui maior vazamento no primeiro modo) cresce exponencialmente, a menos que o conjunto de parâmetros específico coloque o sistema em um regime onde o armazenamento centrado é o minimizador global.

Resultados e Validação

• Experimentos Sintéticos: Implementações de tamanho total para ML-KEM ($q=3329$) e ML-DSA ($q=8380417$) confirmam os fatores de complexidade de amostragem teóricos. Para $d=3, 4, 6$, a representação centrada requer significativamente mais traços do que o armazenamento não sinalizado para atingir a mesma taxa de sucesso, alinhando-se aos limites assintóticos derivados.
• Traços Físicos: A análise foi validada contra traços físicos públicos de uma implementação mascarada de ML-DSA. O predicado de sinal alcançou um Welch $|t|$ de 155.73 e 90.80% de acurácia balanceada, confirmando a presença do canal de vazamento de extensão de sinal previsto pela teoria.
• Eficiência Algorítmica: O ataque ótimo proposto (usando convolução baseada em FFT) conseguiu pontuar todas as hipóteses para $q=8,380,417$ em menos de 35 segundos, demonstrando viabilidade prática.

Significância

O artigo altera fundamentalmente a compreensão do mascaramento aritmético em software. Ele demonstra que a escolha da representação de máquina (centrada vs. não sinalada) não é meramente um detalhe de implementação, mas um componente crítico do canal de vazamento de canal lateral.

• Refutação da Neutralidade: O autor mostra conclusivamente que "A Aritmética Centrada Não é Neutra em Relação ao Vazamento". A extensão de sinal inerente à representação de complemento de dois introduz um espectro de vazamento distinto que não é mitigado apenas pelo mascaramento.
• Diretrizes de Design: O trabalho fornece diretrizes exatas e acionáveis para implementadores:
  • Use armazenamento não sinalizado para segurança de primeira ordem e quando os bits de excesso são baixos ($s < 3$), pois ele minimiza unicamente o vazamento de primeira ordem.
  • Esteja ciente de que o armazenamento centrado geralmente incorre em uma penalidade severa na complexidade de amostragem devido ao maior vazamento no primeiro modo, tornando-se ótimo apenas em ordens muito altas para conjuntos de parâmetros específicos (demonstrando uma mudança de fase na otimalidade).
  • Livros de códigos de peso constante oferecem um caminho teórico para o vazamento zero, mas exigem larguras de palavra específicas que podem não se alinhar com as restrições de hardware padrão.
• Fundamentação Teórica: Ao fornecer leis espectrais exatas e condições de otimalidade de ruído finito, o artigo fecha a lacuna entre a segurança teórica de mascaramento e as realidades práticas de implementação, ofereando uma base rigorosa para avaliar e projetar sistemas criptográficos de reticulados resistentes a canais laterais.