A framework for implementing outsourcing schemes

Resumen

En esta tesis se aborda el problema de la externalización segura de servicios de datos
y computación. El escenario de interés es aquel en el que el usuario posee datos y
quiere subcontratar un servidor en la nube (“Cloud”). Además, el usuario puede
querer también delegar el cálculo de un subconjunto de sus datos al servidor. Se
presentan dos aspectos de seguridad relacionados con este escenario, en concreto,
la integridad y la privacidad y se analizan las posibles soluciones a dichas cuestiones,
aprovechando herramientas criptográficas avanzadas, como el Autentificador
de Mensajes Homomórfico (“Homomorphic Message Authenticators”) y el Cifrado
Totalmente Homomórfico (“Fully Homomorphic Encryption”).
La contribución de este trabajo es tanto teórica como práctica. Desde el punto de
vista de la contribución teórica, se define un nuevo esquema de externalización (en
lo siguiente, denominado con su término inglés Outsourcing), usando como punto
de partida los artículos de [3] y [12], con el objetivo de realizar un modelo muy
genérico y flexible que podría emplearse para representar varios esquemas de ”outsourcing”
seguro. Dicho modelo puede utilizarse para representar esquemas de “outsourcing”
seguro proporcionando únicamente integridad, únicamente privacidad o,
curiosamente, integridad con privacidad. Utilizando este nuevo modelo también se
redefine un esquema altamente eficiente, construido en [12] y que se ha denominado
Outsourcinglin. Este esquema permite calcular polinomios multivariados de grado
1 sobre el anillo Z2k . Desde el punto de vista de la contribución práctica, se ha
construido una infraestructura marco (“Framework”) para aplicar el esquema de
“outsourcing”. Seguidamente, se ha testado dicho “Framework” con varias implementaciones,
en concreto la implementación del criptosistema Joye-Libert ([18]) y
la implementación del esquema propio Outsourcinglin.
En el contexto de este trabajo práctico, la tesis también ha dado lugar a algunas
contribuciones innovadoras:
el diseño y la implementación de un nuevo algoritmo de descifrado para el
esquema de cifrado Joye-Libert, en colaboración con Darío Fiore. Presenta un
mejor comportamiento frente a los algoritmos propuestos por los autores de
[18];la implementación de la función eficiente pseudo-aleatoria de forma amortizada
cerrada (“amortized-closed-form efficient pseudorandom function”) de
[12]. Esta función no se había implementado con anterioridad y no supone
un problema trivial, por lo que este trabajo puede llegar a ser útil en otros
contextos.
Finalmente se han usado las implementaciones durante varias pruebas para medir
tiempos de ejecución de los principales algoritmos.---ABSTRACT---In this thesis we tackle the problem of secure outsourcing of data and computation.
The scenario we are interested in is that in which a user owns some data and wants to
“outsource” it to a Cloud server. Furthermore, the user may want also to delegate
the computation over a subset of its data to the server. We present the security
issues related to this scenario, namely integrity and privacy and we analyse some
possible solutions to these two issues, exploiting advanced cryptographic tools, such
as Homomorphic Message Authenticators and Fully Homomorphic Encryption.
Our contribution is both theoretical and practical. Considering our theoretical
contribution, using as starting points the articles of [3] and [12], we introduce a new
cryptographic primitive, called Outsourcing with the aim of realizing a very generic
and flexible model that might be employed to represent several secure outsourcing
schemes. Such model can be used to represent secure outsourcing schemes that provide
only integrity, only privacy or, interestingly, integrity with privacy. Using our
new model we also re-define an highly efficient scheme constructed in [12], that we
called Outsourcinglin and that is a scheme for computing multi-variate polynomials
of degree 1 over the ring Z2k. Considering our practical contribution, we build a
Framework to implement the Outsourcing scheme. Then, we test such Framework to
realize several implementations, specifically the implementation of the Joye-Libert
cryptosystem ([18]) and the implementation of our Outsourcinglin scheme.
In the context of this practical work, the thesis also led to some novel contributions:
the design and the implementation, in collaboration with Dario Fiore, of a new
decryption algorithm for the Joye-Libert encryption scheme, that performs
better than the algorithms proposed by the authors in [18];
the implementation of the amortized-closed-form efficient pseudorandom function
of [12]. There was no prior implementation of this function and it represented
a non trivial work, which can become useful in other contexts.
Finally we test the implementations to execute several experiments for measuring
the timing performances of the main algorithms.