Dispositivo y procedimiento de generación de claves con seguridad reforzada para algoritmo de cifrado plenamente homomórfico.

Procedimiento de generación de claves secretas y públicas obtenidas por medio de un algoritmo plenamente homomórfico de clave pública basado en la aritmética sobre los enteros,

denominadas claves secretas y claves públicas vDGHV, con seguridad reforzada, implementado en un dispositivo que comprende al menos un microprocesador (11) y una memoria (14), caracterizado por comprender una etapa de generación de una clave secreta SK correspondiente a un número aleatorio p primo o producto de números primos cuyos tamaño y composición se eligen

de modo que la operación de factorización de dicho número aleatorio p sea irrealizable por parte de un atacante.

Dispositivo y procedimiento de generación de claves con seguridad reforzada para algoritmo de cifrado plenamente homomórfico

1. Campo de la invención

El campo de la invención es el de los dispositivos de cifrado llamado plenamente homomórfico.

Más exactamente, la invención se refiere a la implementación de operaciones y de procesamientos numéricos de generación de claves destinadas a un algoritmo de cifrado homomórfico implementado en microprocesadores, y ello al objeto de proveer de un nivel de seguridad significativamente más elevado que la técnica anterior.

La invención se refiere, muy particularmente, a las infraestructuras y dispositivos de generación de claves.

2. Técnica anterior

2.1. Criptografía de clave pública

El procesamiento criptográfico de datos numéricos muchas veces requiere efectuar operaciones de cifrado de clave pública.

En un algoritmo de cifrado de clave pública, el cifrador cifra un mensaje m con el concurso de un algoritmo de cifrado E en un cifrado c = E (PK, m) , con el concurso de una clave pública, denotada por PK.

El destinatario del mensaje descifra el cifrado c aplicando una función de descifrado D tal que m = D (SK, c) donde SK es una clave secreta vinculada a la clave pública PK.

Las claves pública y secreta (respectivamente PK y SK) son generadas con el concurso de un algoritmo probabilístico llamado algoritmo de generación de claves.

Por ejemplo, son algoritmos célebres de cifrado de clave pública el algoritmo llamado RSA descrito en la patente estadounidense U.S. 4.405.829, o el intercambio de claves Diffie-Hellman descrito en la patente estadounidense U.S. 4.200.770.

2.1. Criptografía plenamente homomórfica de clave pública

Reviste un particular interés, para numerosas aplicaciones prácticas, disponer de un Algoritmo Plenamente Homomórfico de Clave Pública (APHCP) .

Un APHCP incluye, aparte de los algoritmos E y D, otros dos algoritmos denotados por ADD y MUL que tienen, para todo mensaje m[1] y m[2], las siguientes propiedades:

m[1] m[2] = D (SK, MUL (E (PK, m[1]) , E (PK, m[2]) ) )

m[1] + m[2] = D (SK, ADD (E (PK, m[1]) , E (PK, m[2]) ) )

Es posible demostrar que, aun si las operaciones m[1] + m[2] y m[1] m[2] se entienden como módulo 2 (a saber, "+" representa la operación lógica de "o-exclusivo" y "" representa la "y lógica") , se puede codificar cualquier procesamiento complejo de datos con el concurso de estas dos únicas operaciones.

Las aplicaciones de los APHCP son múltiples:

- Unos APHCP permiten, por ejemplo, efectuar cálculos sobre los datos médicos de pacientes que figuran en una base de datos sin tener que revelar por ello su identidad.

- Unos APHCP permiten conocer el número de votos obtenidos por los candidatos de una elección sin que se desvele la identidad de los votantes.

- Unos APHCP permiten la creación de protocolos de pago anónimos.

- Unos APHCP permiten la creación de un sistema de ventas donde la cuantía de las pujas se mantendría desconocida, con el fin de evitar que el vendedor tienda a la sobrepuja. Sólo se desvelaría, al final del procedimiento, la mayor cuantía.

