Résumé technique : Bornes inférieures pour le PIR avec prétraitement à partir de la cryptographie boîte noire

1. Énoncé du problème

L'article étudie les limites fondamentales de l'Information Retrieval Privée (PIR) à serveur unique dans le modèle de prétraitement. Dans ce cadre, un client effectue une phase hors ligne pour stocker une petite quantité d'état ($s$ bits) concernant une base de données de $n$ bits, permettant des requêtes en ligne plus efficaces. Bien que des percées récentes aient démontré des schémas de PIR à serveur unique avec une computation et une communication de requête sous-linéaires en exploitant le prétraitement (par exemple, [CHK22, ZPZS24, LMW23]), les frontières théoriques de ces constructions restent floues.

Plus précisément, les auteurs examinent s'il est possible de construire des schémes de PIR à serveur unique qui :

1. Atteignent une computation en ligne amortie sous-linéaire (spécifiquement $o(n/s)$).
2. Reposent sur la cryptographie boîte noire (modélisée via des oracles cryptographiques, incluant les oracles aléatoires, l'obfuscation de boîte noire virtuelle et les groupes multilinéaires génériques).
3. Supportent le PIR Symétrique (SPIR) (où le client n'apprend que l'entrée requise) en utilisant uniquement des fonctions à sens unique (OWF) pendant la phase en ligne.

Les bornes inférieures antérieures pour le PIR avec prétraitement étaient limitées à des classes restreintes de schémas (ex: exigeant des serveurs non-encodants, des requêtes aveugles à la base de données, ou des interactions à un seul aller-retour) ou reposaient sur des hypothèses de complexité non prouvées. Ce travail vise à fournir des bornes inférieures inconditionnelles pour une classe plus large de schémas faisant usage de la cryptographie boîte noire.

2. Méthodologie

Le cœur de la méthodologie de l'article est l'introduction d'un nouveau primitif appelé Dual PIR et d'une réduction du PIR standard avec prétraitement vers ce primitif.

2.1 Dual Private Information Retrieval (Dual PIR)

Les auteurs définissent le Dual PIR comme une inversion du modèle de prétraitement PIR standard :

• Phase de conseil (Advice Phase) : Avant que toute requête ne soit connue, le client génère une chaîne de conseil (transcript) de $t$ bits basée sur la base de données.
• Phase d'indice (Hint Phase) : Étant donné la base de données, un lot de $k$ indices de requête, et le conseil, le client génère un indice (hint) de $s$ bits.
• Reconstruction : En utilisant uniquement les indices de requête, le conseil et l'indice, le client doit reconstruire les entrées de la base de données requises (mais sans accès à la base de données).

Cette formulation transforme le problème d'efficacité du PIR en un problème de compression. Si un schéma de PIR est trop efficace (c'est-à-dire $t = o(n)$ et $s < k$), cela implique l'existence d'un Dual PIR capable de compresser $k$ bits d'information en $s$ bits en utilisant seulement $t$ bits de conseil pré-partagé, ce qui est informationnellement impossible sous certaines conditions.

2.2 Réduction de PIR à Dual PIR

Les auteurs construisent une réduction montrant que tout schéma de PIR sécurisé avec prétraitement peut être transformé en un schéma Dual PIR.

• Conseil (Advice) : Simule l'exécution du PIR pour une requête fixe afin de générer un transcript de communication et un ensemble de requêtes d'oracles cryptographiques du serveur.
• Indice (Hint) : Re-randomise l'état du client pour correspondre au transcript fixe pour une autre requête. Crucialement, pour gérer la nature boîte noire de la cryptographie, l'algorithme d'Indice échantillonne de nouveaux oracles cryptographiques cohérents avec les requêtes précédentes du serveur (en utilisant un oracle aléatoire partagé pour assurer la cohérence).
• Reconstruction : Simule le côté client de la requête PIR en utilisant l'état échantillonné et le transcript fixe.

2.3 Connexion à la prédiction de sous-clé

Pour prouver l'impossibilité d'un Dual PIR efficace, les auteurs connectent le problème à la prédiction de sous-clé dans la cryptographie résiliente aux fuites ([BKR16]). Ils montrent qu'un Dual PIR correct et efficace permettrait à un adversaire de prédire $k$ bits aléatoires d'une clé de $n$ bits étant donné $t$ bits de fuite, avec une probabilité de succès dépassant les bornes informationnelles connues. Spécifiquement, si $t < n/2$ et $k = \Omega(s)$, la probabilité de reconstruction correcte est bornée par $2^{s - \Omega(k)}$.

3. Contributions clés et résultats

3.1 Bornes de computation

L'article établit que pour tout PIR à serveur unique avec prétraitement client faisant usage de la cryptographie boîte noire :

• Théorème 1.1 : Il est impossible d'atteindre à la fois une communication en ligne amortie de $o(n/s)$ et une opération cryptographique du serveur de $o(n/s)$.
• Implication : Tout schéma de ce type doit satisfaire au moins l'une des conditions suivantes :
  1. La communication en ligne amortie est de $\Omega(n/s)$ bits.
  2. Le serveur effectue $\Omega(n/s)$ opérations de bits cryptographiques.
