Sistema de procesamiento de firmas, dispositivo de generación de claves, dispositivo de firmas, dispositivo de verificación, método de procesamiento de firmas y programa de procesamiento de firmas.

Un sistema de procesamiento de firmas (10) que comprende un dispositivo de generación de claves (100),

un dispositivo de firmas (200) y un dispositivo de verificación (300), y que sirve para ejecutar un proceso de firma usando una base Bt y una base B*t para cada número entero t ≥ 0, ..., d+1 (d es un número entero de 1 o más), en donde el dispositivo de generación de claves incluye

una primera parte de entrada de información (130) que toma como entrada un conjunto de atributos Γ que incluye información de identificación t e información de atributo x→ t :≥ (xt,i) (i ≥ 1, ..., nt donde nt es un número entero de 1 o más) para al menos un número entero t ≥ 1, ..., d,

una parte de generación del elemento de clave 0 (142) que genera un elemento de clave k*0 donde un valor Γ predeterminado se establece como coeficiente para un vector base b*0,1 de una base B*0, una parte de generación del elemento de clave t (143) que genera un elemento de clave k*t donde δxt,i (i ≥ 1, ..., nt) obtenido multiplicando la información de atributo x→ t por el valor δ predeterminado se establece como coeficiente para un vector base b*t,i (i ≥ 1, ..., nt) de la base B*t, que concierne a cada información de identificación t incluida en el conjunto de atributos Γ introducido por la primera parte de entrada de información, una parte de generación del elemento de clave d+1 (144) que genera un elemento de clave k*d+1,1 donde el valor δ predeterminado se establece como coeficiente para un vector base b*d+1,1 de una base B*d+1, y un elemento de clave k*d+1,2 donde el valor δ predeterminado se establece como coeficiente para un vector base b*d+1,2 de la base B*d+1, y una parte de transmisión de clave de firma (150) que transmite, al dispositivo de firma, una clave de firma skρ que incluye: el elemento de clave k*0 generado por la parte de generación del elemento de clave 0; el elemento de clave k*t generado por la parte de generación del elemento de clave t que concierne a cada información de identificación t incluida en el conjunto de atributos Γ ; el elemento de clave k*d+1,1 y el elemento de clave k*d+1,2 que se generan por la parte de generación del elemento de clave d+1; y el conjunto de atributos Γ , en donde el dispositivo de firmas incluye una segunda parte de entrada de información (220) que toma como entrada una variable ρ(i) para cada número entero i ≥ 1, ..., L (L es un número entero de 1 o más), cuya variable ρ(i) es cualquiera de una tupla positiva (t, v→ i) y una tupla negativa ¬(t, v→ i) de la información de identificación t (t es cualquier número entero de t ≥ 1, ..., d) y la información de atributo v→ i :≥ (vi, i') (i' ≥ 1, ..., nt); una matriz M predeterminada que tiene L filas y r columnas (r es un número entero de 1 o más); y un mensaje m,

una parte de adquisición de clave de firma (210) que adquiere la clave de firma skτ transmitida por la parte de transmisión de clave de firma,

una parte de cálculo de coeficiente complementario (240) que, en base a la variable ρ(i) introducida por la segunda parte de entrada de información y el conjunto de atributos Γ incluido en la clave de firma skτ adquirida por la parte de adquisición de clave de firma, especifica, entre los números enteros i ≥ 1, ..., L, un conjunto I de un número entero i para el cual la variable ρ(i) es una tupla positiva (t, v→ i) y con el cual un producto interno de v→ i de la tupla positiva y x→ t incluido en el conjunto de atributos Γ indicado por la información de identificación t de la tupla positiva llega a ser 0, y un número entero i para el cual la variable ρ(i) es una tupla negativa ¬(t, v→ i) y

con el cual un producto interno de v→ i de la tupla negativa y x→ t incluido en el conjunto de atributos Γ indicado por la información de identificación t de la tupla negativa no llega a ser 0; y calcula, concerniente a i incluido en el conjunto I especificado, un coeficiente complementario αi con el cual un total de αiMi en base a Mi que es un elemento en una fila de orden i de la matriz M introducida por la segunda parte de entrada de información llega a ser un vector h→ predeterminado,

una parte de generación del elemento de firma 0 (252) que genera un elemento de firma s*0 que incluye el elemento de clave k*0 incluido en la clave de firma skτ,

una parte de generación del elemento de firma i (253) que genera, para cada número entero i ≥ 1 ..., L, un elemento de firma s*i que incluye γik*t obtenido multiplicando el elemento de clave k*t incluido en la clave de firma skτ por un valor γi, estableciendo el valor γi para satisfacer γi :≥ αi cuando el número entero i se incluye en el conjunto I especificado por la parte de cálculo de coeficiente complementario y la variable ρ(i) es una tupla positiva (t, v→ i); estableciendo el valor αi para satisfacer γi :≥ αi/(v→ i · x→ t) cuando el número entero i está incluido en el conjunto I y la variable ρ(i) es una tupla negativa ¬(t, v→ i); y estableciendo el valor γi para satisfacer γi :≥ 0 cuando el número entero i no está incluido en el conjunto I, una parte de generación del elemento de firma L+1 (254) que genera un elemento de firma s*L+1 que incluye una suma del elemento de clave k*d+1,1 incluido en la clave de firma skτ y m'·k*d+1,2 obtenido multiplicando el elemento de clave k*d+1,2 por un valor m' generado usando el mensaje m, y