Un primer APHCP fue publicado por Craig Gentr y en el documento D1 correspondiente al artículo titulado "Fully Homomorphic Encr y ption Using Ideal Lattices" publicado en las actas del coloquio 41st ACM Symposium on Theor y of Computing (STOC) , 2009. Por la gran complejidad de implementación de la que adolece este procedimiento, fue propuesto un segundo procedimiento de APHCP, basado en la aritmética sobre los enteros, por Marten van Dijk, Craig Gentr y , Shai Halevi, y Vinod Vaikuntanathan (vDGHV) en el documento D2 correspondiente al artículo titulado

"Fully Homomorphic Encr y ption over the Integers" publicado en las actas del coloquio EUROCRYPT2010, en las páginas 24 a 43.

Los documentos D1 y D2 se incorporan a la presente memoria descriptiva como referencia.

2.2. Método vDGHV

En el método vDGHV, el procedimiento de generación G de claves secretas y públicas empieza por generar un número impar p correspondiente a una clave secreta SK, denominada clave secreta vDGHV, y una clave pública PK, denominada clave pública vDGHV correspondiente a una colección de números enteros x[i] = q[i] p + r[i] para i desde 0 a k, siendo q[i] y r[i] números aleatorios que cumplen con las imposiciones especificadas en el documento D2.

Los números x[i] son tales que r[i] es de pequeño tamaño con relación a x[i] (por ejemplo, r[i] es un número de 80 ó 100 bits) .

Uno de los elementos de la clave pública vDGHV, el elemento denotado por x[0], presenta una particularidad: para el elemento x[0], debe cumplirse la siguiente condición inicial: r[0] = 0.

Con objeto de cifrar (por intermedio del algoritmo E) un bit m, el originador calcula: c = m + 2r + 2Z donde:

r es un número aleatorio de tamaño más o menos similar al de los r[i] (pudiendo ser la diferencia, por ejemplo, de un bit o dos) ;

Z = x[1] e[1] + ... + x[k] e[k] donde los e[i] son bits aleatorios (es decir, e[i] = 0 ó 1 de manera aleatoria) . Con objeto de descifrar (por intermedio del algoritmo D) un cifrado c, el receptor calcula: m = (c mod p) mod 2. La implementación de las operaciones ADD y MUL utiliza la técnica llamada de "bootstrapping" (correspondiente a

una técnica de inferencia estadística) , conocida para un experto en la materia y descrita en el documento D2.

2.3. Implementación del procedimiento de generación G de claves vDGHV mediante un microprocesador que se comunica con un soporte físico generador aleatorio.

El procedimiento de generación de la clave pública vDGHV, que se ha tratado anteriormente, se implementa en un dispositivo físico 10 cuya arquitectura física se ilustra mediante la figura 1.

Un microprocesador 11 se halla conectado a un medio de interfaz de entrada y de salida de datos 12, a un generador aleatorio 13 y a una memoria 14 de la que el microprocesador lee las instrucciones que codifican un programa Pg que implementa el procedimiento de generación G de claves vDGHV.

En el inicio, el microprocesador 11 empieza a leer el programa Pg de la memoria 14. En su ejecución en el microprocesador 11, el programa Pg genera la clave secreta SK correspondiente a un número impar p, y la clave pública PK = x[0], ..., x[k].

Una vez obtenidos los elementos x[i], el programa Pg da al microprocesador 11 la instrucción de comunicar los elementos x[0], ..., x[k], por intermedio de la interfaz de entrada y de salida de datos 12, con destino a otro dispositivo.

El procedimiento de generación G de claves vDGHV, ilustrado por la figura 2, implementa las siguientes etapas (en cualquier orden) :

Definir r[0] = 0;

generar un número aleatorio impar p (correspondiente a la clave secreta SK) ;

generar k números aleatorios r[i] denotados por r[1], ..., r[k];

generar k+1 números aleatorios q[i] denotados por q[0], ..., q[k].

Seguidamente se implementa una etapa de obtención con el fin de determinar los elementos x[i] = q[i] p + r[i] para i desde 0 a k, definitorios de la clave pública PK.

