Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

Resumo Técnico: Derandomização Parcial para o Compartilhamento de Segredos de Shamir com Resiliência a Vazamentos sobre Campos de Ordem Composta

1. Definição do Problema

O artigo aborda a construção de lugares de avaliação explícitos para esquemas de Compartilhamento de Segredos de Shamir (SSS) que sejam resilientes ao vazamento de bits físicos sobre campos de ordem composta ($\mathbb{F}_{p^d}$ onde $d \ge 2$).

No SSS padrão, um segredo é compartilhado entre $n$ partes de tal forma que quaisquer $k$ possam reconstruí-lo. Embora construções aleatorizadas (escolhendo lugares de avaliação uniformemente ao acaso) sejam conhecidas por serem estatisticamente seguras contra vazamento local, elas exigem aleatoriedade pública confiável. Na prática, adversários podem influenciar a semente aleatória, direcionando o esquema para lugares de avaliação vulneráveis.

Trabalhos anteriores estabeleceram que:

• Sobre campos primos ($\mathbb{F}_p$), lugares de avaliação aleatórios produzem resiliência a vazamentos com alta probabilidade.
• Sobre campos compostos ($\mathbb{F}_{p^d}$), Nguyen (EUROCRYPT 2025) estabeleceu uma dicotomia perfeita: qualquer esquema de compartilhamento de segredos baseado em códigos lineares é ou perfeitamente seguro (distância estatística 0) ou completamente inseguro contra vazamento de bits físicos.
• No entanto, para campos compostos, nenhum método explícito e determinístico de família de lugares de avaliação era conhecido para $k > 2$ ou regimes gerais de vazamento de blocos. As construções explícitas existentes para campos primos dependiam de propriedades de extração de bits não lineares que não se aplicam aos mapas de coordenadas lineares de campos compostos.

O desafio central é derandomizar a escolha dos lugares de avaliação (reduzindo a entropia necessária para especificá-los) enquanto se mantém a segurança perfeita contra o vazamento de bits físicos no cenário de campos compostos.

2. Metodologia e Construção

O autor propõe uma estratégia de derandomização parcial. Em vez de selecionar $n$ pontos de avaliação independentes e aleatórios, eles constroem os lugares de avaliação como as iterações de uma função racional $\Phi$ aplicada a um ponto base escolhido aleatoriamente $x_0$.

A Construção:

• Configuração do Campo: Seja $\mathbb{F} = \mathbb{F}_{p^d}$ com um elemento primitivo $\alpha$.
• Operador de Passo: Defina a transformação de Möbius $\Phi(x) = \frac{\alpha x}{x + 1}$.
• Lugares de Avaliação: Os $n$ lugares de avaliação são definidos como $x_j = \Phi^j(x_0)$ para $j = 0, \dots, n-1$, onde $x_0 \in \mathbb{F}^*$ é um ponto base escolhido aleatoriamente.
• Redução de Entropia: Especificar o esquema requer apenas $d \log p$ bits (para escolher $x_0$), uma redução significativa em relação aos $nd \log p$ bits exigidos para $n$ pontos aleatórios independentes.

Insight Estrutural Chave:
A análise de segurança baseia-se nos polos distintos das iterações de $\Phi$.

• $\Phi^0(x) = x$ tem um polo em $\infty$.
• Para $j \ge 1$, $\Phi^j(x)$ tem um polo em um ponto finito distinto em $\mathbb{F}^*$.
• Esta "distinção de polos" é crucial. O autor contrasta isso com o candidato $\Psi(x) = \alpha x$ (dilatação pura), onde todas as iterações compartilham o mesmo polo em $\infty$, fazendo com que o argumento de segurança colapse.

3. Abordagem Técnica

A prova procede em três fases, aproveitando a dicotomia perfeita estabelecida por Nguyen (2025):

1. A Dicotomia Perfeita (Fase 1):
   O artigo utiliza o fato de que a extração de coordenadas em $\mathbb{F}_{p^d}$ é $\mathbb{F}_p$-linear. Consequentemente, o mapa de vazamento é linear. Isso implica que a distância estatística entre distribuições de vazamento para diferentes segredos é ou 0 ou 1. A segurança perfeita é alcançada se, e somente se, o mapa de vazamento for sobrejetor. Esta condição é equivalente a uma matriz de teste $\Theta_{\vec{i}}$ (derivada dos lugares de avaliação e do padrão de vazamento) ter posto de coluna total sobre $\mathbb{F}_p$.

