RICERCA ITALIANA     

Basi di dati crittografate

Università degli Studi di Bergamo

Abstract

Il progetto ha come oggetto lo sviluppo di soluzioni per la sicurezza informatica in cui si deve realizzare la protezione di informazioni che sono memorizzate e gestite da attori diversi rispetto al proprietario delle informazioni. In questo ambito non sono più applicabili le soluzioni classiche di controllo dell'accesso, in cui i reference monitor controllano ogni richiesta di accesso alla risorsa. Si devono invece utilizzare soluzioni di tipo crittografico, le quali rappresentano tradizionalmente il modo in cui si protegge la sicurezza (confidenzialità e integrità) dell'informazione affidata a un contesto non fidato.
Il contesto che motiva immediatamente la ricerca è quello delle basi di dati, male soluzioni sviluppate in questo progetto promettono di avere impatto anche in numerosi altri contesti.
Per essere affrontata in modo completo, la ricerca in questo ambito deve considerare diversi aspetti, che organizziamo in tre diversi ambiti:
- Crittografia: Quali tecniche crittografiche possono dare garanzie di protezione delle informazioni in questo ambito, soddisfacendo contemporanemante obiettivi di efficienza e permettendo all'insieme di soggetti autorizzati di accedere alla porzione di informazioni cui hanno diritto? Come caratterizzare la vulnerabilità che deriva dalla collusione tra i diversi utenti?
- Modelli per la sicurezza: Come organizzare i privilegi di accesso dei diversi utenti? Come caratterizzare la perdita di confidenzialità che può derivare dal monitoraggio dello stato del sistema, considerando in ambito statico, solo la distribuzione dei valori crittografati, e in ambito dinamico la sequenza di richieste di accesso da parte degli utenti?
- Tecnologia delle basi di dati: Quale impatto ha la definizione di questi meccanismi sulla struttura di un database server? Come bilanciare le esigenze di protezione delle informazioni con le esigenze di accesso efficiente ai dati? Quali componenti è necessario modificare per garantire una piena e potenzialmente trasparente integrazione tra i servizi di protezione e i normali servizi di gestione transazionale delle informazioni? Come rendere l'uso di queste modalità di protezione una ulteriore opzione di progettazione fisica dei dati, in modo tale da rendere possibile l'uso di queste tecniche nell'ambito delle tradizionali architetture di sviluppo di applicazioni?
Tutti questi temi verranno trattati nell'ambito del progetto, il quale ha l'obiettivo di realizzare un prototipo che permetta di sperimentare le diverse soluzioni; il prototipo definisce un naturale contesto di integrazione della ricerca e promette di promuoverere in modo efficace i risultati del progetto.
I tre ambiti sopra evidenziati (crittografia, modelli per la sicurezza e tecnologia delle basi di dati) sono tutti necessari per sfruttare al meglio il potenziale di questa linea di ricerca. Ciascuna delle unità coinvolte nel progetto presenta competenze specifiche in una di queste aree: l'unità dell'Università di Salerno sull'ambito crittografico, l'unità dell'Università di Milano sui modelli per la sicurezza e le tematiche di controllo dell'accesso, l'unità dell'Università di Bergamo sulla tecnologia delle basi di dati relazionali. Questi profili di competenze si complementano in modo ottimale e garantiscono di fornire un contributo significativo al miglioramento dello stato dell'arte in questo ambito, tenendo anche conto che la ricerca svolta fino ad oggi nel contesto internazionale su questi temi si caratterizza proprio per lo scarso livello di integrazione tra queste tre aree. <<<

Coordinatore Scientifico del Programma di Ricerca

Stefano Paraboschi Università degli Studi di BERGAMO

Obiettivo del Programma di Ricerca

Il progetto ha l'obiettivo di sviluppare nuove tecnologie in grado di consentire la realizzazione di basi di dati crittografate. Le motivazioni generali di questa ricerca si possono ricondurre a due osservazioni, una legata allo specifico contesto dei sistemi informativi in rete, l'altra a considerazioni più generali relative all'evoluzione della tecnologia informatica.

