💻 computer science

Pivot: Proactive and Verifiable Threshold Oblivious Pseudorandom Functions From Isogeny Group Actions

Questo articolo introduce PIVOT, un framework di funzione pseudo-casuale soglia proattiva, verificabile e senza dealer basato su azioni di gruppi isogenici che aggiorna in modo sicuro le quote dei server nel tempo per difendersi da avversari mobili, mantenendo al contempo la validità della chiave master e degli output precedenti.

Autori originali: Abhinav Sharma, Vikas Srivastava

Pubblicato 2026-08-04

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Abhinav Sharma, Vikas Srivastava

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

Immagina di cercare di custodire un segreto così prezioso che nessun singolo individuo dovrebbe mai conoscerlo interamente. Dividi il segreto in pezzi di un puzzle e dai un pezzo a ciascuno dei tuoi amici. Questa è l'idea di base della crittografia a soglia (threshold cryptography): hai bisogno di un certo numero di amici (per esempio, 5 su 10) per mettere insieme i loro pezzi e sbloccare il tesoro. Ma c'è un problema subdolo. Se un ladro riesce a intrufolarsi nelle case dei tuoi amici uno alla volta nel corso di un anno, rubando un pezzo dall'Amico A a gennaio, un pezzo dall'Amico B a febbraio, e così via, può eventualmente raccogliere tutti i pezzi necessari per risolvere il puzzle, anche se non ha mai avuto cinque amici contemporaneamente. Questo è chiamato un "avversario mobile" (mobile adversary).

Per fermare questo, i crittografi usano un trucco chiamato sicurezza proattiva (proactive security). Immagina che ogni mese i tuoi amici scambino segretamente i loro pezzi di puzzle con nuovi pezzi che si adattano alla stessa immagine, ma che i vecchi pezzi diventino pezzi di carta straccia inutili. Se un ladro ruba un pezzo oggi, non corrisponderà ai pezzi rubati il mese prossimo. Il segreto rimane al sicuro perché il ladro non può mescolare i vecchi pezzi con quelli nuovi. Ora, aggiungi un colpo di scena: vuoi usare questo segreto per rispondere a delle domande senza mai rivelare il segreto stesso. Questo è una Funzione Pseudocasuale Obliviosa (OPRF). È come un distributore automatico magico: inserisci un codice segreto (come una password) e lui ti restituisce una ricevuta unica e dall'aspetto casuale. La macchina conosce la ricetta segreta, ma non vede mai il tuo codice, e tu non apprendi mai la ricetta. La sfida che questo articolo affronta è costruire una versione "post-quantistica" di questo sistema — uno che sia sicuro anche contro i futuri supercomputer — pur mantenendo il segreto al sicuro dai ladri che cercano di rubare i pezzi nel tempo.

L'articolo introduce un nuovo sistema chiamato PIVOT (Proactive Isogeny-based Verifiable Oblivious Threshold PRF). Pensa a PIVOT come a una cassaforte post-quantistica ad alta tecnologia che utilizza un tipo speciale di magia matematica chiamata azioni di gruppo isogeniche (isogeny group actions). In termini semplici, immagina un enorme parco giochi circolare dove puoi girare su te stesso. Se giri un certo numero di volte (il segreto), finisci in un punto specifico. La magia è che puoi girare in piccoli passi con persone diverse e, finché tutti girate il numero totale corretto di giri, finirete nello stesso punto, anche se nessuno conosce il numero totale di giri. PIVOT usa questo per permettere a un gruppo di server di lavorare insieme per fornire a un client una "ricevuta" per il suo input segreto, senza che il client veda mai il segreto dei server o i server vedano l'input del client.

Gli autori dimostrano che PIVOT risolve il problema dell' "avversario mobile". Dimostrano che i server possono aggiornare periodicamente i loro pezzi di puzzle (share) senza cambiare il segreto principale o la "serratura" pubblica della cassaforte. Ciò significa che anche se un ladro ruba un pezzo oggi, quel pezzo diventerà inutile il mese prossimo quando i pezzi verranno aggiornati. L'articolo dimostra anche che il sistema è verificabile: il client può controllare che i server abbiano eseguito correttamente i calcoli e non abbiano deviato dal protocollo e, se un server sbaglia, il sistema può individuare esattamente quale sia e scacciarlo.

