RICERCA ITALIANA     

Cryptographic databases

Università degli Studi di Bergamo

Abstract

This project aims at developing solutions for data security, allowing to protect sensitive data stored and managed by entities different from the information owner. In such a scenario, classical solutions for access control, where reference monitors control each access request to the data, cannot be employed. On the other hand, cryptographic solutions, providing data confidentiality and integrity over insecure channels, can be used. The main application of this research project is in databases, but we will develop solutions which can be used also in other areas.
The research will consider different topics, which can be organized into three different areas:
-Cryptography: Which cryptographic techniques can be used in such a scenario to allow, in an efficient and secure way, authorized users to access the data? How to formalize the security requirements against collusion attacks carried out by a group of users?
-Security Models: How to organize access privileges for different users? How to characterize the lack of confidentiality due to system monitoring, by considering, in a static environment, only the distribution of the encrypted values and, in a dynamic environment, the sequence of users' access requests?
-Database Technologies: What is the impact of such techniques on the structure of a database server? How to trade-off security and efficiency? Which components need to be modified to allow a transparent integration among security services and standard transaction services? How to integrate such protection modes within the physical data protection process, in order to use them in traditional platforms for application development?
These issues will be considered in the project, whose goal is to realize a prototype by means of which different solutions can be evaluated; such a prototype will define a natural framework to integrate research efforts and to promote a widespread diffusion of the project results. The above areas (Cryptography, Security Models, and Database Technologies), are all needed to take advantage of such a research line. Each of the units involved in the project has acknowledged skills in one of the areas: the unit of Salerno (UNISA) in Cryptography, the unit of Milano (UNIMI) in Access Control Models, and the unit of Bergamo (UNIBG) in Database Technologies. The three units are complementary to each other and they will provide a significant contribution to the state of the art. Indeed, it can be observed that research by international groups in this area lacks in integration among the areas presented above; the project aims to fill this gap. <<<

Principal Investigator

Stefano Paraboschi Università degli Studi di BERGAMO

Research Objectives

The goal of the project is to develop new technologies enabling the realization of encrypted databases. Two are the main motivations which are supported by the following observations, the former related to on-line information systems context, the latter related to more general considerations on the evolution of the information technology. As regards online information systems, there is an increasing trend towards data outsourcing and the development of related services are registering a growing interest in the software services market. Outsourcing relational databases to external providers promises a number of advantages in terms of improved efficiency: indeed, management costs can be reduced and higher availability and more effective disaster protection than in-house operations can be provided. An obstacle to the realization of this scenario, is that data owners may not entirely trust providers. It is therefore of primary importance to provide means of protecting the secrecy of the information remotely stored, without necessarily requiring trust in the subject managing the information, while guaranteeing its availability to legitimate clients. Such techniques could support the realization of a wider market for these services and would make such approach an important option in the design of any information system.

At a higher level of analysis, it is possible to observe how the evolution of the information technology registers a continuous growth of information storing, processing and transmission capabilities. Another very important aspect is that each of the component shows a different growing rate. Storing capability shows a higher growth rate than processing capabilities, which in turn has a higher rate with respect to the transmission capabilities rate. This leads to the conclusion that in the next future, information systems will manage a growing amount of information, which will be efficiently accessed and processed only if the information is "near" to the subject which needs to process the requested information. Inevitably, for efficiency reasons, large amounts of information will be transferred and stored in places out of the control of the subjects which should have the right to manage privileges for accessing the information. In addition to the context related to the management of outsourced databases, the technologies developed in this project promise to have a significant impact in different fields of application: transmission of digital content, sensor networks, etc.

The units have a strong background and complementary competences in database and security areas. Their joint work promises to provide a significant contribution to improve the state of the art.

UNISA: UNISA unit will study the problems related to the definition of new cryptographic techniques enabling flexibility in offering access to data for group of users with different privileges and providing research techniques for encrypted data without violating confidentiality. The unit will be responsible for providing a prototype implementation of some of the cryptographic function proposed.

UNIMI: UNIMI research will be focused on the development of models for access control enabling the attribution of specific authorization for groups composed by a large number of users and large amount of information. The research will consider dynamic management of authorizations and inference control.

