Blog.

Private Set Intersection: cos’è? | Differential Privacy


Autore
Andrea Provino
Data
Tempo di lettura
5 minuti
Categoria
AI, Privacy Preserving

private-set-intersection-data-science-machne-learning-deep-learning-homorphic-encryption-italia

La Private Set Intersection è una tecnica crittografica avanzata con la quale due parti sono in grado di calcolare l’intersezione dei loro dati senza tuttavia esporli a terzi, preservando la privacy reciproca.

In altre parole la Private Set Intersection permette di confermare la presenza di un datapoint condiviso (e.g. location, ID, etc…) tra due parti.

In un precedente post abbiamo analizzato le tecniche di privacy-preserving adottabili nello sviluppo di un’applicazione, costretta a gestire informazioni personali ad alto rischio.

Considerando le esigenze imposte dalla situazione globale attuale, l’esempio che abbiamo preso in considerazione era quello di un’app di tracing,

Siamo così stati in grado di mettere in luce alcune avanzate, seppur relativamente semplici, tecniche preservazione della privacy. Di queste, oggi approfondiamo quella di Private Set Intersection (PSI).

Abbiamo una nuova, fresca, giornata di navigazione davanti a noi! Prepariamoci a macinare miglia!

Prima però, assicuriamoci di allineare il nostro vocabolario comune, così da eliminare il rischio di fraintendimenti.

Più nello specifico dobbiamo avere chiari in mente i concetti di :

  • Crittografia
  • Homorphic Encryption
  • Secure multi-party computation

Leggiamo insieme questo post, e poi torniamo qui!

Avendo ripassato il lessico fondamentale della crittografia, e chiarito i termini tecnici senza i quali non potremmo capire questo post, possiamo ora spiegare le vele!

Private Set Intersection

La PSI è dunque un tecnica di privacy-preserving che permette a due parti di calcolare l’intersezione dei loro dati, producendo un terzo insieme contenente i datapoint comuni, senza compromettere la privacy individuale.

La PSI può essere implementata con l’ausilio di differenti tecniche, tra cui quella di Homorphic Encryption, grazie alla quale è possibile compiere operazioni matematiche su dati criptati avendo la certezza che il risultato sia corretto, senza compromettere la sicurezza dell’informazione (i.e. Mantenendola privata, ergo criptata).

Avendo approfondito la tecnica di Homorphic Encryption qui, passeremo veloci sull’argomento.

L’interazione server-client è lo scenario più comune in cui questa tecnica trova applicazione: solamente il client riceve il risultato dell’intersezione.

Ovviamente, esistono diverse varianti in cui la Private Set Intersection è messa in pratica. Un esempio è quella in cui il client riceve solo la dimensione dell’intersezione, e non il contenuto, o dove il calcolo è compiuto dallo stesso client.

Real World Scenario

Data la semplicità dello scenario server-client, lo useremo come esempio per comprende l’argomento più a fondo.

Prima però, devi sapere un’ultima cosa.

Lo schema di criptazione scelto e la tecnica di Private Set Intersection formano un protoccolo (protocol).

Gli inglesi hanno un’espressione per indicare una soluzione semplice a un problema complesso: la chiamano silver bullet.

Bene, contrariamente a quello che pensavi di aver intuito, non esiste alcun silver bullet in riferimento ai protocolli di privacy-preserving.

Dobbiamo al contrario studiare le esigenze per ogni caso e progettare il protocollo di conseguenza, affinché risulti sicuro e sufficientemente veloce.

Non sarebbe avvincente, se fosse semplice.

Per sviluppare un protocollo efficace, occorre dunque tenere conto ad esempio di:

  • Dimensione dei dati gestiti dal server e dal client
  • Natura di eventuali attacchi avversari (adversarial attack) da prevenire
  • Presenza di risorse limitate (e.g. computazione su dispositivi mobili).

Il PSI Protocol che abbiamo delineato è quindi un caso particolare, di una vasta famiglia di plausibili protocolli.

Private Set Intersection Examples

Di seguito trovi una lista di scenari in cui poter applicare il Private Set Intersection Protocol, che ti ricordo avere come tratti distintivi:

  • La presenza di due parti
  • L’interesse delle parti di non mostrare i propri dati
  • La necessità delle parti di conoscere l’esistenza di eventuali elementi comuni tra i propri dati