Per quanto riguarda i sistemi informativi in rete, si può osservare che la tematica della gestione in outsourcing dei dati riveste un notevole interesse nel mercato dei servizi software. I vantaggi in termini di maggiore efficienza che una organizzazione può ottenere tramite una gestione remota in outsourcing del proprio sistema informativo sono assai significativi: si riducono fortemente i costi di gestione e manutenzione e si ottengono maggiori garanzie di continuità e affidabilità del servizio. Uno dei principali ostacoli alla realizzazione di questa visione è però proprio la diffidenza di un'organizzazione a concedere "fiducia" relativamente alla gestione dei propri dati. La definizione di tecniche in grado di offrire garanzie relative alla protezione delle informazioni che non richiedano di attribuire fiducia al gestore dei dati consentirebbe di ampliare enormemente l'interesse per una modalità di gestione dei dati e delle applicazioni di questo tipo.

Con un'analisi di livello più alto, osserviamo che l'evoluzione delle tecnologie dell'informazione mostra una continua crescita delle capacità di memorizzazione, elaborazione, e trasferimento delle informazioni. Un aspetto estremamente significativo è però il diverso tasso di crescita che caratterizza ciascuno di questi componenti. La capacità di memorizzazione dell'informazione aumenta con un tasso molto elevato, superiore al tasso di crescita della capacità computazionale dei sistemi, il quale a sua volta è superiore al tasso di crescita della capacità di trasferimento delle informazioni. Questi sono andamenti di lungo periodo che continueranno a operare anche nei prossimi anni. Ciò porta a ritenere che i sistemi informatici del futuro gestiranno sempre maggiori quantità di informazione, cui si riuscirà a fare accesso in modo efficiente solo se l'informazione sarà disponibile vicino al componente che ha la necessità di elaborare questa informazione. Inevitabilmente, per ragioni di efficienza, contenuti di ampie dimensioni dovranno quindi essere trasferiti e poi conservati per l'uso in vari contesti, al di fuori del controllo di chi ha diritto di attribuire privilegi di accesso alle informazioni. Aldilà quindi del contesto più immediato legato alla gestione di basi di dati in outsourcing, l'insieme di tecnologie sviluppate nel progetto promettono di avere un impatto in diversi ambiti, come è giustificato dalla notevole varietà di aree applicative che hanno dato origine a diverse delle ricerche significative in questo ambito (distribuzione di contenuti televisivi digitali, reti di sensori, etc.).

Le unità presentano un profilo di competenze che si complementa molto bene e che promette di dare un contributo significativo al miglioramento dello stato dell'arte.

UNISA: L'unità UNISA affronterà lo studio delle problematiche relative alla definizione di tecniche crittografiche in grado di offrire flessibilita` nell'accesso ai dati da parte di profili di utenti eterogenei e con la possibilità di offrire strumenti di ricerca all'interno dell'informazione cifrata che non violino la confidenzialità dell'informazione. Nell'ambito del progetto l'unità è anche responsabile di costruire un'implementazione prototipale delle funzioni crittografiche definite.

UNIMI: La ricerca di UNIMI si focalizzerà sullo sviluppo di modelli di controllo dell'accesso che permettono di rappresentare le autorizzazioni in contesti caratterizzati da grandi comunità di utenti e grandi collezioni di informazioni. Lo studio dovrebbe considerare anche le problematiche relative alla gestione della dinamica delle autorizzazioni. Un altro tema è costituito dallo studio delle problematiche legate al controllo dell'inferenza.

UNIBG: L'unità UNIBG si caratterizza per l'esperienza sul fronte delle tecnologie dei DBMS. Aldilà dello studio sui problemi specifici che sorgono nell'integrazione all'interno di un DBMS di queste modalità di protezione dell'informazione, il lavoro di UNIBG si focalizzerà sulla realizzazione di un prototipo che estenderà un DBMS esistente (probabilmente Postgres, su cui UNIBG ha acquisito una certa esperienza) in modo da dimostrare concretamente e rendere disponibile a una comunità allargata i risultati di questa attività di ricerca. L'implementazione integrerà le implementazioni delle funzioni crittografiche prodotte da UNISA.

Il progetto è strutturato in 8 workpackage, ciascuno sotto la responsabilità di una specifica unità.

WP0: Stato dell'arte (Unità: R:UNIBG, C: UNIMI, UNISA)
WP1: Tecniche crittografiche per la ricerca selettiva dei dati (Unità: R: UNISA, C: UNIMI)
WP2: Tecniche crittografiche per la gestione dei privilegi (Unità: R: UNISA, C: UNIMI)
WP3: Prototipo dei servizi crittografici (Unità: R: UNISA, C: UNIBG)
WP4: Modelli per il controllo d'accesso in basi di dati cifrate (Unità: R: UNIMI, C: UNIBG, UNISA)
WP5: Modelli per la valutazione della protezione ad attacchi ad inferenza (Unità: R: UNIMI, C: UNISA)
WP6: Integrazione tra crittografia e sistemi relazionali (Unità: R: UNIBG, C: UNIMI)
WP7: Implementazione del prototipo di base di dati (Unità: R: UNIBG, C: UNISA)
WP8: Divulgazione dei risultati (Unità: R:UNIBG, C: UNIMI, UNISA)