UNIBG: The specific role of the UNIBG unit in the project is to bring to the project its expertise on database technology. Besides studying the integration of the proposed approach with traditional DBMS systems, UNIBG research will be focused on the realization of a prototype extending an existing open source database engine (probably PostgresSQL, on which our research unit has some experience) in order to show and make available the obtained results. The implementation will integrate the cryptographic functions proposed by UNISA unit. The project is composed of 8 workpackages, each led by a specific unit:

WP0: State of the art (R: UNIBG, C: UNIMI, UNISA)
WP1: Cryptographic techniques for selective data retrieval (R: UNISA, C: UNIMI)
WP2: Cryptographic techniques for privileges control (R: UNISA, C: UNIMI)
WP3: Prototype of cryptographic services (R: UNISA, C: UNIBG)
WP4: Access control models for encrypted databases (R: UNIMI,C: UNIBG, UNISA)
WP5: Models for evaluation of protection against inference attacks (R: UNIMI, C: UNISA)
WP6: Integration with current relational systems (R: UNIBG, C: UNIMI)
WP7: Prototype implementation (R: UNIBG, C: UNISA)
WP8: Dissemination (R: UNIBG, C: UNIMI, UNISA)

Let us focus the attention on the following aspects, which we would like to be considered when evaluating our research proposal. First, we would like to put in evidence the relevance of the project for its immediate applications and in perspective on the long run. The leading researchers of the units can guarantee the quality of the work. Furthermore, the project addresses both theoretical aspects and practical results, being finalized to the development of software whose functionality will verify the proposed techniques.

Another aspect which characterizes our proposal is the high degree of complementarity among the three units: such kind of collaboration is particularly interesting when there is a widening of the perspective produced by groups putting together their own background. In this proposal the 3 units bring together complementary experiences in the field and have strong links, guaranteeing that a high degree of cooperation can be achieved.

On the other hand, it should be taken into account that it would not be possible to carry on the project without the financing, even if the research units have strong links and have already done common work in the past on such research themes. Each research initiative needs an adequate financial support in order to produce interesting results, particularly when there is the aim to develop a prototype. <<<

Timescale

24 months

National and international background

The project theme requires to consider the status of several previous research lines. We synthetically analyze the areas with the most impact.

Protection of information in outsourced databases
In most organizations, databases hold a critical concentration of sensitive information and the volume of this information is increasing very quickly. Ensuring an adequate level of protection to databases' content is an essential part of any comprehensive security program. Database encryption [DWK-81] is a time-honored technique that introduces an additional layer to conventional network and application-level security solutions, preventing exposure of sensitive information even if the database server is compromised. The scenario is becoming more complicated because many organizations prefer to outsource their data center operations to external application providers rather than allowing direct access to their databases from potentially hostile networks like the Internet. Furthermore, outsourcing relational databases to external providers promises higher availability and more effective disaster protection than in-house operations. As a consequence of this trend toward outsourcing, highly sensitive data are now stored on systems run in locations that are not under the data owner's control, such as leased space and untrusted partners' sites. Therefore, data confidentiality and even integrity can be put at risk by outsourcing data storage and management. Adoption of security best practices in outsourced locations, such as the use of firewalls and intrusion detection tools, is not under the data owner's control. In addition, data owners may not entirely trust providers' discretion; on the other hand, preventing a provider from inspecting data stored on its own machines is very difficult. For this kind of services to work successfully it is therefore of primary importance to provide means of protecting the secrecy of the information remotely stored, while guaranteeing its availability to legitimate clients. Since confidentiality demands that data decryption must be possible only at the client side, techniques are needed enabling external servers to execute queries on encrypted data, otherwise the whole relations involved in the query would be sent to the client for query execution. A first proposal towards the solution of this problem was presented in [HILM-02, HIM-02] where the authors proposed storing, together with the encrypted database, additional indexing information. Such indexes can be used by the DBMS to select the data to be returned in response to a query. In [DDJPS-03] the authors propose a hash-based method for database encryption suitable for selection queries. To execute interval-based queries, the B+-tree structures typically used inside DBMSs is adapted. In [DDPS-04] the authors illustrate an approach for obfuscating data that guarantees protection of data while allowing the execution of both equality and range queries on the obfuscated data. Privacy homomorphism has been also proposed for allowing the execution of aggregation queries over encrypted data [HIM-04, HM-04].