• Optimalité : Cette borne est optimale. Les schémas existants (ex: [WR25]) atteignent $O(n/s)$ de communication sans opérations crypto du serveur, tandis que d'autres (ex: [ZPZS24]) atteignent $O(n/s)$ de communication sans opérations crypto du serveur mais nécessitent de rafraîchir l'état du client. La borne inférieure confirme qu'on ne peut pas contourner ces deux goulots d'étranglement simultanément.

3.2 Doubly Efficient PIR (DEPIR)

Les auteurs écartent l'existence de Doubly Efficient PIR (où le client et le serveur ont tous deux un temps sous-linéaire) construit à partir de la cryptographie boîte noire.

• Théorème 1.2 : Il n'existe pas de DEPIR à serveur unique avec une computation de requête sous-linéaire ($t = o(n)$) pour une seule requête, même si le serveur effectue un encodage arbitraire.
• Ce résultat s'applique au DEPIR à clé publique et améliore les résultats d'impossibilité antérieurs qui étaient restreints aux requêtes à un seul aller-retour avec des serveurs passifs.

3.3 Bornes de communication

L'article dérive des bornes de communication spécifiques pour des classes restreintes de PIR :

• Théorème 1.4 : Si un schéma de PIR satisfait l'une des conditions suivantes, il nécessite $\Omega(n/s)$ de communication amortie :
  1. Le serveur effectue $o(n/s)$ opérations cryptographiques.
  2. Les opérations cryptographiques du serveur dépendent uniquement du transcript de communication (usage de la crypto aveugle à la base de données).
  3. Le schéma offre une confidentialité parfaite dans un modèle idéalisé.

3.4 Symmetric PIR (SPIR)

L'article traite de la construction de la Symmetric PIR (SPIR) avec prétraitement client, où le client n'apprend que l'entrée requise.

• Construction (Théorème 1.5) : Les auteurs présentent une construction de SPIR avec prétraitement client qui repose uniquement sur les fonctions à sens unique (OWF) durant la phase de requête en ligne. Le schéma atteint $\tilde{O}(n/s)$ en communication et en computation, supportant $\tilde{O}(s)$ requêtes par phase hors ligne.
• Limitation (Théorème 1.6) : Dans le modèle de l'oracle aléatoire, aucun schéma SPIR de ce type ne peut supporter plus de $k > s$ requêtes par phase hors ligne. Cela contraste avec le PIR non symétrique, qui peut supporter un nombre illimité de requêtes en rafraîchissant l'état. Les auteurs prouvent que supporter $k > s$ requêtes nécessite la cryptographie à clé publique ou une communication linéaire.

3.5 Weak PIR

Les bornes inférieures s'étendent aux schémas de "Weak PIR" qui fournissent une confidentialité uniquement contre des adversaires effectuant un nombre polynomial de requêtes d'oracles cryptographiques (similaire aux puzzles de Merkle).

• Théorème 1.3 & 1.5 : Même pour des adversaires faibles, le temps de requête en ligne sous-linéaire est impossible pour le PIR à serveur unique avec prétraitement si les parties honnêtes et l'adversaire effectuent un nombre comparable de requêtes d'oracles.

4. Signification et affirmations

L'article affirme résoudre la question ouverte de l'efficacité maximale possible pour le PIR à serveur unique avec prétraitement sous les hypothèses de la cryptographie boîte noire.

• Résultats inconditionnels : Contrairement aux travaux antérieurs (ex: [ISW24]) qui reposaient sur des hypothèses de complexité (comme la séparation de SZK et BPP) ou restreignaient le modèle de requête (aveugle à la base de données, un seul aller-retour), ces bornes inférieures sont inconditionnelles et s'appliquent à une classe beaucoup plus large de schémas, incluant ceux avec plusieurs tours et des requêtes dépendant de la base de données.
• Optimalité des constructions actuelles : Les résultats valident que les constructions récentes atteignant $\tilde{O}(n/s)$ en communication ou en computation sont essentiellement optimales ; on ne peut pas minimiser simultanément la communication et la computation du serveur en dessous de ce seuil sans briser les hypothèses de la cryptographie boîte noire.
• Faisabilité du SPIR : Ce travail démontre que le Symmetric PIR est réalisable avec seulement des OWF dans la phase en ligne, à condition que le nombre de requêtes soit limité à la taille de l'état stocké par le client ($s$). Cela clarifie le compromis entre la symétrie (confidentialité des données) et la capacité de requête dans le modèle de prétraitement.
• Impossibilité du DEPIR : L'article écarte définitivement l'existence de DEPIR à clé publique avec une computation de requête sous-linéaire issue de la cryptographie boîte noire, réglant ainsi un problème ouvert important dans le domaine.

En résumé, l'article établit que les "goulots d'étranglement" identifiés dans les récentes constructions de PIR (soit une communication élevée, soit une computation serveur élevée) sont des limitations fondamentales inhérentes à la cryptographie boîte noire, et non de simples artefacts des techniques de construction actuelles.