💻 computer science

Information-Theoretic Distributed Point Functions with Shorter Keys

Cet article présente une nouvelle fonction de point distribuée information-théorique (ITDPF) 1-privée, parfaitement sécurisée, sur le groupe $\mathbb{Z}_p$ , qui atteint des clés secrètes asymptotiquement plus courtes que les schémas existants en exploitant une conversion de partage basée sur des techniques récentes de récupération d'information privée.

Auteurs originaux : Hang Deng, Liang Feng Zhang

Publié 2026-04-28

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Hang Deng, Liang Feng Zhang

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous possédez une carte au trésor secrète qui pointe vers exactement un emplacement spécifique sur une grille géante (disons une ville avec des millions de pâtés de maisons). Vous souhaitez donner des copies de cette carte à un groupe d'amis afin qu'ils puissent, ensemble, déterminer où se trouve le trésor. Cependant, vous imposez une règle stricte : aucun petit groupe d'amis (par exemple, deux ou moins) ne doit pouvoir déduire l'emplacement simplement en comparant leurs copies. Ils doivent combiner toutes leurs pièces pour résoudre l'énigme.

Ceci est le problème central d'une Fonction de Point Distribuée (DPF). C'est un outil cryptographique qui divise une « fonction de point » (une fonction qui est nulle partout sauf en un point spécial) en de nombreuses « parts » (clés).

L'Ancienne Méthode vs La Nouvelle Méthode

L'Ancienne Méthode (Les Sacs à Dos Lourds) :
Les méthodes précédentes pour réaliser cela de manière sécurisée (spécifiquement la sécurité « informationnelle », ce qui signifie qu'elles sont sûres même face à des superordinateurs dotés d'une puissance infinie) obligeaient les amis à porter des sacs à dos très lourds. Ces sacs contenaient les « clés » nécessaires pour résoudre l'énigme. À mesure que la ville (les données) grossissait, ces sacs devenaient exponentiellement plus grands, rendant le système lent et peu pratique.

La Nouvelle Méthode (Les Sacs Légers) :
Cet article présente une nouvelle méthode qui crée des sacs beaucoup plus légers. Les auteurs, Hang Deng et Liang Feng Zhang, ont construit un système où les clés sont significativement plus courtes (plus petites) que n'importe quelle méthode parfaitement sûre précédente, en particulier lorsque les données deviennent énormes.

Comment Ils Ont Fait : La « Recette Secrète »

Les auteurs n'ont pas inventé un nouveau sortilège magique à partir de zéro ; ils ont utilisé une recette astucieuse (appelée le cadre LKZ) qui transforme un type d'outil de partage de secrets en un autre.

L'Ingrédient (PIR) : La sauce secrète qu'ils ont utilisée est un outil de pointe appelé Récupération d'Information Privée (PIR). Considérez le PIR comme un moyen de demander un livre spécifique à un bibliothécaire sans que celui-ci sache quel livre vous avez demandé. Une percée récente de Ghasemi, Kopparty et Sudan a rendu ce processus de « demande » incroyablement efficace.
La Conversion (Le Tour de Magie) : Les auteurs ont découvert comment traduire le mécanisme de « demande » de ce nouveau PIR en le mécanisme de « division de clés » nécessaire pour leur DPF.
- Analogie : Imaginez que l'ancien PIR consistait à demander un livre à un bibliothécaire en remplissant un formulaire complexe de 10 pages. Le nouveau PIR utilise un code minuscule de 2 mots. Les auteurs ont trouvé un moyen de transformer ce petit code de 2 mots en les clés secrètes de la carte au trésor, garantissant que les clés restent minuscules.

Le Résultat : Une Clé Parfaitement Sûre et Minuscule

L'article prétend avoir construit un système qui est :

Parfaitement Sûr : Même si un pirate dispose d'une puissance de calcul infinie, il ne peut rien apprendre sur l'emplacement secret s'il vole quelques clés.
Efficace : Les « clés » (les données que chaque serveur détient) sont asymptotiquement plus courtes. En termes simples : à mesure que la quantité de données augmente, la taille des clés croît beaucoup plus lentement qu'auparavant.
Flexible : Il fonctionne pour n'importe quelle taille de nombre premier (un type spécifique de groupe mathématique), ce qui couvre un large éventail de besoins pratiques.

L'Écueil (Limites)

Les auteurs sont honnêtes concernant les compromis :

