ES2532332T3 - Sistema de compartición de secretos, aparato de compartición, aparato de gestión de partes, aparato de adquisición, métodos de procesamiento de los mismos, método de compartición de secretos, programa y medio de grabación - Google Patents

Abstract

Un sistema de compartición de secretos caracterizado por que comprende un aparato de compartición (110); - >= L h 1 ( ) a a aparatos de gestión de partes PA(a , h(a )) donde a >= 1, ..., L, L > 2, h(a ) >= 1, ..., H(a ), H(a ) > 2; y un aparato de adquisición (130); en donde el aparato de compartición (110) incluye unidades de compartición de secretos (114-a ) adaptadas para generar partes SH(a , h(a )) compartiendo secretos de información secreta con un esquema de compartición de secretos separadamente para subconjuntos respectivos SUB(a ) cada uno de los cuales está formado de H(a ) aparatos de gestión de partes PA(a , 1), ..., PA (a , H(a )) y para sacar las partes SH (a , h(a )); los aparatos de gestión de partes PA (a , h(a )) incluyen generadores de valores de secretos compartidos (124-a -h(a )) adaptados para generar valores de secretos compartidos DSH(a , h(a )) y sacar los valores de secretos compartidos DSH(a , h(a )) respectivamente, cada uno de los valores de secretos compartidos DSH(a , h(a )) que se genera realizando una operación común a una de las partes SH(a , h(a )) y la información común que contiene uno de los valores comunes s (a ), cada uno de los valores comunes s (a ) que está compartido en cada uno de los subconjuntos SUB(a ), la información común usada por los aparatos de gestión de partes PA(a , h(a )) que pertenecen al mismo de los subconjuntos SUB(a ) que es el mismo y los aparatos de gestión de partes PA(a , h(a )) que pertenecen al mismo de los subconjuntos SUB(a ) que realizan la misma operación común; el aparato de adquisición (130) incluye: unidades de reconstrucción (134-a ) adaptados para generar valores de secretos reconstruidos SUBSK(a ) que corresponden a los subconjuntos SUB(a ) respectivamente, cada uno de los valores de secretos reconstruidos SUBSK(a ) que se genera realizando un procesamiento de reconstrucción con el esquema de compartición de secretos para cada uno de los subconjuntos SUB(a ), usando una pluralidad de los valores de secretos compartidos DSH(a , h(a )) que corresponde al mismo de los subconjuntos SUB(a ); y una unidad de composición (137) adaptada para generar información de generación SK usando los valores de secretos reconstruidos SUBSK(a ) y para sacar la información de generación SK.

Description

E10767169

06-03-2015

DESCRIPCIÓN

Sistema de compartición de secretos, aparato de compartición, aparato de gestión de partes, aparato de adquisición, métodos de procesamiento de los mismos, método de compartición de secretos, programa y medio de grabación

5

CAMPO TÉCNICO La presente invención se refiere a técnicas de compartición de secretos.

ANTECEDENTES DE LA TÉCNICA

10 El almacenamiento de información secreta implica el riesgo de pérdida o destrucción de la información secreta y el riesgo de robo. El riesgo de pérdida o destrucción se puede reducir almacenando una pluralidad de copias de la información secreta. Esto, no obstante, aumenta el riesgo de robo. Una solución para eliminar estos riesgos es un esquema de compartición de secretos (SSS) (referencia a la bibliografía no de patente 1 y 2, por ejemplo).

15 En el esquema de compartición de secretos, se generan una pluralidad de partes SH(1) a SH(N) a partir de la información secreta MSK y se gestionan separadamente por una pluralidad de aparatos de gestión de partes PA(1) a PA(N) y la información secreta MSK se puede reconstruir solamente cuando se obtiene un número predeterminado

o mayor de partes entre las partes SH(1) a SH(N). Un método típico para el esquema de compartición de secretos se describirá a continuación.

20

[Esquema de compartición de secretos de umbral (N,N)]

En un esquema de compartición de secretos de umbral (N, N), si se dan todas las partes SH(1) a SH(N), se puede reconstruir la información secreta MSK, mientras que si se dan cualesquiera (N – 1) partes SH(φ 1) a SH(φ N-1), 25 nunca se puede obtener la información secreta MSK. Un ejemplo se dará más adelante.

-SH1, …, SHN-1 se seleccionan aleatoriamente. -SHN = MSK – (SH1 + … + SH N-1) se calcula. -Las partes SH1, …, SHN se gestionan separadamente por una pluralidad de aparatos de gestión de partes

30 PA(1), …, PA(N). -Si se dan todas las partes SH1, …, SHN, se puede reconstruir la información secreta MSK por el procesamiento de reconstrucción representado como MSK = SH1 + … + SHN.

La operación MSK = SH1 + … + SHN para reconstruir la información secreta MSK a partir de las partes SH1 a SHN es

35 lineal. Si el procesamiento de reconstrucción se realiza con los resultados de la misma operación lineal CALC para las partes individuales, usando las partes SH(1) a SH(N) y un valor σ como operandos, los resultados que son las partes SH’(1) a SH’(N), se puede obtener el resultado de la operación lineal CALC usando la información secreta MSK y el valor σ como operandos. Si el procesamiento de reconstrucción se ejecuta con SH’(1) = σ ·SH(1), …, SH’(N) = σ ·SH(N) como las partes SH’(1), …, SH’(N), se puede obtener lo siguiente, por ejemplo.

40

σ ·SH(1) + … + σ ·SH(N) = σ ·(SH(1) + … + SH(N)) = σ ·MSK (1)

45 Por otra parte, si el procesamiento de reconstrucción se ejecuta con los resultados de la misma operación lineal CALC para las partes individuales, usando las partes SH(1) a SH(N) y los valores independientes σ (1) a σ (N) como operandos, los resultados que son las partes SH’(1) a SH’(N), no se puede obtener normalmente el resultado de la operación usando la información secreta MSK como operando. Si el procesamiento de reconstrucción se ejecuta con SH’(1) = σ (1)·SH(1), …, SH’(N) = σ (N)·SH(N) como las partes SH’(1), …, SH’(N), se puede obtener lo

50 siguiente, por ejemplo.

σ (1)·SH(1) + … + σ (N)·SH(N) (2)

[Esquema de compartición de secretos de umbral (K, N)] 55 En un esquema de compartición de secretos de umbral (K, N), si se dan cualesquiera K partes diferentes SH(φ 1) a

SH(φ K), se puede reconstruir la información secreta MSK, mientras que si se dan cualesquiera (K – 1) partes

SH(φ 1) a SH(φ K-1), nunca se puede obtener la información secreta MSK. Se da un ejemplo más adelante.

-Se selecciona aleatoriamente un polinomio de grado de orden (K – 1) f(x) = ξ 0+ ξ 1 ·x+ ξ 2 ·x 2 + … + ξ K-1

60 ·x K-1 que satisface f(0) = MSK. Es decir, se especificaξ 0 = MSK y se seleccionan aleatoriamenteξ 1a ξ k-1.

E10767169

06-03-2015

Las partes se dan por SH ρ =( ρ , f( ρ )) ( ρ = 1 aN). -Si se obtienen cualesquiera K partes diferentes SH(φ 1) a SH(φ K) ((φ 1, …, φ K) ⊂ (1, …, N)), la información secreta MSK se puede reconstruir por el procesamiento de reconstrucción siguiente, usando la Expresión de interpolación de Lagrange, por ejemplo.

imagen1

10 Aquí, el símbolo

imagen2indica que el operando de orden ρ [elemento (φρ -φρ ) del denominador, elemento (x φρ ) del numerador] no está presente desde el principio. El denominador de la Expresión (4) es

imagen3

15 y el numerador de la Expresión (4) es

imagen4

Estas relaciones mantienen en el campo.

20

La operación de la Expresión (3) es lineal. Un valor reconstruido con los resultados de la misma operación lineal CALC para partes individuales, que usa las partes SH(φ 1) a SH(φ K) y el valor σ como operandos, los resultados

que son las partes SH(φ 1) a SH(φ K), llegan a ser iguales al resultado de la operación lineal CALC que usa la información secreta MSK y el valorσ como operandos. Si un valor se reconstruye con los resultados de la misma 25 operación lineal CALC para las partes individuales usando las partes SH(φ 1) a SH(φ K) y los valores independientes

σ (φ 1) a σ (φ K) como operandos, los resultados que son las partes SH’(φ 1) a SH’(φ K), el resultado de la operación que usa la información secreta MSK como un operando que no se puede obtener normalmente.

La bibliografía no de patente 3 describe esquemas para compartir secretos multinivel entre grupos usando

30 concatenación de códigos Reed-Solomon. En los esquemas propuestos se puede reconstruir un secreto de nivel inferior por un número de grupos menor, mientras que reconstruir un secreto de nivel mayor necesita la colaboración de un número de grupos mayor.

A partir de la bibliografía de patente 1 un método y aparato para almacenamiento de datos seguro que usa bases de

35 datos distribuidas genera una primera pluralidad de partes, usando un primer esquema de umbral, basado en un bloque de datos, con al menos un subconjunto de la primera pluralidad de partes que se necesitan para recrear el bloque de datos. La primera pluralidad de partes entonces se distribuye a una pluralidad de bases de datos distribuidas.

40 BIBLIOGRAFÍA DE LA TÉCNICA ANTERIOR

BIBLIGRAFÍA NO DE PATENTES Bibliografía no de patente 1: Kaoru Kurosawa, Wakana Ogata, “Introduction to Modern Cryptography” (escrita en japonés), (ciclo de conferencias de Ingenieros Electrónicos, de Información y Comunicaciones), CORONA

45 PUBLISHING Co, Ltd., marzo de 2004, páginas 116 – 119.

Bibliografía no de patente 2: A Shamir, “How to Share a Secret”, Comunicaciones de la ACM, noviembre de 1979, Volumen 22, Número 11, páginas 612-613.

50 Bibliografía no de patente 3: Hachiro Fujita et al., “Sharing Multilevel Secrets among Groups using Concatenation of Reed-Solomon Codes”, EL INSTITUTO DE INGENIEROS ELECTRÓNICOS, DE INFORMACIÓN Y COMUNICACIÓN, GIJUTSU HOKOKU, INFORME TÉCNICO DEL IEICE, vol. 108, nº 472, 9 de marzo de 2009,

15

25

35

45

55

E10767169

06-03-2015

páginas 65-70.

BIBLIOGRAFÍA DE PATENTE

Bibliografía de patente 1: US 6 363 481 B1

COMPENDIO DE LA INVENCIÓN PROBLEMAS A SER RESUELTOS POR LA INVENCIÓN

Se considera un sistema que satisface las siguientes condiciones.

Condición 1: Un aparato de compartición genera una pluralidad de partes SH(1) a SH(N) mediante compartición de secretos de la información secreta MSK y permite a una pluralidad de aparatos de gestión de partes PA(1) a PA(N) gestionar las partes separadamente. Condición 2: El aparato de gestión de partes PA(1) a PA(N) ejecuta algún tipo de operaciones separadamente. Condición 3: Un aparato de adquisición no puede obtener la información secreta MSK, pero si se dan los resultados de operación generados por un número predeterminado o mayor de aparatos de gestión de partes, se puede obtener la información de generación SK, que es la misma que el resultado de una operación que usa la información secreta MSK y un valor dado σ como operandos.

No obstante, no es fácil implementar ese tipo de sistema. Si los aparatos de gestión de partes PA(1) a PA(N) ejecutan las operaciones usando los valores independientes σ (1) a σ (N), el aparato de adquisición no puede generar la información de generación SK por procesamiento de reconstrucción usando los resultados de las operaciones por los aparatos de gestión de partes como partes. Además, dado que el valor σ puede ser información a partir de cual se predice la información de generación SK, se prefiere desde la perspectiva de seguridad que todos los aparatos de gestión de partes PA(1) a PA(N) no comparten el valor σ en sí mismo.

En vista de ese punto, un objeto de la presente invención es implementar de manera segura un sistema que satisface las condiciones 1 a 3.

MEDIOS PARA RESOLVER LOS PROBLEMAS En vista de los problemas anteriores, la presente invención proporciona un sistema de compartición de secretos, un aparato de compartición, un aparato de gestión de partes, un aparato de adquisición, un método de compartición de secretos, un método de procesamiento para un aparato de compartición, un método de procesamiento para un aparato de gestión de partes y un método de procesamiento para un aparato de adquisición que tiene los rasgos de las reivindicaciones independientes respectivas. Las realizaciones preferidas de la invención se describen en las reivindicaciones dependientes.

Según la presente invención, un aparato de compartición genera las partes SH(α , h(α )) por compartición de secretos de información secreta separadamente para cada uno de los subconjuntos SUB(α ), cada uno de los subconjuntos SUB(α ) que está formado de H(α ) aparatos de gestión de partes PA(α , 1) a PA(α , H(α )) que

L

pertenece a un conjunto de ∑ h(α) aparatos de gestión de partes PA(α , h(α )) (α = 1, …, L, L > 2, h(α )=

α=1 1, …, H(α ), H(α ) > 2) y saca las partes SH(α , h(α )). Cada uno de los aparatos de gestión de partes PA(α , h(α )) genera un valor de secreto compartido DSH(α , h(α )) realizando una operación común a la parte SH(α , h(α )) e información común que contiene un valor común σ (α ) compartido en cada uno de los subconjuntos SUB(α ) y saca el valor de secreto compartido DSH(α , h(α )). La información común usada por los generadores de valores de secretos compartidos de los aparatos de gestión de partes PA(α , h(α )) que pertenecen al mismo subconjunto SUB(α ) es el mismo y los generadores de valores de secretos compartidos de los aparatos de gestión de partes PA(α , h(α )) que pertenecen al mismo subconjunto SUB(α ) realizan la misma operación común.

Un aparato de adquisición genera valores de secretos reconstruidos SUBSK(α ) que corresponden a los subconjuntos SUB(α ) respectivamente. Cada uno de los valores de secretos reconstruidos SUBSK(α ) se genera por procesamiento de reconstrucción para cada subconjunto SUB(α ) usando una pluralidad de valores de secretos compartidos DSH(α , h(α )) que corresponden al mismo subconjunto SUB(α ). El aparato de adquisición saca los valores de secretos reconstruidos SUBSK(α ). El aparato de adquisición entonces genera información de generación SK usando los valores de secretos reconstruidos SUBSK(α ) y saca la información de generación SK.

Según la presente invención, la información secreta se comparte secretamente separadamente para cada subconjunto SUB(α ) y los valores de secretos compartidos DSH(α , h(α )) se generan usando información común que contiene un valor común σ (α ) compartido en cada subconjunto SUB(α ). Cada uno de los valores de secretos reconstruidos SUBSK(α ) obtenidos por procesamiento de reconstrucción para cada subconjunto SUB(α )

10

15

20

25

30

35

40

45

50

55

60

65

E10767169

06-03-2015

llega a ser el mismo que el resultado de una operación que incluye la información secreta y la información común que contiene el valor común σ (α ) como operandos. Por lo tanto, la información de generación SK generada usando los valores de secretos reconstruidos SUBSK(α ) después de la reconstrucción puede ser la misma que el resultado de una operación que contiene la información secreta y un valor dado σ como operandos. Según la presente invención, no todos los aparatos de gestión de partes PA(α , h(α )) comparten el valor dado σ , de

manera que se proporciona un alto nivel de seguridad.

EFECTOS DE LA INVENCIÓN Como se describió anteriormente, según la presente invención, se puede implementar de manera segura un sistema que satisface las condiciones 1 a 3.

BREVE DESCRIPCIÓN DE LOS DIBUJOS La Figura 1 es un diagrama de bloques que ilustra la estructura general de un sistema de compartición de secretos según una primera realización; La Figura 2 es un diagrama de bloques que ilustra la estructura de un aparato de compartición en la Figura 1; La Figura 3A es un diagrama de bloques que ilustra la estructura de un aparato de gestión de partes en la primera realización; La Figura 3B es un diagrama de bloques que ilustra la estructura de un generador de valor común en la primera realización; La Figura 4 es un diagrama de bloques que ilustra la estructura de un aparato de adquisición en la primera realización; La Figura 5A es un diagrama de bloques que ilustra una unidad de compartición de secretos en la Figura 2 en detalle; La Figura 5B es un diagrama de bloques que ilustra un generador de valores de secretos compartidos en la Figura 3A en detalle; La Figura 6 es un diagrama de bloques que ilustra una unidad de reconstrucción en la Figura 4 en detalle; La Figura 7 es una vista que ilustra el procesamiento de compartición de secretos entero en la primera realización; La Figura 8A es una vista que ilustra un ejemplo de procesamiento en el aparato de compartición en la primera realización; La Figura 8B es una vista que ilustra un ejemplo de procesamiento en el paso S112 en detalle; La Figura 9A es una vista que ilustra un ejemplo de procesamiento en el aparato de gestión de partes en la primera realización; La Figura 9B es una vista que ilustra un ejemplo de procesamiento en el paso S124 en detalle; La Figura 10A es una vista que ilustra un ejemplo de procesamiento en el aparato de adquisición en la primera realización; La Figura 10B es una vista que ilustra un ejemplo de procesamiento en el paso S134; La Figura 11A es una vista que ilustra la estructura de una unidad de compartición de secretos en una primera modificación de la primera realización; La Figura 11B es una vista que ilustra la estructura de un generador de valores de secretos compartidos en la primera modificación de la primera realización; La Figura 12A es una vista que ilustra la estructura de un generador de valores de secretos compartidos en una segunda modificación de la primera realización; La Figura 12B es una vista que ilustra la estructura de una unidad de reconstrucción en la segunda modificación de la primera realización; La Figura 13A es una vista que ilustra la estructura de una unidad de compartición de secretos en una tercera modificación de la primera realización; La Figura 13B es una vista que ilustra la estructura de un generador de valores de secretos compartidos en la tercera modificación de la primera realización; La Figura 13C es una vista que ilustra la estructura de una unidad de reconstrucción en la tercera modificación de la primera realización; La Figura 14A es una vista que ilustra la estructura de una unidad de compartición de secretos en una cuarta modificación de la primera realización; La Figura 14B es una vista que ilustra la estructura de un generador de valores de secretos compartidos en la cuarta modificación de la primera realización; La Figura 14C es una vista que ilustra la estructura de una unidad de reconstrucción en la cuarta modificación de la primera realización; La Figura 15 es un diagrama de bloques que ilustra la estructura de un aparato de compartición según una segunda realización; La Figura 16 es un diagrama de bloques que ilustra la estructura de un aparato de gestión de partes en la segunda realización; La Figura 17 es un diagrama de bloques que ilustra la estructura de un aparato de adquisición en la segunda realización; La Figura 18 es un diagrama de bloques que ilustra la estructura de una unidad de composición en la Figura 17;

10

15

20

25

30

35

40

45

