Departamento de Computación

El cómputo en la "nube" promete revolucionar la forma en que las empresas manejan, distribuyen y comparten su información. El dueño de los datos (cliente) puede delegar casi todo el procesamiento de la información a la "nube". La nube puede ser vista como una colección de servidores, los cuales proveen el almacenamiento, procesamiento y mantenimiento de los datos del cliente. No hace falta decir que este nuevo concepto de cómputo ha ocasionado un ahorro considerable en términos de costos para el dueño de la información. Entre otros, un servicio importante que provee la nube es el de bases de datos (DAS por sus siglas en inglés). En este servicio el cliente delega la tarea de almacenamiento y mantenimiento de su información a un tercero (servidor no confiable). El modelo DAS permite que el cliente cree, modifique y recuperare información de la base de datos que se encuentra en una ubicación remota. Estas operaciones son realizadas por el servidor en nombre del cliente. Sin embargo, delegar esta tarea a un tercero crea nuevos retos de seguridad. Los dos principales objetivos de la criptografía con respecto a la seguridad son privacidad y autenticación. Estos problemas de seguridad también son relevantes para las bases de datos subcontratadas. El cliente que mantiene sus datos con una tercera entidad no confiable tiene dos preocupaciones importantes: la primera que la información puede ser sensible y por ello puede no querer revelarla al servidor y la segunda es que la información cuyo almacenamiento y mantenimiento ha sido delegado, será utilizada por él. El uso que generalmente se le da a los datos consiste en que el cliente debe poder consultar la base de datos y las respuestas a sus consultas serán generadas por el servidor. Es natural que el cliente este preocupado porque un servidor malicioso no le provea las respuestas correctas. El objetivo de este trabajo es diseñar dos esquemas: uno en el que la base de datos pueda ser cifrada y que aún así se puedan ejecutar consultas y otro en que el cliente pueda verificar si el servidor esta respondiendo de forma correcta. Estos problemas son conocidos como privacidad en bases de datos y procesamiento de consultas autenticado, respectivamente. En esta tesis se estudiaron ambos de manera formal, se plantearon sus definiciones de seguridad, y además se diseñaron esquemas eficientes para resolverlos. Finalmente, se analiza la seguridad de los esquemas propuestos y también se reporta su desempeño.

Abstract

Cloud computing holds the promise of revolutionizing the manner in which enterprises manage, distribute, and share information. The data owner (client) canoutsource almost all his/her information processing tasks to a "cloud". The cloud can be seen as a collection of servers, which caters the data storage, processing and maintenance needs of the client. Needless to say this new concept of computing has already brought significant savings in terms of costs for the data owner. Among others, an important task provided by a cloud is Database as a Service (DAS). In this service the client delegates the duty of storage and maintenance of his data to a third party (an un-trusted server). The DAS model allows the client to create, modify and retrieve data from databases in a remote location. These operations are performed by the server on behalf of the client. However, delegating this duty to a third party brings in some new security challenges. The two main security goals of cryptography are privacy and authentication. These security issues are relevant to the outsourced databases also. The client who keeps the data with an untrusted entity has two main concerns. One being that the data may be sensitive and the client may not want to reveal it to the server and the second one is the data whose storage and maintenance has been delegated would be used by the client. The typical usage of the data would be that the client should be able to query the database and the answers to the client’s queries would be provided by the server. It is natural for the client to be concerned about a malicious server who does not provide correct answers to his queries. In this work we aim to devise two schemes: one in which the client can encrypt the database and still performs queries that are answered by the server and another one where the client would be able to verify whether the server is responding correctly to his queries. The first problem is called privacy in databases and the second one is known as the authenticated query processing. In this thesis we address both of them. We view the above two problems in a formal manner and provide its security definitions. Further we device some efficient schemes which solve them. Finally, we analyze the security of the proposed schemes and also provide some experimental performance data.