💻 computer science

Search-Bound Proximity Proofs: Binding Encrypted Geographic Search to Zero-Knowledge Verification

Cet article propose les Preuves de Proximité Liées à la Recherche (SBPP), un protocole qui comble la lacune de traçabilité entre les recherches géographiques chiffrées et les preuves à connaissance nulle en intégrant des métadonnées de session vérifiables sans alourdir le circuit cryptographique, permettant ainsi une attribution forensique fiable avec une surcharge négligeable.

Auteurs originaux : Yoshiyuki Ootani

Publié 2026-04-07

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yoshiyuki Ootani

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

🌍 Le Problème : Le "Trou de Mémoire" des Applications de Localisation

Imaginez une application de réalité augmentée (comme Pokémon GO ou une application de tourisme) qui vous permet de débloquer des trésors numériques cachés dans votre ville.

Le processus se déroule en deux étapes :

La Recherche (Le Détective) : Votre téléphone demande à un serveur : "Y a-t-il un trésor à moins de 1 km de moi ?" Le serveur répond : "Oui, il y en a un à la Tour Eiffel."
La Vérification (Le Gardien) : Vous devez prouver que vous êtes réellement devant la Tour Eiffel pour obtenir le trésor, sans révéler votre position exacte au serveur (pour votre vie privée). Vous utilisez une preuve mathématique magique (une "Preuve à Connaissance Nulle" ou ZKP) qui dit : "Je suis à moins de 10 mètres du but, croyez-moi sur parole."

Le problème actuel :
Ces deux étapes sont comme deux pièces séparées d'une maison. Une fois que vous avez fini la recherche, le serveur oublie tout (il "vide sa mémoire"). Plus tard, si un auditeur veut vérifier qui a obtenu quel trésor et quand, il regarde la preuve mathématique. Mais cette preuve ne contient aucune information sur la recherche initiale.

C'est comme si vous aviez un ticket de cinéma (la preuve) qui dit "Entrée autorisée", mais qui ne mentionne ni la date, ni le film, ni votre nom. Un malin pourrait voler ce ticket, le coller sur un autre film, et dire : "J'ai vu ce film-là à cette heure-là !" Le serveur ne peut pas le prouver car il n'a plus la trace de la recherche originale. C'est ce que les auteurs appellent le "trou de l'origine de l'autorisation".

🛠️ La Solution : SBPP (La Preuve "Collée" à la Recherche)

Les chercheurs (Yoshiyuki Ootani) proposent une nouvelle méthode appelée SBPP (Search-Bound Proximity Proofs). L'idée est de "coller" la preuve mathématique à la recherche initiale de manière indissociable.

Voici comment ils font, avec une analogie simple :

1. Le Code Secret Unique (Le Nonce)

Lorsque vous lancez une recherche, le serveur vous donne un code secret unique (comme un numéro de série de billet de loterie) qui n'existe que pour cette recherche précise.

Avant : Votre preuve mathématique ne contenait pas ce code.
Maintenant : Vous devez insérer ce code dans la preuve mathématique elle-même.
Résultat : Si quelqu'un essaie d'utiliser une preuve d'hier pour une recherche d'aujourd'hui, le code ne correspondra pas. La preuve devient invalide. C'est comme si votre billet de cinéma avait votre photo et l'heure exacte imprimés dessus.

2. L'Arbre de la Liste (La Racine Merkle)

Le serveur vous donne une liste de trésors possibles (par exemple : 50 trésors dans le quartier).

