💻 computer science

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

Questo articolo propone i "Search-Bound Proximity Proofs" (SBPP), un nuovo protocollo che colma il divario di provenienza nell'autorizzazione per i sistemi di ricerca geografica crittografata, permettendo l'audit forense delle prove di prossimità senza modificare i circuiti ZKP e con un overhead computazionale trascurabile.

Autori originali: Yoshiyuki Ootani

Pubblicato 2026-04-07

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Yoshiyuki Ootani

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Il Problema: "Il Colpo di Scena del Detective"

Immagina di essere in una città piena di scatole magiche (i "drop" o contenuti digitali) nascoste in punti specifici. Per trovare una scatola, devi chiedere al "Portiere" (il server) dove sono quelle vicine a te. Il Portiere ti dice: "Ehi, ce ne sono tre nel raggio di un chilometro".

Poi, per aprire la scatola, devi dimostrare al Portiere che sei davvero lì, vicino a quella specifica scatola, senza però dirgli esattamente dove ti trovi (per proteggere la tua privacy). Usi una prova magica (una "Zero-Knowledge Proof") che dice: "Credo di essere a meno di 100 metri da questa scatola, fidati della mia parola".

Il problema attuale:
Oggi, il Portiere e la Magia lavorano in due stanze separate.

Tu chiedi le scatole (Fase 1).
Tu mostri la prova magica (Fase 2).

Se il Portiere cancella la memoria di cosa hai chiesto nella Fase 1 (per risparmiare spazio), e tu mostri la prova magica nella Fase 2, nessuno potrà mai collegare le due cose.
È come se un ladro rubasse una chiave da un'auto parcheggiata ieri, la nascondesse, e poi domani la usasse per aprire un'altra auto. Se la polizia controlla solo la chiave e la serratura, non sa quale auto fosse quella originale. Un malintenzionato potrebbe prendere una prova valida generata per un'auto e attaccarla a un'altra, ingannando l'audit (il controllo forense).

La Soluzione: "Il Braccialetto Inseparabile" (SBPP)

Gli autori di questo studio (Yoshiyuki Ootani) hanno creato un sistema chiamato SBPP (Search-Bound Proximity Proofs). Immaginalo come un braccialetto di plastica sigillato che unisci al tuo corpo nel momento esatto in cui chiedi le informazioni.

Ecco come funziona, passo dopo passo, con un'analogia da "Festa in Casa":

1. L'Invito e il Braccialetto (La Sessione)

Quando entri nella festa (la ricerca), il portiere non ti dà solo una lista di stanze. Ti dà un braccialetto unico con un codice segreto (il Nonce) e un sigillo che elenca esattamente quali stanze sono aperte in quel momento (il Merkle Root).

L'innovazione: Questo braccialetto non è solo un pezzo di carta; è parte integrante del tuo "pass" per la prova magica.

2. La Prova Magica (Il ZKP)

Quando vuoi aprire una scatola, la tua prova magica non dice solo "Sono qui". Dice: "Sono qui, E ho questo braccialetto specifico, E questo braccialetto corrisponde esattamente alla lista di stanze che mi è stata data in quel preciso momento".
La prova magica "ingloba" il braccialetto dentro di sé. Non puoi separarli.

3. Il Controllo Forense (L'Audit)

Mesi dopo, arriva l'ispettore (l'auditor). Vuole sapere: "Chi ha aperto questa scatola e quando?".

Senza SBPP: L'ispettore guarda la prova magica. Vede che è valida, ma non sa a quale ricerca apparteneva. È come vedere una foto sfocata senza data.
Con SBPP: L'ispettore guarda la prova. Vede il codice del braccialetto e il sigillo della lista. Controlla il registro del portiere (che ora è un documento firmato e immutabile). Se il codice del braccialetto nella prova corrisponde a quello del registro, è una prova inconfutabile che quell'accesso è avvenuto in quel preciso momento e per quel preciso gruppo di opzioni.

