Università degli Studi dell’Insubria
Facoltà di Scienze MM. FF. NN.
Corso di Laurea in Informatica
Interrogazioni private di database mediante
Filtri di Bloom:
implementazione ed esperimenti
Tesi di laurea di
Relatore: Prof. Alberto Trombetta
Dipartimento di Informatica e Comunicazione
Gianguido Bardelli
Matr. 611825
Introduzione
“Privacy-Enhanced Searches Using
Encrypted Bloom Filters”
di Bellovin-Cheswick
Linguaggio C
Libreria Miracl
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Introduzione
• Assenza di fiducia tra le parti
• Client non deve sapere nulla oltre al richiesto
• Server non deve risalire all’obiettivo della query
• Filtri di Bloom criptati
• Algoritmo Pohlig-Hellman
• Una terza parte indipendente dalle due
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Filtro di Bloom
0
0,
0
0
1,
2, ………………………………,m-1
h0() = x0
h1() = x1
0
0
0
0
0
0
0
....
xi compreso tra 0 e m-1
hn() = xn
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Filtro di Bloom: inserimento(1)
0
0
0
0
0
0
0
0
0
0
h0(record) = 1
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Filtro di Bloom: inserimento(2)
0
1
0
0
0
0
0
0
0
0
h0(record) = 1
h1(record) = 4
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Filtro di Bloom: inserimento(3)
0
1
0
0
1
0
0
0
0
0
h0(record) = 1
…...
h1(record) = 4
hn(record) = 1
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Filtro di Bloom: ricerca
0
1
0
0
1
0
1
0
0
0
h0(record) = 1
…….
h1(record) = 4
hn(record) = 8
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Filtro di Bloom
Server usa filtri di Bloom criptati
Ogni client dovrebbe conoscere
la chiave del server!
Algoritmo Pohlig-Hellman
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Algoritmo Pohlig-Hellman
Le chiavi formano un gruppo abeliano:
Data una chiave esiste la sua inversa;
Per ogni coppia di chiavi k,j esiste una
terza chiave r = k  j-1
Se cripto un dato {x}j con r
ottengo {x}k
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Algoritmo Pohlig-Hellman
Il client possiede la chiave j, il server k e
la terza parte r
La terza parte è il tramite client / server
Conosce solo la sua chiave
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Poligh-Hellman: chiavi di criptazione
Criptare X con chiave k:
{x}k = xk mod p
p numero primo della forma 2p´ + 1,
p´ primo
K dispari diverso da p´
P almeno di 1024 bit
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Poligh-Hellman: chiavi di decriptazione
Chiave di decriptazione d tale che
kd ≡ 1 mod (p - 1)
Si calcola efficientemente grazie
all’algoritmo di Euclide
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Schema base
3
Alice
Bob
2: {x}b
1: {x}a
Ted
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Warrant Server
5
Alice
Bob
4
1: {x}a
3: {x} filtrata
2: {x}warrant server
Ted
Warrant
Server
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Index Server
6: dato richiesto
5: richiesta
Alice
1: {x}a
Bob
4: {x}b
Index Server
3
2
Ted
Warrant Server
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Prestazioni dell’architettura
Limitata da due fattori:
• Ricerca nei filtri di Bloom
• Velocità nella criptazione
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Prestazioni algoritmo PH
Test effettuati con chiavi
da 512 bit e 1024 bit
Criptati file diversi
da 50kb a 500kb
Media su 20 prove per file
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Prestazioni PH: risultati
t(s)
120
100
80
60
40
512
1024
50
3,2
10,05
100
6,65
20,45
200
13,55
40,8
300
19,85
61
400
26,85
81,5
500
33,5
102,08
20
0
50
100
200
300
400
500
kb
512 bit
1024 bit
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti
Conclusioni
• Filtro di Bloom: semplice ma efficace
• Sistema:
- flessibile
- indipendente dall’algoritmo di criptazione
- integrabile in schemi più complessi
Gianguido Bardelli
Interrogazioni private di database mediante Filtri di Bloom: implementazione ed esperimenti