Ci preme in chiusura sottolineare i seguenti aspetti, che riteniamo debbano essere considerati con attenzione in fase di valutazione della proposta. Innanzitutto, riteniamo evidente la significatività del tema del progetto, sia valutando il contesto immediato di applicazione, sia le prospettive di lungo termine. I responsabili delle unità danno inoltre garanzie che nel progetto verrà svolto un lavoro scientifico di qualità. Il progetto inoltre non presenta solo contenuti teorici, ma impiega buona parte delle risorse verso lo sviluppo di software, che consentirà di verificare direttamente il funzionamento delle tecniche sviluppate e inoltre offrirà una modalità interessante di diffusione dei risultati.

Progetti di questo tipo sono tanto più interessanti quanto maggiore è il grado di allargamento di prospettiva che deriva dalla collaborazione tra esperienze diverse; d'altra parte, la collaborazione tra gruppi che usano approcci diversi può incontrare difficoltà se i temi di interesse sono distanti e se non esistono meccanismi di coordinamento efficaci. Per quanto riguarda questo progetto, osserviamo che le 3 unità hanno mostrato già interesse su questo tema, portano competenze ben integrabili e presentano dei legami consolidati tra di esse, per cui si possono dare forti garanzie che il progetto vedrà un notevole impegno da parte di tutte le unità e osserverà un alto grado di cooperazione.

Non bisogna d'altra parte pensare che, dato il precedente lavoro sui temi da parte delle unità e la presenza di questi legami, l'iniziativa di ricerca possa procedere anche senza il finanziamento del progetto. Queste iniziative che richiedono di svolgere attività in collaborazione, particolarmente se viene prevista la costruzione di prototipi software relativamente sofisticati, necessitano di un sostegno finanziario adeguato. <<<

Durata

24 mesi

Base di partenza scientifica nazionale o internazionale

Il tema del progetto richiede di considerare diverse linee di ricerca sviluppate in passato. Analizziamo sinteticamente le tematiche di maggiore interesse.

Protezione delle informazioni in basi di dati outsourced
Nella maggior parte delle organizzazioni, le basi di dati vengono usate per gestire una grande quantità di informazioni critiche e la loro dimensione sta crescendo sempre più velocemente. Garantire un adeguato livello di protezione al loro contenuto è una parte essenziale di un qualsiasi programma di pianificazione della sicurezza. La cifratura delle basi di dati [DWK-81] è una tecnica assodata nel tempo che introduce uno strato aggiuntivo alle soluzioni tradizionali per la sicurezza a livello di rete e applicativo, prevenendo l'esposizione di dati anche se il database server è compromesso. Il contesto sta diventando di recente molto più complicato in quanto molte aziende preferiscono affidare la gestione dei propri dati ad enti esterni (Application Service Provider), piuttosto che consentire l'accesso diretto alle proprie basi di dati per mezzo di reti potenzialmente ostili come Internet. Inoltre, dare in gestione i dati a provider esterni ne assicura una maggiore disponibilità e una migliore protezione da calamità che non gestendoli internamente. Per tali ragioni, dati molto sensibili sono ora mantenuti e gestiti da sistemi che non sono sotto il diretto controllo del proprietario. La confidenzialità e l'integrità dei dati può pertanto essere messa a rischio. L'adozione di techniche per la sicurezza da parte dei provider quali, ad esempio, firewall e sistemi di gestione delle intrusioni non è sotto il controllo del proprietario dei dati. Oltre a ciò i proprietari dei dati possono non fidarsi completamente della discrezionalità del provider; d'altra parte impedire ai provider di accedere ai dati memorizzati sulle loro macchine è complicato. Perché questo tipo di servizio funzioni è di primaria importanza fornire mezzi per proteggere la segretezza dell'informazione memorizzata in remoto, garantendone la disponibilità agli utenti legittimi. Dato che la protezione della confidenzialità dei dati richiede che questi siano decifrati solo lato utente, sono necessarie tecniche che consentano ai server remoti di eseguire le interrogazioni direttamente sui dati cifrati, altrimenti tutte le relazioni coinvolte nell'interrogazione dovrebbero essere inviate per intero al client. Una prima proposta in questo senso è stata presentata in [HILM-02,HIM-02] dove gli autori propongono di memorizzare, unitamente alla base di dati cifrata, degli indici che il DBMS può usare per la selezione dei dati da restituire in seguito ad una interrogazione. In [DDJPS-03] si propone un metodo di indicizzazione basato su funzioni di hash e che permette la gestione di interrogazioni di selezione. Le interrogazioni di intervallo sono invece supportate per mezzo di indici che sfruttano gli alberi B+ comunemente usati dai DBMS per l'esecuzione efficiente di interrogazioni. In [DDPS-04] si illustra un approccio per offuscare i dati che ne garantisce la protezione, pur consentendo la valutazione sia di condizioni di uguaglianza sia di intervallo sui dati cifrati. Sono state proposte anche tecniche omomorfe per la privacy per consentire l'esecuzione di interrogazioni aggregate sui dati cifrati [HIM-04,HM-04].