50

55

60

E10767169

06-03-2015

La Figura 19 es una vista que ilustra el procesamiento de compartición de secretos entero en la segunda realización; La Figura 20 es una vista que ilustra un ejemplo de procesamiento en el aparato de compartición en la segunda realización; La Figura 21 es una vista que ilustra un ejemplo de procesamiento en el aparato de gestión de partes en la segunda realización; y La Figura 22 es una vista que ilustra un ejemplo de procesamiento en el aparato de adquisición en la segunda realización.

DESCRIPCIÓN DETALLADA DE LAS REALIZACIONES Las realizaciones de la presente invención se describirán más adelante con referencia a los dibujos.

[Primera realización] Se describirá primero una primera realización de la presente invención.

[Definiciones] Se describirán primero los términos y símbolos a ser usados en la realización.

Fq: Fq representa un campo finito de orden q, donde q es un entero igual o mayor que 1. Por ejemplo, el orden q es un número primo de una potencia de un número primo. En otras palabras, el campo finito Fq es un campo primo o un campo de extensión sobre el campo primo, por ejemplo. Se pueden definir fácilmente operaciones en el campo finito primo Fq como operaciones de módulo con el orden q como módulo, por ejemplo. Se pueden definir fácilmente operaciones en el campo de extensión Fq definido como operaciones de módulo con un polinomio irreducible como módulo, por ejemplo. Se describe un método específico para configurar un campo finito Fq, por ejemplo, en la bibliografía de referencia 1, “ISO/IEC 18033-2: Information technology – Security techniques – Encryption algorithms

– Part 2: Asymmetric ciphers”.

0F: 0F representa un elemento identidad aditivo del campo finito Fq. 1F: 1F representa un elemento identidad multiplicativo del campo finito Fq.

E: E representa una curva elíptica sobre el campo finito Fq. E se define como un conjunto que tiene un punto específico O llamado un punto en el infinito y otros puntos (x,y) de x,y ∈ Fq que satisface la siguiente ecuación de Weierstrass en coordenadas afines:

2 32

y +a1xy+a3y=x +a2x +a4x+a6

donde a1, a2, a3, a4, a6, ∈ Fq. Una operación binaria “+” llamada una adición de curva elíptica se puede definir para cualesquiera dos puntos en la curva elíptica E y una operación unitaria “-“ llamada una inversa aditiva se puede definir para cualquier punto en la curva elíptica E. Es bien conocido que un conjunto finito de puntos racionales en la curva elíptica E forma un grupo con respecto a la adición de curva elíptica. También es bien conocido que una operación llamada una multiplicación escalar de curva elíptica se puede definir con la adición de curva elíptica. Un método de operación específica de operaciones elípticas tal como la adición de curva elíptica en un ordenador también es bien conocido. (Por ejemplo, ver la bibliografía de referencia 1, bibliografía de referencia 2, “RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems” y la bibliografía de referencia 3, Ian F. Blake, Gadiel Seroussi y Nigel P. Smart, “Elliptic Curves in Cryptography”, Pearson Education, ISBN 4-89471-431-0).

Un conjunto finito de puntos racionales en la curva elíptica E tiene un subgrupo de orden p (p > 1). Por ejemplo, un conjunto finito E[p] de p puntos de división en la curva elíptica E forma un subgrupo de puntos racionales en la curva elíptica, donde #E representa el recuento de elementos del conjunto finito de los p puntos de división en la curva elíptica E y #E es divisible por el primo grande p. Los p puntos de división en la curva elíptica E son puntos A en la curva elíptica E que satisfacen la multiplicación escalar de curva elíptica p·A = O.

G: G representa un grupo cíclico. Ejemplos del grupo cíclico G incluyen el conjunto finito E[p] de p puntos de

división en la curva elíptica E, subgrupos de los mismos y grupos de residuos. En la realización, una operación definida en el grupo cíclico G se expresa aditivamente. Más específicamente, χ·Ω∈G para

χ∈Fq y Ω∈G significa que la operación definida en el grupo cíclico G se aplica a Ω∈G, χ veces y Ω 1

+ Ω 2 ∈G para Ω 1, Ω 2 ∈G significa que la operación definida en el grupo cíclico G se aplica a Ω 1 ∈Gy Ω 2 ∈G.

g: g representa un generador del grupo cíclico G.

[Estructura general] La Figura 1 es un diagrama de bloques que ilustra la estructura general de un sistema de compartición de secretos 1 según una primera realización.

10

15

20

25

30

35

40

45

50

55

E10767169

06-03-2015

Como se ilustra en la Figura 1, el sistema de compartición de secretos 1 en esta realización incluye un aparato de

L

compartición 110, ∑ h(α) aparatos de gestión de partes [PA(α , h(α )) (α = 1 a L, L > 2, h(α ) = 1 a H(α ),

α=1

H(α ) > 2] 120-α -h(α ), un aparato de adquisición 130 y generadores de valores comunes 140-1 a 140-L y esas unidades se estructuran para permitir comunicación entre ellas a través de la red 150. En aras de la simplicidad, una estructura que incluye un único aparato de compartición 110 y un único aparato de adquisición 130 se describirán en esta realización aunque la estructura puede incluir dos o más aparatos de compartición 110 y/o dos o más aparatos de adquisición 130. Por la misma razón, se describirá en esta realización una estructura que incluye un único

L

conjunto de ∑ h(α) aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ), aunque se puede incluir una

α=1

pluralidad de estos conjuntos.

L

Como se muestra en la Figura 1, el conjunto de ∑ h(α) aparatos de gestión de partes [PA(α , h(α ))] 120-α

α=1 h(α ) se divide en una pluralidad de subconjuntos SUB(α ) que incluye H(α ) aparatos de gestión de partes PA(α , 1) a PA(α , H(α )). Cada subconjunto SUB(α ) corresponde a un generador de valor común 140-α para generar un valor σ (α ) a ser compartido en cada subconjunto SUB(α ).

[Aparato de compartición 110] La Figura 2 es un diagrama de bloques que ilustra la estructura del aparato de compartición 110 en la Figura 1. La Figura 5A es un diagrama de bloques que ilustra una unidad de compartición de secretos 114-α en la Figura 2 en detalle.

Como se muestra en la Figura 2, el aparato de compartición 110 en esta realización incluye un almacenamiento temporal 111, un almacenamiento 112, un controlador 113, unidades de compartición de secretos 114-α (α =1a L) y un transmisor 115. Como se muestra en la Figura 5A, la unidad de compartición de secretos 114-α en esta realización incluye una unidad de selección de función 114a-α , un generador de índices 114b-α y una unidad de procesamiento de compartición 114c-α .

El aparato de compartición 110 en esta realización es un aparato especial que incluye un ordenador conocido o especializado dotado con una unidad central de proceso (CPU), una memoria de acceso aleatorio (RAM), una memoria solamente de lectura (ROM) y similares y un programa especial, por ejemplo. El almacenamiento temporal 111 y el almacenamiento 112 son, por ejemplo, un almacenamiento auxiliar tal como una RAM, un registro, una memoria caché, un dispositivo en un circuito integrado o un disco duro o un área de almacenamiento formada combinando al menos alguno de estos. El controlador 113 y las unidades de compartición de secretos 114-α (α = 1 a L) son unidades de procesamiento implementadas por la CPU ejecutando programas predeterminados, por ejemplo. Al menos una parte del controlador 113 y las unidades de compartición de secretos 114-α (α = 1 a L) se

pueden implementar por un circuito integrado especializado. El transmisor 115 es un dispositivo de comunicación tal como un módem o una tarjeta de red de área local (LAN).

El aparato de compartición 110 ejecuta un procesamiento bajo el control del controlador 113. Cada parte de datos sacada desde cada unidad de procesamiento se almacena en el almacenamiento temporal 111 o en el almacenamiento 112 y una descripción de los mismos se simplificará más adelante. Los datos almacenados en el almacenamiento temporal 111 o el almacenamiento 112 se lee, introduce a una unidad de procesamiento y usa para procesamiento de los mismos, cuando sea necesario.

[Aparato de gestión de partes [PA(α , h(α ))] 120-α -h(α )] La Figura 3A es un diagrama de bloques que ilustra la estructura del aparato de gestión de partes PA(α , h(α ))] 120-α -h(α ) en la primera realización. La Figura 5B es un diagrama de bloques que ilustra un generador de valores de secretos compartidos 124-α -h(α ) en la Figura 3A en detalle.

Como se muestra en la Figura 3A, cada uno de los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) en esta realización incluye un almacenamiento temporal 121-α -h(α ), un almacenamiento 122-α -h(α ), un controlador 123-α -h(α ), el generador de valores de secretos compartidos 124-α -h(α ), un transmisor 125-α h(α ) y un receptor 126-α -h(α ). Como se muestra en la Figura 5B, el generador de valores de secretos compartidos 124-α -h(α ) incluye una unidad de operación lineal 124a-α -h(α ) y una unidad de composición de valores de secretos compartidos 124b-α -h(α ).

Cada uno de los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) es un aparato especial que incluye un ordenador conocido o especializado dotado con una CPU, una RAM, una ROM y similares y un programa especial, por ejemplo. Más específicamente, el almacenamiento temporal 121-α -h(α ) y el almacenamiento 122-α -h(α ) son, por ejemplo, un almacenamiento auxiliar tal como una RAM, un registro, una memoria caché, un dispositivo en

10

15

20

25

30

35

40

45

50

55

60

E10767169

06-03-2015

un circuito integrado o un disco duro o un área de almacenamiento formada combinando al menos alguno de estos. El controlador 123-α -h(α ) y el generador de valores de secretos compartidos 124-α -h(α ) son unidades de procesamiento implementadas por la CPU que ejecuta programas predeterminados, por ejemplo. Al menos una parte del controlador 123-α -h(α ) y el generador de valores de secretos compartidos 124-α -h(α ) 114-α se pueden implementar por un circuito integrado especializado. El transmisor 125-α -h(α ) y el receptor 126-α -h(α )

son dispositivos de comunicación tales como un módem o una tarjeta LAN.

Cada uno de los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) ejecuta un procesamiento bajo el control del controlador 123-α -h(α ). Cada parte de datos sacada de cada unidad de procesamiento se almacena en el almacenamiento temporal 121-α -h(α ) o el almacenamiento 122-α -h(α ) y una descripción de los mismos se simplificará más adelante. Los datos almacenados en el almacenamiento temporal 121-α -h(α ) o el almacenamiento 122-α -h(α ) se leen, introducen a una unidad de procesamiento y usan para procesamiento de los mismos, cuando sea necesario.

[El generador de valor común 140-α ] La Figura 3B es un diagrama de bloques que ilustra la estructura de un generador de valor común 140-α en la primera realización.

Como se muestra en la Figura 3B, cada uno de los generadores de valores comunes 140-α en esta realización incluye un generador de números aleatorios 141-α y un transmisor 142-α . El generador de valor común 140-α en esta realización es una unidad especial que incluye un ordenador conocido o especializado dotado con una CPU, una RAM, una ROM y similares y un programa especial, por ejemplo y el generador de números aleatorios 141-α se puede implementar por un circuito integrado especializado.

[Aparato de adquisición 130] La Figura 4 es un diagrama de bloques que ilustra la estructura del aparato de adquisición 130 en la primera realización. La Figura 6 es un diagrama de bloques que ilustra una unidad de reconstrucción 134-α en la Figura 4 en detalle.

Como se muestra en la Figura 4, el aparato de adquisición 130 en esta realización incluye un almacenamiento temporal 131, un almacenamiento 132, un controlador 133, unidades de reconstrucción 134-α (α = 1 a L), una unidad de composición 137, un transmisor 135 y un receptor 136. Como se muestra en la Figura 6, cada una de las unidades de reconstrucción 134-α incluye una unidad de cálculo de coeficientes 134a-α y una unidad de operación de polinomios 134b-α .

El aparato de adquisición 130 en esta realización es un aparato especial que incluye un ordenador conocido o especializado dotado con una CPU, una RAM, una ROM y similares y un programa especial, por ejemplo. Más específicamente, el almacenamiento temporal 131 y el almacenamiento 132 son, por ejemplo, un almacenamiento auxiliar tal como una RAM, un registro, una memoria caché, un dispositivo en un circuito integrado o un disco duro o un área de almacenamiento formada combinando al menos alguno de estos. El controlador 133, las unidades de reconstrucción 134-α y la unidad de composición 137 son unidades de procesamiento implementadas por la CPU que ejecuta programas predeterminados. Al menos una parte del controlador 133, las unidades de reconstrucción 134-α (α = 1 a L) y la unidad de composición 137 se pueden implementar por un circuito integrado especializado. El transmisor 135 y el receptor 136 son dispositivos de comunicación tales como un módem o una tarjeta LAN.

El aparato de adquisición 130 ejecuta un procesamiento bajo el control del controlador 133. Cada parte de datos sacada de cada unidad de procesamiento se almacena en el almacenamiento temporal 131 o almacenamiento 132 y la descripción se simplificará más adelante. Los datos almacenados en el almacenamiento temporal 131 o el almacenamiento 132 se leen, introducen a una unidad de procesamiento y usan para procesamiento de los mismos, cuando es necesario.

[Procesamiento de compartición de secretos] El procesamiento de compartición de secretos en esta realización se describirá a continuación.

[Procesamiento preparatorio]

En el procesamiento preparatorio para procesamiento de compartición de secretos en esta realización, la información θ∈ Fq para identificar la información secreta θ ·g ∈ G se almacena en el almacenamiento 112 del aparato de compartición 110.

[Procesamiento de compartición de secretos entero] La Figura 7 es una vista que ilustra el procesamiento de compartición de secretos entero en la primera realización. El procesamiento de compartición de secretos entero en esta realización se describirá a continuación con referencia a la Figura 7.

10

15

20

25

30

35

40

45

50

55

E10767169

06-03-2015

En esta realización, el aparato de compartición 110 (Figura 1) primero genera las partes SH(α ,h(α )) realizando

una compartición de secretos de la información secreta θ ·g ∈ G separadamente para cada subconjunto SUB(α )y saca las partes SH(α ,h(α )) (paso S11). Las partes SH(α ,h(α )) se envían separadamente a través de la red 150 a los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ).

Cada uno de los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) a los cuales se enviaron las partes SH(α ,h(α )) genera un valor de secreto compartido DSH(α ,h(α )) realizando una operación común predeterminada a la parte SH(α ,h(α )) y una información común que incluye un valor común σ (α ) compartido en cada subconjunto SUB(α ) y saca el valor de secreto compartido DSH(α ,h(α )) (paso S12).

En esta realización, los valores comunes σ (α ) compartidos separadamente en diferentes subconjuntos SUB(α ) son independientes unos de otros. Los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) en el mismo subconjunto SUB(α ) usan la misma información común. En particular, la información común usada como un ejemplo en esta realización contiene el valor común σ (α ) y la información proporcionada w en común con todos los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ), proporcionados por los aparatos de adquisición

130. Los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) que pertenecen al mismo subconjunto SUB(α ) realizan la misma operación común. En esta realización, todas las operaciones comunes son la misma. La operación común en esta realización es una operación lineal.

Los valores de secretos compartidos DSH(α ,h(α )) sacados por los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) se envían separadamente a través de la red 150 al aparato de adquisición 130. El aparato de adquisición 130 genera un valor de secreto reconstruido SUBSK(α ) por procesamiento de reconstrucción para cada subconjunto SUB(α ) usando una pluralidad de valores de secretos compartidos DSH(α , h(α )) que corresponden al mismo subconjunto SUB(α ) (paso S13).

El aparato de adquisición 130 entonces crea la información de generación SK usando los valores de secretos reconstruidos SUBSK(α ) generados separadamente para los subconjuntos SUB(α ) y saca la información de generación SK (paso S14). En esta realización, el aparato de adquisición 130 crea la información de generación SK realizando una combinación lineal de los valores de secretos reconstruidos SUBSK(α ).

[Procesamiento (en el paso S11) en el aparato de compartición] La Figura 8A es una vista que ilustra un ejemplo de procesamiento en el aparato de compartición en la primera realización. La Figura 8B es una vista que ilustra un ejemplo de procesamiento en el paso S112 en detalle. El procesamiento en el aparato de compartición 110 se describirá a continuación en detalle con referencia a esas figuras.

El controlador 113 del aparato de compartición 110 (Figura 2) especifica α = 1 y almacena el ajuste en el

almacenamiento temporal 111 (paso S111). La información θ∈ Fq para identificar la información secreta θ ·g ∈ G se lee a continuación desde el almacenamiento 112 e introduce a la unidad de compartición de secretos 114-α . La

unidad de compartición de secretos 114-α comparte la información secreta θ ·g usando la información θ∈ Fq, genera H(α ) partes SH(α , 1) a SH(α , H(α )) que corresponden al subconjunto SUB(α ) y las saca (paso S112).

Detalles del paso S112: La unidad de compartición de secretos 114-α en esta realización genera las partes SH(α , h(α )) realizando compartición de secretos de la información secreta para cada subconjunto SUB(α ) usando un esquema de compartición de secretos de umbral (R(α ), H(α )) (R(α ) es una constante que satisface 2 < R(α ) < H(α )).

Como se muestra en la Figura 8B, la unidad de selección de función 114a-α en la unidad de compartición de secretos 114-α (Figura 5A) selecciona aleatoriamente un polinomio de grado de orden (R(α ) – 1) f(α , x) ∈ Fq

que satisface f(α ,ω )= θ con respecto a un elemento predeterminado ω∈ Fq de un campo finito Fq y lo saca (paso S112a), donde x es una variable formada por un elemento del campo finito Fq y un ejemplo del elemento ω ∈ Fq es 0F.

El generador de índices 114b-α entonces genera los índices φ (h(α ))∈ Fq que corresponde a cada uno de h(α )

= 1 a H(α ) y los saca (paso S112b). Si los índices son φ (h(α )) = h(α )∈Fq o si los índices φ (h(α ))∈Fq ya se han obtenido, se puede omitir el procesamiento en el paso S112.

La unidad de procesamiento de compartición 114c-α usa el polinomio f(α , x) ∈Fq y los índices φ (h(α ))∈Fq

10

15

20

25

30

35

40

45

50

55

60

E10767169

06-03-2015

para generar las partes

imagen5

y las saca (paso S112c, fin de la descripción detallada del paso S112).

El controlador 113 juzga si α almacenado en el almacenamiento temporal 111 es L (paso S113). Si no se juzga que α = L, el controlador 113 especifica α + 1 como un nuevo valor de α , almacena el ajuste en el almacenamiento temporal 111 (paso S114) y ejecuta el procesamiento en el paso S112 con el nuevo valor de α . Si se juzga en el paso S113 que α = L, las partes SH(α , h(α )) sacadas de las unidades de compartición de secretos 114-α se envían al transmisor 115. El transmisor 115 envía las partes SH(α , h(α )) a través de la red 150 a los aparatos de gestión de partes correspondientes [PA(α , h(α ))] 120-α -h(α ) (paso S115). La parte SH(1, 1) se envía al aparato de gestión de partes [PA(1, 1)] 120-1-1; la parte SH(1, 2) se envía al aparato de gestión de partes [PA(1, 2)] 120-1-2; …; la parte SH(L, H(L)) se envía al aparato de gestión de partes [PA(L, H(L))] 120-L-H(L).