Protection of information from inference attacks
Another interesting problem to be taken into consideration is that the indexing information attached to the encrypted database can be exploited to reconstruct the database content and/or break the indexing code [CDDJPS-05]. While the indexing information should be related with the data well enough to provide for an effective query execution mechanism, the relationship between indexes and data should not open the door to inference and linking attacks that can compromise the protection granted by encryption [D-82]. Inference and linking attacks are two well-known problems in database security ([FJ-03] presents a survey of inference control in various system settings, such as statistical databases, multilevel secure databases, general purpose databases). In particular, inference problems have been studied extensively in the context of multilevel database systems where most inference research addresses detection of inference channels within a database or at query processing time [DH-96,MMJ-96]. Other approaches have investigated inference in the context of microdata release [S-01]. While certainly some commonalities can be identified, the indexed/encrypted database scenario presents peculiar characteristics that require the development of new solutions.
However, recent proposals for evaluation the inference exposure such as the one reported in [CDDJPS-05] can represent a starting point. Here, the authors consider two cases that differ in the assumption about the attacker's prior knowledge. The common aspect of these two cases is that the attacker has a complete access to the encrypted database. 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 authors gave a quantitative model for evaluating the robustness of the indexes obtained by applying either the direct encryption or a hash-based method in these two cases. In summary, they have shown that to achieve a higher degree of protection against inference, it is convenient to use a hash function to encode index values. Here, only a static analysis has been taken into consideration; dynamic attacks could possibly rely on additional information that could facilitate the reconstruction of the correspondence between encrypted and plaintext values.

Access control models and cryptographic techniques
The database-as-a-service scenario raises also many other interesting research issues and there are many challenges in developing techniques for ensuring a selective information sharing and dissemination process. One challenge is to develop efficient access control techniques.
Access control is the process of mediating requests presented by users or agents (subjects) to perform actions on the resources and data (objects) maintained by a system, and determining whether each request should be granted or denied [SD-01]. Currently, there are approaches that allows to define different access rights on an XML document [W-02] by means of different encryption keys. More precisely, with these approaches the XML documents can be stored encrypted on the (potentially insecure and vulnerable) web server. The decisions about access rights to different portions of the document can be made by the document creator and be immediately applied to the XML document by using different encryption keys for different portions of the same XML document. In this way, users obtain only the keys associated with the portions of XML documents for which they have an access right.
In this scenario, cryptographic techniques play also a critical role. The application of cryptographic techniques starts from the classification of users according to their own privileges. A security class can represent a person, a department, or a user group in an organization. The set of rules that specify the information flow between different user classes in the system defines an access control policy. An access control policy can be implemented by using a key assignment scheme, that is, a method to assign a key and some private information to each class. The encryption key will be used by each class to protect its data by means of a symmetric cryptosystem. The private information will be used by each class to compute the keys assigned to its accessible set. This assignment is carried out by a central authority, which is active only at the distribution phase. The main advantages of this solution is that each user is not required to interact with the central authority in order to compute the keys for the classes in its accessible set.
A straightforward implementation of a key assignment scheme requires each class to memorize the encryption keys assigned to all classes in its accessible set. The disadvantage of this solution is that it penalizes users in classes with large accessible sets, since they need to handle more information than users in classes with smaller accessible sets. The problem of reducing the inherent complexity of the above solution was first considered in [AT-83], where an elegant key assignment scheme to solve the access control problem in a system organized as a partially ordered hierarchy (poset) was proposed. In that scheme, the key assigned to each class can be used, along with some public parameters generated by the central authority, to compute the key assigned to any class lower down in the hierarchy. Such a solution requires an expensive operation, the modular exponentiation, in order to perform key derivations; moreover, such a solution does not allow inserting or deleting classes in the hierarchy. Subsequently, many researchers have proposed schemes that either have better performances or allow to modify the hierarchy without regenerating keys from scratch [CHW-92,S-88].
In several situations a user may be assigned to a certain class for only a certain period of time. For example, consider a group of users who jointly work on a project in a specific time interval or a user moving from a working group to another one. In such situations the users need a different key for each time period. Key assignment schemes with temporal constraints (called time-bound schemes) were first proposed in [T-02]. In particular, the author proposed a scheme for partially ordered hierarchies where the key derivation is constrained not only by the hierarchy on the classes, but also by the time period. Unfortunately, in [YY-03] it was shown that the scheme in [T-02] is insecure against collusive attacks. Subsequently, different time-bound schemes have been proposed in [HC-04] and [C-04]. Such schemes have also been shown to be insecure against collusive attacks [TM-05,DFM-06].

