Secret sharing with additive access structures from correlated random variables

Résumé Technique : Partage de Secret avec des Structures d'Accès Additives à partir de Variables Aléatoires Corrélationnées

Énoncé du Problème
Le document traite du problème du partage de secret dans un environnement dynamique où l'ensemble des participants autorisés (la structure d'accès) évolue au fil du temps. Les modèles traditionnels de partage de secret supposent généralement une structure d'accès fixe ; si la structure change, les parts doivent être redistribuées, ce qui entraîne une inefficacité. Bien que le modèle de « Structure d'Accès Évolutive » (EAS) permette une croissance monotone, il suppose que les participants rejoignent le système séquentiellement et reçoivent des parts via des canaux privés.

Ce travail introduit le modèle de Structure d'Accès Additive (AAS), qui diffère de l'EAS de deux manières fondamentales :

1. Initialisation Simultanée : Tous les participants sont présents initialement.
2. Source de Randomité Corrélationnée : Les parts sont générées simultanément à partir d'une source de randomité corrélationnée (par exemple, les mesures de gain de canal dans les réseaux sans fil) plutôt que d'être distribuées via des canaux privés.
3. Communication Publique : Le dépositaire communique avec les participants via un canal public, sans bruit et authentifié. Le dépositaire apprend les changements apportés à la structure d'accès (nouveaux groupes autorisés) uniquement au moment où ils se produisent et doit adapter la stratégie de partage de secret de manière itérative.

L'objectif est de déterminer une stratégie de partage de secret permettant aux groupes autorisés de récupérer un secret avec une grande fiabilité tout en garantissant que les groupes non autorisés n'apprennent qu'une information négligeable, tout en maximisant le débit de secret (la taille du secret partagé normalisée par le nombre d'observations de la source).

Méthodologie
Les auteurs proposent une stratégie de partage de secret basée sur le binage aléatoire (random binning) adapté à un contexte dynamique. Le cœur de la méthodologie implique :

• Binage Quantifié : Le dépositaire observe une séquence $Y^n$ provenant d'une source corrélationnée $(Y, X_L)$. Pour chaque étape de temps $t$, le dépositaire et les participants utilisent des fonctions de binage aléatoire prédéterminées ($g_i$ et $h_j$) qui associent les séquences sources à des indices.
• Codage Itératif : À chaque étape $t$, le dépositaire détermine le nombre d'indices de binage ($k_t$) à inclure dans le message public et le nombre d'indices ($\sigma_t$) à désigner comme secret. Ces décomptes sont choisis en fonction de l'ensemble autorisé actuel $A_t$ et de l'ensemble non autorisé $U_t$.
• Spécification de Stratégie A Priori : Un aspect novateur de la preuve est l'introduction d'un nombre quantifié de binages. Cela permet la construction d'une stratégie de partage de secret unique qui est entièrement spécifiée a priori. Crucialement, cette stratégie ne dépend pas de la connaissance de la façon dont l'AAS évoluera lors des étapes futures ; le dépositaire a seulement besoin de connaître la structure d'accès actuelle pour déterminer le message et le secret pour cette étape spécifique.
• Décodage : Les participants autorisés utilisent leurs observations locales ($X^n_A$), les messages publics accumulés et les fonctions de binage pour identifier l'unique séquence source cohérente avec les contraintes de typicalité et les indices de bin reçus.

Contributions Clés et Résultats
Le document établit les résultats théoriques suivants :

1. Accessibilité des Débits de Structure Fixe : Les auteurs prouvent qu'il existe une stratégie pour le modèle AAS où le débit de secret accessible à n'importe quelle étape $t$ est indépendant des structures d'accès de toutes les autres étapes. Plus précisément, le débit accessible $R_t$ correspond au meilleur débit connu pour un modèle de structure d'accès fixe :
   $$R_t = \min_{U \in U_t} H(Y | X_U) - \max_{A \in A_t} H(Y | X_A)$$
   Ce résultat implique que la nature dynamique de la structure d'accès ne dégrade pas intrinsèquement le débit de secret par rapport à un scénario statique.

2. Capacité pour les Structures d'Accès à Seuil : Le document prouve que lorsque la structure d'accès à une étape donnée forme une Structure d'Accès à Seuil (où tout groupe de taille $\ge f_1(t)$ est autorisé et tout groupe de taille $\le f_2(t)$ est non autorisé), la stratégie proposée atteint la capacité. Pour un cas spécifique où le dépositaire partage des clés privées indépendantes avec les participants, la capacité est démontrée comme suit :
   $$R_t = H(X)(f_1(t) - f_2(t))$$

3. Omniscience vs Causalité : Une conclusion importante est que pour le cas de l'AAS à seuil, un dépositaire omniscient (connaissant toute la séquence future des structures d'accès) ne gagne aucun avantage sur un dépositaire causal (qui ne connaît que la structure actuelle) en termes de débits de secret accessibles.

Signification et Revendications
Le document prétend généraliser les modèles de partage de secret reposant sur la randomité corrélationnée, passant de structures d'accès additives fixes à dynamiques. La principale signification réside dans la démonstration que l'adaptabilité dynamique ne se fait pas au détriment de l'efficacité du débit de secret. Les auteurs montrent que l'on peut atteindre les mêmes limites de performance que les meilleures stratégies statiques sans nécessiter de connaissance préalable de l'évolution du système.

Le travail souligne que le résultat « surprenant » est l'indépendance du débit accessible à l'instant $t$ vis-à-vis de l'historique ou du futur de la structure d'accès. Bien que le document fournisse une preuve d'existence non constructive pour le cas général de l'AAS (en s'appuyant sur la méthode probabiliste pour démontrer l'existence de fonctions de binage appropriées), il note explicitement que fournir une preuve d'accessibilité constructive pour l'AAS général demeure un problème ouvert, ce qui le distingue des preuves constructives existantes pour les structures fixes.

Le document conclut que pour les structures dynamiques basées sur des seuils, la capacité est pleinement caractérisée, et que l'absence de prévoyance concernant les changements futurs de la structure d'accès ne pénalise pas la performance du système.