Resumen

En la actualidad la mayoría de compañías requieren manejar una gran cantidad de información para que su funcionamiento sea correcto. Con el objetivo de que estos datos sean almacenados, administrados y procesados; el dueño (el cliente) debe invertir recursos especializados con los que posiblemente no cuente. Por ello el cliente puede delegar esta tarea a un tercero (el servidor). Este modelo es conocido como Database as a Service (DAS) y ha cobrado popularidad e importancia para la tendencia del cómputo nube. Además brinda a los clientes la capacidad de crear, almacenar, modificar y consultar información desde un lugar remoto; todas estas operaciones son realizadas por el servidor como representante del cliente. Al delegar la gestión de la base de datos a un tercero surgen nuevos problemas, entre los más importantes se encuentran la confidencialidad y la disponibilidad de los datos. Debido a que el servidor tiene acceso a toda la información, éste podría divulgarla, modificarla o destruirla. Por lo que surge una importante pregunta que debe ser resuelta en este contexto: ¿Bajo qué condiciones es posible delegar una base de datos a un servidor que no es confiable?

La solución obvia es el cifrado de la información. El cliente puede cifrar sus datos antes de almacenarlos en el servidor y con esto se soluciona el problema de confidencialidad. El servidor tiene otras responsabilidades además de almacenar la información, como es el ejecutar ciertas operaciones: procesar consultas, modificar, etc. El utilizar criptografía clásica trae consigo otros problemas, ya que un buen esquema de cifrado debe destruir la estructura natural presente en la información, lo que generalmente causa la reducción de la eficiencia en el procesamiento de consultas y otro tipo de operaciones como (insertar, modificar, consultar, etc.), debido a que no pueden ser efectuadas bajo los mecanismos que una base de datos utiliza normalmente. Entonces, el reto consiste en construir un esquema de cifrado que permita que la información del cliente sea cifrada y almacenada en el servidor no confiable sin que la confidencialidad pueda ser violada, además las primitivas criptográficas utilizadas deben permitir que las operaciones que son de interés para el cliente puedan ser ejecutadas por el servidor en la información cifrada sin tener conocimiento de los datos originales.

El esquema de cifrado propuesto en esta tesis logra dos objetivos que se encuentran en conflicto, el brindar seguridad y también permitir que las consultas puedan ser procesadas. Nuestra propuesta utiliza diferentes tipos de primitivas criptográficas: un cifrador por bloques (AES), un cifrador basado en homomorfismo (Paillier 1999) y un cifrador que preserva el orden (Boldyreva et.al. 2009); los cuales se aplican a diferentes tipos de datos, permitiendo así que una gran variedad de operaciones puedan ser procesadas en información cifrada de manera eficiente.

Now-a-days almost every company needs to handle an enormous amount of information for its proper functioning. Storage, maintenance and processing of such enormous amount of data needs lot of resources and expertise which the owner of the data (the client) may not have. Thus the client may delegate the duty of storage and maintenance of his/her data to a third party (the server). This model commonly known as as Database as a Service (DAS) has gained lot of popularity in the recent times, also this model is very important in the context of the emerging concept of cloud computing. The DAS model allows the client to perform operations like create, modify and retrieve from a remote location. These operations are performed by the server on behalf of the client. Delegating the duty of storing and maintaining the database to a third party brings in some new problems. The privacy and availability of the data being of primary importance among them. As the server which stores and maintains the data has access to all the information, can potentially disclose, modify or damage the stored information. Thus the important question which has to be solved in this context is: under what conditions one can delegate a database to an un-trusted server.

The most obvious solution comes through data encryption. The client can encrypt the data before delegating it to the server and thus may provide a solution to the problem of privacy. However, normal encryption brings in some new problems. The server is not only responsible for storing the data, but it also performs certain operations on the data like processing queries, updating etc. on behalf of the client. A good encryption scheme is supposed destroy all natural structure present in the data which is generally detrimental to efficient query processing and performing other important operations on the stored data. Moreover, the normal database mechanisms to perform the operations (like create, modify, retrieve etc.) can no longer be used on the encrypted information. Thus, the challenge is to come up with an encryption mechanism which allows the storage of the encrypted information in an un-trusted server without breach of privacy, moreover the encryption applied should be such that normal operations which are of interest to the client can be performed on the encrypted data by the server without the knowledge of the original data. In this thesis we propose an encryption mechanism which achieves the two conflicting objectives of providing security and also being friendly to query processing. Our proposal uses different types of encryption primitives depending on the type of the data. In particular, we use a block cipher (AES), a homomorphic encryption scheme (Paillier 1999) and an order preserving encryption scheme (Boldyreva et al. 2009) in a specific manner such that it allows a variety of operations can be carried out on the encrypted data. Our encryption mechanism allows a large class of queries to be processed on the encrypted data with significant efficiency.