2.4. Inconvenientes de la técnica anterior El procedimiento de generación G de claves vDGHV anteriormente mencionado presenta una brecha de seguridad. En efecto, en la medida en que la clave secreta SK se corresponde con el número p que es un número impar aleatorio, es perfectamente posible que este número p pueda escribirse como un producto de factores primos:

a[1] a[L]

p p[1] p[L] .

... En el presente caso, los números p[i] representan números primos y los enteros a[i] representan potencias, es decir, el número de veces que cada p[i] aparece en la clave secreta p.

Para un experto en la materia, es sabido que existen métodos que permiten descomponer por completo o parcialmente p en factores primos. Por ejemplo, un primer método, conocido con el nombre de factorización en curva elíptica de Lenstra, permite extraer ciertos factores primos de números enteros. Este primer método se encuentra descrito en el artículo de Lenstra Jr., H. W. "Factoring integers with elliptic curves" publicado en la revista Annals of Mathematics (2) 126 (1987) páginas 649 a 673 e incorporado como referencia. Un segundo método conocido con el nombre de algoritmo de factorización por criba sobre los cuerpos de números generalizado también permite obtener tal descomposición.

Aplicando un método de factorización de este tipo a la clave pública x[0] = p q[0] = q[0] p[1][1] ... p[L][L], un ocasional atacante podría descubrir al menos un factor p[j] integrante de la composición... [Seguir leyendo]

1. Procedimiento de generación de claves secretas y públicas obtenidas por medio de un algoritmo plenamente homomórfico de clave pública basado en la aritmética sobre los enteros, denominadas claves secretas y claves públicas vDGHV, con seguridad reforzada, implementado en un dispositivo que comprende al menos un microprocesador (11) y una memoria (14) , caracterizado por comprender una etapa de generación de una clave secreta SK correspondiente a un número aleatorio p primo o producto de números primos cuyos tamaño y composición se eligen

de modo que la operación de factorización de dicho número aleatorio p sea irrealizable por parte de un atacante.

2. Procedimiento de generación de claves según la reivindicación 1, caracterizado por comprender las siguientes etapas:

(a) Definir r[0] = 0;

(b) generar dicha clave secreta SK correspondiente a dicho número aleatorio p;

(c) generar k números aleatorios r[i] denotados por r[1], ..., r[k];

(d) generar k+1 números aleatorios q[i] denotados por q[0], ..., q[k];

(e) formar elementos x[i] = q[i] p + r[i] para i desde 0 a k, definitorios de una clave pública PK;

(f) devolver dicha clave pública PK = {x[0], ..., x[k]} y la clave secreta SK = p.

3. Dispositivo que comprende al menos un microprocesador (11) conectado a un medio de interfaz de entrada y de salida de datos (12) , a un generador aleatorio (13) de claves secretas y públicas obtenidas por medio de un algoritmo plenamente homomórfico de clave pública basado en la aritmética sobre los enteros, denominadas claves secretas y claves públicas vDGHV, con seguridad reforzada, y a una memoria (14) en la que dicho microprocesador implementa medios de generación de una clave secreta SK correspondiente a un número aleatorio p primo o producto de números primos cuyos tamaño y composición se eligen de modo que la operación de factorización de dicho número aleatorio p sea irrealizable por parte de un atacante.

4. Dispositivo según la reivindicación 3, caracterizado por que dicho microprocesador (11) implementa medios de generación de una clave secreta SK correspondiente a un número primo aleatorio p.

5. Producto programa de ordenador, que comprende instrucciones de código de programa para la implementación del procedimiento según al menos una de las reivindicaciones 1 a 2 cuando dicho programa se ejecuta en un ordenador.

6. Medio de almacenamiento legible por ordenador y no transitorio, que almacena un programa de ordenador que comprende un juego de instrucciones ejecutables por un ordenador o un procesador para llevar a la práctica el procedimiento según al menos una de las reivindicaciones 1 a 2.