Protezione dell'informazione da attacchi di inferenza
Un altro problema interessante da prendere in considerazione è legato al fatto che gli indici aggiunti alla base di dati cifrata possono essere sfruttati per ricostruirne il contenuto e/o per rompere il metodo di indicizzazione [CDDJPS-05]. Se da un lato i metodi di indicizzazione dovrebbero fornire degli indici che devono essere correlati ai dati in modo da fornire un meccanismo efficace di esecuzione delle interrogazioni, dall'altro lato la relazione fra indici e dati non dovrebbe facilitare attacchi di inferenza o basati sulla correlazione fra i dati e che potenzialmente possono compromettere la protezione garantita dalla crittografia [D-82]. Questi tipi di attacchi sono ben noti nell'ambito dell'area di ricerca sulla sicurezza delle basi di dati ([FJ-03] presenta uno studio sul controllo di inferenza in diversi tipi di sistema, come basi di dati statistiche, basi di dati multilivello sicure, basi di dati generiche). In particolare, i problemi di inferenza sono stati ampiamente studiati nel contesto di sistemi di basi di dati multilivello, dove si è studiato in dettaglio il problema della individuazione di canali di inferenza in una base di dati o durante il processo di interrogazione [DH-96,MMJ-96]. Altri approcci hanno studiato il problema della inferenza nell'ambito del rilascio di microdati [S-01]. Sebbene certamente possono essere individuate delle similitudini, lo scenario di basi di dati crittate e indicizzate presenta delle caratteristiche peculiari che richiedono l'introduzione di nuovi approcci.
Comunque, recenti proposte per la valutazione dell'esposizione ad inferenza come quella riportata in [CDDJPS-05] possono rappresentare un punto di partenza. In [CDDJPS-05], si considerano due casi che differiscono sulla conoscenza pregressa dell'intruso, mentre l'aspetto in comune è che questi ha totale accesso alla base di dati cifrata. Nel primo scenario, l'attaccante conosce la distribuzione esatta (o approssimata) dei valori in chiaro nella base di dati originale, oltre alla base di dati cifrata. Nel secondo scenario, l'attaccante conosce sia la base di dati cifrata che quella in chiaro. Gli autori forniscono, per entrambi gli scenari, un modello qualitativo per valutare la robustezza degli indici ottenuti sia tramite cifratura diretta che tramite funzioni di hash. In conclusione si mostra che per ottenere un più elevato grado di protezione contro l'inferenza, è opportuno usare una funzione di hash per l'indicizzazione. Si noti che in [CDDJPS-05] è stata presa in considerazione solo un'analisi statica; attacchi dinamici potrebbero fare affidamento su informazioni aggiuntive che potrebbero facilitare la ricostruzione della corrispondenza fra i valori in chiaro e quelli cifrati.