La Règle du « Un Seul Serveur » : Actuellement, cette construction spécifique garantit uniquement qu'un seul serveur ne peut pas apprendre le secret s'il collabore avec d'autres. Si vous souhaitez vous protéger contre la collusion de deux ou trois serveurs, le système devrait exploser en taille (nécessitant exponentiellement plus de serveurs), ce qui est actuellement trop inefficace pour être utile.
Mathématiques Spécifiques : Il fonctionne mieux avec des types spécifiques de groupes mathématiques (groupes d'ordre premier), bien que les auteurs suggèrent qu'il pourrait être étendu à des groupes plus complexes à l'avenir.

Résumé

En bref, cet article est comme un ingénieur qui a trouvé un moyen de réduire un coffre-fort de sécurité massif et encombrant à la taille d'un coffre de poche sans perdre aucune de sa solidité. Ils ont fait cela en empruntant une technique de « crochetage de serrure » hautement efficace à un domaine différent (la Récupération d'Information Privée) et en l'adaptant pour diviser des secrets entre des serveurs. Le résultat est un système mathématiquement incassable et beaucoup plus rapide à utiliser que tout ce qui l'a précédé.

1. Énoncé du problème

Le papier aborde la construction de Fonctions de Point Distribuées Information-Théoriques (ITDPF).

