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

Résumé Technique : Dérandomisation Partielle pour le Partage de Secret de Shamir Résistant aux Fuites sur des Corps d'Ordre Composé

1. Énoncé du Problème

L'article traite de la construction de lieux d'évaluation explicites pour les schémas de partage de secret de Shamir (SSS) qui sont résilients contre la fuite de bits physiques sur des corps d'ordre composé ($\mathbb{F}_{p^d}$ où $d \ge 2$).

Dans le SSS standard, un secret est partagé parmi $n$ parties de telle sorte que n'importe quel groupe de $k$ peut le reconstruire. Les constructions randomisées (choisissant les lieux d'évaluation uniformément au hasard) sont connues pour être statistiquement sûres contre les fuites locales, mais elles nécessitent une randomité publique de confiance. En pratique, les adversaires peuvent influencer la graine aléatoire, orientant le schéma vers des lieux d'évaluation vulnérables.

Des travaux antérieurs ont établi que :

• Sur les corps premiers ($\mathbb{F}_p$), les lieux d'évaluation aléatoires produisent une résilience aux fuites avec une haute probabilité.
• Sur les corps composés ($\mathbb{F}_{p^d}$), Nguyen (EUROCRYPT 2025) a établi une dichotomie parfaite : tout schéma de partage de secret basé sur des codes linéaires est soit parfaitement sûr (distance statistique 0), soit complètement non sécurisé contre la fuite de bits physiques.
• Cependant, pour les corps composés, aucune famille explicite et déterministe de lieux d'évaluation n'était connue pour $k > 2$ ou pour des régimes de fuite par blocs généraux. Les constructions explicites existantes pour les corps premiers reposaient sur des propriétés d'extraction de bits non linéaires qui ne s'appliquent pas aux applications de coordonnées linéaires des corps composés.

Le défi central est de dérandomiser le choix des lieux d'évaluation (réduisant l'entropie nécessaire pour les spécifier) tout en maintenant une sécurité parfaite contre la fuite de bits physiques dans le cadre des corps composés.

2. Méthodologie et Construction

L'auteur propose une stratégie de dérandomisation partielle. Au lieu de sélectionner $n$ points d'évaluation indépendants et aléatoires, ils construisent les lieux d'évaluation comme les itérés d'une fonction rationnelle $\Phi$ appliquée à un point de base choisi aléatoirement $x_0$.

La Construction :

• Configuration du Corps : Soit $\mathbb{F} = \mathbb{F}_{p^d}$ avec un élément primitif $\alpha$.
• Opérateur d'Étape : Définir la transformation de Möbius $\Phi(x) = \frac{\alpha x}{x + 1}$.
• Lieux d'Évaluation : Les $n$ lieux d'évaluation sont définis comme $x_j = \Phi^j(x_0)$ pour $j = 0, \dots, n-1$, où $x_0 \in \mathbb{F}^*$ est un point de base choisi aléatoirement.
• Réduction d'Entropie : Spécifier le schéma nécessite seulement $d \log p$ bits (pour choisir $x_0$), une réduction significative par rapport aux $nd \log p$ bits requis pour $n$ points aléatoires indépendants.

Intuition Structurelle Clé :
L'analyse de sécurité repose sur les pôles distincts des itérés de $\Phi$.

• $\Phi^0(x) = x$ possède un pôle en $\infty$.
• Pour $j \ge 1$, $\Phi^j(x)$ possède un pôle distinct en un point fini de $\mathbb{F}^*$.
• Cette « distinction des pôles » est cruciale. L'auteur contraste cela avec le candidat $\Psi(x) = \alpha x$ (dilatation pure), où tous les itérés partagent le même pôle en $\infty$, provoquant l'effondrement de l'argument de sécurité.

3. Approche Technique

La preuve se déroule en trois phases, en s'appuyant sur la dichotomie parfaite établie par Nguyen (2025) :