Modelli per il controllo dell'accesso e relative tecniche crittografiche
Lo scenario "database-as-a-service" introduce molti altri spunti per la ricerca e ci sono vari problemi nello sviluppo di tecniche per assicurare una condivisione e divulgazione selettiva dell'informazione. Uno di questi è lo sviluppo di tecniche efficienti per il controllo dell'accesso.
Il controllo dell'accesso è un servizio di sicurezza che data una richiesta di accesso presentata da un utente o agente (soggetto) per eseguire una data azioni su risorse e/o dati (oggetti) gestiti dal sistema, determina se deve essere concessa o meno [SD-01]. Recentemente, sono state proposte delle tecniche che permettono di definire diversi diritti di accesso su documenti XML [W-02] definendo diverse chiavi di cifratura. Più precisamente, questi approcci consentono la memorizzazione in forma crittata di documenti XML su (potenzialmente insicuri e vulnerabili) server Web. I diritti di accesso sulle varie porzioni di un documento XML vengono definiti dal creatore del documento e sono applicate usando diverse chiave di cifratura per le diverse porzioni del documento. Gli utenti ottengono così solo le chiavi associate alle porzioni di testo su cui hanno un diritto di accesso.
In questo ambito riveste inoltre una notevole importanza l'individuazione di opportune tecniche crittografiche, che partono da una classificazione degli utenti in base ai loro privilegi. Una classe può essere costituita da un singolo utente, da più utenti appartenenti allo stesso dipartimento, da un gruppo di lavoro su uno specifico progetto, etc. Una politica di controllo degli accessi può essere implementata mediante uno schema di assegnamento di chiavi crittografiche, cioè un metodo per assegnare una chiave crittografica e delle informazioni private a ciascuna classe. La chiave viene utilizzata dalla classe per cifrare i suoi dati sensibili, mediante un crittosistema simmetrico, mentre l'informazione privata viene utilizzata per calcolare le chiavi assegnate alle classi a cui l'accesso viene consentito dalla politica. Tale assegnamento viene effettuato da un'autorità centrale fidata, che partecipa solo alla fase di inizializzazione. Il vantaggio di questa soluzione è che ciascun utente non necessita di alcuna interazione con l'autorità centrale per accedere alla porzione di dati di sua competenza.
Una implementazione banale di uno schema per l'assegnamento di chiavi richiede alle classi con maggiori privilegi di accesso di custodire tante chiavi quante sono le classi a cui l'accesso è consentito. Allo scopo di ottenere una soluzione più efficiente della precedente, in [AT-83] è stato proposto un elegante schema di assegnamento di chiavi in un sistema organizzato come una gerarchia parzialmente ordinata (poset). In tale schema la chiave assegnata a ciascuna classe può essere utilizzata, insieme ad alcuni parametri pubblici generati dall'autorità centrale, per calcolare le chiavi assegnate a tutte le classi sottostanti nella gerarchia. La soluzione proposta richiede l'utilizzo di un'operazione computazionalmente onerosa, l'esponenziazione modulare, per la derivazione delle chiavi da parte delle classi; inoltre, non consente l'aggiunta o la rimozione di classi all'interno della gerarchia. In seguito sono stati proposti vari schemi che garantiscono migliori performance rispetto allo schema in [AT-83] o consentono la modifica della gerarchia senza la necessità di assegnare le chiavi ex novo ([CHW-92,S-88]).
In molte situazioni l'appartenenza di un utente ad una certa classe può dipendere anche da vincoli temporali. Ad esempio, si consideri un gruppo di utenti che partecipa ad un progetto di lavoro in un determinato intervallo di tempo, oppure un utente che passa da un gruppo di lavoro all'altro. In tali situazioni è necessario assegnare agli utenti una chiave diversa per ciascun periodo di tempo. Schemi di assegnamento di chiavi con vincoli temporali sono stati proposti in [T-02]. In particolare, è stato proposto uno schema per gerarchie parzialmente ordinate in cui la derivazione delle chiavi non è vincolata solo dalle relazioni tra le classi, ma anche dal tempo. Purtroppo in [YY-03] è stato provato che lo schema proposto in [T-02] è insicuro contro attacchi da parte di coalizioni di classi. Successivamente, schemi temporizzati sono stati proposti in [HC-04] e [C-04]. Anche tali schemi sono vulnerabili ad attacchi da parte di coalizioni di classi, come è stato provato in [TM-05] e [DFM-06].