Cryptographic techniques for information retrieval
Research in the cryptography community has also considered the theme of information retrieval, with approaches that are independent from the ones developed in the database community (which are based on the use of indexing techniques).
A first example is the PIR scheme (Private Information Retrieval) [CGKS-98], which enables a user to retrieve information privately with respect to the database manager. In other words, the manager, from his own view, does not get any information about the item in which the user is interested in. In the recent years, emphasis in this research area has been given mainly to the realization of efficient, in terms of communication complexity, PIR schemes. Indeed, privacy imposes a substantial overhead on the interaction between the user and the database. Two models have been considered.
In the unconditionally secure model [CGKS-98,BIM-00,IK-99,BIKR-02] user privacy is unconditional, independent of the computational power held by the manager. However, an unconditional secure PIR scheme, to be realized, requires several copies of the same database and, also, that database managers cannot communicate among them. Some papers have weakened such an assumption [IK-99,BDD-01].
In the computational secure model [KO-97,GR-05] user privacy is guaranteed if some reasonable and widely accepted assumptions concerning with the computational power of the database manager are met. In this model, database replication is not needed. Interesting variants of PIR schemes are described in [DIO-01,KO-00,NP-99,OS-99].

Another research theme has considered the support for efficient searches. Searchable encryption (SE) schemes [BDOP-04] allow a user to delegate a third party to execute the search of specific keywords on ciphertexts in such a way that the only information the third party gains is whether or not a number of specified keywords belong to the plaintext. Such encryption schemes avoid the need of providing the third party with the decryption key or with the decrypted plaintext. In the last years a number of searchable encryption schemes have been proposed. The solutions can be divided into two classes: symmetric and asymmetric encryption schemes.
In the symmetric case, in a first stage the user sends to the Application Service Provider (ASP), who manages the data, the encrypted information. In a second stage, the same user or a delegate, the one who possesses the encryption/decryption key, can query the ASP by recovering the proper records. Moreover, the ASP does not get any information neither on the keyword used in the query nor on the recovered information. In [SWP-00] the authors study the problem of searching in encrypted data in the symmetric case. In that paper, the authors proposed a scheme which encrypts each keyword (or each pattern) of a document separately. This scheme is not secure against statistical attacks. In [G-03] the author proposes a scheme that uses Bloom filters. One of the problems of this approach is that Bloom filters induce "false positives", that is, the ASP sends records that are not related to the keyword the user is searching for. Furthermore, the ASP may obtain information on the set of keywords used by the user. In [CM-04] the authors propose a variation of the scheme presented in [G-03] which solves the problem of statistical attacks. However this scheme is not flexible enough to handle updates of the information with arbitrary keywords.
In asymmetric SE schemes, the information is encrypted using the public key of the receiver. This means that anyone may encrypt some information and store it on the ASP so that in a second stage, the intended receiver may recover them. In order to perform a keyword search, the user generates a trapdoor information and sends this information to the ASP. The knowledge of the trapdoor allows the ASP to perform the desired operation while preventing him to gain any information on the keyword or on the information that is associated to it. The first scheme in this class has been presented in [BDOP-04]. In this paper the authors present a scheme that is secure in the random oracle model. The basic tool used in this paper is, essentially, an Id-based encryption (IBE) scheme presented in [BF-04]. Starting from [BDOP-04], the authors in [AB+-05] prove that the existence of anonymous IBE scheme implies the existence of public key searchable encryption schemes. Furthermore, the authors present a construction for an identity-based encryption scheme with keyword search based on the existence of anonymous hierarchical IBE. For the case of complex searches, there are solutions that allow the possibility to perform only conjunctive searches [BKM-01,GSW-04,PKL-04] in the symmetric or asymmetric settings. There is currently no solution that allows to perform arbitrary keyword searches. <<<