RICERCA ITALIANA     

Research program

Cryptographic databases

University Co-ordinator

Università degli Studi di MILANO - TECNOLOGIE DELL'INFORMAZIONE - ()

Research Unit Leader

Pierangela Samarati

Description

In the last few years, the research unit at Dipartimento di Tecnologie dell'Informazione, Università di Milano (henceforth called the UNIMI) has been focusing its activity on innovative approaches to the specification and enforcement of authorizations and to the development of new techniques for data protection. The previous research represents a starting point for the work of the unit in the proposed project. The activity of the UNIMI research unit has been organized into several workpackages (WPs), according to the overall project organization. The UNIMI unit has a leading role in WP4 and WP5 and participates in WP0, WP1, WP2, WP6, and WP8. We now describe the task of UNIMI in the various WPs.

WP0 State of the art ( UNIBG, UNIMI, UNISA)
Continued growth of the Internet and advances in networking technology have introduced a trend toward outsourcing data management and information technology to external service providers. Sensitive information which needs to be secured is therefore available by simply pressing a button. The interest in this new outsourced databases paradigm is witnessed by a large number of ongoing research projects, as well as of prototypes under development. This new paradigm poses different research challenges. One of the foremost challenges is the security of stored data. A fundamental service for ensuring data is the access control. Although access control has been deployed as a security mechanism almost since the birth of large database systems, security of a database was considered an additional problem to be addressed when the need arose, and after threats to the secrecy and integrity of data had occurred. The construction of an authorization-based access control framework for outsourced databases is still an open problem and requires a significant extension to current solutions.
WP0 is aimed at identifying and sharing all relevant knowledge about current research approaches and results on innovative indexing techniques for querying outsourced encrypted databases and for ensuring their confidentiality and integrity. The analysis will provide the basis for the definition of an authorization-based access control framework regulating the access to outsourced databases. The state of the art evaluation will be carried out comprehensively, evaluating the diverse literature that can impact the development of our security solutions for the emerging Database as a Service paradigm, in particular: index management, inference and record linkage attacks, cryptographic solutions and related key management, query management and execution, access control.

WP1 Cryptographic techniques for selective data retrieval ( UNISA, UNIMI)
The requirement that the database content remains secret to the database server itself introduces new challenges and problems. Conventional encrypted DBMSs assume trust in the DBMS, which can decrypt data for query execution. In an outsourced environment scenario, such an assumption is not applicable anymore as the party to which the service is being outsourced cannot be granted full access to the plaintext data. Since confidentiality demands that data decryption must be possible only at the client side, techniques are needed enabling servers to execute queries directly on the encrypted data. Existing proposals towards the solution of this problem are based on the association, with each encrypted tuple, of additional indexing information obtained from the plaintext values of attributes that can be used in the queries. All such proposals, while providing a first step towards the solution remain limited either in their ability to execute non trivial (e.g., interval or aggregated queries) queries at the server, or because vulnerable to attacks exploiting indexes to obtain knowledge on the corresponding plaintext values. A major challenge in the outsourced database scenario is how to compute and represent indexing information for querying encrypted database. This challenge is the focus of this WP. The work will be carried out taking into account two conflicting requirements challenge the solution of the problem: on one side, the indexing information should be related with the data well enough to provide for an effective query execution mechanism; on the other side, the relationship between indexes and data should not open the door to inference and linking attacks that can compromise the protection granted by encryption. It is therefore important to provide approaches to indexing encrypted data constructed with efficiency and confidentiality in mind, providing a balance between these two requirements.

WP2 Cryptographic techniques for privileges control ( UNISA, UNIMI)
WP2 is aimed to analyze the existing cryptographic techniques to control privileges when accessing the database content. We plan to exploit techniques based on differential cryptography aimed at translating access hierarchies into key assignment schemes. The key assignment schema will satisfy the following four fundamental requirements: Key generation should be computationally easy; The size of the key should not vary significantly depending on the number of classes in the hierarchy; The amount of re-encrypting and re-keying that must be done following any hierarchy re-arrangements should be kept to a minimum; The resulting cryptosystem should allow fast and secure data encryption and decryption. We will also address the problem of updates that can modify the users, the data, or their authorizations and propose techniques to enforce them while maintaining a limited cost in terms of key reassignment or decryption/encryption. In particular, with respect to authorization revocation, we plan to study possible extension and application of super encryption techniques, which can allow enforcement of new constraints simply by imposing another level of encryption (via a new key) without requiring invalidation of those existing ones (and corresponding decryption and re-encryption of the data).

