Modeling and assessing inference exposure in encrypted databases

The scope and character of today's computing environments are progressively shifting fromtraditional, one-on-one client-server interaction to the new cooperative paradigm. It then be-comes of primary importance to provide means of protecting the secrecy of the information, whileguaranteeing its availability to legitimate clients. Operating on-line querying services securely onopen networks is very di_cult; therefore many enterprises outsource their data center operationsto external application service providers. A promising direction towards prevention of unautho-rized access to outsourced data is represented by encryption. However, data encryption is oftensupported for the sole purpose of protecting the data in storage while allowing access to plaintextvalues by the server, which decrypts data for query execution.In this paper, we present a simple yet robust single-server solution for remote querying ofencrypted databases on external servers. Our approach is based on the use of indexing informationattached to the encrypted database, which can be used by the server to select the data to bereturned in response to a query without the need of accessing the plaintext database content. Ourindexes balance the trade o_ between e_ciency requirements in query execution and protectionrequirements due to possible inference attacks exploiting indexing information. We investigatequantitative measures to model inference exposure and provide some related experimental results.