[Procesamiento en generador de valor común] El generador de valor común 140-α (Figura 3B) genera el valor común σ (α ) compartido por los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) incluidos en el subconjunto SUB(α ) que corresponde al generador de valor común 140-α . En esta realización se especifica un número aleatorio generado por el generador de números aleatorios 141-α como el valor común σ (α ) y el transmisor 142-α envía el valor común σ (α ) a los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) incluidos en el subconjunto SUB(α ).

[Procesamiento (en el paso S12) en los aparatos de gestión de partes] La Figura 9A es una vista que ilustra un ejemplo de procesamiento en los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) en la primera realización. La Figura 9B es una vista que ilustra un ejemplo de procesamiento en el paso S124 en detalle. El procesamiento en los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) en esta realización se describirá a continuación con referencia a esas figuras.

Cada uno de los receptores 126-α -h(α ) de los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) (Figura 3A) recibe la parte enviada SH(α ,h(α )) y la almacena en el almacenamiento 122-α -h(α ) (paso S121). Si el procesamiento en el paso S121 fue ejecutado en el pasado y si la parte SH(α ,h(α )) ya ha sido almacenada en el almacenamiento 122-α -h(α ) del aparato de gestión de partes [PA(α , h(α ))] 120-α -h(α ), se puede omitir el procesamiento en el paso S121.

Cada uno de los receptores 126-α -h(α ) de los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) también recibe el valor común σ (α ) enviado desde cada uno de los generadores de valores comunes 140-α y lo almacena en cada uno de los almacenamientos 122-α -h(α ) (paso S122).

En esta realización, la información proporcionada w leída desde el almacenamiento 132 del aparato de adquisición 130 (Figura 4) se envía desde el transmisor 135 a través de la red 150 a los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ). La información proporcionada w es común a todos los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ). La información proporcionada w se recibe por cada uno de los receptores 126-α -h(α ) de los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) (Figura 3A) y se almacena en cada uno de los almacenamientos 122-α -h(α ) (paso S123).

Cada uno de los generadores de valores de secretos compartidos 124-α -h(α ) lee la parte SH(α , h(α )), el valor común σ (α ) y la información proporcionada w desde cada uno del almacenamiento 122-α -h(α ). Cada uno de los generadores de valores de secretos compartidos 124-α -h(α ) genera un valor de secreto compartido DSH(α , h(α )) realizando una operación común FNC1 a la parte SH(α , h(α )) e información común que incluye el valor común σ (α ) y la información proporcionada w y saca el valor de secreto compartido DSH(α , h(α )) (paso S124).

Detalles del paso S124: La información común usada por los generadores de valores de secretos compartidos 124-α -h(α ) de los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) en el mismo subconjunto SUB(α ) es la misma y los generadores de valores de secretos compartidos 124-α -h(α ) de los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) en el mismo subconjunto SUB(α ) realizan la misma operación común. Las partes en esta realización se expresan por la Expresión (5).

Como se muestra en la Figura 9B, cada una de las unidades de operación lineal 124a-α -h(α ) en los generadores de valores de secretos compartidos 124-α -h(α ) en esta realización se da el valor común σ (α ), la información

E10767169

06-03-2015