Tecniche crittografiche per la ricerca di informazioni
La ricerca in ambito crittografico ha anche considerato il tema della ricerca di informazioni, con approcci indipendenti rispetto a quelli studiati nella comunità delle basi di dati (che si basano sull'adattamento delle strutture di indicizzazione).
Un primo esempio è dato dallo schema PIR (Private Information Retrieval) [CGKS-98], che permette all'utente di recuperare informazione privatamente rispetto al gestore della base di dati. In altre parole, il gestore, dalla propria osservazione, non riesce a saper nulla circa le informazioni reali a cui l'utente è interessato. L'enfasi in questo settore di ricerca è stata posta nel corso dei recenti anni passati principalmente sulla realizzazione di schemi PIR efficienti dal punto di vista della complessità di comunicazione. L'esigenza di privacy impone, infatti, limitazioni gravose ai costi dell'interazione utente-base di dati. Sono stati presi in considerazione due modelli.
Nel modello incondizionatamente sicuro [CGKS-98,IK-99,BIM-00,BIKR-02] la privacy dell'utente è totale, indipendente dal potere computazionale del gestore avversario. Tuttavia, uno schema PIR incondizionatamente sicuro, per essere realizzabile, richiede che esistano diverse copie identiche della base di dati e che i rispettivi gestori non siano in grado di comunicare tra di loro. Alcuni lavori hanno indebolito quest'ultima assunzione [IK-99,BDD-01].
Nel modello computazionalmente sicuro [KO-97,GR-05] la privacy dell'utente è garantita se ragionevoli e ampiamente accettate limitazioni alla capacità computazionale del gestore sono soddisfatte. In questo modello non sono richieste repliche della base di dati. Varianti interessanti di schemi PIR sono trattate in [DIO-01,KO-00,NP-99,OS-99].

Un secondo tema di ricerca ha considerato tecniche crittografiche con supporto per la ricerca. Uno schema SE (Searchable Encryption) [BDOP-04] consente ad un utente di delegare la ricerca di una keyword in un testo cifrato ad una terza parte. In un SE l'unica informazione che la terza parte ottiene riguarda l’appartenenza o meno della keyword al testo in chiaro associato. Gli SE evitano la necessità di fornire alla terza parte la chiave di decifratura od il plaintext stesso. Negli ultimi anni sono stati presentati vari schemi SE. Le soluzioni possono essere divise in due classi: SE simmetrici ed asimmetrici.
Nel caso simmetrico, in una prima fase l’utente invia alla base di dati le informazioni cifrate. In una seconda fase, l’utente stesso o un suo delegato, possessore della chiave di cifratura/decifratura, può inviare query alla base di dati, ottenendo come risposta i record che soddisfano la query. Inoltre, la base di dati non ottiene alcuna informazione sia riguardo le keyword usate nella query sia riguardo alle informazioni ottenute come risposta. In [SWP-00] viene studiato il problema della ricerca su dati cifrati nel caso simmetrico. In questo lavoro gli autori propongono uno schema che cifra separatamente ogni keyword (o pattern) di un documento. Questo schema non è sicuro rispetto ad attacchi statistici. In [G-03] l'autore propone uno schema che utilizza filtri di Bloom. Un problema di questo approccio è legato al fatto che i filtri di Bloom inducono ``falsi positivi'', cioè la base di dati restituisce informazioni che non corrispondono alle keyword ricercate. Inoltre la base di dati può ottenere informazioni sull'insieme di keyword utilizzate dall'utente. In [CM-04] gli autori propongono una variazione dello schema proposto in [G-03] che risolve il problema degli attacchi statistici, ma non risulta sufficientemente flessibile per garantire aggiornamenti delle informazioni con keyword arbitrarie.
Negli SE asimmetrici, le informazioni vengono cifrate utilizzando la chiave pubblica del ricevente. In questo caso chiunque può cifrare delle informazioni e memorizzarle presso la base di dati in modo tale che in una seconda fase il ricevente possa recuperarle. Per eseguire una ricerca di una keyword l'utente genera una trapdoor che viene inviata alla base di dati e che consente a quest'ultimo di eseguire l'operazione richiesta senza ottenere informazioni sulla keyword o sulle informazioni ad essa associata. Il primo schema in questa classe è stato presentato in [BDOP-04]. In questo lavoro gli autori presentano uno schema sicuro nel random oracle model. Lo strumento utilizzato in questo schema è uno schema di cifratura ID-based (IBE) presentato in [BF-04]. Partendo da [BDOP-04], gli autori in [AB+-05] provano che l'esistenza di schemi IBE anonimi implica l'esistenza di SE asimmetrici. Inoltre, gli autori presentano una costruzione per un IBE con keyword search basata su IBE gerarchici anonimi. I lavori finora citati consentono soltanto ricerche del tipo ``w appartiente al database?''. Per il caso di query complesse, cioè formulate attraverso espressioni booleane arbitrarie, non esistono soluzioni generali. Esistono solo schemi [BKM-01,GSW-04,PKL-04] che consentono l'esecuzione di query descritte dall'AND di query semplici. <<<