1. La Dichotomie Parfaite (Phase 1) :
   L'article utilise le fait que l'extraction de coordonnées dans $\mathbb{F}_{p^d}$ est $\mathbb{F}_p$-linéaire. Par conséquent, la carte de fuite est linéaire. Cela implique que la distance statistique entre les distributions de fuite pour différents secrets est soit 0, soit 1. La sécurité parfaite est atteinte si et seulement si la carte de fuite est surjective. Cette condition est équivalente à une matrice de test $\Theta_{\vec{i}}$ (dérivée des lieux d'évaluation et du motif de fuite) ayant un rang maximal sur $\mathbb{F}_p$.

2. Non-dégénérescence par Fractions Partielles (Phase 2) :
   Pour prouver que la matrice de test a un rang maximal, l'auteur doit montrer qu'aucune combinaison linéaire non triviale des puissances des lieux d'évaluation ne s'annule. Ils définissent une fonction rationnelle $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$.
   En utilisant la décomposition en fractions partielles, ils exploitent les pôles distincts de $\Phi^j$. Parce que les pôles sont distincts, le résidu de $G_\ell$ en un pôle spécifique est déterminé par un seul terme de la somme. Si $G_\ell$ était identiquement nulle, tous les coefficients devraient s'annuler. Cet argument de « non-dégénérescence » permet de borner le nombre de points de base « mauvais » $x_0$ qui causent l'échec de la condition de rang.

3. Extension Multi-blocs (Phase 3) :
   L'argument est étendu aux fuites multi-blocs (où plusieurs coordonnées par part sont fuyées). L'auteur traite les coefficients de corps provenant des combinaisons linéaires au sein des parts, montrant que l'argument de fraction partielle reste valide à condition que le motif de fuite soit « admissible » (positions de blocs distinctes par part).

4. Résultats Clés

Théorème 1.1 (Sécurité Parfaite contre la Fuite Mono-bloc) :
Pour les paramètres $n = O(d / \log_p d)$ et pour tout seuil $k \ge 2$, il existe un ensemble de points de base « mauvais » $Bad \subset \mathbb{F}^*$ dont la taille est $|Bad| \le n + n(dp)^n$. Pour tout $x_0 \notin Bad$, le schéma utilisant les lieux d'évaluation $x_j = \Phi^j(x_0)$ est parfaitement sûr (distance statistique exactement 0) contre tout motif de fuite mono-bloc.

• Cela implique une sécurité parfaite contre toute fuite d'un seul bit physique par part pour tout nombre premier $p$.
• Un bon $x_0$ est garanti d'exister lorsque $d > n(1 + \log_p d) + \log_p(2n)$.

Théorème 1.2 (Fuite Multi-blocs) :
Pour un motif de fuite admissible fixé avec $M$ blocs totaux fuyés, la taille de l'ensemble mauvais est bornée par $n + n \cdot p^M$. Un bon $x_0$ existe si $M < d - \log_p(2n)$.

• Pour une sécurité universelle contre tous les motifs avec $\le M$ blocs, la borne est $|Bad| \le n + n(dpe)^M$, avec une existence garantie lorsque $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$.

Classificateur :
L'article fournit un classificateur explicite (Algorithme 1) qui, étant donné un $x_0$ candidat, vérifie la condition de rang maximal pour tous les motifs de fuite. Cela sert de test probant pour certifier la sécurité de la construction structurée.

5. Signification et Comparaison

L'article revendique les contributions et distinctions suivantes :

• Sécurité Parfaite vs Sécurité Statistique : Contra-irement aux constructions randomisées précédentes sur les corps composés qui offraient une sécurité statistique ($\epsilon = 2^{-\Omega(d)}$), cette construction atteint une sécurité parfaite (distance statistique 0) pour un régime de paramètres restreint.
• Dérandomisation : Elle réduit la randomité requise pour spécifier le schéma de $nd \log p$ bits à $d \log p$ bits en restreignant les lieux d'évaluation à une famille à un seul paramètre (l'orbite de $\Phi$).
• Construction Explicite : Elle fournit la première famille explicite de lieux d'évaluation pour $k > 2$ sur les corps composés qui résiste à la fuite de bits physiques, dépassant le paradigme des « lieux aléatoires ».
• Limites et Compromis :
  • Le nombre de parties $n$ est limité à $O(d / \log_p d)$, alors que les constructions randomisées supportent $O(dk / \log_p d)$. L'auteur conjecture que cette perte d'un facteur $k$ est inhérente aux constructions à un seul paramètre.
  • La l'universalité multi-bloc est actuellement limitée par un goulot d'étranglement de l'énumération des motifs, entraînant des bornes exponentielles pour l'ensemble mauvais en $M$.
  • La construction repose sur la structure algébrique spécifique de la transformation de Möbius $\Phi(x) = \alpha x / (x+1)$ ; l'alternative de dilatation $\alpha x$ échoue à fournir la sécurité.

Le travail ne prétend pas résoudre le problème de la dérandomisation pour tous les régimes de paramètres, identifiant cela comme un problème ouvert, ainsi que la borne de taille polynomiale pour l'universalité multi-bloc. La contribution principale est une dérandomisation partielle rigoureuse qui atteint la sécurité parfaite dans un régime spécifique et pratiquement pertinent en exploitant les pôles distincts des itérés rationnels.