2. Não-degenerescência de Frações Parciais (Fase 2):
   Para provar que a matriz de teste tem posto total, o autor deve mostrar que nenhuma combinação linear não trivial das potências dos lugares de avaliação se anula. Eles definem uma função racional $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$.
   Usando decomposição em frações parciais, eles exploram os polos distintos de $\Phi^j$. Como os polos são distintos, o resíduo de $G_\ell$ em qualquer polo específico é determinado por um único termo na soma. Se $G_\ell$ fosse identicamente zero, todos os coeficientes teriam que ser nulos. Este argumento de "não-degenerescência" limita o número de pontos base "ruins" que fazem o posto da condição falhar.

3. Extensão para Múltiplos Blocos (Fase 3):
   O argumento é estendido para vazamento de múltiplos blocos (onde múltiplas coordenadas por compartilhamento são vazadas). O autor lida com os coeficientes de campo provenientes de combinações lineares dentro dos compartilhamentos, mostrando que o argumento de fração parcial permanece válido desde que o padrão de vazamento seja "admissível" (posições de blocos distintas por compartilhamento).

4. Resultados Principais

Teorema 1.1 (Segurança Perfeita contra Vazamento de Bloco Único):
Para parâmetros $n = O(d / \log_p d)$ e qualquer limiar $k \ge 2$, existe um conjunto de "pontos base ruins" $Bad \subset \mathbb{F}^*$ com tamanho $|Bad| \le n + n(dp)^n$. Para qualquer $x_0 \notin Bad$, o esquema usando lugares de avaliação $x_j = \Phi^j(x_0)$ é perfeitamente seguro (distância estatística exatamente 0) contra qualquer padrão de vazamento de bloco único.

• Isso implica segurança perfeita contra vazamento de um único bit físico por compartilhamento para qualquer primo $p$.
• Um bom $x_0$ é garantido quando $d > n(1 + \log_p d) + \log_p(2n)$.

Teorema 1.2 (Vazamento de Múltiplos Blocos):
Para um padrão de vazamento admissível fixo com $M$ blocos totais vazados, o tamanho do conjunto ruim é limitado por $n + n \cdot p^M$. Um bom $x_0$ existe se $M < d - \log_p(2n)$.

• Para segurança universal contra todos os padrões com $\le M$ blocos, o limite é $|Bad| \le n + n(dpe)^M$, com existência garantida quando $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$.

Classificador:
O artigo fornece um classificador explícito (Algoritmo 1) que, dado um candidato $x_0$, verifica a condição de posto total para todos os padrões de vazamento. Isso serve como um teste sólido para certificar a segurança da construção estruturada.

5. Significância e Comparação

O artigo reivindica as seguintes contribuições e distinções:

• Segurança Perfeita vs. Segurança Estatística: Ao contrário de construções aleatorizadas anteriores sobre campos compostos que ofereciam segurança estatística ($\epsilon = 2^{-\Omega(d)}$), esta construção alcança segurança perfeita (distância estatística 0) para um regime restrito de parâmetros.
• Derandomização: Reduz a aleatoriedade necessária para especificar o esquema de $nd \log p$ bits para $d \log p$ bits, restringindo os lugares de avaliação à órbita de $\Phi$.
• Construção Explícita: Fornece a primeira família explícita de lugares de avaliação para $k > 2$ sobre campos compostos que resiste ao vazamento de bits físicos, indo além do paradigma de "lugares aleatórios".
• Limitações e Trocas (Trade-offs):
  • O número de partes $n$ é limitado a $O(d / \log_p d)$, enquanto construções aleatorizadas suportam $O(dk / \log_p d)$. O autor conjectura que esta perda de fator-$k$ é inerente às construções de parâmetro único.
  • A universalidade de múltiplos blocos é atualmente limitada por um gargalo de enumeração de padrões, resultando em limites de conjunto ruim exponenciais em $M$.
  • A construção depende da estrutura algébrica específica da transformação de Möbius $\Phi(x) = \alpha x / (x+1)$; a alternativa de dilatação $\alpha x$ falha em fornecer segurança.

O trabalho não afirma resolver o problema da derandomização para todos os regimes de parâmetros ou fornecer um limite de tamanho de conjunto ruim polinomial para a universalidade de múltiplos blocos, identificando estes como problemas abertos. A principal contribuição é uma derandomização parcial rigorosa que alcança segurança perfeita em um regime específico e praticante relevante ao explorar os polos distintos das iterações racionais.