Avant : Le serveur gardait cette liste en mémoire. Une fois la liste effacée, on ne pouvait plus vérifier si le trésor que vous avez débloqué faisait partie de la liste originale.
Maintenant : Le serveur crée une "empreinte digitale" mathématique de toute la liste (une racine d'arbre Merkle) et l'insère aussi dans votre preuve.
Résultat : Même si le serveur a effacé la liste, l'auditeur peut vérifier plus tard : "Ah, cette preuve contient l'empreinte de la liste du 12 avril. Et ce trésor spécifique est bien dans cette liste." C'est comme avoir un cachet officiel sur la liste complète des invités, même si la liste papier a été jetée.

3. Le Cachet de la Poste (Le Reçu Signé)

Enfin, le serveur vous donne un reçu signé numériquement qui atteste : "J'ai bien généré cette liste et ce code secret pour cette session."

Résultat : Même des mois plus tard, un auditeur peut prendre votre preuve, regarder le reçu, et dire : "C'est authentique. Ce trésor a bien été autorisé lors de cette recherche précise."

🕵️‍♂️ Pourquoi c'est génial ? (Les Bénéfices)

Imaginez que vous êtes un inspecteur de police (l'auditeur) qui doit enquêter sur une fraude dans ce système.

Sans SBPP : Vous voyez une preuve valide. Vous ne savez pas si elle a été utilisée pour la recherche A ou la recherche B. Vous ne pouvez pas prouver qui a triché. C'est le chaos.
Avec SBPP : Vous regardez la preuve.
- Si le code secret ne correspond pas à la date de la recherche -> Fraude détectée ! (Quelqu'un a réutilisé une vieille preuve).
- Si le trésor n'est pas dans la liste "empreinte digitale" -> Fraude détectée ! (Quelqu'un a inventé un trésor qui n'existait pas).
- Si le cachet du serveur est faux -> Fraude détectée !

⚡ Est-ce que ça ralentit tout ?

C'est la question cruciale. Ajouter ces vérifications mathématiques prend du temps.
Les chercheurs ont testé leur système sur des données réelles (plus de 110 000 lieux à Tokyo).

Le résultat : L'ajout de cette sécurité ne prend que 0,03 millisecondes de plus par rapport au système de base.
L'analogie : C'est comme ajouter une étiquette de sécurité sur un colis. Cela prend une fraction de seconde, mais cela garantit que le colis n'a pas été ouvert en cours de route. Pour l'utilisateur, c'est imperceptible (le temps de charger la preuve mathématique elle-même est de 125 ms, l'ajout est négligeable).

🎯 En résumé

Ce papier résout un problème invisible mais dangereux : comment prouver, des mois plus tard, qu'une preuve de localisation a bien été autorisée par une recherche spécifique, même si le serveur a tout oublié ?

La réponse est de transformer la preuve en un document juridique indissociable qui contient en son cœur les codes de la recherche, la liste des options autorisées et le cachet du serveur. Cela permet de faire de la "police scientifique" (audit forensique) sur des applications de géolocalisation, sans ralentir les utilisateurs et sans révéler leur position exacte.

1. Problématique : Le fossé de la provenance d'autorisation

L'article identifie une faille critique dans les systèmes de contenu géolocalisé (LBS) qui combinent une recherche géographique cryptée (pour protéger la vie privée de l'utilisateur lors de la découverte de contenu) et des preuves de proximité à connaissance nulle (ZKP) (pour prouver la présence physique sans révéler les coordonnées exactes).

Le contexte : Ces systèmes fonctionnent en deux phases découplées :
1. Découverte : Le client interroge le serveur pour trouver du contenu nearby (souvent via des requêtes cryptées comme GridSE).
2. Vérification : Le client génère une preuve ZKP (ex: Groth16) pour prouver qu'il est à proximité d'un objet spécifique et le déverrouiller.
Le problème (Le "Search-Verify Gap") : Dans les déploiements actuels, ces deux phases sont indépendantes. Une fois l'état de la session côté serveur effacé (pour des raisons de confidentialité ou de gestion de ressources), il est impossible d'attribuer de manière forensique une preuve ZKP à la session de recherche qui l'a autorisée.
La conséquence : Un adversaire peut intercepter une preuve valide générée lors d'une session $S_1$ et la réassocier à une session différente $S_2$ (ou à un audit ultérieur). Cela crée un fossé de provenance d'autorisation : un auditeur ne peut pas vérifier cryptographiquement si la preuve correspondait bien à la recherche initiale autorisée, rendant les audits de conformité (ex: contrôle d'accès géofencé) vulnérables à la falsification.

2. Méthodologie et Proposition : SBPP

Les auteurs formalisent ce problème sous le nom de SAP (Search-Authorized Proof) et proposent une solution appelée SBPP (Search-Bound Proximity Proofs).

A. Le Concept SAP

Ils définissent trois propriétés de sécurité essentielles pour combler ce fossé :

P1 (Liaison d'autorisation) : Une preuve valide pour une session $S$ ne doit pas être acceptée pour une session $S' \neq S$ .
P2 (Justesse de l'ensemble de résultats) : Une preuve ne doit pas être acceptée si l'objet déverrouillé ne faisait pas partie de l'ensemble des résultats autorisés pour cette session.
P3 (Provenance d'autorisation) : Même après la purge de l'état serveur, un auditeur doit pouvoir vérifier, via un enregistrement d'audit, que la preuve a été générée dans le contexte d'autorisation correct.

B. L'Attaque de Réassociation (Audit Re-Association)

Les auteurs démontrent que les mécanismes d'autorisation "externes" (où le jeton d'autorisation est vérifié à côté de la preuve mais pas dans celle-ci) sont vulnérables. Si les mêmes paramètres de contenu (ex: un "drop" spécifique) apparaissent dans plusieurs sessions, un attaquant peut prendre une preuve de la session 1 et l'associer au jeton d'autorisation de la session 2. Comme la preuve ZKP ne contient pas d'information d'identification de session, la vérification échoue à détecter cette substitution.

C. La Solution SBPP

SBPP résout ce problème en intégrant les éléments de contexte de la recherche directement dans la preuve ZKP via ses entrées publiques, sans modifier le circuit cryptographique sous-jacent.

Le protocole SBPP décompose le contexte d'autorisation en trois composants indépendants :

Nonce de session ( $N$ ) : Un nombre aléatoire unique généré par le serveur pour chaque session de recherche. Il est inclus dans le "digest de défi" de la preuve. Cela assure la propriété P1.
Racine Merkle ($root(R)$) : Le serveur construit un arbre de Merkle sur l'ensemble des résultats de recherche ( $R$ ) et ne stocke que la racine. Le client inclut cette racine dans le digest de la preuve et fournit une preuve d'appartenance (Merkle path) pour l'objet spécifique. Cela assure la propriété P2 et permet la vérification hors ligne.
Reçu signé ( $\rho$ ) : Le serveur signe les métadonnées de la session (nonce, racine Merkle, etc.) après la recherche. Ce reçu permet la vérification P3 (provenance) même après la suppression de l'état serveur, car l'auditeur peut reconstituer le contexte à partir du reçu et de la preuve.

Avantage clé : SBPP n'ajoute aucune contrainte au circuit ZKP existant (ex: Groth16). Il utilise simplement un mécanisme de liaison par hachage (digest) qui lie le nonce et la racine Merkle aux entrées publiques de la preuve.

3. Contributions Clés

Définition formelle (SAP) : Introduction de la notion de sécurité "Search-Authorized Proof" et identification de six classes d'attaques, dont la réassociation d'audit (A4b).
Preuve de vulnérabilité : Démonstration qu'une autorisation externe (hors preuve) est insuffisante pour garantir la provenance forensique, même avec des jetons signés, tant que la preuve elle-même n'est pas liée à la session.
Implémentation SBPP : Une réalisation pratique qui décompose l'audit en composants vérifiables indépendamment (Nonce, Racine Merkle, Reçu), permettant une isolation des pannes au niveau des propriétés.
Évaluation complète : Analyse sur des données synthétiques et réelles (110 776 POI OpenStreetMap) et sur des appareils mobiles.

4. Résultats Expérimentaux

Les auteurs ont évalué SBPP sur une implémentation basée sur le système Zairn (utilisant Groth16 et BN128).

Performance (Latence) :
- L'ajout de SBPP au protocole de recherche GridSE n'entraîne qu'une surcharge négligeable : environ 27 µs (médiane) pour la gestion de session et le calcul du digest.
- Par rapport à une base de temps de 125 ms pour la génération de la preuve ZKP (sur mobile), la surcharge totale est inférieure à 0,03 %.
- La génération de preuve sur mobile (iPhone 16 Pro) prend environ 42 ms (chaud), et 125 ms sur Android (POCO X7 Pro).
Sécurité et Résistance aux Attaques :
- SBPP bloque efficacement toutes les classes d'attaques, y compris la réassociation de session (A2) et l'évasion de l'ensemble de résultats (A4b), là où les solutions naïves (V1-V7) échouent.
- L'audit hors ligne fonctionne parfaitement : même après la purge de l'état serveur, un auditeur peut re-vérifier la preuve en utilisant le reçu signé et la preuve d'appartenance Merkle.
Isolation des Pannes :
- Contrairement à une approche "hash opaque" (V8) où une erreur de hachage ne permet pas de savoir quelle propriété est violée, SBPP permet de localiser précisément la faille :
  - Mismatch de Nonce = Réassociation de session.
  - Échec de la preuve Merkle = Évasion de l'ensemble de résultats.
  - Échec de la signature = Contexte falsifié.
Évolutivité :
- La taille de l'état serveur en mode "Compact" (Full SBPP) est constante ( $O(1)$ ), ne stockant que la racine Merkle, indépendamment du nombre de résultats.
- La construction de l'arbre Merkle pour 50 000 points prend environ 54 ms.

5. Signification et Impact

Ce travail est significatif car il résout un problème fondamental de chaîne de confiance dans les systèmes de localisation privés.

Conformité et Audit : SBPP rend possible l'audit forensique de systèmes géolocalisés sensibles (ex: accès à des médias restreints par géofencing, contrôles d'accès sécurisés) sans compromettre la vie privée des utilisateurs ni la confidentialité des requêtes de recherche.
Architecture Modulaire : En démontrant que la liaison entre la recherche et la preuve peut être faite sans modifier les circuits ZKP complexes, SBPP offre une voie de mise en œuvre pratique pour les systèmes existants.
Limites et Perspectives : L'article précise que SBPP suppose un serveur "honnête mais curieux" (Honest-But-Curious). Il ne protège pas contre un serveur malveillant qui omettrait des résultats ou signerait des racines biaisées (ce qui nécessiterait un traitement de requête vérifiable). De plus, il ne masque pas les fuites de motifs d'accès (access pattern leakage) inhérentes aux systèmes de recherche cryptée (SSE).

En résumé, SBPP comble le fossé entre la découverte cryptée et la vérification cryptographique, garantissant que chaque preuve de proximité est indissociable de la session de recherche qui l'a autorisée, même après la disparition des données temporaires.