Use CaseDescrizione
Private Contact DiscoveryIndividuare quali utenti (client) della mia lista contatti privata (server) soddisfino certi requisiti
DNA testing and pattern matchingGli utenti in possesso della propria sequenza DNA (client), intendo scoprire qualli tratti sono collegati a malattie o disturbi noti, salvati in un database (server)
Remote diagnosticsUn programma di diagnosi medica assegna lo status (malato o non malato) alla cartella clinica di un paziente (client). Mentre l’utente apprende informazioni sulla propria salute, il programma e il proprietario (server) non leggono in chiario i dati utente.
Private record linkageI dati di un cliente comune sono registrati sulle piattforme private di due parti (server). Per consentire l’operazione di data mining la condivisione dei dati può essere compiuta senza compromettere la privacy dei dati gestiti.

Prossimamente aggiorneremo l’articolo aggiungendo l’implementazione pratica (i.e Il codice) di questa sorprendente tecnica.

Tipologie di Private Set Intersection

In questa pubblicazione, preparata da 4 italiani di Banca d’Italia e ISTAT, sono presentati 4 scenari che possono supportare, in modo generico, le richieste di condivisione d’informazioni sensibili.

Definiamo allora:

  • private set intersection (PSI)
  • PSI with enrichment (PSI-E)
  • PSI with analytics (PSI-A)
  • private data mining

Analizziamo rapidamente ogni scenario, eccetto il primo, poiché ampiamente già trattato, per meglio coglierne le applicazioni d’uso reali.

PSI-E

Volendo darne una definizione formale, siano P1 e P2 i data owner di due grandi dataset che identifichiamo con D1 e D2.

Le due parti intendono definire l’intersezione, esatta o approssimativa, dei loro dati e generare un’unione, senza tuttavia rilevare informazioni riservate non necessarie al task.

Terminato il calcolo dell’intersezione, inizia allora la fase di arricchimento.

Entrambe le parti possono ora calcolare l’unione delle informazioni presenti in entrambi i set dati.

PSI-A

Nello scenario di Private Set Intersection with Analytics, le due parti intendono condurre analisi statistiche sull’intersezione dei loro dati in modo privato, tutelando la privacy delle istanze.

In questo caso, dopo aver definito l’intersezione applicando la PSI, l’unica informazione appresa dalle parti al di fuori degli identificatori d’intersezione, è il risultato della funzione statistica applicata ai dati dell’altra parte, o data owner.

Private Data Mining

È uno scenario simile al precedente, con l’eccezione di applicazione della funzione analitica sull’unione dei dati di entrambe le parti, anziché sui soli dati della parte coinvolta.

Fonte

Per il momento è tutto.

Un caldo abbraccio, Andrea.

TaggedAIdeep learningdifferential privacyprivacy


Ultimi post

Patricia Merkle Trie

Il Practical Algorithm To Retrieve Information Coded In Alphanumeric Merkle Trie, o Patricia Merkle Trie è una struttura dati chiave-valore usatada Ethereum e particolarmente efficiente per il salvataggio e la verifica dell’integrità dell’informazione. In questo post ne studieremo le caratteristiche. Prima di procedere, ci conviene ripassare l’introduzione al Merkle Tree nella quale abbiamo chiarito il […]

Andrea Provino
ethereum-patricia-merkle-tree
Tree Data Structure: cos’è un Merkle Tree

Un Merkle Tree è una struttura dati efficiente per verificare che un dato appartenga a un insieme esteso di elementi. È comunemente impiegato nelle Peer to Peer network in cui la generazione efficiente di prove (proof) contribuisce alla scalabilità della rete. Capire i vantaggi di questa struttura ci tornerà utile nel nostro percorso di esplorazione […]

Andrea Provino
merkle-tree-cover
UTXO: come funziona il modello Unspent Transaction Outputs

Per tenere traccia dei bilanci utente, la blockchain di Bitcoin sfrutta un modello di contabilità definito UTXO o Unspent Transaction Outputs. In questo articolo ne esaminiamo le caratteristiche. Ogni blockchain è dotata di un sistema di contabilità, un meccanismo attraverso cui tenere traccia dei bilanci di ciascun utente. I due grandi modelli di riferimento nel […]

Andrea Provino
bitcoin-utxo
Cos’è Ethereum

Possiamo definire Ethereum come una macchina a stati distribuita che traccia le transizioni di un archivio dati general-purpose (i.e. una memoria in grado di registrare qualsiasi dato esprimibile come coppia di chiave e valore o key-value) all’interno della Ethereum Blockchain. È arrivato il momento di esplorare uno dei progetti tecnologici più innovativi e interessanti degli […]

Andrea Provino
ethereum