Departamento de Computación

Mantener la privacidad en la información ha cobrado mayor importancia en las últimas décadas. Con el surgimiento de Internet y la centralización de los datos, es cada vez más necesario dotar de seguridad a nuestra información para protegerla contra robos, plagios, extorsiones, etc. Gracias a este gran avance tecnológico en la comunicación global nació DaaS (Database as a Service), una arquitectura que ofrece el servicio de hosting de bases de datos brindando la comodidad de administrar las bases de datos y permitir consultas desde cualquier terminal que pueda conectarse a Internet. A pesar de que estas empresas que prestan el servicio de hosting de datos ofrecen cierto nivel de seguridad para que solamente el poseedor de la misma pueda consultarla, el prestatario del servicio tiene acceso total a nuestra información. Para cubrir este aspecto se ha hecho uso de las bondades de seguridad que la Criptografía ofrece. Han surgido diversos esquemas que cifran por completo la base de datos con el fin de que el prestatario del servicio no pueda ser capaz de interpretar la información; lo malo es que para realizar consultas a la base de datos cifrada el tiempo de espera del cliente es bastante significativo ya que para realizar la consulta se deben realizar diversas funciones de descifrado y así obtener la información en claro. Es por esta razón que nos sentimos motivados a diseñar un modelo que permita satisfacer consultas eficientes y seguras en una base de datos bajo el contexto DaaS. Este trabajo de tesis presenta un esquema que en vez de cifrar por completo la base de datos, fragmenta la información y gracias a esto, gran parte de la información puede permanecer en texto claro. Fragmentar la base de datos implica separar aquellos atributos que juntos nos denotan información valiosa, como puede ser el nombre de un empleado y su sueldo, y cifrar la relación existente entre estos datos. Así, fragmentar los datos trae grandes beneficios tanto en tópicos de seguridad como en eficiencia; debido a que las consultas se realizan a los datos en texto claro, éstas son realizadas en tiempo real y generadas por el motor de búsqueda del Sistema Manejador de Bases de Datos. Además, nuestro esquema no sólo se preocupa por la seguridad de la información, sino también de la autenticidad de la misma; si un dato no ha sido autenticado, no podemos saber si éste ha sido modificado de forma intencional o accidental. Es por este motivo que los datos cifrados en nuestro esquema son autenticados mediante un cifrado con autenticación.
Por otra parte, y ya que la fragmentación de la base de datos es un problema NP-difícil debido a que corresponde al mismo problema de coloración de hipergrafos, se diseño e implementó una heurística que permitiera resolver este problema y minimizar el número de fragmentos. Se diseño un algoritmo genético que permitiera realizar la fragmentación y se comparó directamente contra otra heurística mostrada en la literatura; los resultados obtenidos fueron bastante satisfactorios, nuestro algoritmo genético obtuvo significativamente menos fragmentos de los obtenidos con la otra heurística. .

Abstract

During the last decade privacy of information has gained a lot of attention. With the rapid expansion of the internet and centralized data storage mechanisms it has become very important to protect the stored information against non-authorized access and processing. Rapid technological development has brought many new data storage solutions, one of them is Database as a Service (Daas). DaaS is a specific architecture providing database hosting services. In the DaaS model, the owner of the data delegates the duty of maintaining his/her data to a third party (called the server) which hosts the database and process his/her queries. These kind of service providers which provides the service of data hosting may add some security mechanism on the stored data, but the service provider has full access to it. It is undesirable as the owner may not want to reveal the data to the server. Numerous cryptographic techniques can be used by the owner to protect the data. But such an encryption applied to the whole data brings in a new problem: the server needs to process queries on the encrypted data. Last said would be very inefficient, as a good encryption scheme would destroy all the structure which exists in the original data, hence indexing and other techniques generally applied for efficient query processing can no longer be applied. Thus specialized cryptographic schemes are required.
In this thesis we deal with the problem of secure storage in the DaaS model which is friendly to efficient query processing. We present a scheme in which instead of encrypting the total database, we fragment the information and encrypt only parts of it. By using this strategy the majority of the information stays un-encrypted, and thusquery processing can also be done efficiently. Fragmenting a database implies to separate those attributes which have a sensitive association between them. For example, in an employees database the individual attributes employee name and salary are not themselves sensitive, but the association between them is not revealed. Fragmentation of a database provides some security to the data without hampering the ease of query processing, and they can be done by the database management system without much extra overhead. Our scheme also adds an additional security service of authentication along with encryption. Authentication allows detection of accidental or intentional changes made within a database. We obtain authentication by using a primitive called authenticated encryption. The other part which the thesis deals with is the problem of creating fragments. The problem of creating minimum fragments is the same as the minimum hyper-graph coloring problem which is known to be NP hard. We developed a heuristic based on genetic algorithm to create the minimum number of fragments given a database. Our scheme gives significantly lesser number of fragments compared to other heuristics reported in the literature.