Cifrado homomórfico

Craig Gentry, de IBM, ha publicado un algoritmo de cifrado homomórfico completo. ¿Que es un algoritmo de cifrado homomórfico? Supongamos que tenemos un esquema de cifrado (simétrico o asimétrico, da igual, supongamos simétrico) basado en dos funciones E(x,k) que cifra x usando k como clave, y D(x,k) que descifra x usando k como clave. Si el esquema funciona se cumplirá que:

D(E(x,k),k)=x

Pues bien, el algoritmo es homomórfico si además existe un conjunto de pares de funciones (f,f’) que cumplen:

D(f’(E(x,k))=f(x)

Donde f’ puede ser igual a f o no, pero dada f podemos saber f’ (y viceversa). Es decir el cifrado es homomórfico cuando podemos hacer operaciones sobre los datos cifrados, sin descifrarlos, sabiendo como afectará el resultado a los datos en claro.

¿Porque es importante poder hacer esto? Pues supongamos que tenemos externalizada una base de datos donde hay datos confidenciales. El proveedor de almacenamiento ha puesto a nuestra disposición una base de datos relacional y hemos almacenado allí los datos de empleados, cifrando todas las columnas. Si el cifrado no es homomórfico y queremos obtener los empleados que tienen como apellido ‘Apellido’ tendríamos que hacer, de forma esquemática:

1. Descargar toda la tabla de personal (select * from employee)
2. Desencriptar toda la tabla en local (puesto que solo nosotros sabemos la clave)
3. Hacer la consulta de selección sobre los datos desencriptados.

En cambio, si el cifrado fuese homomórfico para las operaciones de cadena (substring) el proceso sería:

1. Cifrar el valor a buscar (’Apellido’). Supongamos que cifrado de apellido es ‘odillepA’.
2. Hacer la consulta: select * from employee where name like ‘%odillepA%’;
3. Desencriptar el resultado de la consulta, que serán solo las filas que nos interesan.

Como podemos ver el segundo caso es mucho más eficiente puesto que usamos más recursos del proveedor de almacenamiento, menos recursos de red y menos recursos nuestros, que al fin y al cabo es lo que se busca al externalizar el almacenamiento.
Un esquema de cifrado es homomórfico completo cuando para toda función f podemos encontrar f’ tal que
D(f’(E(x,k))=f(x)

Es decir, podemos hacer todas las operaciones sobre los datos cifrados sabiendo el efecto que tendrán sobre los datos en claro, pero sin saber cuales son los datos en claro. El que un esquema de cifrado tenga homomorfismo parcial no es raro. Por ejemplo, RSA es homomórfica respecto a la multiplicación. Siendo (Pvk,Pbk) un par de claves (privada, pública), entonces para todo (x,y) se cumple que :

D(E(x*y,Pvk),Pbk)=x*y

El problema del homorfismo completo se creía irresoluble hasta la publicación del artículo al que hacíamos referencia previamente. Bruce Schneier afirma que el algoritmo presentado en el artículo es totalmente impráctico usando la tecnología actual y calcula que, según la ley de Moore pasarán unos 40 años antes de que una búsqueda realizada sobre datos cifrados con este algoritmo sea tan eficiente como una búsqueda sobre datos en claro actualmente.

Mas info:
Craig Gentry