Perché è geniale? (Le 3 Regole d'Oro)

Il paper definisce tre cose fondamentali che questo sistema garantisce:

Il Braccialetto è unico (P1): Non puoi prendere la prova di oggi e usarla domani con un braccialetto diverso. Se provi a staccare la prova dal suo contesto, la magia si rompe.
La lista è corretta (P2): Non puoi dire "Ho aperto la scatola X" se la scatola X non era nella lista che ti è stata data quel giorno. La prova contiene la "mappa" delle opzioni disponibili.
La firma del Portiere (P3): Anche se il Portiere cancella la sua memoria interna, ha lasciato una firma digitale sul registro. L'ispettore può verificare tutto anni dopo senza bisogno che il Portiere tenga i dati in memoria.

L'Attacco che hanno sventato

Gli autori hanno mostrato come, senza questo sistema, un hacker potrebbe fare un trucco chiamato "Re-association".
Immagina due persone, Alice e Bob.

Alice chiede le scatole vicino al parco e ottiene una prova.
Bob chiede le stesse scatole (stesso parco, stesso orario) e ottiene un'altra prova.
Un hacker ruba la prova di Alice e la "incolla" alla richiesta di Bob.
Senza SBPP, il sistema pensa: "Ok, la prova è valida, la richiesta è valida". Non si accorge che la prova non appartiene a quella specifica sessione.
Con SBPP: La prova di Alice contiene il "codice del braccialetto" di Alice. Quando Bob la usa, il sistema vede: "Ehi, questo braccialetto non corrisponde alla tua richiesta!". Blocco immediato.

In Sintesi

Questo lavoro risolve un problema invisibile ma pericoloso: come collegare una richiesta di ricerca a una prova di accesso in modo che nessuno possa barare, nemmeno dopo che i dati temporanei sono stati cancellati.

Non serve cambiare la "magia" (l'algoritmo crittografico) che usano i computer. Basta aggiungere un piccolo "collante" (il nonce e il sigillo della lista) che lega indissolubilmente la domanda alla risposta. È come mettere un timbro a secco su un documento: se provi a staccarlo, il documento si strappa.

Risultato pratico:

Sicurezza: Nessuno può attribuire un accesso alla persona sbagliata o al momento sbagliato.
Privacy: Il server non sa dove sei esattamente, ma sa che hai accesso legittimo.
Velocità: È così veloce che l'utente non se ne accorge nemmeno (meno di un millisecondo in più rispetto al normale).

È un po' come passare dall'avere una chiave che apre qualsiasi porta (se hai la chiave giusta) all'avere una chiave che apre solo quella porta, solo in quel momento, e che lascia una traccia indelebile sul muro che dice esattamente chi l'ha usata e quando.

1. Il Problema: Il "Gap" di Provenienza dell'Autenticazione

Il paper affronta una lacuna critica nei sistemi basati sulla posizione (LBS) che combinano ricerca geografica crittografata (per proteggere la privacy dell'utente durante la scoperta dei contenuti) con prove di prossimità a conoscenza zero (ZKP) (per verificare la posizione senza rivelare coordinate esatte).

Il Contesto: Attualmente, la fase di "scoperta" (ricerca di contenuti vicini) e la fase di "verifica" (sblocco del contenuto tramite ZKP) sono disaccoppiate. La ricerca usa token crittografati, mentre la verifica usa una prova ZKP (es. Groth16).
La Lacuna (Search-Verify Gap): Una volta che lo stato della sessione sul server viene eliminato (purged), non esiste alcun meccanismo forense per collegare una prova ZKP alla specifica sessione di ricerca che l'ha autorizzata. Le input pubbliche della prova non contengono informazioni identificative della sessione.
La Minaccia: In un modello di server "honest-but-curious" (che segue il protocollo ma è curioso di analizzare i dati), un avversario può eseguire un attacco di riassegnazione dell'audit. Un avversario può prendere una prova valida generata in una sessione $S_1$ e riassociarla a una sessione $S_2$ (o a un token di autorizzazione diverso), creando un registro di audit fuorviante che attribuisce erroneamente l'accesso a un utente o a un contesto diverso. Le soluzioni basate su log esterni o token firmati separati dalla prova non sono sufficienti perché la prova stessa rimane "agnostica" rispetto alla sessione.

2. Metodologia e Proposta: SBPP

Gli autori formalizzano il problema come il concetto di sicurezza Search-Authorized Proof (SAP) e propongono una soluzione chiamata Search-Bound Proximity Proofs (SBPP).

Concetti Chiave di SBPP

SBPP risolve il problema vincolando la prova ZKP alla sessione di ricerca all'interno della prova stessa, senza modificare il circuito ZKP esistente. La metodologia si basa su tre componenti crittografici decomposti:

Nonce di Sessione (P1): Un valore casuale crittografico generato dal server all'inizio della sessione.
Commitment del Risultato (P2): La radice di un albero di Merkle (Merkle root) calcolata sui risultati della ricerca (gli ID dei "drop" trovati).
Ricevuta Firmata (P3): Una ricevuta firmata digitalmente dal server che attesta il contesto (nonce, radice, ecc.).

Funzionamento del Protocollo

Sessione e Ricerca: Il client avvia una sessione e invia token di ricerca crittografati. Il server restituisce gli ID dei drop candidati e calcola la radice di Merkle del set di risultati.
Generazione della Prova: Il client calcola un digest di sfida (challenge digest) che include:
- L'ID del drop selezionato.
- Il nonce della sessione ( $N$ ).
- La radice di Merkle del set di risultati ($root(R)$).
- Altri metadati (versione policy, epoca).
  Questo digest viene inserito come input pubblico nel circuito ZKP (Groth16).
Verifica e Audit:
- Online: Il server verifica che il digest nella prova corrisponda al nonce e alla radice memorizzati nella sessione corrente.
- Offline (Audit): Dopo la cancellazione dello stato della sessione, un auditor può verificare la provenienza utilizzando la prova ZKP, il percorso di appartenenza Merkle e la ricevuta firmata. Poiché il digest è vincolato alla prova ZKP, non è possibile riassociare la prova a un contesto diverso senza violare la sicurezza della funzione hash o della firma.

3. Contributi Chiave

Definizione SAP (Search-Authorized Proof): Formalizzazione di tre proprietà di sicurezza:
- P1 (Binding dell'autorizzazione): Una prova valida per una sessione non può essere accettata in un'altra.
- P2 (Correttezza del set di risultati): Una prova non può essere accettata se il contenuto non era nel set di risultati autorizzati.
- P3 (Provenienza dell'audit): Impossibilità di creare registri di audit fuorvianti dopo la cancellazione dello stato.
Attacco di Riassegnazione dell'Audit: Dimostrazione pratica che i meccanismi di autorizzazione "esterni" alla prova (proof-external) falliscono nel prevenire la riassegnazione quando gli stessi parametri di ricerca si ripetono in sessioni diverse.
Implementazione SBPP: Una realizzazione pratica che non richiede modifiche al circuito ZKP (mantenendo i 474 vincoli di Groth16), utilizzando invece un vincolo basato su digest.
Isolamento dei Guasti a Livello di Proprietà: A differenza di soluzioni che usano un hash opaco di un token (che nasconde tutti i dettagli), SBPP permette di isolare esattamente quale componente ha fallito in un audit (es. mismatch del nonce vs. violazione della radice Merkle vs. firma invalida).

4. Risultati Sperimentali

Gli autori hanno valutato SBPP su dati sintetici e reali (110.776 POI di OpenStreetMap a Tokyo).

Sicurezza:
- SBPP blocca il 100% degli attacchi di riassegnazione (A2) e di provenienza dell'audit (A4b), a differenza delle soluzioni naive o basate su token esterni che falliscono in questi scenari.
- Le prove ZKP rimangono session-specific: un tentativo di riutilizzare una prova in un'altra sessione viene rifiutato con probabilità trascurabile.
Performance:
- Overhead: L'overhead del percorso del protocollo (gestione sessione, calcolo digest) è di circa 27 µs (media) rispetto a GridSE, un aumento del 7%.
- Latenza Totale: Su dispositivi mobili, la generazione della prova ZKP (dominante) richiede 42-125 ms. L'overhead totale di SBPP su questo baseline è inferiore allo 0,03%.
- Scalabilità: La verifica offline e la gestione dello stato del server (modalità "Compact") richiedono spazio O(1) (solo la radice di Merkle), indipendentemente dalla dimensione del set di risultati.
Audit Offline: È possibile verificare la provenienza dell'autorizzazione anche dopo la cancellazione dello stato della sessione, utilizzando solo la prova, il percorso Merkle e la ricevuta firmata.

5. Significato e Impatto

Il lavoro di Ootani è significativo perché:

Chiude il Gap Forense: Risolve il problema fondamentale di tracciabilità nei sistemi LBS privacy-preserving, permettendo audit conformi (es. per controlli di accesso geofenced) senza sacrificare la privacy dell'utente durante la ricerca.
Efficienza Pratica: Dimostra che un vincolo crittografico forte tra ricerca e verifica può essere implementato con un overhead computazionale trascurabile e senza modificare i circuiti ZKP complessi già esistenti.
Nuovo Modello di Sicurezza: Introduce il concetto di "Search-Authorized Proof", spostando l'attenzione dalla sola privacy della ricerca alla provenienza dell'autorizzazione, un aspetto cruciale per la responsabilità (accountability) nei sistemi distribuiti.
Distinzione dai Limiti: Il paper chiarisce onestamente cosa SBPP non fa (non protegge dai pattern di accesso SSE, non previene lo spoofing della posizione, non garantisce che il server sia onesto nella selezione dei risultati), definendo chiaramente i confini del suo contributo.

In sintesi, SBPP fornisce un ponte crittografico robusto tra la fase di scoperta dei dati e la fase di verifica dell'identità/posizione, rendendo i sistemi di contenuti basati sulla posizione sia privati che auditabili in modo forense.