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.

Tipo: Patente Internacional (Tratado de Cooperación de Patentes). Resumen de patente/invención. Número de Solicitud: PCT/EP2012/057879.

Solicitante: COMPAGNIE INDUSTRIELLE ET FINANCIERE D'INGENIERIE INGENICO.

Nacionalidad solicitante: Francia.

Dirección: 28-32, boulevard de Grenelle 75015 Paris FRANCIA.

Inventor/es: NACCACHE, DAVID, CORON, JEAN-SEBASTIEN, TIBOUCHI,MEHDI.

Fecha de Publicación: .

Clasificación Internacional de Patentes:

  • H04L9/00 SECCION H — ELECTRICIDAD.H04 TECNICA DE LAS COMUNICACIONES ELECTRICAS.H04L TRANSMISION DE INFORMACION DIGITAL, p. ej. COMUNICACION TELEGRAFICA (disposiciones comunes a las comunicaciones telegráficas y telefónicas H04M; selección H04Q). › Disposiciones para las comunicaciones secretas o protegidas.
  • H04L9/30 H04L […] › H04L 9/00 Disposiciones para las comunicaciones secretas o protegidas. › Clave pública, es decir, siendo imposible de invertir por computador el algoritmo de cifrado, y no exigiéndose secreto a las claves de cifrado de los utilizadores.

PDF original: ES-2546560_T3.pdf

 


Fragmento de la descripción:

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]

 


Reivindicaciones:

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.

 

Patentes similares o relacionadas:

Sistema y método de autenticación y encriptación a prueba de intercepción, del 6 de Mayo de 2020, de Ni, Min: Metodo para autenticar a un usuario mediante el uso de un codigo de acceso predeterminado almacenado electronicamente que comprende un numero predeterminado […]

Método y sistema para aprovisionamiento y almacenamiento de clave criptográfica mediante criptografía de curva elíptica, del 26 de Febrero de 2020, de MasterCard International Incorporated: Un método para distribuir múltiples claves criptográficas usadas para acceder a datos, que comprende: recibir , por un dispositivo de recepción de un servidor […]

Procedimiento de voto con cadena de firmas, del 11 de Diciembre de 2019, de Siemens Mobility GmbH: Procedimiento de voto con cadena de firmas que comprende los siguientes pasos: a) provision de una pluralidad M de replicantes (R1, R2, RM) […]

Procedimiento y aparato para la transmisión de entramado con integridad en un sistema de comunicación inalámbrica, del 6 de Noviembre de 2019, de QUALCOMM INCORPORATED: Un procedimiento para el entramado de paquetes en un sistema de transmisión inalámbrico que admite transmisiones de radiodifusión, el procedimiento que comprende: […]

Sistema de comunicación de datos basado en la unidad de filtro que incluye una plataforma de cadena de bloques, del 6 de Noviembre de 2019, de SIEMENS AKTIENGESELLSCHAFT: Sistema adaptado para realizar la comunicación de datos, que comprende una primera interfaz adaptada para comunicarse con una primera […]

Procedimiento y sistema para la comunicación segura entre una etiqueta RFID y un dispositivo de lectura, del 10 de Abril de 2019, de Giesecke+Devrient Mobile Security GmbH: Procedimiento para la comunicación segura entre una etiqueta RFID (20a, 20b) y un dispositivo de lectura (30a, 30b), comprendiendo el procedimiento las […]

Sistema de autenticación persistente que incorpora códigos de acceso de un solo uso, del 3 de Abril de 2019, de Haventec PTY LTD: Un método para mantener una autenticación continuada del usuario de una aplicación sin la necesidad de introducir y re-introducir un nombre de […]

Sistema de procesamiento de cifrado, dispositivo de generación de claves, dispositivo de cifrado, dispositivo de desciframiento, dispositivo de delegación de claves, método de procesamiento de cifrado y programa de procesamiento de cifrado, del 11 de Febrero de 2019, de MITSUBISHI ELECTRIC CORPORATION: Un sistema de procesamiento criptográfico 10 que realiza un proceso criptográfico utilizando una base Bt y una base B*t para cada número entero t de […]

Utilizamos cookies para mejorar nuestros servicios y mostrarle publicidad relevante. Si continua navegando, consideramos que acepta su uso. Puede obtener más información aquí. .