PAC to the Future: Zero-Knowledge Proofs of PAC Private Systems

Titolo: PAC to the Future: Zero-Knowledge Proofs of PAC Private Systems

Autori: Guilhem Repetto, Nojan Sheybani, Gabrielle De Micheli, Farinaz Koushanfar.
Contesto: Companion Proceedings of the ACM Web Conference 2026 (WWW Companion '26).

1. Il Problema

L'articolo affronta la crescente preoccupazione riguardo alla privacy dei dati utente nelle macchine di apprendimento automatico (ML) su larga scala e nei sistemi cloud.

• Limiti delle tecniche attuali: Le tecniche tradizionali di privacy-preserving, come la Differential Privacy (DP), spesso comportano una significativa perdita di utilità dei dati quando si richiedono garanzie di privacy forti, specialmente su dataset piccoli o complessi.
• Il problema della fiducia (Trustless Environment): In scenari di calcolo esternalizzato (es. cloud computing), gli utenti devono fidarsi del fornitore di servizi per l'esecuzione corretta delle operazioni e l'applicazione corretta del rumore di privacy. Non esiste un modo verificabile per garantire che il rumore sia stato calcolato e applicato correttamente senza rivelare i dati sensibili o la logica proprietaria del sistema.
• La sfida: Come garantire che un meccanismo di privacy (in questo caso basato su PAC) sia stato eseguito correttamente e che le garanzie di privacy siano state rispettate, mantenendo la riservatezza dei dati e dell'algoritmo?

2. Metodologia

Il paper propone un nuovo framework che combina la Privacy PAC (Probably Approximately Correct) con le Zero-Knowledge Proofs (ZKP), specificamente utilizzando lo schema zk-STARK.

Concetti Chiave:

• PAC Privacy: A differenza della DP, la PAC Privacy offre garanzie di privacy rigorose per algoritmi "black-box" adattando dinamicamente il rumore necessario. Non richiede di conoscere i dettagli interni dell'algoritmo, ma si basa sulla distribuzione dei dati e sulla funzione di reward dell'attaccante.
• zk-STARKs (Zero-Knowledge Scalable Transparent Arguments of Knowledge):
  • Scelti al posto degli zk-SNARKs per la loro trasparenza (nessuna necessità di un "trusted setup") e la sicurezza post-quantum (basata su funzioni hash resistenti alle collisioni).
  • Utilizzati in modalità non interattiva per generare prove pubbliche verificabili da chiunque.

Flusso del Sistema:

Il sistema è progettato per un ambiente dove un Prover (server cloud) esegue calcoli su dati privati e un Verifier (client) verifica l'integrità.

1. Generazione del Rumore (Noise Generation):
   • Il Prover calcola una matrice di covarianza $\Sigma$ necessaria per generare il rumore gaussiano $B$ che garantisce la privacy PAC.
   • Poiché $\Sigma$ deve rimanere privato, il Prover calcola l'hash $h(\Sigma)$ all'interno di un circuito ZK.
   • Viene generata una prova che attesta che $h(\Sigma)$ corrisponde a una matrice calcolata correttamente secondo l'algoritmo PAC, senza rivelare $\Sigma$.
2. Esecuzione del Meccanismo (PAC Execution):
   • Il Prover riceve un punto dati $x$ (o un filtro per query DB) e un seme casuale $s$ (fornito dal Verifier).
   • Utilizza $s$ e la matrice $\Sigma$ (nascosta) per generare deterministicamente il rumore $B$.
   • Calcola il risultato $M(x) + B$ (dove $M$ è l'algoritmo ML o statistico).
   • Genera una prova ZK che verifica:
     • L'uso corretto della matrice $\Sigma$ (verificando che $h(\Sigma)$ corrisponda all'hash pubblico).
     • La correttezza del calcolo di $M(x) + B$.
3. Vincoli di Implementazione (RISC-Zero):
   • Per funzionare in un ambiente ZK deterministico (come RISC-Zero), gli algoritmi non possono avere loop dipendenti dall'input o generare casualità interna.
   • Soluzioni applicate:
     • I loop (es. iterazioni di K-means) sono fissi e pre-calcolati.
     • La casualità è gestita tramite semi forniti dal Verifier.
     • Le strutture dati (es. gruppi di cluster) sono dimensionate in modo fisso, usando flag booleani per indicare elementi validi/invalidi, mantenendo la dimensione della traccia di esecuzione costante.

3. Contributi Chiave

1. Framework End-to-End: Prima implementazione che integra PAC Privacy con zk-STARKs non interattivi per fornire garanzie di privacy verificabili in ambienti non fidati.
2. Verificabilità del Rumore: Il sistema permette di provare che il rumore di privacy è stato generato e applicato correttamente secondo le specifiche PAC, senza rivelare i parametri del rumore o i dati grezzi.
3. Adattamento di Algoritmi ML e DB: Adattamento specifico di algoritmi complessi (K-means, SVM) e query statistiche su database per funzionare all'interno dei vincoli rigidi dei circuiti ZK (determinismo, dimensioni fisse).
4. Sicurezza Post-Quantum: L'uso di zk-STARKs garantisce che il sistema rimanga sicuro anche contro computer quantistici futuri.

4. Risultati Sperimentali

Gli autori hanno implementato il framework utilizzando RISC-Zero e hanno valutato le prestazioni su tre casi d'uso:

• K-means (Clustering):
  • I risultati mostrano una crescita affine (lineare) del numero di cicli di calcolo (Risc cycles) in funzione del numero di campioni ($M$) e del numero di cluster ($K$).
  • L'overhead è prevedibile e gestibile per dataset di piccole e medie dimensioni.
• SVM (Support Vector Machines):
  • Si osserva un comportamento generalmente affine, ma con lievi fluttuazioni dovute a operazioni intensive di memoria e uso della cache nel circuito zkVM, che introducono variabilità nei conteggi dei cicli.
• Statistiche su Database:
  • Le query statistiche (media, mediana) su database filtrati mostrano anch'esse una scalabilità affine rispetto alla dimensione del database e alla dimensionalità dei punti.

Conclusioni sulle prestazioni: L'overhead computazionale per la generazione delle prove è fattibile per applicazioni reali di piccole e medie dimensioni, mantenendo un'utilità dei dati vicina a quella del plaintext (dati non offuscati).

5. Significato e Impatto

Questo lavoro rappresenta un passo fondamentale verso la creazione di sistemi di calcolo cloud verificabili e privati.

• Riduzione dell'Asimmetria di Fiducia: Permette agli utenti di verificare l'integrità computazionale e la conformità alle policy di privacy senza dover fidarsi ciecamente del fornitore del servizio cloud.
• Superamento dei limiti della DP: Offre un'alternativa alla Differential Privacy che mantiene una migliore utilità dei dati, risolvendo il problema della verifica di tale utilità in contesti trustless.
• Futuro della Privacy: Dimostra la fattibilità pratica di combinare garanzie di privacy teoriche (PAC) con crittografia avanzata (ZK), aprendo la strada a servizi di ML e database più sicuri e trasparenti per l'era post-quantum.

In sintesi, il paper trasforma la privacy da una promessa basata sulla fiducia in una garanzia matematica verificabile, rendendo possibile l'outsourcing sicuro di calcoli sensibili su algoritmi complessi.