L'articolo esclude esplicitamente l'idea di poter conservare gli stessi pezzi del puzzle per sempre. Argomenta che se i pezzi non cambiano, un ladro mobile alla fine vincerà. Argomenta anche contro i design che nascondono i contributi dei singoli server dietro un server "virtuale", perché PIVOT vuole rendere visibile e conto ogni contributo dei server. Gli autori sono molto sicuri dei loro risultati; non si sono limitati a indovinare o a simulare il sistema in modo semplice. Hanno fornito una prova matematica rigorosa che mostra come il sistema funzioni correttamente e rimanga sicuro contro un tipo specifico di attaccante (un attaccante "semi-onesto" che segue le regole ma cerca di apprendere i segreti) sotto le assunzioni standard sulla difficoltà di risolvere questi enigmi isogenici.

Nel mondo reale, questo potrebbe essere utilizzato per cose come l'accesso privato alle password o database criptati che rimangano sicuri per decenni. Se un'azienda deve proteggere i dati degli utenti per un lungo periodo, non può semplicemente fare affidamento su un segreto statico che potrebbe essere rubato pezzo dopo pezzo. PIVOT permette loro di ruotare il proprio personale di sicurezza (i server) e aggiornare regolarmente le proprie chiavi, garantendo che il database rimanga bloccato e la privacy degli utenti rimanga intatta, anche se il sistema è sotto un attacco costante e lento. L'articolo conclude che, sebbene questo sistema sia un po' più complesso e lento rispetto alle versioni più semplici (perché richiede una catena di server che si passano la "palla" dei dati uno dopo l'altro), il compromesso vale la pena per la sicurezza a lungo termine e la capacità di dimostrare che nessuno ha deviato dal protocollo.

Sintesi Tecnica: PIVOT – Funzioni Pseudocasuali Oblivous Proattive e Verificabili da Azioni di Gruppo Isogenico

1. Definizione del Problem

Le Funzioni Pseudocasuali Oblivious (OPRF) permettono a un client di valutare una funzione chiave su un input privato senza rivelare l'input al server. In una OPRF a soglia (threshold OPRF), la chiave segreta è distribuita tra $n$ server, richiedendo che almeno $t$ server cooperino per la valutazione. Mentre gli schemi a soglia standard proteggono contro la corruzione statica (dove un set fisso di server viene compromesso), essi falliscono contro un avversario mobile. In un modello di minaccia mobile, un attaccante può compromettere diversi server nel tempo, accumulando quote da diverse epoche. Se le quote rimangono statiche, l'avversario può eventualmente raccogliere $t$ quote dallo stesso stato di condivisione e ricostruire la chiave master, anche se non controlla mai $t$ server simultaneamente.

Le esistenti OPRF a soglia basate su isogenie sono progettate principalmente per modelli di corruzione statica. Inoltre, i meccanismi esistenti di condivisione proattiva dei segreti nei gruppi classici non si traducono facilmente nel contesto isogenico a causa della necessità di collegare gli impegni polinomiali (nel campo scalare) con le azioni di gruppo isogenico (sulle curve ellittiche). Manca una costruzione che offra simultaneamente:

Sicurezza post-quantistica (basata su isogenie).
Verificabilità (garantire che i server valutino sotto la chiave corretta).
Sicurezza proattiva (aggiornamento periodico delle quote per contrastare gli avversari mobili).
Generazione della chiave senza dealer (senza setup fidato).
Migrazione del comitato (cambiare il set di server o la soglia senza ri-criptare i dati applicativi).

2. Metodologia e Costruzione

Il documento introduce PIVOT (Proactive Isogeny-based Verifiable Oblivious Threshold PRF), un framework costruito su azioni di gruppo isogenico efficaci (ad es. CSIDH). La struttura algebrica centrale si basa sulla proprietà commutativa delle azioni isogeniche: $[a]([b]E) = [a+b]E$ .

Architettura Core

PIVOT mantiene una singola chiave master a lungo termine $k$ e una chiave pubblica $pk = [k]E_0$ . Tuttavia, la rappresentazione di $k$ cambia nel tempo. Il sistema opera in epoche. In un'epoca $e$ , i server detengono le quote $s^{(e)}_i = F_e(i)$ di un polinomio di Shamir $F_e(X)$ dove $F_e(0) = k$ . Il vettore di impegno dei coefficienti pubblici $A^{(e)}$ certifica il polinomio $F_e$ .

Il protocollo consiste in cinque procedure principali:

Generazione della Chiave Distribuita senza Dealer (DKG):
- Ogni server agisce come un dealer di Verifiable Secret Sharing (VSS), campionando un polinomio casuale e distribuendo le quote.
- I contributi qualificati vengono aggregati per formare il polinomio master iniziale $F_0(X) = \sum f_j(X)$ .
- Link Proofs: Un'innovazione critica è l'uso di prove Non-Interactive Zero-Knowledge (NIZK) per collegare il termine costante del polinomio impegnato (la quota scalare) all'esponente usato nella catena sequenziale di azioni isogeniche che genera la chiave pubblica $pk$. Ciò assicura che la chiave pubblica corrisponda al segreto condiviso senza ricostruire $k$ .
Valutazione a Soglia:
- Il client oscura il proprio input $x$ mappandolo in una curva $X = H_1(ctx \| x)$ e applicando un'azione casuale $[r]$ , inviando $B = [r]X$ .
- Un quorum di $t$ server applica le loro quote pesate da Lagrange sequenzialmente: $Q_h = [\lambda^I_{i_h} s^{(e)}_{i_h}] Q_{h-1}$ .
- Grazie alla proprietà additiva dell'azione, la curva finale è $Q_t = [k]B$ .
- Il client de-oscura per ottenere $Y = [k]X$ e deriva l'output.
- Verifica: Ogni server fornisce una prova NIZK ( $\pi_{eval}$ ) che certifica che l'azione eseguita corrisponde alla quota impegnata nel vettore pubblico $A^{(e)}$ dell'epoca corrente.
Aggiornamento Proattivo delle Quote (Share Refresh):
- Per contrastare gli avversari mobili, i server aggiornano periodicamente le quote senza cambiare $k$ .
- I "dealer di aggiornamento" qualificati campionano polinomi a quota zero $z_j(X)$ dove $z_j(0)=0$ .
- Il nuovo polinomio è $F_{e+1}(X) = F_e(X) + \sum z_j(X)$ . Poiché i termini costanti sommano a zero, $F_{e+1}(0) = k$ .
- Gli impegni dei coefficienti vengono aggiornati in modo omomorfico. Le vecchie quote vengono eliminate in modo sicuro dopo la transizione.
Verifica, Blame e Restart Robusto:
- Se un server sottomette una prova o una quota malformata, la parte che lo rileva genera un certificato di blame (una trascrizione firmata del fallimento).
- Il server accusato viene rimosso e il protocollo viene riavviato con un nuovo quorum. Ciò garantisce aborti identificabili.
Resharing del Comitato:
- Permette la migrazione a un nuovo set di server o a una nuova soglia $t'$ .
- Un vecchio quorum tratta le proprie quote pesate da Lagrange come termini costanti per i nuovi polinomi distribuiti al nuovo comitato.
- Crucialmente, questo trasferisce il segreto $k$ senza ricostruirlo, preservando la chiave pubblica e tutti gli output OPRF precedentemente generati.

Sfide Tecniche Affrontate

Consistenza della Testimone Cross-Domain: Il documento formalizza la necessità di relazioni NP congiunte (ad es. $R_{link}, R_{eval}$ ) che leghino uno scalare impegnato nel campo allo stesso scalare usato nell'azione isogenica. Provare questi elementi separatamente è insufficiente; la testimone (witness) deve essere identica attraverso i domini.
Consistenza dell'Epoca: Il protocollo impone che le catene di valutazione utilizzino quote da un singolo certificato di epoca per evitare la miscelazione di quote da polinomi diversi.

3. Contributi Chiave

Funzionalità Formale: Gli autori definiscono una funzionalità ideale $\mathcal{F}_{pTVOPRF}$ per una VOPRF a soglia proattiva a lungo termine, modellando esplicitamente avversari mobili che possono cambiare il set di server corrotti tra le epoche.
Costruzione senza Dealer: Una costruzione che combina azioni di gruppo isogenico efficaci con la condivisione segreta di Shamir e impegni additivamente omomorfi, dove la chiave master non viene mai ricostruata da una singola parte.
Manutenzione Proattiva: Un meccanismo per rinnovare le quote dei server contro gli avversari mobili preservando la chiave master, la chiave pubblica e tutti gli output OPRF storici. Questo include un protocollo di transizione di epoca coordinato.
Relazioni NP Congiunte: L'identificazione e la formalizzazione di specifiche relazioni NIZK necessarie per collegare il dominio della condivisione del segreto (coefficienti polinomiali) con il dominio dell'azione isogenica (trasformazioni di curve).
Resharing del Comitato: Un protocollo per migrare il segreto a un nuovo comitato o cambiare la soglia senza invalidare i database criptati esistenti indicizzati dagli output OPRF.
Analisi di Sicurezza: Una prova di sicurezza basata su simulazione nel modello dell'oracolo casuale sotto le assunzioni di vettorizzazione e one-more hidden-group-action, provando la privacy dell'input e la segretezza della chiave contro avversari semi-onesti mobili.

4. Risultati e Performance

Correttezza: Il documento prova che il protocollo mantiene l'invariante per cui la chiave master $k$ e la chiave pubblica $pk$ rimangono costanti attraverso le operazioni di DKG, valutazione, aggiornamento e resharing.
Sicurezza: La costruzione è provata sicura contro un avversario semi-onesto mobile che corrompe meno di $t$ server in una singola epoca. La sicurezza si basa sulla cancellazione sicura delle vecchie quote e sulla privacy informazionale della condivisione di Shamir.
Trade-off di Efficienza:
- Dimensione della Trascrizione: A differenza degli approcci a server virtuali basati su MPC che offrono trascrizioni client di dimensione costante, PIVOT ha una trascrizione client di $O(t)$ perché espone la catena sequenziale di $t$ valutazioni parziali e prove.
- Latenza: La valutazione richiede $t$ azioni di gruppo e prove sequenziali, creando un collo di bottiglia di latenza lineare rispetto alla soglia.
- Manutenzione: L'aggiornamento proattivo e il resharing del comitato comportano una comunicazione $O(n^2)$ (a causa della distribuzione delle quote punto-a-punto) ma non richiedono azioni isogeniche, rendendoli adatti per l'ammortamento su lunghi periodi.
- Applicazioni: Il documento evidenzia che, sebbene il costo online sia più elevato, la capacità di aggiornare le quote e migrare i comitati senza ri-criptare grandi database (ad es. nei servizi di lookup privati) fornisce un'efficienza operativa significativa per servizi a lungo termine.

5. Significato e Rivendicazioni

Il documento afferma di presentare la prima VOPRF a soglia da azioni di gruppo isogenico che fornisce sicurezza proattiva contro un avversario mobile.

Gli autori posizionano PIVOT non come un'ottimizzazione delle prestazioni rispetto alle esistenti OPRF a singolo server o basate su MPC, ma come un framework completo di funzionalità per servizi a lungo termine. La significatività risiede nella scelta architettonica di esporre esplicitamente la struttura a soglia piuttosto che nasconderla dietro un server virtuale. Questa esplicitezza consente:

Applicazione diretta dell'aggiornamento proattivo (aggiunta di polinomi a quota zero).
Responsabilità individuale (attribuzione del blame).
Migrazione fluida del comitato senza ricostruzione della chiave.

Il documento conclude che per i servizi che richiedono una longevità operativa di anni in presenza di una compromissione graduale, il costo di una trascrizione $O(t)$ è un trade-off necessario per la capacità di rinnovare periodicamente lo stato di sicurezza del sistema senza interrompere il servizio crittografico sottostante o ri-criptare i dati dipendenti.