proporcionada w y f(α ,φ (h(α )))·g en la parte SH(α , (h(α )) =(φ (h(α )), f(α ,φ (h(α )))·g). La unidad de operación lineal 124a-α -h(α ) realiza la operación dada por

imagen6

5

y saca el resultado de la operación dsh(α ,φ (h(α ))) (paso S124a).

Cada resultado de operación de salida dsh(α ,φ (h(α ))) se introduce a cada una de las unidades de composición de valores de secretos compartidos 124b-α -h(α ). Además, cada índice φ (h(α )) de la parte SH(α , (h(α )) =

10 (φ (h(α )), f(α ,φ (h(α )))·g) se introduce a cada f de las unidades de composición de valores de secretos compartidos 124b-α -h(α ) y cada una de las unidades de composición de valores de secretos compartidos 124bα -h(α ) genera un valor de secreto compartido DSH(α , (h(α )) por la operación dada por

imagen7

15

y lo saca (paso S124b, fin de la descripción detallada del paso S124).

Cada valor de secreto compartido generado DSH(α , (h(α )) se envía a cada uno de los transmisores 125-α h(α ). Cada transmisor 125-α -h(α ) envía el valor de secreto compartido DSH(α , (h(α )) a través de la red 150

20 al aparato de adquisición 130 (paso S125).

[Procesamiento (en los pasos S13 y S14) en el aparato de adquisición] La Figura 10A es una vista que ilustra un ejemplo de procesamiento en los aparatos de adquisición en la primera realización y la Figura 10B es una vista que ilustra un ejemplo de procesamiento en el paso S134.

25

Los valores de secretos compartidos DSH(α , (h(α )) enviados desde los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) se reciben por el receptor 136 en el aparato de adquisición 130 (Figura 4) y almacenan en el almacenamiento 132 (paso S131).

30 El controlador 133 juzga si el número de valores de secretos compartidos DSH(α , (h(α )) almacenados en el almacenamiento 132 es mayor o igual a un número requerido (paso S132). En esta realización, se juzga si R(α ) (2 < R(α ) < H(α )) o mayor que diferentes valores de secretos compartidos DSH(α , (h(α )) se almacenan en el almacenamiento 132 con respecto a cada uno de α = 1 a L. Si no se juzga aquí que el número de valores de secretos compartidos DSH(α , (h(α )) almacenados en el almacenamiento 132 es mayor o igual al número

35 requerido, el procesamiento vuelve al paso S131.

Si se juzga que el número de valores de secretos compartidos DSH(α , (h(α )) almacenados en el almacenamiento 132 es mayor o igual al número requerido, el controlador 133 especifica α = 1 y almacena el ajuste en el almacenamiento temporal 131 (paso S133). Entonces, el número requerido de los valores de secretos compartidos

40 DSH(α , (h(α )), que corresponden al subconjunto SUB(α ) se leen desde el almacenamiento 132 e introducen a la unidad de reconstrucción 134-α . La unidad de reconstrucción 134-α genera un valor de secreto reconstruido SUBSK(α ) por un procesamiento de reconstrucción para cada subconjunto SUB(α ) usando los valores de secretos compartidos de entrada DSH(α , (h(α )) y saca el valor de secreto reconstruido SUBSK(α ) para cada subconjunto SUB(α ) (paso S134).

45

Detalles del paso S134: Los valores de secretos compartidos DSH(α , (h(α )) en esta realización se dan por la Expresión (7). La unidad de reconstrucción 134-α (Figura 6) da R(α ) diferentes valores de secretos compartidos DSH(α , (h(α )) para cada valor de α . Los valores de secretos compartidos DSH(α , (h(α )) que corresponden a cada valor deα introducido

50 a la unidad de reconstrucción 134-α se expresarán como sigue.

imagen8

donde

E10767169

06-03-2015

imagen9

Como se muestra en la Figura 10B, los índices φ 1(α )a φ (α ) de DSH(α ,φ 1(α )) a DSH(α ,φ (α ))

R (α ) R (α )

dados por la Expresión (8) se introducen a la unidad de cálculo de coeficientes 134a-α y la unidad de cálculo de coeficientes 134a-α realiza la siguiente operación para cada valor de ρ = 1 a R(α ).

imagen10

10 Los coeficientes λρ (x) ( ρ = 1 a R(α )) se generan y sacan (paso S134a).

Los coeficientes generados λρ (x) y dsh1(α ) a dsh ) (α ) que corresponden a DSH(α ,φ 1(α )) a

R (α

DSH(α ,φ R (α ) (α )) dados por la Expresión (8) se introducen a la unidad de operación de polinomios 134b-α . La

unidad de operación de polinomios 134b-α genera el valor de secreto reconstruido SUBSK(α ) del subconjunto 15 SUB(α ) por la operación dada por

SUBSK(α )

= λ 1(ω ) y dsh1(α ) +...+ λ R (α ) (ω )·dsh ) (α ) ∈G (12)

R (α

20

y lo saca (paso S134b, fin de la descripción detallada del paso S134).

Entonces, el controlador 133 juzga si α almacenado en el almacenamiento temporal 131 es L (paso S135). Si no se juzga que α = L, el controlador 133 especifica α + 1 como un nuevo valor de α , almacena el ajuste en el 25 almacenamiento temporal 131 (paso S136) y ejecuta el procesamiento en el paso S134 con el nuevo valor de α .

Si se juzga en el paso S135 que α = L, los valores de secretos reconstruidos SUBSK(α ) sacados de las unidades de reconstrucción 134-α se envían a la unidad de composición 137. La unidad de composición 137 genera la información de generación

30

SK = FNC2(SUBSK(1), …, SUBSK(L)) (13)

usando los valores de secretos reconstruidos SUBSK(α ) generados para los subconjuntos SUB(α ) y saca la información de generación SK (paso S141).

35

Detalles del paso S141:

Se darán más adelante ejemplos de la Expresión (13).

40 Ejemplo 1:

SK = SUBSK(1) + … + SUBSK(L) ∈G (14)

Ejemplo 2:

45

SK = CE1·SUBSK(1) + … + CEL·SUBSK(L) ∈G (15)

donde CE α∈Fq es un coeficiente y un ejemplo del coeficiente es el elemento inverso de multiplicación (L)-1 ∈Fq de

L. Algunos de los coeficientes CE1 a CEL pueden ser 0F. En ese caso, la información de generación SK se genera

50 usando solo un término parcial de SUBSK(1) + … + SUBSK(L). La unidad de composición 137 puede seleccionar aleatoriamente que un coeficiente sea 0F a partir de los coeficientes CE1 a CEL. Esto mejorará el nivel de seguridad. La unidad de composición 137 también se puede adaptar para especificar los coeficientes CE1 a CEL libremente.

10

15

20

25

30

35

40

45

50

55

E10767169

06-03-2015

Esto permite al aparato de adquisición 130 generar la información de generación SK sin usar los valores de secretos reconstruidos SUBSK(α ’) que corresponden a los subconjuntos SUB(α ’) que tienen un nivel de fiabilidad bajo, por ejemplo (fin de la descripción detallada del paso S141).

[Rasgos de la primera realización] En esta realización, el aparato de compartición 110 genera las partes SH(α , (h(α )) realizando compartición de

secretos de la información secreta θ ·g ∈ G para cada subconjunto SUB(α ) separadamente; los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) generan los valores de secretos compartidos DSH(α , (h(α )) conduciendo la operación común, usando las partes SH(α , (h(α )) y la información común que incluye los valores comunes σ (α ) y la información proporcionada w; el aparato de adquisición 13 genera los valores de secretos reconstruidos SUBSK(α ) realizando el procesamiento de reconstrucción para cada subconjunto SUB(α ), usando una pluralidad de valores de secretos compartidos DSH(α , (h(α )) que corresponden al mismo subconjunto SUB(α ) y genera la información de generación SK usando los valores de secretos reconstruidos SUBSK(α ).

Como se describió anteriormente, se usa el valor común σ (α ) compartido en cada subconjunto SUB(α ) y la compartición de secretos, la operación común y el procesamiento de reconstrucción se realizan para cada subconjunto SUB(α ). Por lo tanto, son posibles todas estas partes de procesamiento. No todos los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α ) comparten el valor σ y el valor común σ (α ) se comparte en cada uno de los subconjuntos SUB(α ), de manera que se proporciona un alto nivel de seguridad. Especialmente, en esta realización, los valores comunes σ (α ) compartidos en diferentes subconjuntos SUB(α ) son independientes unos de otros. Esto asegura un alto nivel de seguridad.

En esta realización, todos los aparatos de gestión de partes [PA(α , h(α ))] 120-α -h(α )(α = 1 a L) realizan la misma operación común FNC1. La operación común FNC1 es lineal. Por lo tanto, en esta realización, generando la información de generación SK a través de una combinación lineal de los valores de secretos reconstruidos SUBSK(α ), la información de generación SK generada usando los valores de secretos reconstruidos SUBSK(α )

se puede hacer igual al resultado obtenido realizando la operación común FNC1 usando la información secreta θ ·g y un valor σ dado como operandos.

Esta realización usa el esquema de compartición de secretos de umbral (R(α ), H(α )) para compartición de secretos de la información secreta θ ·g ∈ G en cada subconjunto SUB(α ). En este esquema, cada una de las partes SH(α , (h(α )) incluye un elemento f(α ,φ (h(α )))·g ∈G de un grupo cíclico G, donde x representa una variable x que está formada de un elemento de un campo finito Fq, f(α , x) ∈Fq representa un polinomio de grado de orden (R(α ) -1) que satisface f(α ,ω )= θ con respecto a un elemento predeterminado ω∈Fq del campo finito Fq y φ (h(α )) representa un índice que corresponde a h(α ). La compartición de secretos de la información

secreta θ ·g ∈ G, la cual es un elemento del grupo cíclico, evita que θ se escape incluso si la información secreta

θ ·g reconstruida a partir de las partes SH(α , (h(α )) se escapa, bajo la suposición de que es difícil resolver un problema logarítmico discreto en el grupo cíclico G. Esto proporciona un alto nivel de seguridad.

[Primera modificación de la primera realización] Se describirá a continuación una primera modificación de la primera realización.

En la primera realización, un elemento del grupo cíclico G es una información secreta θ ·g ∈ G y la información

secreta se comparte. Se puede compartir el elemento θ∈ Fq del campo finito Fq. En ese caso, las partes SH(α , (h(α )) obtenidas por compartición de secretos usando el esquema de compartición de secretos de umbral (R(α ),

H(α )) incluyen un elemento f(α ,φ (h(α ))) ∈ Fq del campo finito Fq donde una variable formada por un elemento

del campo finito Fq es x, un polinomio de grado de orden (R(α ) -1) f(a, x) ∈ Fq satisface f(α , ω )= θ con respecto a un elemento predeterminado ω∈ Fq del campo finito Fq y un índice que corresponde a h(α ) esφ (h(α )).

La Figura 11A es una vista que ilustra la estructura de una unidad de compartición de secretos 214-α en la primera modificación de la primera realización y la Figura 11B es una vista que ilustra la estructura de un generador de valores de secretos compartidos 224-α -h(α ) en la primera modificación de la primera realización. En estas figuras, a componentes idénticos a aquellos en la primera realización se dan los mismos números de referencia que en la primera realización.

En la primera modificación de la primera realización, las unidades de compartición de secretos 114-α en la Figura

E10767169

06-03-2015

5A se sustituyen con las unidades de compartición de secretos 214-α ; y los generadores de valores de secretos compartidos 124-α -h(α ) en la Figura 5B se sustituyen con los generadores de valores de secretos compartidos 224-α -h(α ). Los otros componentes son los mismos que aquellos en la primera realización.

5 Modificación del paso S112 en la primera modificación de la primera realización En la primera modificación de la primera realización, el procesamiento en el paso S112 ilustrado en la Figura 8B se modifica como sigue.

Los pasos S112a y S112b mostrados en la Figura 8B se ejecutan primero. Entonces, en lugar del paso S112c, cada 10 una de las unidades de procesamiento de compartición 214c-α (Figura 11A) en la unidad de compartición de secretos 214-α genera las partes

SH(α , h(α )) = (ϕ (h(α )), f(α ,ϕ (h(α )))) (16)

15 usando el polinomio f(α , x) ∈ Fq y el índice φ (h(α ))∈ Fq y las saca (fin de la descripción de la modificación del paso S112 en la primera modificación de la primera realización).

Modificación del paso S124 en la primera modificación de la primera realización:

20 En la primera modificación de la primera realización, el procesamiento en el paso S124 en la Figura 9B se modifica como sigue.

En lugar del paso S124a, a cada una de las unidades de operación lineal 224a-α -h(α ) (Figura 11B) se da el valor común σ (α ), la información proporcionada w y f(α ,φ (h(α ))) en la parte SH(α , h(α )) = (φ (h(α )), f(α ,φ 25 (h(α )))) y realiza la operación dada por

dsh(α ,ϕ (h(α ))) = σ (α )·w·f(α ,ϕ (h(α )))·g ∈ G (17)

y saca el resultado dsh(α ,φ (h(α )))∈ G. Cada resultado de operación dsh(α ,φ (h(α )))∈ G llega a ser una 30 información parcial del valor de secreto compartido DSH(α , h(α )). Entonces, se ejecuta el procesamiento en el paso S124b mostrado en la Figura 9B (fin de la descripción de una modificación del paso S124 en la primera modificación de la primera realización). El otro procesamiento es el mismo que en la primera realización.

[Segunda modificación de la primera realización] 35 Se describirá a continuación una segunda modificación de la primera realización.

En la segunda modificación de la primera realización, el elemento θ∈ Fq del campo finito Fq se comparte con un esquema de compartición de secretos también. Una diferencia de la primera modificación de la primera realización es que cada uno de los resultados de operación dsh(α ,φ (h(α ))) no es un elemento del grupo cíclico G sino que

40 es un elemento del campo finito Fq.

La Figura 12A es una vista que ilustra la estructura de un generador de valores de secretos compartidos 324-α h(α ) en la segunda modificación de la primera realización y la Figura 12B es una vista que ilustra la estructura de una unidad de reconstrucción 334-α en la segunda modificación de la primera realización. En estas figuras, a

45 componentes idénticos a aquellos en la primera realización se dan los mismos números de referencia que en la primera realización.

En la segunda modificación de la primera realización, los generadores de valores de secretos compartidos 124-α h(α ) en la Figura 5B se sustituyen con generadores de valores de secretos compartidos 324-α -h(α ) y las

50 unidades de reconstrucción 134-α en la Figura 6 se sustituyen con las unidades de reconstrucción 334-α . Como en la primera modificación de la primera realización, las unidades de procesamiento de compartición 114c-α en la Figura 5A se sustituyen con las unidades de procesamiento de compartición 214c-α . Los otros componentes son los mismos que en la primera realización.

55 Modificación del paso S112 en la segunda modificación de la primera realización: Una modificación del paso S112 en la segunda modificación de la primera realización es la misma que la modificación del paso S112 en la primera modificación de la primera realización.

Modificación del paso S124 en la segunda modificación de la primera realización:

60

E10767169

06-03-2015

En la segunda modificación de la primera realización, el procesamiento en el paso S124 en la Figura 9B se modifica como sigue.

En lugar del paso S124a, a cada una de las unidades de operación lineal 324a-α -h(α ) (Figura 12A) se da el valor 5 común σ (α ), la información proporcionada w y f(α ,φ (h(α ))) en la parte SH(α , h(α )) = (φ (h(α )), f(α ,φ (h(α )))) y realiza la operación dada por

dsh(α ,ϕ (h(α ))) = σ (α )·w·f(α ,ϕ (h(α ))) ∈ Fq (18)

10 y saca el resultado dsh(α ,φ (h(α )))∈ Fq. Cada resultado de operación dsh(α ,φ (h(α )))∈Fq llega a ser una información parcial del valor de secreto compartido DSH(α , h(α )). Entonces, se ejecuta el procesamiento en el paso S124b mostrado en la Figura 9B.

Modificación del paso S134 en la segunda modificación de la primera realización:

15 Se ejecuta primero el procesamiento en el paso S134a mostrado en al Figura 10B. Entonces, en lugar del procesamiento en el paso S134b mostrado en al Figura 10B, a cada una de las unidades de operación de

polinomios 334b-α (Figura 12B) se da los coeficientes λ p(x) y dsh1(α ) a dsh R (α ) (α ) de DSH(α ,φ 1(α )) a

DSH(α ,φ (α )) dados por la Expresión (8) y genera un valor de secreto reconstruido SUBSK(α ) del

R (α )

20 subconjunto SUB(α ) por la operación dada más adelante

SUBSK(α )

={ λ 1(ω )·dsh1(α ) +...+ λ (ω )·dsh (α )}·g ∈ G (19)

R (α ) R (α )

25 y lo saca (fin de la descripción de la modificación del paso S134 en la segunda modificación de la primera realización). El otro procesamiento es el mismo que en la primera realización.

[Tercera modificación de la primera realización]

30 En una tercera modificación de la primera realización, la información secreta se comparte usando el esquema de compartición de secretos de umbral (H(α ), H(α )) en lugar del esquema de compartición de secretos de umbral (R(α ), H(α )).

La Figura 13A es una vista que ilustra la estructura de una unidad de compartición de secretos 414-α en la tercera

35 modificación de la primera realización, la Figura 13B es una vista que ilustra la estructura de un generador de valores de secretos compartidos 424-α -h(α ) en la tercera modificación de la primera realización y la Figura 13C es una vista que ilustra la estructura de una unidad de reconstrucción 434-α en la tercera modificación de la primera realización.

40 En la tercera modificación de la primera realización, las unidades de compartición de secretos 114-α en la Figura 5A se sustituyen con unidades de compartición de secretos 414-α , los generadores de valores de secretos compartidos 124-α -h(α ) en la Figura 5B se sustituyen con los generadores de valores de secretos compartidos 424-α -h(α ) y las unidades de reconstrucción 134-α en la Figura 6 se sustituyen con las unidades de reconstrucción 434-α . Los otros componentes son los mismos que en la primera realización.

45

Modificación del paso S112 en la tercera modificación de la primera realización:

En la tercera modificación de la primera realización, el procesamiento en el paso S112 mostrado en la Figura 8B se modifica como sigue.

50

Cada uno de los generadores de números aleatorios 414a-α en la unidad de compartición de secretos 414α (Figura 13A) selecciona (H(α ) – 1) elementos

SH(α , 1), …, SH(α , H(α )-1) ∈ G (20)

55

del grupo cíclico G aleatoriamente y los saca.

La información secreta θ .g∈G y (H(α ) – 1) elementos SH(α , 1) a SH(α , H(α )-1) ∈ G del grupo cíclico G se introducen a una unidad de operación de elemento inverso 414b-α . La unidad de operación de elemento inverso

E10767169

06-03-2015

414b-α genera SH(α , h(α )) por la operación dada por

SH(α , h(α )) = θ ·g -{ SH(α , 1) + … +SH(α , H(α )-1)} ∈ G (21)

5 y la saca.

Cada una de las unidades de compartición de secretos 414-α saca

SH(α , 1), …, SH(α , H(α )) ∈ G

10

como partes del subconjunto SUB(α ). Estas partes satisfacen

SH(α , 1) + SH(α , 2) + … + SH(α , H(α )) = θ ·g ∈ G (22)

15 (fin de la descripción de una modificación del paso S112 en la tercera modificación de la primera realización).

Modificación del paso S124 en la tercera modificación de la primera realización:

En la tercera modificación de la primera realización, el procesamiento en el paso S124 mostrado en la Figura 9B se 20 modifica como sigue.

A cada uno de los generadores de valores de secretos compartidos 424-α -h(α ) (Figura 13B) se da el valor común σ (α ), la información proporcionada w y las partes SH(α , 1) a SH(α , H(α )), genera los valores de secretos compartidos DSH(α , h(α )) por la operación dada por

25

DSH(α , h(α )) = σ (α )·w·SH(α , h(α )) ∈ G (23)

y los saca (fin de la descripción de una modificación del paso S124 en la tercera modificación de la primera realización).

30 Modificación del paso S132 en la tercera modificación de la primera realización: En la tercera modificación de la primera realización, el procesamiento en el paso S132 mostrado en la Figura 10A se modifica como sigue.

35 En la tercera modificación, el controlador 133 juzga si el número de valores de secretos compartidos DSH(α , h(α )) almacenados en el almacenamiento 132 es mayor o igual que un número requerido y el número requerido en la tercera modificación es H(α ). En otras palabras, se juzga en la tercera modificación si todos los valores de secretos compartidos DSH(α , (h(α )) están almacenados en el almacenamiento 132 con respecto a cada uno de α = 1 aL.

40 Modificación del paso S134 en la tercera modificación de la primera realización: En la tercera modificación de la primera realización, el procesamiento en el paso S134 mostrado en la Figura 10B se modifica como sigue.

45 El valor de secreto compartido DSH(α , (h(α )) en la tercera modificación se da por la Expresión (23). Todos los valores de secretos compartidos DSH(α , (h(α )) (h(α ) = 1 a H(α )) que corresponden a α se introducen a la unidad de reconstrucción 434-α (Figura 13C). La unidad de reconstrucción 434-α entonces genera un valor de secreto reconstruido SUBSK(α ) que corresponde al subconjunto SUB(α ) por la operación dada por

50 SUBSK(α ) = DSH(α , 1) + … +DSH(α , H(α )) ∈ G (24)

y lo saca (fin de la descripción de la modificación del paso S134 en la tercera modificación de la primera realización). El otro procesamiento es el mismo que en la primera realización.

55 [Cuarta modificación de la primera realización] También en una cuarta modificación de la primera realización, la información secreta se comparte usando el esquema de compartición de secretos de umbral (H(α ), H(α )) en lugar del esquema de compartición de secretos

de umbral (R(α ), H(α )). Una diferencia con la tercera modificación es que la información secreta θ∈ Fq, la cual es un elemento del campo finito Fq, se comparte con el esquema de compartición de secretos.

60

La Figura 14A es una vista que ilustra la estructura de una unidad de compartición de secretos 514-α en la cuarta modificación de la primera realización; la Figura 14B es una vista que ilustra la estructura de un generador de

E10767169

06-03-2015

valores de secretos compartidos 524-α -h(α ) en la cuarta modificación de la primera realización; y la Figura 14C es una vista que ilustra la estructura de una unidad de reconstrucción 534-α en la cuarta modificación de la primera realización.

5 En la cuarta modificación de la primera realización, las unidades de compartición de secretos 114-α en la Figura 5A se sustituyen con las unidades de compartición de secretos 514-α ; los generadores de valores de secretos compartidos 124-α -h(α ) en la Figura 5B se sustituyen con los generadores de valores de secretos compartidos 524-α -h(α ); y las unidades de reconstrucción 134-α en la Figura 6 se sustituyen con las unidades de reconstrucción 534-α . Los otros componentes son los mismos que en la primera realización.

10

Modificación del paso S112 en la cuarta modificación de la primera realización: En la cuarta modificación de la primera realización, el procesamiento en el paso S112 mostrado en la Figura 8B se modifica como sigue.

15 Cada uno de los generadores de números aleatorios 514a-α en la unidad de compartición de secretos 514α (Figura 14A) selecciona (H(α ) – 1) elementos

SH(α , 1), …, SH(α , H(α )-1) ∈ Fq (25)

20 del elemento finito Fq aleatoriamente y los saca.

A cada una de la unidad de operación de elementos inversos 514b-α se da la información secreta θ∈ Fq y los (H(α ) – 1) elementos SH(α , 1) a SH(α , H(α )-1) ∈ Fq del elemento finito Fq, genera SH(α , h(α )) por la operación dada por

25

SH(α , h(α )) = θ -{ SH(α , 1) + …+ SH(α , H(α )-1)} ∈ Fq (26) y la saca. 30 Cada una de la unidad de compartición de secretos 514-α saca SH(α , 1), …, SH(α , H(α )) ∈ Fq (27) como partes del subconjunto SUB(α ). Estas partes satisfacen

35

SH(α , 1) + SH(α , 2) + … + SH(α , H(α )) = θ∈ Fq (28) (fin de la descripción de la modificación del paso S112 en la cuarta modificación de la primera realización). 40 Modificación del paso S124 en la cuarta modificación de la primera realización:

En la cuarta modificación de la primera realización, el procesamiento en el paso S124 mostrado en la Figura 9B se modifica como sigue. A cada uno de los generadores de valores de secretos compartidos 524-α -h(α ) (Figura 14B) se da el valor común

45 σ (α ), la información proporcionada w y las partes SH(α , 1) a SH(α , H(α )), genera un valor de secreto compartido DSH(α , h(α )) por la operación dada por DSH(α , h(α )) = σ (α )·w·SH(α , h(α )) ∈ Fq (29) 50 y lo saca (fin de la descripción de una modificación del paso S124 en la cuarta modificación de la primera realización). Modificación del paso S132 en la cuarta modificación de la primera realización: La modificación del paso S132 en la cuarta modificación de la primera realización es la misma que en la tercera 55 modificación de la primera realización. Modificación del paso S134 en la cuarta modificación de la primera realización: En la cuarta modificación de la primera realización, el procesamiento en el paso S134 mostrado en la Figura 10B se 60 modifica como sigue. El valor de secreto compartido DSH(α , h(α )) en la cuarta modificación se da por la Expresión (29). Todos los

E10767169

06-03-2015

5

10

15

20

25

30

35

40

45

50

55

60

valores de secretos compartidos DSH(α , (h(α )) (h(α ) = 1 a H(α )) que corresponden a α se introducen a la unidad de reconstrucción 534-α que corresponden a α (Figura 14C). La unidad de reconstrucción 534-α entonces genera un valor de secreto reconstruido SUBSK(α ) del subconjunto SUB(α ) por la operación dada por

SUBSK(α ) = {DSH(α , 1) + … +DSH(α , H(α ))}·g ∈ G (30)

y lo saca (fin de la descripción de la modificación del paso S134 en la cuarta modificación de la primera realización). El otro procesamiento es el mismo que en la primera realización.

[Otras modificaciones de la primera realización] Se pueden hacer otras modificaciones de la primera realización dentro del alcance de la presente invención. Por ejemplo, la operación dada por

DSH(α , h(α )) = σ (α )·w·SH(α , h(α )) ∈ Fq (31)

se puede llevar a cabo en lugar de la Expresión (29) en la cuarta modificación de la primera realización y la operación de la Expresión (24) se puede llevar a cabo en lugar de la Expresión (30). El valor de secreto reconstruido SUBSK(α ) puede ser un elemento del campo finito Fq.

En esta realización, se usa el mismo esquema de compartición de secretos en cada subconjunto SUB(α ) para compartir un secreto. Se pueden usar diferentes esquemas de compartición de secretos para diferentes subconjuntos SUB.

El generador de valor común 140-α se proporciona para cada subconjunto SUB(α ) en esta realización. Cualquier aparato de gestión de partes dado en cada subconjunto SUB(α ) puede tener la función del generador de valor común. En ese caso, el generador de valor común 140-α llega a ser innecesario.

En esta realización, la operación común FNC1 se lleva a cabo usando las partes SH(α , h(α )) y la información común que contiene el valor común σ (α ) y la información proporcionada w para generar el valor de secreto compartido DSH(α , h(α )). El valor de secreto compartido DSH(α , h(α )) se puede generar usando el valor común σ (α ) como la información común sin usar la información proporcionada. La información común puede contener el valor común σ (α ), la información proporcionada w y otra información.

La operación común para obtener los valores de secretos compartidos DSH(α , h(α )) debe ser la misma en cada subconjunto SUB(α ). No obstante, diferentes subconjuntos SUB(α ) no siempre necesitan llevar a cabo la misma operación común.

[Segunda Realización] Se describirá a continuación una segunda realización de la presente invención. Esta realización es una aplicación de la primera realización para generación de claves en cifrado de predicado de producto interior.

[Definiciones] Se definirán primero los términos y símbolos a ser usados en las realizaciones.

Matriz: Una matriz representa una disposición rectangular de elementos de un conjunto en el cual se definen unas operaciones. No solamente los elementos de un anillo sino también los elementos de un grupo pueden formar una matriz.

(·)T: (·)T representa una matriz traspuesta de “·”.

(·)-1: (·)-1 representa una matriz inversa de “·”.

∧ : ∧ representa AND Lógica

∨ : ∨ representa OR Lógica

Z: Z representa un conjunto de enteros

k: k representa un parámetro de seguridad (k ∈ Z,k >0) Fq: Fq representa un campo finito de orden q, donde q es un entero igual o mayor que 1. Por ejemplo, el orden q es un número primo de una potencia de un número primo. En otras palabras, el campo finito Fq es un campo primo o un campo de extensión sobre el campo primo, por ejemplo. 0F: 0F representa un elemento identidad aditivo del campo finito Fq

1F: representa un elemento identidad multiplicativo del campo finito Fq δ

(i,j): δ (i,j) representa una función delta de Kronecker. Cuando i = j, δ (i,j) = 1F.

Cuando i ≠ j, δ (i,j) = 0F.

E: E representa una curva elíptica sobre el campo finito Fq.

E10767169

06-03-2015

G1, G2, GT: G1, G2, GT representan grupos cíclicos de orden q, respectivamente. Ejemplos de los grupos cíclicos G1 y G2 incluyen el conjunto finito E[p] de p puntos de división en la curva elíptica E y subgrupos de los mismos. G1 puede ser igual a G2 o G1 puede no ser igual a G2. Ejemplos del grupo cíclico GT incluyen un

5 conjunto finito que forma un campo de extensión del campo finito Fq. Un ejemplo específico del mismo es un conjunto finito de la raíz de orden p de 1 en el cierre algebraico del campo finito Fq.

En la realización, operaciones definidas en los grupos cíclicos G1 y G2 se expresan aditivamente y una operación definida en el grupo cíclico GT se expresa multiplicativamente. Más específicamente, χ·Ω∈G1 para χ∈Fq y

10 Ω∈G1 significa que la operación definida en el grupo cíclico G1 se aplica a Ω∈G1, χ veces y Ω 1+ Ω 2 ∈G1

para Ω 1, Ω 2 ∈G1 significa que la operación definida en el grupo cíclico G1 se aplica a Ω 1 ∈G1 y Ω 2 ∈G1. De la misma forma, χ·Ω∈G2 para χ∈Fq y Ω∈G2 significa que la operación definida en el grupo cíclico G2 se aplica a

Ω∈G2, χ veces y Ω 1+ Ω 2 ∈G2 para Ω 1, Ω 2 ∈G2 significa que la operación definida en el grupo cíclico G2

se aplica a Ω 1 ∈G2 y Ω 2 ∈G2. Al contrario, Ω χ∈ GT para χ∈Fq y Ω∈GT significa que la operación definida

15 en el grupo cíclico GT se aplica a Ω∈GT, χ veces y Ω 1· Ω 2 ∈GT para Ω 1, Ω 2 ∈GT significa que la operación

definida en el grupo cíclico GT se aplica a Ω 1 ∈GT y Ω 2 ∈GT.

n: n representa un entero igual o mayor que 1 ζ : ζ representa un entero igual o mayor que 1. Un ejemplo de ζ es 2 o3.

n+ζ n+ζ

20 G1 : G1 representa un producto directo de (n + ζ ) grupos críticos G1.

n+ζ n+ζ

G2 : G2 representa un producto directo de (n + ζ ) grupos críticos G2.

g1, g2, gT: g1, g2, gT representa generadores de los grupos cíclicos G, G1, G2, GT, respectivamente.

V: V representa un espacio de vector (n + ζ ) dimensional formado del producto directo de los (n + ζ )

grupos cíclicos G1.

25 V*: V* representa un espacio de vector (n + ζ ) dimensional formado del producto directo de los (n + ζ ) grupos cíclicos G2.

e: e representa una función (en lo sucesivo conocida como “función bilineal”) para calcular un mapa bilineal

n+ζ n+ζ n+ζ

no degenerado que correlaciona el producto directo G1 x G2 del producto directo G1 y el producto

n+ζ

directo G2 al grupo cíclico GT. La función bilineal e saca un elemento del grupo cíclico GT en respuesta a la

30 entrada de (n + ζ ) elementos γβ ( β = 1, …, n + ζ ) del grupo cíclico G1 y (n + ζ ) elementos γβ *( β =

1, …, n+ ζ ) del grupo cíclico G2.

n+ζ n+ζ

e:G1 xG2 → GT (32)

35 La función bilineal e satisface las siguientes características:

n+ζ n+ζ

-Bilinealidad: Las siguiente relación se satisface para todo Γ 1 ∈ G1 , Γ 2 ∈ G2 y ν , κ∈ Fq

ν · κ

e(ν · Γ 1, κ · Γ 2) = e( Γ 1, Γ 2) (33)

40

n+ζ n+ζ

-No degeneración: Esta función no correlaciona todo Γ 1 ∈ G1 y Γ 2 ∈ G2 sobre el elemento de identidad del grupo cíclico GT.

-Computabilidad: Existe un algoritmo para calcular eficientemente e( Γ 1, Γ 2) para todo

45

n+ζ n+ζ

Γ 1 ∈ G1 , Γ 2 ∈ G2 (34)

En la realización, la función bilineal e se forma siguiendo una función bilineal que correlaciona el producto directo G1 x G2 de los grupos cíclicos G1 y G2 al grupo cíclico GT.

50

Par: G1xG2 → GT (35)

La función bilineal e saca un elemento del grupo cíclico GT en respuesta a un vector (n + ζ ) dimensional de entrada E10767169

06-03-2015

( γ 1, …, γ ) formado de (n + ζ ) elementos γβ ( β = 1, …, n + ζ ) del grupo cíclico G1 y un vector (n + ζ )

n+ζ

dimensional de entrada (γ 1*, …, γ *) formado de (n + ζ ) elementos γβ *( β = 1, …, n + ζ ) del grupo

n+ζ

cíclico G2.

n+ζ

5 e= Πβ =1 Par( γβ , γβ * ) (36)

La función bilineal Par saca un elemento del grupo cíclico GT en respuesta a un elemento de entrada del grupo cíclico G1 y un elemento de entrada del grupo cíclico G2 y satisface las siguientes características:

10 -Bilinealidad: La siguiente relación se satisface para todo Ω 1 ∈G1, Ω 2 ∈G2, y ν , κ∈ Fq

ν · κ

Par(ν · Ω 1, κΩ 2) = Par( Ω 1, Ω 2) (37)

-No degeneración: Esta función no correlaciona todo

15

Ω 1 ∈G1 y Ω 2 ∈G2 (38)

sobre el elemento identidad del grupo cíclico GT.

20 -Computabilidad: Existe un algoritmo para calcular eficientemente Par( Ω 1, Ω 2) para todo Ω 1 ∈G1, Ω 2 ∈G2.

Un ejemplo específico de la función bilineal Par es una función para realizar una operación de cálculo de emparejamiento tal como un emparejamiento de Weil o un emparejamiento de Tate. (Ver la bibliografía de referencia 25 4, Alfred. J. Menezes, “Elliptic Curve Public Key Cryptosystems”, Kluwer Academic Publishers, ISBN 0-7923-9368-6,

páginas 61-81, por ejemplo). Dependiendo del tipo de curva elíptica E, una función de emparejamiento e( Ω 1, phi( Ω 2)) ( Ω 1 ∈G1, Ω 2 ∈G2) que es una combinación de una función predeterminada phi y la función para cálculo de emparejamiento tal como un emparejamiento de Tate se pueden usar como la función bilineal Par (ver la bibliografía de referencia 2, por ejemplo). Como el algoritmo para realizar un cálculo de emparejamiento en un 30 ordenador, se puede usar el algoritmo de Miller (ver la bibliografía de referencia 5, V. S. Miller, “Short Programs for Functions on Curves”, 1986, http://crypto.stanford.edu/miller/miller.pdf) o algún otro algoritmo conocido. Los métodos de formación de un grupo cíclico y una curva elíptica para cálculo de emparejamiento eficaz han sido conocidos. (Por ejemplo, ver la bibliografía de referencia 2; la bibliografía de referencia 6, A. Miyaji, M. Nakabayashi, y S. Takano, “New Explicit Conditions of Elliptic Curve Traces for FR Reduction”, IEICE Trans. Fundamentals, Vol. E84-A,

35 Nº 5, páginas 1234-1243, mayo de 2001, la bibliografía referencia 7, P. S. L. M. Barreto, B. Lynn, M. Scott, “Constructing Elliptic Curves with Prescribed Embedding Degrees”, Actas SCN ‘2002, LNCS 2576, páginas 257-267, Springer-Verlag. 2003; y la bibliografía referencia 8, R. Dupont, A. Enge, F. Morain, “Building Curves with Arbitrary Small MOV Degree over Finite Prime Fields”, http//eprint.iacr.org/2002/094/.

40 ai(i = 1, …, n + ζ ): ai(i = 1, …, n + ζ ) representa unos vectores de base (n + ζ ) dimensional que tiene (n

+ ζ ) elementos del grupo cíclico G1 como elementos.

Por ejemplo, cada uno de los vectores de base ai es el vector (n + 1) dimensional en el que el elemento i-dimensional es κ 1· g1 ∈G1 y los elementos restantes son elementos identidad (cada uno de los cuales se expresa aditivamente 45 como “0”) del grupo cíclico G1. En ese caso, los elementos de los vectores de base (n + ζ ) dimensional ai (i = 1, …,

n+ ζ ) se pueden enumerar como sigue:

a1= (κ 1· g1,0, 0,…, 0)

50 a2= (0, κ 1 · g1, 0, …, 0) (39)

……

a n+ζ = (0, 0, 0, …,κ 1 · g1)

55

Aquí, κ 1 es una constante que es un elemento del campo finito Fq distinto del elemento identidad aditivo 0F. Un ejemplo de κ 1 ∈Fq es κ 1 = 1F. Los vectores de base ai son bases ortogonales. Cada vector (n + ζ ) dimensional

E10767169

06-03-2015

que tiene (n + ζ ) elementos del grupo cíclico G1 como elementos se expresa por una combinación lineal de los vectores de base (n + ζ ) dimensionales ai (i = 1, …, n + ζ ). Es decir, los vectores de base (n + ζ ) dimensionales ai extienden el espacio de vector V, descrito anteriormente.

5 ai*(i = 1, …, n + ζ ): ai*(i = 1, …, n + ζ ) representa los vectores de base (n + ζ ) dimensionales que tienen (n + ζ ) elementos del grupo cíclico G2 como elementos. Por ejemplo, cada uno de los vectores de base ai* es el vector (n + ζ ) dimensional en el que el elemento de orden i es κ 2· g2 ∈G2 y los elementos restantes son elementos

identidad (cada uno de los cuales se expresa aditivamente como “0”) del grupo cíclico G2. En ese caso, los elementos de los vectores de base ai* (i = 1, …, n + ζ ) se pueden enumerar como sigue:

10

a1*= (κ 2· g2, 0, 0, …, 0)

a2* = (0, κ 2 · g2, 0, …, 0) (40)

15 ……

a n+ζ *= (0, 0, 0, …,κ 2 · g2)

Aquí, κ 2 es una constante que es un elemento del campo finito Fq distinto del elemento identidad aditivo 0F. Un 20 ejemplo de κ 2 ∈Fq es κ 2 = 1F. Los vectores de base ai* son bases ortogonales. Cada vector (n + ζ ) dimensional

que tiene (n + ζ ) elementos del grupo cíclico G2 como elementos se expresa por una combinación lineal de los vectores de base (n + ζ ) dimensionales ai* (i = 1, …, n + ζ ). Es decir, los vectores de base (n + ζ ) dimensionales ai* extienden el espacio de vector V*, descrito anteriormente.

25 Los vectores de base ai y los vectores de base ai* satisfacen la siguiente expresión para un elementos τ = κ 1· κ 2 del campo finito Fq distinto de 0F.

τδ (i, j)

e(ai, aj* ) = gT (41)

30 Cuando i = j, se satisface la siguiente expresión a partir de las Expresiones (36) y (37).

e(ai, aj* ) = Par(κ 1 · g1, κ 2 · g2) · Par(0, 0) · … · Par(0, 0) κκ

= Par(g1, g2)1 2 · Par(g1, g2)0·0 · … · Par(g1, g2)0·0

κκ τ

= Par(g1, g2)1 2 = gT

n+ζ

Cuando i ≠ j, el lado derecho de e(ai, aj* ) = Π i=1 Par (ai , aj* ) no incluye Par(κ 1 · g1, κ 2 · g2) y es el producto de Par(κ 1 · g1, 0), Par(0,κ 2 · g2) y Par(0, 0). Además, se satisface la siguiente expresión a partir de la Expresión (37).

40

Par(g1, 0) = Par(0, g2) = Par(g1, g2)0 Por lo tanto, cuando i ≠ j, se satisface la siguiente expresión. 45 e(ai, aj* ) = e(g1, g2)0 = gT0 Especialmente cuando τ = κ 1· κ 2 = 1F (por ejemplo, κ 1= κ 2 = 1F), se satisface la siguiente expresión. δ (i, j)

e(ai, aj* ) = gT (42)

50 Aquí, gT0 = 1 es el elemento identidad del grupo cíclico GT y gT1 = gT es un generador del grupo cíclico GT. En ese caso, los vectores de base ai y los vectores de base ai* son bases ortogonales normales duales y el espacio de vector V y el espacio de vector V* son un espacio de vector dual en el que se puede definir la correlación bilineal (espacio de vector de emparejamiento dual (DPVS)).

55

A: “A” representa una matriz de (n + ζ ) filas por (n + ζ ) columnas que tiene los vectores de base ai (i = 1, …, n +

E10767169

06-03-2015

ζ ) como elementos. Cuando los vectores de base ai (i = 1, …, n + ζ ) se expresan por la Expresión (39), por ejemplo, la matriz A es como sigue:

imagen11

A*: “A*” representa una matriz de (n + ζ ) filas por (n + ζ ) columnas que tiene los vectores de base ai* (i = 1, …, n

+ ζ ) como elementos. Cuando los vectores de base ai* (i = 1, …, n + ζ ) se expresan por la Expresión (40), por ejemplo, la matriz A* es como sigue:

imagen12

X: X representa una matriz de (n + ζ ) filas por (n + ζ ) columnas que tiene elementos del campo finito Fq como

entradas. La matriz X se usa para transformación de coordenadas de los vectores de base ai. La matriz X se expresas como χ i,j ∈Fq, la matriz X es como sigue:

imagen13

donde cada χ i,j ∈Fq es la entrada en la fila de orden i y la columna de orden j (i=1, …, n+1, j=1, …, n+1) de la matriz X.

20

Aquí, cada entrada χ i,j de la matriz X se llama coeficiente de transformación.

X*: X* representa la matriz traspuesta de la matriz inversa de la matriz X. X* = (X-1)T. La matriz X* se usa para transformación de coordenadas de los vectores de base ai*. La matriz X* es como sigue:

25

imagen14

donde cada χ i,j*∈Fq es la entrada en la fila de orden i y la columna de orden j de la matriz X*. 30 Aquí, cada entrada χ i,j* de la matriz X* se llama coeficiente de transformación. En ese caso, se satisface X·(X*)T = I, donde “I” representa una matriz unidad de (n + 1) filas por (n + 1) columnas. En otras palabras, la matriz unidad se expresa como sigue.

E10767169

06-03-2015

imagen15

Se satisface la siguiente expresión.

imagen16

Aquí, los vectores (n + ζ ) dimensionales se definirán más adelante.

imagen17

El producto interior de los vectores (n + ζ ) dimensionales

satisface la siguiente expresión a partir de la

Expresión (48).

imagen18

imagen19

bi: bi representa vectores de base (n + ζ ) dimensionales que tienen (n + ζ ) elementos del grupo cíclico G1 como elementos. Los vectores de base bi se obtiene por transformación de coordenadas de los vectores de base ai (i = 1, …, n + 1) con la matriz X. Es decir, los vectores de base bi se obtienen por el siguiente cálculo

imagen20

Cuando los vectores de base aj (j = 1, …, n + ζ ) se expresan por la Expresión (39), cada elemento de los vectores de base bi se muestra más adelante.

imagen21

Cada vector (n + ζ ) dimensional que tiene (n + ζ ) elementos del grupo cíclico G1 como elementos se expresa por una combinación lineal de los vectores de base (n + ζ ) dimensionales bi (i = 1, …, n + ζ ). Es decir, los vectores de base (n + ζ ) dimensionales bi expanden el espacio de vector V, descrito anteriormente.

bi*: bi* representa los vectores de base (n + ζ ) dimensional que tienen (n + ζ ) elementos del grupo cíclico G2 como elementos. Los vectores de base bi* se obtienen por transformación de coordenadas de los vectores de base ai*(i= 1,…, n+ ζ ) con la matriz X*. Es decir, los vectores de base bi* se obtienen por el siguiente cálculo

E10767169

06-03-2015

imagen22

Cuando los vectores de base aj (j = 1, …, n + ζ ) se expresan por la Expresión (40), cada elemento de los vectores de base bi* se muestran más adelante.

imagen23

Cada vector (n + ζ ) dimensional que tiene (n + ζ ) elementos del grupo cíclico G2 como elementos se expresa por una combinación lineal de los vectores de base (n + ζ ) dimensionales bi* (i = 1, …, n + ζ ). Es decir, los vectores 10 de base (n + ζ ) dimensionales bi* expanden el espacio de vector V*, descrito anteriormente.

Los vectores de base bi y los vectores de base bi* satisfacen la siguiente expresión para los elementos τ = κ 1· κ 2 del campo finito Fq distinto de 0F:

τδ (i, j)

15 e(bi, bj* ) = gT (56) La siguiente expresión se satisface a partir de las Expresiones (36), (51), (53) y (55).

imagen24

20

Especialmente cuando τ = κ 1· κ 2 = 1F (por ejemplo, κ 1= κ 2 = 1F), se satisface la siguiente expresión.

δ (i, j)

e(bi, bj* ) = gT (57)

25 En ese caso, los vectores de base bi y los vectores de base bi* son la base ortogonal normal dual de un espacio de vector de emparejamiento dual (el espacio de vector V y el espacio de vector V*).

Siempre que se satisface la Expresión (56), se pueden usar los vectores de base ai y ai* distintos de los mostrados en las Expresiones (39) y (40) como ejemplos y los vectores de base bi y bi* distintos de los mostrados en las 30 Expresiones (52) y (54) como ejemplos.

B: B representa una matriz de (n + ζ ) filas por (n + ζ ) columnas que tiene los vectores de base bi (i = 1, …, n +

ζ ) como elementos. Se satisface B = X·A. Cuando los vectores de base bi se expresan por la Expresión (53), por ejemplo, la matriz B es como sigue:

35

E10767169

06-03-2015

imagen25

B*: B* representa una matriz de (n + ζ ) filas por (n + ζ ) columnas que tiene los vectores de base bi* (i = 1, …, n +

ζ ) como elementos. Se satisface B* = X*·A*. Cuando los vectores de base bi* (i = 1, …, n + ζ ) se expresan por la

Expresión (55), por ejemplo, la matriz B* es como sigue:

imagen26

w →:w→ representa un vector n dimensional que tiene elementos del campo finito Fq como elementos.

10

w → = (w1, …, wn) ∈Fqn (60)

wµ:wµ representa el elemento de orden µ ( µ = 1, …, n) del vector n dimensional.

15 v →:v→ representa un vector n dimensional que tiene elementos del campo finito Fq como elementos.

v → = (v1, …, vn) ∈Fqn (61)

vµ:vµ representa el elemento de orden µ ( µ = 1, …, n) del vector n dimensional.

20

[Cifrado de predicado del producto interior] El esquema básico del cifrado de predicado del producto interior se describirá más adelante.

[Cifrado de predicado]

25 En el cifrado de predicado (algunas veces llamado cifrado de función), un texto cifrado se puede descifrar cuando una combinación de una información de atributo y una información de predicado hace verdadera una fórmula lógica predeterminada. Una de la información de atributo y la información de predicado se incorpora en el texto cifrado y la otra se incorpora en la información de clave. El cifrado de predicado convencional se describe, por ejemplo, en la bibliografía de referencia 9, Jonathan Katz, Amit Sahai y Brent Waters, “Predicate Encryption Supporting

30 Disjunctions, Polynomial Equations, and Inner Products”, uno de los cuatro documentos de Eurocrypt 2008 invitados por la Journal of Cryptology.

E10767169

06-03-2015

[Cifrado de predicado del producto interior] En el cifrado de predicado del producto interior, un texto cifrado se puede descifrar cuando el producto interior de la información de atributo y la información de predicado que son vectores es cero. En el cifrado de predicado del

5 producto interior, un producto interior de cero es equivalente a la fórmula lógica de verdadero.

[Relación entre fórmula lógica y polinomio] En el cifrado de predicado del producto interior, la fórmula lógica formada de una(s) OR lógica(s) y/o una(s) AND lógica(s) se expresa por un polinomio.

10

La OR lógica (x = η 1) ∨ (x = η 2) de una proposición 1 que indica que x es η 1 y una proposición 2 que indica que x es η 2 se expresa por el siguiente polinomio.

(x -η 1)·(x -η 2) (62)

15

Entonces, las relaciones entre valores verdaderos y los valores de función de la Expresión (62) se muestran en la siguiente tabla.

Tabla 1

20

Proposición 1 (x = η 1)

Proposición 2 (x = η 2) OR lógica (x = η 1) ∨ (x = η 2) Valor de función (x = η 1)·(x = η 2)

Verdadera

Verdadera

Verdadera

0

Verdadera

Falsa Verdadera 0

Falsa

Verdadera Verdadera 0

Falsa

Falsa

Falsa

Distinto de 0

Como se entiende a partir de la Tabla 1, cuando la OR lógica (x = η 1) ∨ (x = η 2) es verdadera, el valor de función de la Expresión (62) es cero; y cuando la OR lógica (x = η 1) ∨ (x = η 2) es falsa, el valor de función de la Expresión

(62) es un valor distinto de cero. En otras palabras, la OR lógica (x = η 1) ∨ (x = η 2) de verdadera es equivalente al

25 valor de función de cero en la Expresión (62). Por lo tanto, la OR lógica se puede expresar por la Expresión (62). La AND lógica (x = η 1) ∧ (x = η 2) de la proposición 1 que indica que x es η 1 y la proposición 2 que indica que x es η 2 se expresa por el siguiente polinomio.

imagen27

30

donde

y son números aleatorios. Entonces, las relaciones entre valores verdaderos y los valores de función

de la Expresión (63) se muestran en la siguiente tabla.

Tabla 2

35

Proposición 1 (x = η 1)

Proposición 2 (x = η 2) AND lógica (x = η 1) ∧ (x = η 2) Valor de función

Verdadera

Verdadera

Verdadera

0

Verdadera

Falsa Falsa Distinto de 0

Falsa

Verdadera Falsa Distinto de 0

Falsa

Falsa

Falsa

Distinto de 0

Como se entiende a partir de la Tabla 2, cuando la AND lógica (x = η 1) ∧ (x = η 2) es verdadera, el valor de función de la Expresión (63) es cero; y cuando la AND lógica (x = η 1) ∧ (x = η 2) es falsa, el valor de función de la Expresión (63) es un valor distinto de cero. En otras palabras, una AND lógica (x = η 1) ∧ (x = η 2) de verdadera es

40 equivalente a un valor de función de cero en la Expresión (63). Por lo tanto, la AND lógica se puede expresar mediante la Expresión (63).

Como se describió anteriormente, usando las Expresiones (62) y (63), una fórmula lógica formada por una(s) OR lógica(s) y/o una(s) AND lógica(s) se puede expresar por el polinomio f(x). Un ejemplo se mostrará más adelante.

45

Fórmula lógica: {(x = η 1) ∨ (x = η 2) ∨ (x = η 3)} ∧ (x = η 4) ∧ (x = η 5)

imagen28

E10767169

06-03-2015

(64)

5

En la Expresión (62), se usa un elemento indeterminado x para expresar la OR lógica. También se puede usar una pluralidad de elementos indeterminados para expresar una OR lógica. Por ejemplo, cuando se usan dos elementos indeterminados x0 y x1, la OR lógica (x0 = η 0) ∨ (x1 = η 1) de la proposición 1 que indica que x0 es η 0 y la

proposición 2 que indica que x1 es η 1 se puede expresar el siguiente polinomio.

10

(x0 -η 0) · (x1 -η 1)

También se pueden usar tres o más elementos indeterminados para expresar una OR lógica por un polinomio.

15 En la Expresión (63), se usa un elemento indeterminado x para expresar la AND lógica. También se puede usar una pluralidad de elementos indeterminados para expresar una AND lógica. Por ejemplo, la AND lógica (x0 = η 0) ∧ (x1 = η 1) de la proposición 1 que indica que x0 es η 0 y la proposición 2 que indica que x1 es η 1 se puede expresar por el siguiente polinomio.

imagen29

También se pueden usar tres o más elementos indeterminados para expresar una AND lógica por un polinomio.

Una fórmula lógica que incluye una(s) OR lógica(s) y/o una(s) AND lógica(s) se expresa con H (H > 1) tipos de

25 elementos indeterminados x0, …, xH-1 como el polinomio f(x0, …, xH-1). Se supone que una proposición para cada uno de los elementos indeterminados x0, …, xH-1 es “xh es η h”, donde η h (h = 0, …, H-1) es una constante

determinada para cada proposición. Entonces, en el polinomio f(x0, …, xH-1) que indica la fórmula lógica, la proposición que indica que un elemento indeterminado xh es una constante η h se expresa por el polinomio que indica la diferencia entre el elemento indeterminado xh y la constante η h; la OR lógica de las proposiciones se

30 expresa por el producto de los polinomios que indican las proposiciones; y la AND lógica de las proposiciones o las OR lógicas de las proposiciones se expresa por una combinación lineal de los polinomios que indican las proposiciones o las OR lógicas de las proposiciones. Por ejemplo, se usan cinco elementos indeterminados x0, …, x4 para expresar una fórmula lógica

35 {(x0 =η 0) ∨ (x1 =η 1) ∨ (x2 =η 2)} ∧ (x3 = η 3) ∧ (x4 = η 4)

por el siguiente polinomio

imagen30

40

[Relación entre polinomio y producto interior] El polinomio f(x0, …, xH-1) que indica una fórmula lógica se puede expresar por el producto interior de dos vectores n dimensionales. Más específicamente, el polinomio f(x0, …, xH-1) es igual al producto interior de un vector

45 v → = (v1, …, vn) que tiene los elementos indeterminados de los términos del polinomio f(x0, …, xH-1) como elementos y un vector w → = (w1, …, wn)

50

que tiene los coeficientes de los términos del polinomio f(x0, …, xH-1) como elementos

f(x0, …, xH-1) = w→ ·v →

55 En otras palabras, si el polinomio f(x0, …, xH-1) que indica una fórmula lógica es cero es equivalente a si el producto interior del vector v→ que tiene los elementos indeterminados de los términos del polinomio f(x0, …, xH-1) como elementos y el vector w→ que tiene los coeficientes de los términos del polinomio f(x0, …, xH-1) como elementos es cero.

E10767169

06-03-2015

f(x0, …, xH-1) = 0 ↔ w → ·v → =0

Por ejemplo, un polinomio f(x) = θ 0·x 0 + θ 1·x +…+θ n-1·x n-1 expresado con un elemento indeterminado x se puede expresar por el producto interior de dos vectores n dimensionales como sigue.

5

w → = (w1, …, wn) = (θ 0, ...,θ n-1) (65) n-1)

v → = (v1, …, vn) = (x0, ..., x (66) 10 f(x) = w→ ·v → (67) En otras palabras, si el polinomio f(x) que indica una fórmula lógica es cero es equivalente a si el producto interior en la Expresión (67) es cero. 15 f(x) = 0 ↔ w → ·v → = 0 (68) Cuando un vector que tiene los elementos indeterminados de los términos del polinomio f(x0, …, xH-1) como elementos se expresa por 20 w → = (w1, …, wn) y un vector que tiene los coeficientes de los términos del polinomio f(x0, …, xH-1) como elementos se expresa por v → = (v1, …, vn)

25

si el polinomio f(x0, …, xH-1) que indica una fórmula lógica es cero es equivalente a si el producto interior del vector w → y el vector v→ es cero.

Por ejemplo, cuando se usan las siguientes expresiones en lugar de las expresiones (65) y (66),

30

n-1)

w → = (w1, …, wn) = (x0, ..., x (69)

v → = (v1, …, vn) = (θ 0, ...,θ n-1) (70)

35 si el polinomio f(x) que indica una fórmula lógica es cero es equivalente a si el producto interior en la Expresión (67) es cero.

En el cifrado de predicado del producto interior, uno de los vectores v→ = (v0, …, vn-1) y w→ = (w0, …, wn-1) se usa como la información de atributo y el otro se usa como la información de predicado. Una de la información de atributo 40 y la información de predicado se incorpora en el texto cifrado y la otra se incorpora en la información de clave. Por ejemplo, se usa un vector n dimensional (θ 0, ...,θ n-1) como información de predicado, otro vector n dimensional (x0, ..., x n-1) se usa como información de atributo, una de la información de atributo y la información de predicado se incorpora en el texto cifrado y la otra se incorpora en la información de clave. Se supone en la siguiente descripción que un vector n dimensional incorporado en la información de clave es w→ = (w1, …, wn) y otro vector n dimensional

45 incorporado en el texto cifrado es v→ = (v1, …, vn). Por ejemplo,

Información de predicado: w→ = (w1, …, wn) = (θ 0, ...,θ n-1) n-1)

Información de atributo: v→ = (v1, …, vn) = (x0, ..., x 50 Alternativamente,

Información de predicado: v→ = (v1, …, vn) = (θ 0, ...,θ n-1) n-1)

Información de atributo: w→ = (w1, …, wn) = (x0, ..., x

55 [Esquema básico del cifrado de predicado del producto interior] Un ejemplo de esquema básico de un mecanismo de encapsulación de claves (KEM) que usa el cifrado de predicado del producto interior se describirá más adelante. Este esquema incluye Setup(1k), GenKey(MSK, w→), Enc(PA, v→) y Dec(SKw, C2).

60 Configuración de Setup(1k):

Entrada: Parámetro de seguridad k Salida: Información de clave maestra MSK, parámetro público PK

E10767169

06-03-2015

En un ejemplo de Setup(1k), se usa el parámetro de seguridad k como n y se seleccionan la matriz de (n + ζ ) filas por (n + ζ ) columnas A que tiene los vectores de base (n + ζ ) dimensionales ai (i = 1, …, n + ζ ) como elementos, la matriz de (n + ζ ) filas por (n + ζ ) columnas A* que tiene el vector de base ai* (i = 1, …, n + ζ ) 5 como elementos y las matrices de (n + ζ ) filas por (n + ζ ) columnas X y X* usadas para transformación de coordenadas. Entonces, el vector de base (n + ζ ) dimensional bi (i = 1, …, n + ζ ) se calcula a través de transformación de coordenadas por la Expresión (52) y los vectores de base (n + ζ ) dimensional bi* (i = 1, …, n + ζ ) se calculan a través de transformación de coordenadas por la Expresión (54). Entonces, la matriz de (n + ζ ) filas por (n + ζ ) columnas B* que tiene los vectores de base bi* (i = 1, …, n + ζ ) como elementos se saca como la

10 información de clave maestra MSK; y los espacios de vector V y V*, la matriz de (n + ζ ) filas por (n + ζ ) columnas B que tiene los vectores de base bi (i = 1, …, n + ζ ) como elementos, el parámetro de seguridad k, el campo finito Fq, la curva elíptica E, los grupos cíclicos G1, G2 y GT, los generadores g1, g2 y gT, la función bilineal e y otros se sacan como el parámetro público PK.

15 Generación de información de clave GenKey(MSK, w→):

Entrada: Información de clave maestra MSK, vector w→

Salida: Información de clave D* que corresponde al vector w→

20

En un ejemplo de GenKey(MSK, w→), un elementoα∈Fq se selecciona a partir del campo finito Fq. Entonces, la matriz B*, la cual es la información de clave maestra MSK, se usa para generar y sacar una información de clave D* que corresponde al vector w→ de la siguiente manera.

imagen31

Si es difícil resolver un problema logarítmico discreto en el grupo cíclico G2, es difícil separar y extraer el componente de bµ* de la información de clave D*.

30 Cifrado Enc(PA, v→):

Entrada: Parámetro público PK, vector v→ Salida: Texto cifrado C2, clave común K

35 En un ejemplo de Enc(PA, v→), se generan la clave común K y un número aleatorio υ 0, que es un elemento del campo finito Fq. Entonces, el parámetro público PK, tal como la matriz B, los elementos υ 1, …, υζ del campo finito Fq, el vector v→ y el número aleatorio υ 0 se usan para generar el texto cifrado C2 de la siguiente forma.

imagen32

40 τυ1Se sacan el texto cifrado C2 y la clave común K. Un ejemplo de la clave común K es gT ∈GT, donde υ 1 significa υ 1. Un ejemplo de τ es 1F, como se describió anteriormente. Si es difícil resolver un problema logarítmico discreto en el grupo cíclico G1, es difícil separar y extraer el componente bµ del texto cifrado C2.

45 Descifrado y compartición de clave Dec(SKw, C2):

Entrada: Información de clave D1* que corresponde al vector w→, texto cifrado C2

Salida: Clave común K

50 En un ejemplo de Dec(SKw, C2), el texto cifrado C2 y la información de clave D1* se introducen a la función bilineal e de la Expresión (32). Entonces, a partir de las características de las Expresiones (33) y (56), se satisface lo siguiente.

E10767169

06-03-2015

imagen33

Cuando el producto interior w→ ·v → es cero, la Expresión (73) se puede deformar a la siguiente forma.

imagen34

τυ1

A partir de este resultado, se genera y se saca la clave común K. Un ejemplo de la clave común K es gT ∈GT.

[Estructura general]

10 La Figura 15 es un diagrama de bloques que ilustra la estructura de un aparato de compartición 810 según la segunda realización. La Figura 16 es un diagrama de bloques que ilustra la estructura de aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) según la segunda realización. La Figura 17 es un diagrama de bloques que ilustra la estructura de un aparato de adquisición 830 según la segunda realización. La Figura 18 es un diagrama de bloques que ilustra la estructura de una unidad de composición 835 en la Figura 17. En esas figuras, a componentes

15 idénticos a aquellos en la primera realización se dan los mismos números de referencia que en la primera realización en aras de la simplicidad.

Un sistema de compartición de secretos según esta realización se obtiene sustituyendo el aparato de compartición 110 en la Figura 1 con el aparato de compartición 810, sustituyendo los aparatos de gestión de partes [PA(α , 20 h(α ))] 120-α -h(α ) con los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) y sustituyendo el aparato de adquisición 130 con el aparato de adquisición 830.

[Aparato de compartición 810] Como se muestra en la Figura 15, el aparato de compartición 810 en esta realización incluye un almacenamiento

25 temporal 111, un almacenamiento 112, un controlador 113, unidades de compartición de secretos 814-α (α =1a L) y un transmisor 115. El aparato de compartición 810 en esta realización se implementa ejecutando un programa predeterminado leído en un ordenador conocido dotado con una CPU, una RAM, una ROM y similares, por ejemplo.

[Aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α )]

30

Como se ilustra en la Figura 16, cada uno de los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) en esta realización incluye un almacenamiento temporal 121-α -h(α ), un almacenamiento 122-α -h(α ), un controlador 123-α -h(α ), un generador de valores de secretos compartidos 824-α -h(α ), un transmisor 125-α h(α ) y un receptor 126-α -h(α ). Cada uno de los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) en

35 esta realización se implementa ejecutando un programa predeterminado leído en un ordenador conocido dotado con una CPU, una RAM, una ROM y similares, por ejemplo.

[Generador de valor común 140-α ] El generador de valor común 140-α es el mismo que en la primera realización.

40

[Aparato de adquisición 830] Como se ilustra en la Figura 17, el aparato de adquisición 830 en esta realización incluye un almacenamiento temporal 131, un almacenamiento 132, un controlador 133, unidades de reconstrucción 834-α (α = 1 a L), una unidad de composición 835, un transmisor 135 y un receptor 136. Como se muestra en la Figura 18, la unidad de

45 composición 835 incluye una primera unidad de operación 835a y una segunda unidad de operación 835b. El aparato de adquisición 830 en esta realización se implementa ejecutando un programa predeterminado leído en un

15

35

45

55

E10767169

06-03-2015

ordenador conocido dotado con una CPU, una RAM, una ROM y similares, por ejemplo.

[Procesamiento de compartición de secretos] El procesamiento de compartición de secretos en esta realización se describirá a continuación.

Esta realización es una aplicación de la primera realización: Una matriz B* (Expresión (59)), que es la información de clave maestra MSK del cifrado de predicado del producto interior, se comparte con un esquema de compartición de secretos y se reconstruye la información de claves D*, como se da por la Expresión (71). En la descripción dada más adelante, la información de claves D* de la Expresión (71) se generaliza a la información de generación dada por

imagen35

La Expresión (71) es un ejemplo cuando ζ = 1. Los elementos

imagen36

de la matriz B* dada por la Expresión (55) se expresan como

imagen37

Cuando el vector de base bi* de la Expresión (55) se expresa como

imagen38

Esta indica que la compartición de secretos de la matriz B* y la reconstrucción de la información de generación SK se pueden ejecutar extendiendo la primera realización o sus modificaciones a múltiples dimensiones.

La diferencia de la primera realización y sus modificaciones se describirá principalmente más adelante. Las partes en común a ellas no se describirán.

[Procesamiento preparatorio] En el procesamiento preparatorio para el procesamiento de compartición de secretos en esta realización, la

información θ (i, β ) ∈Fq para identificar la información secreta θ (i, β ) · g2 ∈ G2(i = 1 a n + ζ , β =1an+ ζ ) cada parte de la cual es un elemento del vector de base bi*, se almacena en el almacenamiento 112 del aparato de compartición 810.

[Procesamiento de compartición de secretos entero] La Figura 19 es una vista que ilustra el procesamiento de compartición de secretos entero en la segunda realización. El procesamiento de compartición de secretos entero en esta realización se describirá a continuación con referencia a la Figura 19.

En esta realización, el aparato de compartición 810 (Figura 15) genera las partes SH(i, β , α ,h(α ))

compartiendo la información secreta θ (i, β ) · g2 ∈ G2 , cada parte de la cual es un elemento de los vectores de

base bi*, para cada uno de los subconjuntos SUB(α ) separadamente y saca las partes SH(i, β , α ,h(α )) (paso S81). El esquema de compartición de secretos específicos es el mismo que en la primera realización. Un conjunto de partes SH(i, β , α ,h(α ))∈ G2(i = 1 a n + ζ , β =1an+ ζ ) se llama una parte SH(α ,h(α )). Las partes SH(α ,h(α )) se envían a través de la red 150 a los aparatos de gestión de partes correspondientes [PA(α ,

h(α ))] 820-α -h(α ).

Cada uno de los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) al cual se envió cada una de las partes SH(α ,h(α )) genera un valor de secreto compartido DSH(α ,h(α )) usando las partes SH(i, β , α ,h (α )) que forman cada una de las partes SH(α ,h(α )), un valor común σ (α ) usado en cada uno de los

subconjuntos SUB(α ) y un vector n dimensional w→ = (w1, …, wn) que tiene elementos de un campo finito Fq como elementos wµ ( µ = 1 a n) (paso S82). El valor de secreto compartido DSH(α ,h(α )) en esta realización es

E10767169

06-03-2015

imagen39

donde SHbi* (α ,h(α )) está siguiendo el vector de base compartido (n + ζ ) dimensional, que tiene (n + ζ ) partes SH(i, 1, α ,h(α )) a SH(i, n+ ζ , α ,h(α )) como elementos.

imagen40

En esta realización, los valores comunes (σ (α )) de diferentes subconjuntos SUB(α ) son independientes unos de 10 otros.

Los valores de secretos compartidos DSH(α , h(α )) sacados de los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) se envían separadamente a través de la red 150 al aparato de adquisición 830. Usando la pluralidad de valores de secretos compartidos DSH(α , h(α )) que corresponden al mismo subconjunto SUB(α ), el aparato

15 de adquisición 830 genera un valor de secreto reconstruido SUBSK(α ) expresado como sigue por el procesamiento de reconstrucción para cada subconjunto SUB(α ) (paso S83).

imagen41

20 Este procesamiento se puede implementar ejecutando el procesamiento de reconstrucción en la primera realización

o sus modificaciones para cada dimensión µ de los valores de secretos compartidos DSH(α , h(α )).

El aparato de adquisición 830 entonces genera información de generación SK usando los valores de secretos reconstruidos SUBSK(α ) generados para los subconjuntos correspondientes SUB(α ) y saca la información de

25 generación SK (paso S84).

En esta realización, el aparato de adquisición 830 genera la información de generación SK realizando una combinación lineal de los valores de secretos reconstruidos SUBSK(α ). Un ejemplo de la información de generación se expresa como sigue.

30

imagen42

[Procesamiento (en el paso S81) en el aparato de compartición] La Figura 20 es una vista que ilustra un ejemplo de procesamiento en el aparato de compartición en la segunda 35 realización. El procesamiento en el aparato de compartición 810 se describirá a continuación en detalle con referencia a esta figura.

El controlador 113 del aparato de compartición 810 (Figura 15) especifica α =1y β = 1 y almacena los ajustes en el almacenamiento temporal 111 (paso S811). El controlador 113 del aparato de compartición 810 entonces 40 especifica i = 1 y almacena el ajuste en el almacenamiento temporal 111 (paso S812).

La información θ (i, β ) ∈Fq para identificar la información secreta θ (i, β ) · g2 ∈ G2(i = 1 a n + ζ , β =1an+

ζ ) se lee del almacenamiento 112 e introduce a la unidad de compartición de secretos 814-α . La unidad de compartición de secretos 814-α genera H(α ) partes

45

imagen43

para un subconjunto SUB(α ) compartiendo la información secreta θ (i, β ) · g2 usando la información θ (i, β ) ∈Fq y las saca (paso S813). Este procesamiento se puede ejecutar por el mismo método que en el paso S112 de la 50 primera realización o sus modificaciones.

5

10

15

20

25

30

35

40

45

50

55

E10767169

06-03-2015

El controlador 113 entonces juzga si β almacenado en el almacenamiento temporal 111 es n + ζ (paso S814). Si

no se juzga que β =n+ ζ , el controlador 113 especifica β + 1 como un nuevo valor de β , almacena el ajuste en el almacenamiento temporal 111 (paso S815) y hace que el procesamiento del paso S813 sea ejecutado con este nuevo valor de β .

Si se juzga en el paso S814 que β =n+ ζ , el controlador 113 especifica β = 1 y almacena el ajuste en el almacenamiento temporal 111 (paso S816). Entonces, el controlador 113 juzga si i almacenado en el almacenamiento temporal 111 es n + ζ (paso S817). Si no se juzga que i = n + ζ el controlador 113 especifica i + 1 como un nuevo valor de i, almacena el ajuste en el almacenamiento temporal 111 (paso S818) y hace que el

procesamiento del paso S813 sea ejecutado con el nuevo valor de i.

Si se juzga en el paso S817 que i = n + ζ , el controlador 113 juzga si α almacenada en el almacenamiento temporal 111 es L (paso S113). Si no se juzga que α = L, el controlador 113 especifica α + 1 como un nuevo valor de α , almacena el ajuste en el almacenamiento temporal 111 (paso S114) y hace que el procesamiento del paso S812 sea ejecutado con el nuevo valor de α .

Si se juzga en el paso S113 que α = L, las partes SH(α ,h(α ))sacadas de las unidades de compartición de

secretos 814-α se envían al transmisor 115. El transmisor 115 envía conjuntos de (n + ζ )2 partes

imagen44

a los aparatos de gestión de partes correspondientes [PA(α , h(α ))] 820-α -h(α ) a través de la red 150 (paso

S819). La parte SH(1, 1) formada de (n + ζ )2 partes SH(i, β , 1, 1) (i = 1 a n + ζ , β =1an+ ζ ) se envía al

aparato de gestión de partes [PA(1, 1)] 820-1-1; la parte SH(1, 2) formada de (n + ζ )2 partes SH(i, β , 1, 2) (i = 1 a

n+ ζ , β =1an+ ζ ) se envía al aparato de gestión de partes [PA(1, 2)] 820-1-2; …; y la parte SH(L, H(L))

formada de (n + ζ )2 partes SH(i, β , L, H(L)) (i = 1 a n + ζ , β =1an+ ζ ) se envía al aparato de gestión de partes [PA(L, H(L))] 820-L-H(L).

[Procesamiento en generador de valor común] Cada uno de los generadores de valores comunes 140-α (Figura 3B) genera un valor común σ (α ) a ser compartido por los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) incluidos en el subconjunto SUB(α ) que corresponde al generador de valor común 140-α . En esta realización, se usa un número aleatorio generado por el generador de números aleatorios 141-α como el valor común σ (α ) y el transmisor 142-α envía el valor común σ (α ) a los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) incluidos en el subconjunto SUB(α ).

[Procesamiento (en el paso S82) de los aparatos de gestión de partes] La Figura 21 es una vista que ilustra un ejemplo de procesamiento en los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) en la segunda realización. El procesamiento en los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) en esta realización se describirá a continuación con referencia a esta figura.

Cada uno de los receptores 126-α -h(α ) de los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) recibe la parte SH(α -h(α )) formada de las (n + ζ )2 partes enviadas SH(i, β , α , h(α )) (i = 1 a n + ζ , β =1a

n+ ζ ) y la almacena en el almacenamiento 122-α -h(α ) (paso S821). Si el procesamiento en el paso S821 se ejecutó antes y si la parte SH(α -h(α )) ya ha sido almacenada en el almacenamiento 122-α -h(α ) del aparato de gestión de partes [PA(α , h(α ))] 820-α -h(α ), se puede omitir el procesamiento del paso S821.

Cada uno de los receptores 126-α -h(α ) de los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) recibe cada uno de los valores comunes σ (α ) enviados desde los generadores de valores comunes 140-α y los almacena en cada uno de los almacenamientos 122-α -h(α ) (paso S122).

En esta realización, un vector n dimensional w→ = (w1, …, wn), que es la información proporcionada leída desde el almacenamiento 132 del aparato de adquisición 830 (Figura 17), se envía desde el transmisor 135 a través de la red 150 a los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ). El vector n dimensional w→ = (w1, …, wn) es común a todos los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ). El vector n dimensional w→ = (w1,

E10767169

06-03-2015

…, wn) se recibe por cada uno de los receptores 126-α -h(α ) de los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) (Figura 16) y se almacena en cada uno de los almacenamientos 122-α -h(α ) (paso S823).

Cada uno de los generadores de valores de secretos 824-α -h(α ) lee la parte SH(α , h(α )), el valor común

5 σ (α ) y el vector n dimensional w→ = (w1, …, wn) desde cada uno de los almacenamientos 122-α -h(α ). Cada uno de los generadores de valores de secretos 824-α -h(α ) genera un valor de secreto compartido DSH(α , h(α )) dado por la Expresión (81), usando la parte SH(α , h(α )) y la información común que contiene el valor común σ (α )yw→ = (w1 a wn) y saca el valor de secreto compartido DSH(α , h(α )) (paso S824).

10 Cada uno de los valores de secretos compartidos generados DSH(α , h(α )) se envía a cada uno de los transmisores 125-α -h(α ). Los transmisores 125-α -h(α ) envían los valores de secretos compartidos DSH(α , h(α )) a través de la red 150 al aparato de adquisición 830 (paso S125).

[Procesamiento (en los pasos S83 y S84) en el aparato de adquisición]

15 La Figura 22 es una vista que ilustra un ejemplo de procesamiento en el aparato de adquisición en la segunda realización.

Los valores de secretos compartidos DSH(α , h(α )) enviados desde los aparatos de gestión de partes [PA(α , h(α ))] 820-α -h(α ) se reciben por el receptor 136 del aparato de adquisición 830 (Figura 17) y se almacenan en

20 el almacenamiento 132 (paso S131).

Entonces, el controlador 133 juzga si el número de valores de secretos compartidos DSH(α , h(α )) almacenados en el almacenamiento 132 es mayor o igual al número requerido (paso S132). Si no se juzga aquí que los valores de secretos compartidos DSH(α , h(α )) del número requerido o mayor se almacenan en el almacenamiento 132, el

25 procesamiento vuelve al paso S131.

Si se juzga que el número de valores de secretos compartidos DSH(α , h(α )) almacenados en el almacenamiento 132 es mayor o igual que el número requerido, el controlador 133 especifica α = 1 y almacena el ajuste en el almacenamiento temporal 131 (paso S133). Entonces, el número requerido de valores de secretos compartidos

30 DSH(α , h(α )) que corresponden al subconjunto SUB(α ) se leen desde el almacenamiento 132 e introducen a la unidad de reconstrucción 834-α . La unidad de reconstrucción 834-α genera un valor de secreto reconstruido SUBSK(α ) dado por la Expresión (82), por el procesamiento de reconstrucción para el subconjunto SUB(α ), usando los valores de secretos compartidos de entrada DSH(α , h(α )) y saca el valor de secreto reconstruido SUBSK(α ) del subconjunto SUB(α ) (paso S834).

35

El controlador 133 a continuación juzga si α almacenado en el almacenamiento temporal 131 es L (paso S135). Si no se juzga aquí que α = L, el controlador 133 especifica α + 1 como un nuevo valor de α , almacena el ajuste en el almacenamiento temporal 131 (paso S136) y hace que el procesamiento en el paso S834 sea ejecutado con el nuevo valor de α .

40

Si se juzga en el paso S135 que α = L, los valores de secretos reconstruidos SUBSK(α ) sacados de las unidades de reconstrucción correspondientes 134-α se envían a la unidad de composición 835. La primera unidad de operación 835a (Figura 18) de la unidad de composición 835 genera la siguiente combinación lineal y la saca (paso

S841).

45

imagen45

La combinación lineal SUBSK(1) + … + SUBSK(L) se introduce a la segunda unidad de operación 835b. La segunda unidad de operación 835b genera la siguiente información de generación y saca la información de generación SK 50 (paso S842).

imagen46

[Modificación de la segunda realización] 55 Las modificaciones de la primera realización se pueden aplicar a esta realización, también.

10

15

20

25

30

35

40

45

50

E10767169

06-03-2015

[Otras modificaciones y otros] La presente invención no está limitada a las realizaciones descritas anteriormente. Por ejemplo, cada operación definida en el campo finito Fq se puede sustituir con una operación definida en un anillo finito Zq cuyo orden es q. Un método de sustitución de la operación definida en el campo finito Fq con la operación definida en el anillo finito Zq es para permitir un q distinto de números primos y sus potencias.

En lugar de la Expresión (71), se puede usar la siguiente Expresión:

imagen47

donde

imagen48es una constante o una variable (tal como un número aleatorio). El procesamiento descrito anteriormente se puede ejecutar en el orden en el que se describe aquí o se puede ejecutar en paralelo o independientemente, según las capacidades de procesamiento de las unidades que ejecutan el procesamiento o como se necesite. Son posibles otras modificaciones dentro del alcance de la presente invención.

Cuando la estructura descrita anteriormente se implementa por un ordenador, los detalles de procesamiento de las funciones que se deberían proporcionar por cada aparato se describen en un programa. Cuando el programa se ejecuta por un ordenador, las funciones de procesamiento descritas anteriormente se implementan en el ordenador.

El programa que contiene los detalles de procesamiento se puede grabar en un medio de almacenamiento legible por ordenador. El medio de almacenamiento legible por ordenador puede ser cualquier tipo de medio, tal como un dispositivo de almacenamiento magnético, un disco óptico, un medio de almacenamiento magneto óptico y una memoria de semiconductores.

El programa se distribuye por venta, transferencia o préstamo de un medio de grabación portátil tal como un DVD o un CD-ROM con el programa grabado en él, por ejemplo. El programa también se puede distribuir almacenando el programa en una unidad de almacenamiento de un ordenador servidor y transfiriendo el programa desde el ordenador servidor a otro ordenador a través de la red.

Un ordenador que ejecuta este tipo de programa primero almacena el programa grabado en el medio de grabación portátil o el programa transferido desde el ordenador servidor en su unidad de almacenamiento. Entonces, el ordenador lee el programa almacenado en su unidad de almacenamiento y ejecuta el procesamiento según el programa leído. En una forma de ejecución de programa diferente, el ordenador puede leer el programa directamente desde el medio de grabación portátil y ejecutar un procesamiento según el programa o el ordenador puede ejecutar un procesamiento según el programa cada vez que el ordenador recibe el programa transferido desde el ordenador servidor. Alternativamente, el procesamiento se puede ejecutar por un denominado servicio de proveedor de servicios de aplicaciones (ASP), en el que la función de procesamiento se implementa solo dando una instrucción de ejecución de programa y obteniendo los resultados sin transferir el programa desde el ordenador servidor al ordenador. El programa de esta realización incluye información que se proporciona para uso en el procesamiento por un ordenador y se trata por consiguiente como un programa (algo que no es una instrucción directa al ordenador pero son datos o similares que tienen características que determinan el procesamiento ejecutado por el ordenador).

En esta realización, los aparatos se implementan ejecutando el programa predeterminado en el ordenador, pero al menos una parte del procesamiento se puede implementar por hardware.

DESCRIPCIÓN DE LOS NÚMEROS DE REFERENCIA

1: Sistema de compartición de secretos 110, 810: Aparatos de compartición 120, 820: Aparatos de gestión de partes 130, 830: Aparatos de adquisición

140: Generador de valor común

Claims (33)

1. 5

   10

   15

   20

   25

   30

   35

   40

   45

   50

   55

   60

   REIVINDICACIONES

   1. Un sistema de compartición de secretos caracterizado por que comprende

   L

   un aparato de compartición (110); ∑ h(α) aparatos de gestión de partes PA(α , h(α )) donde α = 1,

   α=1

   …, L, L> 2,h(α ) = 1, …, H(α ), H(α ) > 2; y un aparato de adquisición (130); en donde el aparato de compartición (110) incluye unidades de compartición de secretos (114-α ) adaptadas para generar partes SH(α , h(α )) compartiendo secretos de información secreta con un esquema de compartición de secretos separadamente para subconjuntos respectivos SUB(α ) cada uno de los cuales está formado de H(α ) aparatos de gestión de partes PA(α , 1), …, PA (α , H(α )) y para sacar las partes SH (α , h(α )); los aparatos de gestión de partes PA (α , h(α )) incluyen generadores de valores de secretos compartidos (124-α -h(α )) adaptados para generar valores de secretos compartidos DSH(α , h(α )) y sacar los valores de secretos compartidos DSH(α , h(α )) respectivamente, cada uno de los valores de secretos compartidos DSH(α , h(α )) que se genera realizando una operación común a una de las partes SH(α , h(α )) y la información común que contiene uno de los valores comunes σ (α ), cada uno de los valores comunes σ (α ) que está compartido en cada uno de los subconjuntos SUB(α ), la información común usada por los aparatos de gestión de partes PA(α , h(α )) que pertenecen al mismo de los subconjuntos SUB(α ) que es el mismo y los aparatos de gestión de partes PA(α , h(α )) que pertenecen al mismo de los subconjuntos SUB(α ) que realizan la misma operación común; el aparato de adquisición (130) incluye:

   unidades de reconstrucción (134-α ) adaptados para generar valores de secretos reconstruidos SUBSK(α ) que corresponden a los subconjuntos SUB(α ) respectivamente, cada uno de los valores de secretos reconstruidos SUBSK(α ) que se genera realizando un procesamiento de reconstrucción con el esquema de compartición de secretos para cada uno de los subconjuntos SUB(α ), usando una pluralidad de los valores de secretos compartidos DSH(α , h(α )) que corresponde al mismo de los subconjuntos SUB(α ); y una unidad de composición (137) adaptada para generar información de generación SK usando los valores de secretos reconstruidos SUBSK(α ) y para sacar la información de generación SK.

2. 2.

   El sistema de compartición de secretos según la Reivindicación 1, en donde los valores comunes σ (α ) compartidos en diferentes subconjuntos SUB(α ) son independientes unos de otros.

3. 3.

   El sistema de compartición de secretos según la Reivindicación 1 ó 2, en donde los generadores de valores de secretos compartidos (124-α -h(α )) de los aparatos de gestión de partes PA(α , h(α )), donde α = 1, …, L, realizan la misma operación común.

4. 4.

   El sistema de compartición de secretos según la Reivindicación 3, en donde la operación común es lineal; y la unidad de composición (137) está adaptada para generar la información de generación SK realizando una combinación lineal de los valores de secretos reconstruidos SUBSK(α ).

5. 5.

   El sistema de compartición de secretos según la Reivindicación 1, en donde la información común contiene el uno de los valores comunes σ (α ) y la información común proporcionada a todos los aparatos de gestión de partes PA(α , h(α )), proporcionados por el aparato de adquisición (130).

6. 6.

   El sistema de compartición de secretos según la Reivindicación 1, en donde la unidad de composición (137) está adaptada para generar la información de generación SK realizando una combinación lineal de los valores de secretos reconstruidos SUBSK(α ).

7. 7.

   El sistema de compartición de secretos según la Reivindicación 1, en donde la operación común es lineal.

8. 8.

   El sistema de compartición de secretos según la Reivindicación 1, en donde cada una de las unidades de compartición de secretos (114-α ) está adaptada para generar las partes SH(α , h(α )) por compartición de secretos de la información secreta usando un esquema de compartición de secretos de umbral (R(α ), H(α )), donde2 < R(α ) < H(α ), con respecto a al menos una parte de los subconjuntos SUB(α ); y las unidades de reconstrucción (134-α ) están adaptadas para generar los valores de secretos reconstruidos SUBSK(α ) que corresponden a los subconjuntos SUB(α ) respectivamente, cada uno de los valores de secretos reconstruidos SUBSK(α ) que se genera usando R(α ) o más valores de secretos compartidos DSH(α , h(α ))

   5

   10

   15

   20

   25

   30

   35

   40

   45

   50

   que corresponden al mismo de los subconjuntos SUB(α ).
9. 9. El sistema de compartición de secretos según la Reivindicación 8, en donde la información secreta contiene un

   elemento θ ·g ∈ G de un grupo cíclico G, donde g es un generador del grupo cíclico G y θ es un elemento del campo finito Fq; el elemento θ∈ Fq identifica la información secreta; y cada una de las partes SH(α , h(α )) generada usando el esquema de compartición de secretos de umbral (R(α ),

   H(α )) incluye un elemento f(α , φ (h(α )))·g ∈ G del grupo cíclico G, donde x representa una variable que es un elemento del campo finito Fq, f(α , x)∈ Fq representa un polinomio de grado de orden (R(α ) – 1) que satisface

   f(α , ω )= θ con respecto a un elemento predeterminado ω∈ Fq del campo finito Fq y φ (h(α )) representa un índice que corresponde a h(α ).
10. 10. El sistema de compartición de secretos según la Reivindicación 8, en donde la información secreta contiene un elemento θ de un campo finito Fq; y cada una de las partes SH(α , h(α )) generada usando el esquema de compartición de secretos de umbral (R(α ),

    H(α )) incluye un elemento f(α , φ (h(α ))) ∈ Fq del campo finito Fq, donde x representa una variable que es un elemento del campo finito Fq, f(α , x)∈ Fq representa un polinomio de grado de orden (R(α ) – 1) que satisface

    f(α , ω )= θ con respecto a un elemento predeterminado ω∈ Fq del campo finito Fq y φ (h(α )) representa un índice que corresponde a h(α ).

11. 11.

    El sistema de compartición de secretos según la Reivindicación 1, en donde cada una de las unidades de compartición de secretos (114-α ) está adaptada para generar las partes SH(α , h(α )) de la información secreta usando un esquema de compartición de secretos de umbral (H(α ), H(α )) con respecto a al menos una parte de los subconjuntos SUB(α ); y las unidades de reconstrucción (134-α ) están adaptadas para generar los valores de secretos reconstruidos SUBSK(α ) que corresponden a los subconjuntos SUB(α ) respectivamente, cada uno de los valores de secretos reconstruidos SUBSK(α ) que se genera usando H(α ) valores de secretos compartidos DSH(α , h(α )) que corresponden al mismo de los subconjuntos SUB(α ).

12. 12.

    El sistema de compartición de secretos según la Reivindicación 11, en donde la información secreta contiene un elemento θ ·g ∈ G de un grupo cíclico G, donde g es un generador del grupo cíclico G y θ es un elemento de un

    campo finito Fq; y las partes SH(α , h(α )) generadas usando el esquema de compartición de secretos de umbral (H(α ), H(α )) son elementos del grupo cíclico G, que satisfacen SH(α , 1) + SH(α ,2) + … + SH(α , H(α )) = θ ·g ∈ G.

13. 13.

    El sistema de compartición de secretos según la Reivindicación 11, en donde la información secreta contiene un elemento θ de un campo finito Fq; y las partes SH(α , h(α )) generadas usando el esquema de compartición de secretos de umbral (H(α ), H(α )) son elementos del campo finito Fq, que satisfacen SH(α , 1) + SH(α ,2) + … + SH(α , H(α )) = θ∈ Fq.

14. 14.

    El sistema de compartición de secretos según cualquiera de las Reivindicaciones 5 a 13, en donde la

    información secreta es un conjunto de vectores de base bi* que son b1*, …, b *, donde g es un generador de un

    n+ζ

    grupo cíclico G, θ (i, β ) es un elemento de un campo finito Fq, i = 1, …, n + ζ , β = 1, …, n +ζ , n > 1, ζ >1y

    n+ζ

    bi* = (θ (i, 1)·g, …, θ (i, n + ζ )·g) ∈ G es un vector de base (n +ζ ) dimensional que tiene (n + ζ ) elementos del grupo cíclico G como elementos; cada una de las unidades de compartición de secretos (814-α ) está adaptada para generar las partes SH(i, β ,

    α ,h(α ))∈ G por compartición de secretos de los elementos θ (i, β )·g ∈ G de los vectores de base bi* separadamente para los subconjuntos respectivos SUB(α ) y cada una de las partes SH(α , h(α )) es un conjunto de las partes SH(i, β , α ,h(α ))∈ G dondei=1,…,n+ ζ , β = 1, …,n+ζ ; un vector n dimensional w→ = (w1, …, wn) que tiene elementos del campo finito Fq como elementos wµ, donde se

    proporciona µ = 1, …, n; cada uno de los generadores de valores de secretos compartidos (824-α -h(α ) genera cada uno de los valores de secretos compartidos DSH(α , h(α )) usando las partes SH(i, β , α , h(α )) dondei=1,…,n+ ζ , β = 1, …, n

    5

    10

    15

    20

    25

    30

    35

    40

    45

    +ζ ; el uno de los valores comunes σ (α ) y el vector n dimensional w→ y cada uno de los valores de secretos

    nn+ζ

    compartidos DSH(α , h(α )) es DSH(α , h(α )) = σ (α )·{ ∑ wµ·SHbµ*(α , h(α ))} + ∑ SHbµ*(α ,

    µ=1 µ=n+1

    n+ζ

    h(α )) ∈ G con respecto a un vector de base de partes (n +ζ ) dimensional SHbi*(α , h(α )) = SH(i, 1,α ,

    n+ζ

    h(α )), …, SH(i, n + ζ ,α , h(α )) ∈ G formado de (n + ζ ) partes SH(i, 1,α , h(α )), …, SH(i, n + ζ ,α , h(α )); y

    n

    cada uno de los valores de secretos reconstruidos SUBSK(α ) es SUBSK(α )= σ (α )·{ ∑ wµ·bµ*} +

    µ=1

    n+ζ bµ *∈ G n+ζ .

    ∑µ=n+1
15. 15. El sistema de compartición de secretos según la Reivindicación 14, en donde la unidad de composición (835)

    n

    está adaptada para calcular la información de generación SK = {(σ (1) + …+σ (L))/L}·{ ∑ wµ·bµ*} +

    µ=1

    n+ζ

    ∑µ=n+1 bµ*.
16. 16. Un aparato de compartición que comprende unidades de compartición de secretos (114-α ) adaptado para recibir información secreta, para generar partes SH(α , h(α ))) por compartición de secretos de la información secreta separadamente para los subconjuntos SUB(α ) respectivos, cada uno de los subconjuntos SUB(α ) que está formado de H(α ) aparatos de gestión de partes PA(α , 1), …, PA(α , H(α )),α = 1, …, L, L > 2, h(α ) = 1, …, H(α ), H(α ) > 2 y para sacar las partes SH(α , h(α )), el aparato de compartición caracterizado por que la información secreta es un conjunto de vectores de base bi*

    nn+ζ

    que son b1*, …, b * de SUBSK(α )= σ (α )·{ ∑ wµ·bµ*} + bµ *∈ G n+ζ , donde g es un

    n+ζ µ=1 ∑µ=n+1

    generador de un grupo cíclico G, θ (i, β ) es un elemento de un campo finito Fq, i = 1, …, n + ζ , β = 1, …,n

    n+ζ

    +ζ , n > 1, ζ > 1 y bi*= (θ (i, 1)·g, …, θ (i, n+ ζ )·g) ∈ G es un vector de base (n +ζ ) dimensional que

    tiene (n + ζ ) elementos del grupo cíclico G como elementos, w→ es un vector n dimensional w→ = (w1, …, wn) que tiene elementos del campo finito Fq como elementos wµ, µ = 1, …, n y σ (α ) es un valor común σ (α ) compartido en cada uno de los subconjuntos SUB(α ); y

    cada una de las unidades de compartición de secretos (814-α ) está adaptada para generar partes SH(i, β ,α ,

    h(α )) ∈ G por compartición de secretos de los elementos θ (i, β ) ·g ∈ G de los vectores de base bi* separadamente para los subconjuntos SUB(α ) respectivos y cada una de las partes SH(α , h(α )) es un conjunto de las partes SH(i, β ,α , h(α ))∈ G donde i= 1, …, n + ζ , β = 1, …,n +ζ .

17. 17.

    Un aparato de gestión de partes caracterizado por que comprende:

    un generador de valores de secretos compartidos (124-α , h(α )) adaptado para generar un valor de secreto compartido DSH(α , h(α )) realizando una operación común a una de las partes SH(α , h(α )) obtenida por compartición de secretos de la información secreta separadamente para cada uno de los subconjuntos SUB(α ) y la información común que contiene uno de los valores comunes σ (α ), cada uno de los valores comunes σ (α ) que está compartido en cada uno de los subconjuntos SUB(α ), el uno de los valores comunes σ (α ) que está compartido en uno de los subconjuntos SUB(α ), cada uno de los subconjuntos SUB(α ) que está formado de H(α ) aparatos de gestión de partes PA(α , 1), …, PA(α , H(α )) y para sacar el valor de secreto compartido DSH(α , h(α )), donde α = 1, …, L, L > 2, h(α ) = 1, …, H(α ), H(α ) > 2; la información común se comparte con los aparatos de gestión de partes PA(α , h(α )) que pertenecen al mismo de los subconjuntos SUB(α ); y la operación común se realiza por los aparatos de gestión de partes PA(α , h(α )) que pertenecen al mismo de los subconjuntos SUB(α ).

18. 18.

    El aparato de gestión de partes según la Reivindicación 17, en donde los valores comunes σ (α ) compartidos en diferentes subconjuntos SUB(α ) son independientes unos de otros.

19. 19.

    El aparato de gestión de partes según una de las Reivindicaciones 17 y 18, en donde la operación común se

    5

    10

    15

    20

    25

    30

    35

    40

    45

    50

    realiza por todos los generadores de valores de secretos compartidos (124-α -h(α )) de los aparatos de gestión de partes PA(α , h(α )) donde α = 1, …, L.

20. 20.

    El aparato de gestión de partes según la Reivindicación 17, en donde la información común contiene el uno de los valores comunes σ (α ) y la información común proporcionada a todos los aparatos de gestión de partes PA(α , h(α )), proporcionada por el aparato de adquisición (130).

21. 21.

    El aparato de gestión de partes según la Reivindicación 20, en donde la información proporcionada es un vector

    n dimensional w→ = (w1, …, wn) que tiene elementos de un campo finito Fq como elementos wµ ( µ =1, …, n); y el generador de valores de secretos compartidos (824-α -h(α )) genera el valor de secreto compartido DSH(α ,

    h(α )) usando las partes SH(i, β , α , h(α )), el uno del valor común σ (α ) y el vector n dimensional w→;y el valor de secreto compartido DSH(α , h(α )) es

    nn+ζ

    DSH(α ,h(α )) = σ (α )·{ ∑ wµ·SHbµ*(α , h(α ))} + ∑ SHbµ*(α , h(α )) ∈ G n+ζ con respecto a un

    µ=1 µ=n+1

    vector de base de parte (n +ζ ) dimensional SHbi*(α , h(α )) = (SH(i, 1,α , h(α )), …, SH(i, n + ζ ,α , h(α )) ∈

    n+ζ

    G formado de (n + ζ ) partes SH(i, 1,α , h(α )), …, SH(i, n + ζ ,α , h(α )) donde ζ > 1.
22. 22. Un aparato de adquisición que comprende:

    unidades de reconstrucción (134-α ) adaptadas para generar valores de secretos reconstruidos SUBSK(α ) que corresponden a subconjuntos SUB(α ) respectivamente, cada uno de los subconjuntos SUB(α ) que están formados de H(α ) aparatos de gestión de partes PA(α , 1), …, PA(α , H(α )), cada uno de los valores de secretos reconstruidos SUBSK(α ) que se genera por procesamiento de reconstrucción con un esquema de compartición de secretos para cada uno de los subconjuntos SUB(α ) usando una pluralidad de valores de secretos compartidos DSH(α , h(α )) que corresponde al mismo de los subconjuntos SUB(α ), α = 1, …,L, L> 2,h(α ) = 1, …, H(α ), H(α ) > 2; y una unidad de composición (137) adaptada para generar información de generación SK usando los valores de secretos reconstruidos SUBSK(α ) y para sacar la información de generación SK, el aparato de adquisición caracterizado por que además comprende:

    una unidad de salida (135) para sacar un vector n dimensional w→ = (w1, …, wn) que tiene elementos de un campo finito Fq como elementos wµ donde µ = 1, …, n); en donde cada uno de los valores de secretos reconstruidos SUBSK(α ) es SUBSK(α )=

    nn+ζ

    σ (α )·{ ∑ wµ·bµ*} + ∑ bµ *∈ G n+ζ , donde σ (α ) es un valor común compartido de

    µ=1 µ=n+1

    cada uno de los subconjuntos SUB(α ), g es un generador de un grupo cíclico G, θ (i, β ) es un

    elemento del campo finito Fq, i = 1, …, n + ζ , β = 1, …, n+ζ , n > 1, ζ > 1 y bi* = (θ (i, 1)·g, …, θ

    n+ζ

    (i, n + ζ )·g) ∈ G es un vector de base (n +ζ ) dimensional que tiene (n + ζ ) elementos del grupo cíclico G como elementos.
23. 23. El aparato de adquisición según la Reivindicación 22, en donde la unidad de composición (835) está adaptada

    nn+ζ

    para calcular la información de generación SK = {(σ (1) + …+σ (L))/L}·{ ∑ wµ·bµ*} + ∑ bµ*.

    µ=1 µ=n+1
24. 24. Un método de compartición de secretos caracterizado por que comprende los pasos de:

    (a) generar en un aparato de compartición (110), partes SH(α , h(α )) por compartición de secretos de información secreta con un esquema de compartición de secretos separadamente para subconjuntos SUB(α ) respectivos, donde α = 1, …, L, L > 2, cada uno de los subconjuntos SUB(α ) que está formado de H(α ) aparatos de gestión de partes PA(α , 1), …, PA(α , H(α )) que pertenecen a un conjunto formado

    L

    de ∑ h(α ) aparatos de gestión de partes PA(α , h(α )), donde h(α ) = 1, …, H(α ), H(α ) > 2 y que

    α=1

    saca las partes SH(α , h(α ));

    (b) generar, en cada uno de los aparatos de gestión de partes PA(α , h(α )), un valor de secreto compartido DSH(α , h(α )) realizando una operación común a una de las partes SH(α , h(α )) e información común que contiene uno de los valores comunes σ (α ), cada uno de los valores comunes σ (α ) que está compartido en cada uno de los subconjuntos SUB(α ) y que saca el valor de secreto compartido DSH(α ,

    5

    10

    15

    20

    25

    30

    35

    40

    45

    50

    55

    h(α ));

    (c)

    generar, en un aparato de adquisición (130), valores de secretos compartidos SUBSK(α ) que corresponden a los subconjuntos SUB(α ) respectivamente, cada uno de los valores de secretos reconstruidos SUBSK(α ) que se genera por procesamiento de reconstrucción con el esquema de compartición de secretos para cada uno de los subconjuntos SUB(α ), usando una pluralidad de valores de secretos compartidos DSH(α , h(α )) que corresponden al mismo de los subconjuntos SUB(α ); y

    (d)

    generar, en un aparato de adquisición (130), información de generación SK usando los valores de secretos reconstruidos SUBSK(α ) y sacando la información de generación SK; en el paso (b), la información común usada por los aparatos de gestión de partes PA(α , h(α )) que pertenecen al mismo de los subconjuntos SUB(α ) que son el mismo y los aparatos de gestión de partes PA(α , h(α )) que pertenecen al mismo de los subconjuntos SUB(α ) que realizan la misma operación

    común.
25. 25. Un método de procesamiento para un aparato de compartición, el método de procesamiento que comprende los pasos de:

    introducir información secreta al aparato de compartición (110); generar partes SH(α , h(α )) por compartición de secretos de la información secreta separadamente para subconjuntos SUB(α ) respectivos, cada uno de los subconjuntos SUB(α ) que está formado de H(α ) aparatos de gestión de partes PA(α , 1), …, PA(α , H(α )), donde α = 1, …, L, L > 2, h(α ) = 1, …, H(α ), H(α ) > 2, en los primeros medios del aparato de compartición (110); y sacar las partes SH(α , h(α )), en los segundos medios del aparato de compartición (110), el método de procesamiento caracterizado por que la información secreta es un conjunto de vectores de

    nn+ζ

    base bi* que son b1*, …, b * de SUBSK(α )= σ (α )·{ ∑ wµ·bµ*} + ∑ bµ *∈ G n+ζ , donde g

    n+ζ

    µ=1 µ=n+1

    es un generador de un grupo cíclico G, θ (i, β ) es un elemento de un campo finito Fq, i = 1, …, n + ζ , β =

    n+ζ

    1, …, n +ζ , n > 1, ζ > 1 y bi* = (θ (i, 1)·g, …, θ (i, n + ζ )·g) ∈ G es un vector de base (n +ζ )

    dimensional que tiene (n + ζ ) elementos del grupo cíclico G como elementos, w→ es un vector n dimensional

    w → = (w1, …, wn) que tiene elementos del campo finito Fq como elementos wµ, µ = 1, …, n y σ (α ) es un

    valor común σ (α ) compartido en cada uno de los subconjuntos SUB(α ); y cada una de las unidades de compartición de secretos (814-α ) está adaptada para generar partes SH(i, β ,α , h(α ))∈ G por compartición de secretos de los elementos θ (i, β ) ·g ∈ G de los vectores de base bi* separadamente para subconjuntos SUB(α ) respectivos y cada una de las partes SH(α , h(α )) es un conjunto de las partes SH(i, β ,α , h(α ))∈ G donde i= 1, …, n + ζ , β = 1, …, n+ζ .

26. 26.

    Un método de procesamiento para un aparato de gestión de partes, caracterizado por que el método de procesamiento comprende los pasos de:

    generar un valor de secreto compartido DSH(α , h(α )) realizando una operación común a una de las partes SH(α , h(α )) obtenida compartiendo secretos de información secreta separadamente para cada uno de los subconjuntos SUB(α ) y la información común que contiene uno de los valores comunes σ (α ), cada uno de los valores comunes σ (α ) que está compartido en cada uno de los subconjuntos SUB(α ), el uno de los valores comunes σ (α ) que está compartido en uno de los subconjuntos SUB(α ), cada uno de los subconjuntos SUB(α ) que está formado de H(α ) aparatos de gestión de partes PA(α , 1), …, PA(α , H(α )), donde α = 1, …, L, L > 2,h(α ) = 1, …, H(α ), H(α ) > 2, en los primeros medios del aparato de gestión de partes; y sacar el valor de secreto compartido DSH(α , h(α )), en los segundos medios del aparato de gestión de partes; la información común está compartida con los aparatos de gestión de partes PA(α , h(α )) que pertenecen al mismo de los subconjuntos SUB(α ) y la operación común se realiza por los aparatos de gestión de partes PA(α , h(α )) que pertenecen al mismo de los subconjuntos SUB(α ).

27. 27.

    Un método de procesamiento para un aparato de adquisición, caracterizado por que el método de procesamiento comprende los pasos de:

    generar, en los primeros medios del aparato de adquisición (130), valores de secretos reconstruidos SUBSK(α ) que corresponden a subconjuntos SUB(α ) respectivamente, cada uno de los subconjuntos SUB(α ) que está formado de H(α ) aparatos de gestión de partes PA(α , 1), …, PA(α , H(α )), cada uno

    de los valores de secretos reconstruidos SUBSK(α ) que se genera por procesamiento de reconstrucción con un esquema de compartición de secretos para cada uno de los subconjuntos SUB(α ), usando una pluralidad de valores de secretos compartidos DSH(α , h(α )) que corresponden al mismo de los subconjuntos SUB(α ), donde cada uno de los subconjuntos SUB(α ) es un subconjunto formado de H(α ) aparatos de

    5 gestión de partes PA(α , 1), …, PA(α , H(α )),α = 1, …,L,L > 2,h(α ) = 1, …, H(α ), H(α ) > 2; y generar, en los segundos medios del aparato de adquisición (130), información de generación SK usando los valores de secretos reconstruidos SUBSK(α ) y sacar la información de generación SK, el método de procesamiento caracterizado por que además comprende un paso de sacar, desde una unidad de salida (135), un vector n dimensional w→ = (w1, …, wn) que tiene elementos de un campo finito Fq como

    10 elementos wµ, µ = 1, …, n, en donde

    n

    cada uno de los valores de secretos reconstruidos SUBSK(α ) es SUBSK(α )= σ (α )·{ ∑ wµ·bµ*} +

    µ=1

    n+ζ

    ∑ bµ *∈ G n+ζ , donde σ (α ) es un valor común compartido en cada uno de los subconjuntos

    µ=n+1

    SUB(α ), g es un generador de un grupo cíclico G, θ (i, β ) es un elemento del campo finito Fq, i = 1, …, n +

    n+ζ

    ζ , β = 1, …, n + ζ , n > 1, ζ > 1 y bi* = (θ (i, 1)·g, …, θ (i, n + ζ )·g) ∈ G es un vector de base (n

    15 +ζ ) dimensional que tiene (n + ζ ) elementos del grupo cíclico G como elementos.
28. 28. El método de procesamiento según la Reivindicación 27, en donde la información de generación SK es SK =

    nn+ζ

    {(σ (1) + …+σ (L))/L}·{ ∑ wµ·bµ*} + ∑ bµ*.

    µ=1 µ=n+1

    20 29. Un programa para hacer a un ordenador funcionar como el aparato de compartición según la Reivindicación 16.
29. 30. Un programa para hacer a un ordenador funcionar como el aparato de gestión de partes según una de las Reivindicaciones 17 a 21.

    25 31. Un programa para hacer a un ordenador funcionar como el aparato de adquisición según la Reivindicación 22 ó
30. 23.
31. 32. Un medio de grabación legible por ordenador que tiene almacenado en el mismo un programa para hacer a un ordenador funcionar como el aparato de compartición según la Reivindicación 16.

    30
32. 33. Un medio de grabación legible por ordenador que tiene almacenado en el mismo un programa para hacer a un ordenador funcionar como el aparato de gestión de partes según una de las Reivindicaciones 17 a 21.
33. 34. Un medio de grabación legible por ordenador que tiene almacenado en el mismo un programa para hacer a un 35 ordenador funcionar como el aparato de adquisición según la Reivindicación 22 ó 23.