WP4 Access control models for encrypted databases ( UNIMI,UNIBG, UNISA)
All the existing proposals for designing and querying encrypted/indexing outsourced database focus on the challenges posed for protecting data at the server side, and assume the client has complete access to the query result. In other words, tuples are assumed to be encrypted using a single key; knowledge of the key grants complete access to the whole database. Clearly, such an assumption does not fit real world applications, which demand for selective access by different users, groups of users, or applications. A completely open problem, which we plan to address in this WP, is than how to specify and enforce selective access by different users or groups thereof on the outsourced data. A first essential step in the definition of such an access control framework for encrypted databases is a clean identification of the characteristics that it should have. WP2 is aimed at identifying and sharing all relevant knowledge about current research approaches and results on innovative authorization-based access control framework for encrypted databases, including activities performed by participating units. WP4 activity will include a complete analysis of the protection requirements related to information and resources managed. This analysis is required at the light of the complexity of the scenario, where new security requirements may come from different parties: the data owners, the final users, and the database service providers. The analysis, based on our unit's previous experience in the development of query processing techniques on encrypted data will provide the basis for the definition of an authorization-based framework. Traditional database management systems (DBMSs) make use of discretionary access control, based on authorizations specified for users, groups thereof, roles or applications. All the authorizations are specified with respect to the identifier of the subject (login of the user or name of the groups/roles). The DBMS checks each query against the authorizations of the requestor and grants or denies it accordingly. In an outsourced scenario it does not seem viable anymore to request to the DBMS the task of enforcing access control. Such a solution would require the data provider to release to the server its complete security policy (which on the contrary should be confidential). Furthermore, the server should be fully trusted to properly enforce the security policy. A trivial solution to the problem would be assuming a trusted party representing the data owner always interfaces any communication between the users/applications requesting data and the servers storing them. Task of the trusted client would be: 1) to translate the user query in a corresponding query on the encrypted data and forward it to the server; and 2) to decrypt and filter the query result so to reduce it to the data that is user is authorized to see. Such a solution, beside the vulnerability and complexity introduced by requesting a trusted component mediation, puts much of the work on the database provider introducing a bottleneck for computation and communication.

In this WP we plan to develop new solutions allowing the authorization enforcement to be carried out (totally or in part) at the client where the user resides. Our solution will exploit data encryption, by selective release of decryption keys to users (or seen it from a different perspective authorizations will be embedded in the encrypted data themselves). While in principle it is advisable to leave authorization-based access control and cryptographic protections separate, in the DAS scenario such a combination can prove successful, eliminating the drawbacks and weaknesses of the alternative solutions discussed above. The idea is then to use different encryption keys for different data. To access such encrypted data, users have to decrypt it, which could only be done by knowing the encryption algorithm and the specific decryption key being used. The access to the decryption keys could be limited to certain users of the database system and therefore different users could be given different access rights. Our solution will investigate the different issues to be tackled in this respect. We will investigate the different requirements imposed by the DAS scenario, taking into account the different parties (users, provider, server) involved, their communications and computation capabilities, and the information/processed that can be trusted to maintain and execute. We will then propose solutions to specify and enforce constraints allowing users ability to decrypt only specific data. Different approaches can be taken in this respect. For instance, tuples (or groups thereof) could be encrypted with different keys and users released the keys for the tuples they can access. Another alternative is to collect users into groups of privileges and encrypt each tuple (set thereof) with the key associated with the groups of users who can access it. These two alternative approaches can present pros and cons in different settings, which we plan to investigate. Our solution for the determination and assignment of keys will exploit the hierarchical structure that can be formed (either on tuples or on users) with a key generation and assignment schema relays on the idea of key derivation. Intuitively, the key generation scheme operates on the hierarchy: computing the keys of lower-level nodes based on the keys of their predecessors.

WP5 Models for evaluation of protection against inference attacks ( UNIMI, UNIBG, UNISA)
Being closely related to the data, indexing information could open the door to inference attacks exploiting data analysis techniques to reconstruct the database content and/or break the indexing code. The design of indexes, or their validation can then be also based on assessment of the degree of protection provided by different indexing techniques (each of which can affect efficiency in query execution in a different way). Our recent proposals have performed a first step towards this analysis, defining a possible taxonomy of attacks based on the attackers prior knowledge and on two classes of indexing information. In the first scenario, the attacker is aware of the exact (or approximate) distribution of plaintext values in the original database in addition to knowing the encrypted database. In the second scenario, the attacker has both the encrypted and the plaintext database.

The goal of this workpackage is an extension of our previous work which will consider two aspects:

Dynamical aspects.
Dynamic attacks could possibly rely on additional information that could facilitate the reconstruction of the correspondence between encrypted and cleartext values. A strategy that can be used to mitigate this attack is inserting random delays between queries, evenly distribute the database load, and even introducing a number of fake queries in order to hide the ``real'' activities of the database.

Development of information theory models.
We plan to extend the analysis to different indexing scheme and evaluate the degree of protection that different techniques may offer. We aim at merging confidentiality assessment in the process of designing indexes. We will study also different solutions to evaluate information exposure and prevent correlation attacks.

WP6 Integration with current relational systems ( UNIBG, UNIMI)
The goal of WP6 is the study and the analysis of techniques able to introduce within current relational engines an adequate support to the realization of the "database-as-a-service" scenario. Starting from the knowledge of the current status of database technology, we will focus on the key issues that need to be solved to permit a full realization of the potential of this architecture.

Design of novel index structures.
Starting from the solutions that are currently supported by relational engines (trees in their many variants, hash structures, bitmaps, spatial access methods), we will study methods to adapt them to the specific features of this environment and evaluate their performance.

Integration with the Query Optimizer
Starting from the the knoledge of the query optimizers of existing DBMSs, we will identify a strategy for the integration of the above index structures with such query optimizers.

Modular architecture and integration
We will investigate a strategy aimed to modularize the components implementing the access to remote untrusted servers, in order to permit an almost transparent integration of this novel service within an existing DBMS.

Novel Physical Design Methodology
We will study a model for the physical design phase of the database, which permits the use of remote untrusted servers, with the great advantage of a reduction of the impact to current database design methodologies.


WP8 Dissemination ( UNIBG, UNIMI, UNISA)
The UNIMI research unit will cooperate to the collective effort of all units to spread the research results, also by means of a workshop held in cooperation with a major conference of the field. Other technology transfer initiatives are planned involving both industry and standard committees and bodies.