Définition : Une ITDPF $(t, n)$ permet de diviser une fonction de point $f_{\alpha, \beta}(x)$ (qui renvoie $\beta$ à l'entrée $\alpha$ et $0$ ailleurs) en $n$ clés secrètes. Tout sous-ensemble de $\le t$ serveurs ne apprend absolument rien sur la fonction (sécurité parfaite), tandis que la somme des évaluations de l'ensemble des $n$ serveurs reconstruit la valeur de la fonction.
Le défi : La métrique principale pour l'efficacité des DPF est la taille des clés (la taille maximale des clés secrètes). Les ITDPF parfaitement sécurisées existantes pour le groupe de sortie $G = \mathbb{Z}_p$ $G = Z_{p}$ (où $p$ $p$ est un nombre premier quelconque) souffrent de tailles de clés sous-optimales.
- Les travaux antérieurs (par exemple, Boyle et al., Li et al.) ont atteint des tailles de clés avec des exposants impliquant des fonctions telles que $\nu_r(N) = (\log N)^{1/r}(\log \log N)^{1-1/r}$ .
- L'objectif est de réduire la taille asymptotique des clés tout en maintenant une sécurité parfaite et en supportant un nombre premier $p$ arbitraire.

2. Méthodologie

Les auteurs proposent une construction novatrice basée sur le cadre LKZ (Li, Kopparty et Zhang) combiné à des techniques d'Interrogation Privée d'Information (PIR) de l'état de l'art.

A. Le cadre LKZ

Le cadre transforme un Schéma de Partage de Secret (SSS) en une ITDPF via une Conversion de Parts.

Conversion de Parts : Elle nécessite de convertir des parts d'un SSS à seuil $(t, n)$ ( $L_1$ ) en parts d'un SSS additif ( $L_2$ ) de telle sorte que la somme des parts converties révèle une relation spécifique avec le secret original.
Représentation bilinéaire : La fonction de point est représentée comme une fonction bilinéaire des parts converties.
Idée clé : La taille de clé de l'ITDPF résultante est proportionnelle à la complexité de communication du schéma PIR sous-jacent utilisé pour générer la conversion de parts.

B. Exploitation de la PIR basée sur les dérivées GKS

L'innovation technique centrale réside dans l'utilisation du récent schéma PIR 1-privé à $n_r$ serveurs par Ghasemi, Kopparty et Sudan (GKS, STOC 2025).

Mécanisme GKS : Contrairement aux schémas PIR précédents qui ne requéraient que des évaluations d'un polynôme, GKS requiert à la fois des évaluations et des dérivées de Hasse du polynôme.
Fondement mathématique :
- Utilisation de familles $S$ -appariées et de polynômes de décodage $S$ sur des corps finis.
- Introduction de la propriété d'interpolation 0 avec multiplicité. En demandant des dérivées, le schéma peut interpoler le terme constant d'un polynôme creux en utilisant moins de serveurs ou de paramètres plus petits.
- Spécifiquement, GKS atteint une complexité de communication de $2^{O(\nu_{r+1}(N))}$ pour $n_r$ serveurs, où $n_r$ dépend du nombre de facteurs premiers du module.

C. Étapes de la construction proposée

Configuration :
- Sélection d'un module $M = m \cdot p$ (produit de nombres premiers distincts).
- Construction d'une famille $S_M$ -appariée et d'un polynôme de décodage $S_M$ avec multiplicité 2 (rendu possible par les requêtes de dérivées).
Conversion de Parts ($Conv$) :
- Le serveur détient une part $c_\ell$ dérivée d'un vecteur aléatoire $w$ et de l'index cible $\alpha$ .
- Étant donné une entrée $x$ , le serveur calcule un "polynôme de base" $D_x(Z)$ restreint à une ligne multiplicative.
- En utilisant la règle de chaîne, le serveur calcule la dérivée de Hasse d'ordre un de $D_x(Z)$ en des points spécifiques $b_\ell$ .
- Le serveur émet une part convertie impliquant l'évaluation $D_x(b_\ell)$ et le terme de dérivée, pondérés par des coefficients d'interpolation $a_{\ell, k}$ .
Génération de DPF :
- Le générateur crée $2n_r$ clés. Chaque clé consiste en une paire : une part additive de la valeur de sortie et une part du SSS sous-jacent basé sur PIR.
- L'algorithme d'évaluation calcule le produit scalaire des composants de la clé pour récupérer la part additive de $f_{\alpha, \beta}(x)$ .

3. Contributions clés

Nouvelle conversion de parts : Les auteurs dérivent une nouvelle fonction de conversion de parts directement à partir de la PIR basée sur les dérivées GKS. Il s'agit de la première application de la PIR basée sur les dérivées pour construire des ITDPF.
Taille de clé améliorée : Ils construisent une ITDPF $(1, 2n_r)$ $(1, 2 n_{r})$ parfaitement sécurisée avec un groupe de sortie $\mathbb{Z}_p$ $Z_{p}$ .
- Taille de clé : $O(2^{c_2(r) \cdot \nu_{r+1}(N)} \cdot \log p)$ .
- Amélioration : Cela est asymptotiquement plus petit que les meilleures ITDPF parfaitement sécurisées précédentes (par exemple, $2^{O(\nu_r(N))}$ de Li et al.), réduisant effectivement l'exposant de $\nu_r(N)$ à $\nu_{r+1}(N)$ .
Sécurité parfaite : La construction maintient une sécurité parfaite (sécurité informationnelle contre des adversaires à puissance de calcul illimitée), contrairement à certaines alternatives statistiques qui sacrifient la sécurité pour l'efficacité.
Généralité : Le schéma fonctionne pour n'importe quel nombre premier $p$ comme module du groupe de sortie, une généralisation significative par rapport à certaines constructions antérieures.

4. Résultats

Bornes théoriques : Le papier prouve que le schéma proposé satisfait les exigences de correction et de sécurité parfaite du cadre LKZ.
Comparaison (Tableau I) :
- Par rapport au Thm. 10 de [10] (Li et al.), qui a une taille de clé de $O(2^{c_1(r) \cdot \nu_r(N)})$ , le nouveau schéma atteint $O(2^{c_2(r) \cdot \nu_{r+1}(N)})$ . Puisque $\nu_{r+1}(N) < \nu_r(N)$ , les nouvelles clés sont strictement plus courtes asymptotiquement.
- Par rapport au Thm. 1 de [2] (Boyle et al.), le nouveau schéma n'est pas pire et offre une meilleure échelle asymptotique pour de grands $N$ .
Paramètres : Le nombre de serveurs requis est $2n_r$ , où $n_r$ est défini par le nombre de facteurs premiers dans la construction PIR (par exemple, $n_1=2, n_2=3, \dots$ ).

5. Importance

Efficacité dans le MPC et la PIR : Les DPF sont des blocs de construction fondamentaux pour le Calcul Multi-Parties Sécurisé (MPC) et l'Interrogation Privée d'Information (PIR). Réduire la taille des clés se traduit directement par une surcharge de communication et des besoins de stockage réduits dans ces protocoles.
Lien entre PIR et DPF : Ce travail démontre une synergie puissante entre les avancées récentes en PIR (spécifiquement les approches basées sur les dérivées) et la construction de DPF. Il suggère que les améliorations de la complexité de communication en PIR peuvent être directement traduites en DPF plus efficaces.
Directions futures :
- La construction actuelle est limitée aux DPF 1-privés (sécurité contre 1 serveur collusif) car la PIR GKS sous-jacente est 1-privée. Étendre cela à des DPF $t$ -privés avec $t > 1$ sans explosion exponentielle du nombre de serveurs est un défi ouvert.
- L'extension du groupe de sortie de $\mathbb{Z}_p$ d'ordre premier à des groupes abéliens arbitraires est identifiée comme un travail futur.

En résumé, ce papier présente une percée dans l'efficacité des ITDPF parfaitement sécurisées en exploitant les dernières techniques de PIR basées sur les dérivées, atteignant les clés secrètes les plus courtes connues pour les groupes de sortie d'ordre premier.