Google Patentsopen access

Information generation apparatus,method, program, and recording medium therefor — Nippon Telegraph And Telephone Corp. (US20120027206A1)

ABSTRACT

Abstract

Hierarchical cryptography expressed in a general semiordered structure other than a tree structure is implemented. In information generation, random numbers σv and (σvj)jεw(v)εZq are generated; main information kv=σvΣiε{1, . . . , N-1}\w(v)vibi*+bN* is calculated; and derivation information kvj=σvjΣiε{1, . . . , N-1}\w(v)vibi*+bj* is calculated for each jεw(v). In information derivation, random numbers σu and (σuj)jεw(u)εZq are generated; main information ku=σuΣiεw(v)\w(u)uikvi+kv is calculated; and derivation information kuj=σujΣiεw(v)\w(u)uikvi+kvj is calculated for each jεw(v).

Description

TECHNICAL FIELD

The present invention relates to an application of information security technology. For example, the present invention relates to hierarchical cryptography in which a decryption key having a limited decryption ability can be derived from another decryption key.

BACKGROUND ART

The technology described in Non-patent literature 1 is a known conventional technology for hierarchical cryptography.

PRIOR ART LITERATURE

Non-Patent Literature

Non-patent literature 1: Craig Gentry, Alice Siverberg, “Hierarchical ID-Based Cryptography,” ASIACRYPT 2002, pp. 548-566

DISCLOSURE OF THE INVENTION

Problems to be Solved by the Invention

In the technology described in Non-patent literature 1, a key corresponding to a child node in a tree structure can be derived from a key corresponding to a parent node, but key derivation cannot be implemented in a general semiordered structure s other than a tree structure. For example, in a structure having a parent node A, a parent node B, and a common child node C, it is not possible to derive a key of the common child node C from a key of the parent node A or to derive a key of the common child node C from a key of the parent node B.

Means to Solve the Problems

To solve the foregoing problem, an information generation apparatus according to Claim 1 includes a random number generator adapted to generate a random number σ Y εZ q and a random number σ Yj εZ q corresponding to each element jεw(Y) of a set w(Y); a main information generator adapted to use the generated random number σ Y to calculate main information k Y that satisfies k Y =σ Y Σ iε{1, . . . , N-1}\w(Y) Y i b i *+b N *; and a derivation information generator adapted to use the generated random number σ Yj to calculate derivation information k Yj that satisfies k Yj =σ Yj Σ eε{1, . . . , N-1}\ w(Y) Y i b i *+b j * for each element jεw(Y) of the set w(Y); where e is a non-degenerate, bilinear function that outputs one element of a cyclic group G T in response to inputs of N elements γ L (L=1, . . . , N) (N≧2) of a cyclic group G 1 and N elements γ L *(L=1, . . . , N) of a cyclic group G 2 ; b i εG 1 N (i=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 1 as elements; b j *εG 2 N (j=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 2 as elements; a function value obtained when each element of the basis vector b i εG 1 N (i=1, . . . , N) and each element of the basis vector b j *εG 2 N (j=1, . . . , N) are put into the bilinear function e is represented by g T τ·δ(i,j) εG T , using a Kronecker's delta function in which δ(i,j)=1 F when i=j and δ(i,j)=0 F when i≠j; 0 F is an additive unit element of a finite field F q ; 1 F is a multiplicative unit element of the finite field F q ; τ is an element of the finite field F q , other than 0 F ; and g T is a generator of the cyclic group G T ; * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; and the set w(Y) corresponds to the index Y, and w(Y)={i|Y 1 =*}.

An information generation apparatus according to Claim 4 includes a storage unit adapted to store main information k v serving as main information k Y or corresponding to an index v, derived from the main information k Y and derivation information k Yi , and derivation information k vj serving as the derivation information k Yi or corresponding to the index v, derived from the derivation information k Yi ; a child random number generator adapted to generate a random number σ u εZ q ; and a main information deriving unit adapted to use the main information k v and derivation information k vi , both of which are read from the storage unit, and the generated random number σ u to calculate main information k u corresponding to an index u, which satisfies k u =σ u Σ iεw(v)\w(u) u i k vi +k v ; where e is a non-degenerate, bilinear function that outputs one element of a cyclic group G T in response to inputs of N elements γ L (L=1, . . . , N)(N≧2) of a cyclic group G 1 and N elements γ L *(L=1, . . . , N) of a cyclic group G 2 ; b i εG 1 N (i=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 1 as elements; b j *εG 2 N (j=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 2 as elements; a function value obtained when each element of the basis vector b i εG 1 N (i=1, . . . , N) and each element of the basis vector b j *εG 2 N (j=1, . . . , N) are put into the bilinear function e is represented by g T τ·δ(i,j) εG T , using a Kronecker's delta function in which δ(i, j)=1 F when i=j and δ(i, j)=0 F when i≠j; 0 F is an additive unit element of a finite field F q ; 1 F is a multiplicative unit element of the finite field F q ; τ is an element of the finite field F q , other than 0 F ; and g T is a generator of the cyclic group G T ; * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; a set w(Y) corresponding to the index Y is w(Y)={i|Y i =*}; σ Y εZ q is a random number; σ Yi εZ q is a random number corresponding to each element jεw(Y) of the set w(Y); the main information k Y corresponds to the index Y and satisfies k Y =σ Y Σ iε{1, . . . , N-1}\w(Y) Y i b i *+b N *; the derivation information k Yi , corresponds to the index Y and satisfies k Yj =σ Yj Σ iε{1, . . . , N-1}\w(Y) Y i b i *+b j *; * indicates an indeterminate character; the index v is v=(v 1 , . . . , V N-1 )εI=(F q ∪{*}) N-1 ; the index u is u=(u 1 , . . . , u N-1 )εI=(F q ∪{*}) N-1 ; w(v) is a set corresponding to the index v and w(v)={i|v i =*}; w(u) is a set corresponding to the index u and w(u)={i|u i =*}; w(u)⊂w(v); and v i =u i (iε{1, . . . , N−1}\w(v)).

An information generation apparatus according to Claim 6 includes a random number generator adapted to generate a random number r Y εZ q ; a first main information generator adapted to use the generated random number r Y to calculate first main information k Y that satisfies k Y =g 2 a (g 3Πiε{1, . . . , N-1}\w(Y) h i Yi ) rY ; a second main information generator adapted to use the generated random number r Y to calculate second main information g rY ; and a derivation information generator adapted to use the generated random number r Y to calculate derivation information k Yj that satisfies k Yj =h j rY for each element jεw(Y) of a set w(Y); where G and G T are cyclic groups having a prime number order q; g is a generator of the cyclic group G; the cyclic group G has a pairing function e: G×G→G T , which makes g T =e(g, g) a generator of the cyclic group G T ; a is a random number selected at random from Z p ; g, g 1 =g a εG, and g 2 , g 3 , h 1 , . . . , h N-1 εG randomly selected from the cyclic group G are made publicly available as public keys; * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; the set w(Y) corresponds to the index Y; and w(Y)={i|Y i =*}.

An information generation apparatus according to Claim 9 includes a random number generator adapted to generate a random number r u εZ q ; a storage unit adapted to store main information k v serving as main information K Y or corresponding to an index v, derived from first main information k Y and derivation information k Yi , and derivation information k vj serving as derivation information k Yi or corresponding to the index v, derived from the derivation information k Yi ; a first main information deriving unit adapted to use the first main information k v and derivation information k vi , both of which are read from the storage unit, to calculate first main information k u corresponding to an index u, which satisfies k u =k v (Π iεw(v)\w(u) k vi ui )(g 3 Π iε{1, . . . , N-1}\w(v) h i vi Π iεw(v)\w(u) h i ui ) ru ; and a second main information deriving unit adapted to use the generated random number r u to calculate second main information g ru ; where G and G T are cyclic groups having a prime number order q; g is a generator of the cyclic group G; the cyclic group G has a pairing function e: G×G→G T , which makes g T =e(g, g) a generator of the cyclic group G T ; a is a random number selected at random from Z p ; g, g 1 =g a εG, and g 2 , g 3 , h 1 , . . . , h N-1 εG randomly selected from the cyclic group G are made publicly available as public keys; * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; a set w(Y) corresponding to the index Y is w(Y)={i|Y i =*}; r Y εZ q is a random number; the first main information k Y corresponds to the index Y and satisfies k Y =g 2 a (g 3 Π iε{1, . . . , N-1}\w(Y) h i Yi ) rY ; g rY is second main information corresponding to the index Y; the derivation information k Yi corresponds to the index Y and satisfies k Yj =h j rY ; * indicates an indeterminate character; the index v is v=(v 1 , . . . , v N-1 )εI=(F q ∪{*}) N-1 ; w(v) is a set corresponding to the index v and w(v)={i|v i =*}; the index u is u=(u 1 , . . . , u N-1 )εI=(F q ∪{*}) N-1 ; w(u) is a set corresponding to the index u and w(u)={i|u i =*}; set w(u)⊂ set w(v); and v i =u i (iε{1, . . . , N−1}\w(v)).

Effects of the Invention

In a structure having a parent node A, a parent node B, and a common child node C, it is possible to derive information of the common child node C from information of the parent node A and to derive information of the common child node C from information of the parent node B.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is an example functional block diagram of an information generation apparatus according to a first embodiment;

FIG. 2 is an example flowchart of information generation in the first embodiment;

FIG. 3 is an example flowchart of information derivation in the first embodiment;

FIG. 4 is an example functional block diagram of an information generation apparatus according to a second embodiment;

FIG. 5 is an example flowchart of information generation in the second embodiment; and

FIG. 6 is an example flowchart of information derivation in the second embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Embodiments of the present invention will be described below in detail.

Predicate Encryption

An overview of predicate encryption, which is a concept used in a first embodiment, will be described first.

Definitions

Terms and symbols to be used in the embodiments will be defined first.

Matrix: A matrix represents a rectangular arrangement of elements of a set in which an operation is defined. Not only elements of a ring but also elements of a group can form the matrix.

(•) T : Transposed matrix of “•”

(•) −1 : Inverse matrix of “•”

Logical AND

Logical OR

Z: Set of integers

k: Security parameter (kεZ, k>0)

{0, 1}*: Binary sequence having a desired bit length. An example is a sequence formed of integers 0 and 1. However, {0, 1}* is not limited to sequences formed of integers 0 and 1. {0, 1}* is a finite field of order 2 or its extention field.

{0, 1} ζ : Binary sequence having a bit length ζ (ζεZ, ζ>0). An example is a sequence formed of integers 0 and 1. However, {0, 1} ζ is not limited to sequences formed of integers 0 and 1. {0, 1} ζ

TECHNICAL FIELD

The present invention relates to an application of information security technology. For example, the present invention relates to hierarchical cryptography in which a decryption key having a limited decryption ability can be derived from another decryption key.

BACKGROUND ART

The technology described in Non-patent literature 1 is a known conventional technology for hierarchical cryptography.

PRIOR ART LITERATURE

Non-Patent Literature

Non-patent literature 1: Craig Gentry, Alice Siverberg, “Hierarchical ID-Based Cryptography,” ASIACRYPT 2002, pp. 548-566

DISCLOSURE OF THE INVENTION

Problems to be Solved by the Invention

In the technology described in Non-patent literature 1, a key corresponding to a child node in a tree structure can be derived from a key corresponding to a parent node, but key derivation cannot be implemented in a general semiordered structure s other than a tree structure. For example, in a structure having a parent node A, a parent node B, and a common child node C, it is not possible to derive a key of the common child node C from a key of the parent node A or to derive a key of the common child node C from a key of the parent node B.

Means to Solve the Problems

To solve the foregoing problem, an information generation apparatus according to Claim 1 includes a random number generator adapted to generate a random number σ Y εZ q and a random number σ Yj εZ q corresponding to each element jεw(Y) of a set w(Y); a main information generator adapted to use the generated random number σ Y to calculate main information k Y that satisfies k Y =σ Y Σ iε{1, . . . , N-1}\w(Y) Y i b i *+b N *; and a derivation information generator adapted to use the generated random number σ Yj to calculate derivation information k Yj that satisfies k Yj =σ Yj Σ eε{1, . . . , N-1}\ w(Y) Y i b i *+b j * for each element jεw(Y) of the set w(Y); where e is a non-degenerate, bilinear function that outputs one element of a cyclic group G T in response to inputs of N elements γ L (L=1, . . . , N) (N≧2) of a cyclic group G 1 and N elements γ L *(L=1, . . . , N) of a cyclic group G 2 ; b i εG 1 N (i=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 1 as elements; b j *εG 2 N (j=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 2 as elements; a function value obtained when each element of the basis vector b i εG 1 N (i=1, . . . , N) and each element of the basis vector b j *εG 2 N (j=1, . . . , N) are put into the bilinear function e is represented by g T τ·δ(i,j) εG T , using a Kronecker's delta function in which δ(i,j)=1 F when i=j and δ(i,j)=0 F when i≠j; 0 F is an additive unit element of a finite field F q ; 1 F is a multiplicative unit element of the finite field F q ; τ is an element of the finite field F q , other than 0 F ; and g T is a generator of the cyclic group G T ; * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; and the set w(Y) corresponds to the index Y, and w(Y)={i|Y 1 =*}.

An information generation apparatus according to Claim 4 includes a storage unit adapted to store main information k v serving as main information k Y or corresponding to an index v, derived from the main information k Y and derivation information k Yi , and derivation information k vj serving as the derivation information k Yi or corresponding to the index v, derived from the derivation information k Yi ; a child random number generator adapted to generate a random number σ u εZ q ; and a main information deriving unit adapted to use the main information k v and derivation information k vi , both of which are read from the storage unit, and the generated random number σ u to calculate main information k u corresponding to an index u, which satisfies k u =σ u Σ iεw(v)\w(u) u i k vi +k v ; where e is a non-degenerate, bilinear function that outputs one element of a cyclic group G T in response to inputs of N elements γ L (L=1, . . . , N)(N≧2) of a cyclic group G 1 and N elements γ L *(L=1, . . . , N) of a cyclic group G 2 ; b i εG 1 N (i=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 1 as elements; b j *εG 2 N (j=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 2 as elements; a function value obtained when each element of the basis vector b i εG 1 N (i=1, . . . , N) and each element of the basis vector b j *εG 2 N (j=1, . . . , N) are put into the bilinear function e is represented by g T τ·δ(i,j) εG T , using a Kronecker's delta function in which δ(i, j)=1 F when i=j and δ(i, j)=0 F when i≠j; 0 F is an additive unit element of a finite field F q ; 1 F is a multiplicative unit element of the finite field F q ; τ is an element of the finite field F q , other than 0 F ; and g T is a generator of the cyclic group G T ; * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; a set w(Y) corresponding to the index Y is w(Y)={i|Y i =*}; σ Y εZ q is a random number; σ Yi εZ q is a random number corresponding to each element jεw(Y) of the set w(Y); the main information k Y corresponds to the index Y and satisfies k Y =σ Y Σ iε{1, . . . , N-1}\w(Y) Y i b i *+b N *; the derivation information k Yi , corresponds to the index Y and satisfies k Yj =σ Yj Σ iε{1, . . . , N-1}\w(Y) Y i b i *+b j *; * indicates an indeterminate character; the index v is v=(v 1 , . . . , V N-1 )εI=(F q ∪{*}) N-1 ; the index u is u=(u 1 , . . . , u N-1 )εI=(F q ∪{*}) N-1 ; w(v) is a set corresponding to the index v and w(v)={i|v i =*}; w(u) is a set corresponding to the index u and w(u)={i|u i =*}; w(u)⊂w(v); and v i =u i (iε{1, . . . , N−1}\w(v)).

An information generation apparatus according to Claim 6 includes a random number generator adapted to generate a random number r Y εZ q ; a first main information generator adapted to use the generated random number r Y to calculate first main information k Y that satisfies k Y =g 2 a (g 3Πiε{1, . . . , N-1}\w(Y) h i Yi ) rY ; a second main information generator adapted to use the generated random number r Y to calculate second main information g rY ; and a derivation information generator adapted to use the generated random number r Y to calculate derivation information k Yj that satisfies k Yj =h j rY for each element jεw(Y) of a set w(Y); where G and G T are cyclic groups having a prime number order q; g is a generator of the cyclic group G; the cyclic group G has a pairing function e: G×G→G T , which makes g T =e(g, g) a generator of the cyclic group G T ; a is a random number selected at random from Z p ; g, g 1 =g a εG, and g 2 , g 3 , h 1 , . . . , h N-1 εG randomly selected from the cyclic group G are made publicly available as public keys; * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; the set w(Y) corresponds to the index Y; and w(Y)={i|Y i =*}.

An information generation apparatus according to Claim 9 includes a random number generator adapted to generate a random number r u εZ q ; a storage unit adapted to store main information k v serving as main information K Y or corresponding to an index v, derived from first main information k Y and derivation information k Yi , and derivation information k vj serving as derivation information k Yi or corresponding to the index v, derived from the derivation information k Yi ; a first main information deriving unit adapted to use the first main information k v and derivation information k vi , both of which are read from the storage unit, to calculate first main information k u corresponding to an index u, which satisfies k u =k v (Π iεw(v)\w(u) k vi ui )(g 3 Π iε{1, . . . , N-1}\w(v) h i vi Π iεw(v)\w(u) h i ui ) ru ; and a second main information deriving unit adapted to use the generated random number r u to calculate second main information g ru ; where G and G T are cyclic groups having a prime number order q; g is a generator of the cyclic group G; the cyclic group G has a pairing function e: G×G→G T , which makes g T =e(g, g) a generator of the cyclic group G T ; a is a random number selected at random from Z p ; g, g 1 =g a εG, and g 2 , g 3 , h 1 , . . . , h N-1 εG randomly selected from the cyclic group G are made publicly available as public keys; * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; a set w(Y) corresponding to the index Y is w(Y)={i|Y i =*}; r Y εZ q is a random number; the first main information k Y corresponds to the index Y and satisfies k Y =g 2 a (g 3 Π iε{1, . . . , N-1}\w(Y) h i Yi ) rY ; g rY is second main information corresponding to the index Y; the derivation information k Yi corresponds to the index Y and satisfies k Yj =h j rY ; * indicates an indeterminate character; the index v is v=(v 1 , . . . , v N-1 )εI=(F q ∪{*}) N-1 ; w(v) is a set corresponding to the index v and w(v)={i|v i =*}; the index u is u=(u 1 , . . . , u N-1 )εI=(F q ∪{*}) N-1 ; w(u) is a set corresponding to the index u and w(u)={i|u i =*}; set w(u)⊂ set w(v); and v i =u i (iε{1, . . . , N−1}\w(v)).

Effects of the Invention

In a structure having a parent node A, a parent node B, and a common child node C, it is possible to derive information of the common child node C from information of the parent node A and to derive information of the common child node C from information of the parent node B.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is an example functional block diagram of an information generation apparatus according to a first embodiment;

FIG. 2 is an example flowchart of information generation in the first embodiment;

FIG. 3 is an example flowchart of information derivation in the first embodiment;

FIG. 4 is an example functional block diagram of an information generation apparatus according to a second embodiment;

FIG. 5 is an example flowchart of information generation in the second embodiment; and

FIG. 6 is an example flowchart of information derivation in the second embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Embodiments of the present invention will be described below in detail.

Predicate Encryption

An overview of predicate encryption, which is a concept used in a first embodiment, will be described first.

Definitions

Terms and symbols to be used in the embodiments will be defined first.

Matrix: A matrix represents a rectangular arrangement of elements of a set in which an operation is defined. Not only elements of a ring but also elements of a group can form the matrix.

(•) T : Transposed matrix of “•”

(•) −1 : Inverse matrix of “•”

Logical AND

Logical OR

Z: Set of integers

k: Security parameter (kεZ, k>0)

{0, 1}*: Binary sequence having a desired bit length. An example is a sequence formed of integers 0 and 1. However, {0, 1}* is not limited to sequences formed of integers 0 and 1. {0, 1}* is a finite field of order 2 or its extention field.

{0, 1} ζ : Binary sequence having a bit length ζ (ζεZ, ζ>0). An example is a sequence formed of integers 0 and 1. However, {0, 1} ζ is not limited to sequences formed of integers 0 and 1. {0, 1} ζ is a finite field of order 2 (when ζ=1) or an extention field obtained by extending the finite field by degree ζ (when ζ>1).

(+): Exclusive OR operator between binary sequences. For example, the following is satisfied: 10110011(+)11100001=01010010.

F q : Finite field of order q, where q is an integer equal to or larger than 1. For example, the order q is a prime number of a power of a prime number. In other words, the finite field F q is a prime field or an extention field of the prime field, for example. When the finite field F q is a prime field, remainder calculations to modulus q can be easily performed, for example. When the finite field F q is an extention field, remainder calculations modulo an irreducible polynomial can be easily performed, for example. A specific method for configuring a finite field F q is disclosed, for example, in reference literature 1, “ISO/IEC 18033-2: Information technology—Security techniques—Encryption algorithms—Part 2: Asymmetric ciphers”.

0 F : Additive unit element of the finite field F q

1 F : Multiplicative unit element of the finite field F q

δ(i, j): Kronecker's delta function. When i=j, δ(i, j)=1 F .

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

E: Elliptic curve defined on the finite field F q . It is defined as a special point O called the point of infinity plus a set of points (x, y) satisfying x, yεF q and the Weierstrass equation in an affine coordinate system

y 2 +a 1 xy+a 3 y=x 3 +a 2 x 2 +a 4 x+a 6   (1)

where a 1 , a 2 , a 3 , a 4 , a 6 εF q . A binary operation + called an elliptic addition can be defined for any two points on the elliptic curve E, and a unary operation − called an elliptic inverse can be defined for any one point on the elliptic curve E. It is well known that a finite set of rational points on the elliptic curve E forms a group with respect to the elliptic addition. It is also well known that an operation called an elliptic scalar multiplication can be defined with the elliptic addition. A specific operation method of elliptic operations such as the elliptic addition on a computer is also well known. (For example, see reference literature 1, reference literature 2, “RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems”, and reference literature 3, Ian F. Blake, Gadiel Seroussi, and Nigel P. Smart, “Elliptic Curves in Cryptography”, Pearson Education, ISBN 4-89471-431-0.)

A finite set of rational points on the elliptic curve E has a subgroup of order p (p≧1). When the number of elements in a finite set of rational points on the elliptic curve E is #E and p is a large prime number that can divide #E without a remainder, for example, a finite set E[p] of p equally divided points on the elliptic curve E forms a subgroup of the finite set of rational points on the elliptic curve E. The p equally divided points on the elliptic curve E are points A on the elliptic curve E which satisfy the elliptic scalar multiplication pA=O.

G 1 , G 2 , G T : Cyclic groups of order q. Examples of the cyclic groups G 1 and G 2 include the finite set E[p] of p equally divided points on the elliptic curve E and subgroups thereof. G 1 may equal G 2 , or G 1 may not equal G 2 . Examples of the cyclic group G T include a finite set constituting an extention field of the finite field F q . A specific example thereof is a finite set of the p-th root of 1 in the algebraic closure of the finite field F q .

In the embodiments, operations defined on the cyclic groups G 1 and G 2 are expressed as additions, and an operation defined on the cyclic group G T is expressed as a multiplication. More specifically, χ·ΩεG 1 for χεF q and ΩεG 1 means that the operation defined in the cyclic group G 1 is applied to ΩεG 1 χ times, and Ω 1 +Ω 2 εG 1 for Ω 1 , Ω 2 εG 1 means that the operation defined in the cyclic group G 1 is applied to Ω 1 εG 1 and Ω 2 εG 1 . In the same way, χ·ΩεG 2 for χεF q and ΩεG 2 means that the operation defined in the cyclic group G 2 is applied to ΩεG 2 , times, and Ω 1 +Ω 2 εG 2 for Ω 1 , Ω 2 εG 2 means that the operation defined in the cyclic group G 2 is applied to Ω 1 εG 2 and Ω 2 εG 2 . In contrast, Ω χ εG T for χεF q and ΩεG T means that the operation defined in the cyclic group G T is applied to ΩεG T χ times, and Ω 1 ·Ω 2 εG T for Ω 1 , Ω 2 εG T means that the operation defined in the cyclic group G T is applied to Ω 1 εG T and Ω 2 εG T .

G 1 n+1 : Direct product of (n+1) cyclic groups G 1 (n≧1)

G 2 n+1 : Direct product of (n+1) cyclic groups G 2

g 1 , g 2 , g T : Generators of the cyclic groups G 1 , G 2 , G T

V: (n+1)-dimensional vector space formed of the direct product of the (n+1) cyclic groups G 1

V*: (n+1)-dimensional vector space formed of the direct product of the (n+1) cyclic groups G 2

e: Function (bilinear function) for calculating a non-degenerate bilinear map that maps the direct product G 1 n+1 ×G 2 n+1 of the direct product G 1 n+1 and the direct product G 2 n+1 to the cyclic group G T . The bilinear function e receives (n+1) elements γ L (L=1, . . . , n+1) (n≧1) of the cyclic group G 1 and (n+1) elements γ L *(L=1, . . . , n+1) of the cyclic group G 2 and outputs one element of the cyclic group G T .

e: G 1 n+1 ×G 2 n+1 →G T   (2)

The bilinear function e satisfies the following characteristics:

Bilinearity: The following relationship is satisfied for all Γ 1 εG 1 n+1 , Γ 2 εG 2 n+1 , and ν, κεF q

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

Non-degeneracy: This function does not map all

Γ 1 εG 1 n+1 ,Γ 2 εG 2 n+1   (4)

onto the unit element of the cyclic group G T .

Computability: There exists an algorithm for efficiently calculating e(Γ 1 , Γ 2 ) for all Γ 1 εG 1 n+1 , Γ 2 εG 2 n+1 .

In the embodiments, the following function for calculating a non-degenerate bilinear map that maps the direct product G 1 ×G 2 of the cyclic group G 1 and the cyclic group G 2 to the cyclic group G T constitutes the bilinear function e.

Pair: G 1 ×G 2 →G T   (5)

The bilinear function e receives an (n+1)-dimensional vector (γ 1 , . . . , γ n+1 ) formed of (n+1) elements γ L (L=1, . . . , n+1) of the cyclic group G 1 and an (n+1)-dimensional vector (γ 1 *, . . . , γ n+1 *) formed of (n+1) elements γ L *(i=1, . . . , n+1) of the cyclic group G 2 and outputs one element of the cyclic group G T .

e=Π L=1 n+1 Pair(γ L ,γ L *)  (6)

The bilinear function Pair receives one element of the cyclic group G 1 and one element of the cyclic group G 2 and outputs one element of the cyclic group G T , and satisfies the following characteristics:

Bilinearity: The following relationship is satisfied for all Ω 1 e G 1 , Ω 2 εG 2 , and ν, κεF q

Pair(ν·Ω 1 ,κ·Ω 2 )=Pair(Ω 1 ,Ω 2 ) ν·κ   (7)

Non-degeneracy: This function does not map all

Ω 1 εG 1 ,Ω 2 εG 2   (8)

onto the unit element of the cyclic group G T .

Computability: There exists an algorithm for efficiently calculating Pair(Ω 1 , Ω 2 ) for all Ω 1 εG 1 , Ω 2 εG 2 .

A specific example of the bilinear function Pair is a function for performing a pairing operation such as Weil pairing or Tate pairing. (See reference literature 4, Alfred. J. Menezes, “Elliptic Curve Public Key Cryptosystems”, Kluwer Academic Publishers, ISBN 0-7923-9368-6, pp. 61-81, for example.) A modified pairing function e(Ω 1 , phi(Ω 2 )) (Ω 1 εG 1 , Ω 2 εG 2 ) obtained by combining a function for performing a pairing operation, such as Tate pairing, and a predetermined function phi according to the type of the elliptic curve E may be used as the bilinear function Pair (see reference literature 2, for example). As the algorithm for performing a pairing operation on a computer, the Miller algorithm (see reference literature 5, V. S. Miller, “Short Programs for Functions on Curves”, 1986, http://crypto.stanford.edu/miller/miller.pdf) or some other known algorithm can be used. Methods for configuring a cyclic group and an elliptic curve used to efficiently perform a pairing operation have been known. (For example, see reference literature 2; reference literature 6, A. Miyaji, M. Nakabayashi, and S. Takano, “New Explicit Conditions of Elliptic Curve Traces for FR Reduction”, IEICE Trans. Fundamentals, Vol. E84-A, No. 5, pp. 1234-1243, May 2001; reference literature 7, P. S. L. M. Barreto, B. Lynn, M. Scott, “Constructing Elliptic Curves with Prescribed Embedding Degrees”, Proc. SCN '2002, LNCS 2576, pp. 257-267, Springer-Verlag. 2003; and reference literature 8, R. Dupont, A. Enge, F. Morain, “Building Curves with Arbitrary Small MOV Degree over Finite Prime Fields”, http://eprint.iacr.org/2002/094/).

a i (i=1, . . . , n+1): (n+1)-dimensional basis vectors having (n+1) elements of the cyclic group G 1 as elements. An example of the basis vectors a i is an (n+1)-dimensional basis vector having κ 1 ·g 1 εG 1 as an i-dimensional element and the unit element (expressed as “0” in additive expression) of the cyclic group G 1 as the remaining n elements. In that case, the elements of the (n+1)-dimensional basis vectors a i (i=1, . . . , n+1) can be listed as follows:

a

1

=

(

κ

1

·

g

1

,

0

,

0

,

…



,

0

)





a

2

=

(

0

,

κ

1

·

g

1

,

0

,

…



,

0

)





…





a

n

+

1

=

(

0

,

0

,

0

,

…



,

κ

1

·

g

1

)

(

9

)

Here, κ 1 is a constant formed of an element of the finite field F q other than the additive unit element 0 F . An example of κ 1 εF q is κ 1 =1 F . The basis vectors a i are orthogonal bases. Each (n+1)-dimensional vector having (n+1) elements of the cyclic group G 1 as elements is expressed by a linear sum of (n+1)-dimensional basis vectors a i (i=1, . . . , n+1). Therefore, the (n+1)-dimensional basis vectors a i span the vector space V, described earlier.

a i * (i=1, . . . , n+1): (n+1)-dimensional basis vectors having (n+1) elements of the cyclic group G 2 as elements. An example of the basis vectors a i * is an (n+1)-dimensional basis vector having κ 2 ·g 2 εG 2 as an i-dimensional element and the unit element (expressed as “0” in additive expression) of the cyclic group G 2 as the remaining n elements. In that case, the elements of the (n+1)-dimensional basis vectors a i * (i=1, . . . , n+1) can be listed as follows:

a

1

*

=

(

κ

2

·

g

2

,

0

,

0

,

…



,

0

)





a

2

*

=

(

0

,

κ

2

·

g

2

,

0

,

…



,

0

)





…





a

n

+

1

*

=

(

0

,

0

,

0

,

…



,

κ

2

·

g

2

)

(

10

)

Here, κ 2 is a constant formed of an element of the finite field F q other than the additive unit element 0 F . An example of κ 2 εF q is κ 2 =1 F . The basis vectors a i * are orthogonal bases. Each (n+1)-dimensional vector having (n+1) elements of the cyclic group G 2 as elements is expressed by a linear sum of (n+1)-dimensional basis vectors a i * (i=1, . . . , n+1). Therefore, the (n+1)-dimensional basis vectors a i * span the vector space V*, described earlier.

The basis vectors a i and the basis vectors a i * satisfy the following expression for an element τ=κ 1 ·κ 2 of the finite field F q other than 0 F :

e ( a i ,a j *)= g T τδ(i,j)   (11)

When i=j, the following expression is satisfied from Expressions (6) and (7).

e

î¢

(

a

i

,

a

j

*

)

=



Pair

î¢

(

κ

1

·

g

1

,

κ

2

·

g

2

)

·

Pair

î¢

(

0

,

0

)

·

…

·

Pair

î¢

(

0

,

0

)

=



Pair

î¢

(

g

1

,

g

2

)

κ





1



κ





2

·

Pair

î¢

(

g

1

,

g

2

)

0

·

0

·

…

·

Pair

î¢

(

g

1

,

g

2

)

0

·

0

=



Pair

î¢

(

g

1

,

g

2

)

κ





1



κ





2

=

g

T

τ

When i≠j, e(a i , a j *) does not include Pair(κ 1 ·g 1 , κ 2 ·g 2 ) and is the product of Pair (κ 1 ·g 1 , 0), Pair (0, κ 2 ·g 2 ), and Pair(0, 0). In addition, the following expression is satisfied from Expression (7).

Pair( g 1 ,0)=Pair(0, g 2 )=Pair( g 1 ,g 2 ) 0

Therefore, when i≠j, the following expression is satisfied.

e ( a i ,a j *)= e ( g 1 ,g 2 ) 0 =g T 0

Especially when τ=κ 1 ·κ 2 =1 F (for example, κ 1 =κ 2 =1 F ), the following expression is satisfied.

e ( a i ,a j *)= g T δ(i,j)   (12)

Here, g T 0 =1 is the unit element of the cyclic group G T , and g T 1 =g T is a generator of the cyclic group G T . In that case, the basis vectors a i and the basis vectors a i * are dual normal orthogonal bases, and the vector space V and the vector space V* are a dual vector space that constitutes bilinear mapping (dual pairing vector space (DPVS)).

A: An (n+1) row by (n+1) column matrix having the basis vectors a i (i=1, . . . , n+1) as elements. When the basis vectors a i (i=1, . . . , n+1) are expressed by Expression (9), for example, the matrix A is as follows:

A

=

(

CLAIMS

Claims ( 14 )

1 : An information generation apparatus comprising:

a random number generator adapted to generate a random number σ Y εZ q and a random number σ Yj εZ q corresponding to each element jεw(Y) of a set w(Y); a main information generator adapted to use the generated random number σ Y to calculate main information k Y that satisfies k Yj =σ Yj Σ iε{1, . . . , N-1}\w(Y) Y i b i *+b N *; and a derivation information generator adapted to use the generated random number σ Yj to calculate derivation information k Yj that satisfies k Yj Σ iε{1, . . . , N-1}\w(Y) Y i b i *+b j * for each element jεw(Y) of the set w(Y); where e is a non-degenerate, bilinear function that outputs one element of a cyclic group G T in response to inputs of N elements γ L (L=1, . . . , N) (N≧2) of a cyclic group G 1 and N elements γ L * (L=1, . . . , N) of a cyclic group G 2 ; b i εG 1 N (i=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 1 as elements; b j *εG 2 N (j=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 2 as elements; a function value obtained when each element of the basis vector b i εG 1 N (i=1, . . . , N) and each element of the basis vector b j *εG 2 N (j=1, . . . , N) are put into the bilinear function e is represented by g T τ·δ(i,j) εG T , using a Kronecker's delta function in which δ(i, j)=1 F when i=j and δ(i, j)=0 F when i≠j; 0 F is an additive unit element of a finite field F q ; 1 F is a multiplicative unit element of the finite field F q ; τ is an element of the finite field F q , other than 0 F ; and g T is a generator of the cyclic group G T ; and * indicates an indeterminate character, an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 , the set w(Y) corresponds to the index Y, and w(Y)={i|Y i =*}.

2 : The information generation apparatus according to Claim 1 ,

wherein the random number generator further generates a random number σ u εZ q , the information generation apparatus comprising: a storage unit adapted to store main information k v corresponding to an index v and derivation information k vj corresponding to the index v; and a main information deriving unit adapted to use the main information k v and derivation information k vi , both of which are read from the storage unit, and the generated random number σ u to calculate main information k u corresponding to an index u, which satisfies k u =σ u Σ iεw(v)\w(u) u i k vi +k v ; where * indicates an indeterminate character; the index v is v=(v 1 , . . . , V N-1 )εI=(F q ∪{*}) N-1 ; w(v) is a set corresponding to the index v and w(v)={i|v i =*}; the index uis u=(u 1 , . . . , u N-1 )εI=(F q ∪{*}) N-1 ; w(u) is a set corresponding to the index u and w(u)={i|u i =*}; w(u)⊂w(v); and v i =u i (iε{1, . . . , N−1}\w(v)).

3 : The information generation apparatus according to Claim 2 , wherein the random number generator further generates a random number σ uj εZ q , corresponding to each element jεw(u) of the set w(u);

the information generation apparatus further comprising:

a derivation information deriving unit adapted to use the derivation information k vj read from the storage unit and the generated random number σ uj to calculate derivation information k uj corresponding to the index u, which satisfies k uj =σ uj Σ iεw(v)\w(u) u i k vi +k vj , for each element jεw(u) of the set w(u).

4 : An information generation apparatus comprising:

a storage unit adapted to store main information k v serving as main information k Y or corresponding to an index v, derived from the main information k Y and derivation information k Yj , and derivation information k vj serving as the derivation information k Yj or corresponding to the index v, derived from the derivation information k Yj ; a random number generator adapted to generate a random number σ u εZ q ; and a main information deriving unit adapted to use the main information k v and derivation information k vi , both of which are read from the storage unit, and the generated random number σ u to calculate main information k u corresponding to an index u, which satisfies k u =σ u Z iεw(v)\w(u) u i k vi +k v ; where e is a non-degenerate, bilinear function that outputs one element of a cyclic group G T in response to inputs of N elements γ L (L=1, . . . , N) (N≧2) of a cyclic group G 1 and N elements γ L * (L=1, . . . , N) of a cyclic group G 2 ; b i εG 1 N (i=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 1 as elements; b j *εG 2 N (j=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 2 as elements; a function value obtained when each element of the basis vector b i εG 1 N (i=1, . . . , N) and each element of the basis vector b j *εG 2 N (j=1, . . . , N) are put into the bilinear function e is represented by g T τ·δ(i,j) εG T , using a Kronecker's delta function in which δ(i, j)=1 F when i=j and δ(i, j)=0 F when i≠j; 0 F is an additive unit element of a finite field F q ; 1 F is a multiplicative unit element of the finite field F q ; τ is an element of the finite field F q , other than 0 F ; and g T is a generator of the cyclic group G T ; and * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; a set w(Y) corresponding to the index Y is w(Y)={i|Y i =*}; σ Y εZ q is a random number; σ Yi εZ q is a random number corresponding to each element jεw(Y) of the set w(Y); the main information k Y corresponds to the index Y and satisfies k Y =σ Y Σ iε{1, . . . , N-1}\w(Y) Y i b i *+b N *; and the derivation information kyi corresponds to the index Y and satisfies k Yj =σ Yj Σ iε{1, . . . , N-1}\w(y) Y i b i *+b j *; * indicates an indeterminate character; the index v is v=(v 1 , . . . , V N-1 )εI=(F q ∪{*}) N-1 ; the index u is u=(u 1 , . . . , U N-1 )εI=(F q ∪{*}) N-1 ; w(v) is a set corresponding to the index v and w(v)={i|v i =*}; w(u) is a set corresponding to the index u and w(u)={i|u i =*}; w(u)⊂w(v); and v i =u i (iε{1, . . . , N−1}\w(v)).

5 : The information generation apparatus according to Claim 4 , wherein the random number generator further generates a random number σ uj εZ q , corresponding to each element jεw(u) of the set w(u);

the information generation apparatus further comprising:

a derivation information deriving unit adapted to use the derivation information k v j read from the storage unit and the generated random number σ uj to calculate derivation information k uj that satisfies k uj =σ uj Σ iεw(v)\w(u) u i k vi +k vj for each element jεw(u) of the set w(u).

6 : An information generation apparatus comprising:

a random number generator adapted to generate a random number r Y εZ q ; a first main information generator adapted to use the generated random number r Y to calculate first main information k Y that satisfies k Y =g 2 a (g 3 Π iε{1, . . . , N-1}\w(Y) h i Yi ) rY ; a second main information generator adapted to use the generated random number r Y to calculate second main information g rY ; and a derivation information generator adapted to use the generated random number r Y to calculate derivation information k Yj that satisfies k Yj =h j rY for each element jεw(Y) of a set w(Y); where G and G T are cyclic groups having a prime number order q; g is a generator of the cyclic group G; the cyclic group G has a pairing function e: G×G→G T , which makes g T =e(g, g) a generator of the cyclic group G T ; a is a random number selected at random from Z p ; and g, g 1 =g a εG, and g 2 , g 3 , h 1 , . . . , h N-1 εG randomly selected from the cyclic group G are made publicly available as public keys; and * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; the set w(Y) corresponds to the index Y; and w(Y)={i|Y i =*}.

7 : The information generation apparatus according to Claim 6 , wherein the random number generator further generates a random number r u εZ q ,

the information generation apparatus comprising:

a storage unit adapted to store first main information k v corresponding to an index v, second main information g r , and derivation information k vj corresponding to the index v;

a first main information deriving unit adapted to use the first main information k v and derivation information k vi , both of which are read from the storage unit, to calculate first main information k u corresponding to an index u, which satisfies k u =k v (Π iεw(v)\w(u) k vi ui )(g 3 Π iε{1, . . . , N-1}\w(v) h i vi Π iεw(v)\w(u) h i ui ) ru ; and

a second main information deriving unit adapted to use the generated random number r u to calculate second main information g ru ;

where * indicates an indeterminate character; the index v is v=(v 1 , . . . , v N-1 )εI=(F q ∪{*}) N-1 ; w(v) is a set corresponding to the index v and w(v)={i|v i =*}; the index u is u=(u 1 , . . . , U N-1 )εI=(F q ∪{*}) N-1 ; and w(u) is a set corresponding to the index u and w(u)={i|u i =*}; w(u)⊂w(v); and v i =u i (iε{1, . . . , N−1}\w(v)).

8 : The information generation apparatus according to Claim 7 , further comprising a derivation information deriving unit adapted to use the derivation information k vi read from the storage unit and the generated random number r u to calculate derivation information k uj that satisfies k uj =k vj h j ru for element jεw(u) of the set w(u).

9 : An information generation apparatus comprising:

a random number generator adapted to generate a random number r u εZ q ; a storage unit adapted to store main information k v serving as main information K Y or corresponding to an index v, derived from first main information k Y and derivation information k Yj , and derivation information k vj serving as derivation information K Yj or corresponding to the index v, derived from the derivation information k Yj ; a first main information deriving unit adapted to use the first main information k v and derivation information k vi , both of which are read from the storage unit, to calculate first main information k u corresponding to an index u, which satisfies k u =k v (Π iεw(v)\w(u) k vi iu )(g 3 Π iε{1 . . . , N-1}\w(v) h i vi Πiεw(v)\w(u)h i ui ) ru ; and a second main information deriving unit adapted to use the generated random number r u to calculate second main information g ru ; where G and G T are cyclic groups having a prime number order q; g is a generator of the cyclic group G; the cyclic group G has a pairing function e: G×G→G T , which makes g T =e(g, g) a generator of the cyclic group G T ; a is a random number selected at random from Z p ; and g, g 1 =g a εG, and g 2 , g 3 , h 1 , . . . , h N-1 εG randomly selected from the cyclic group G are made publicly available as public keys; * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; and a set w(Y) corresponding to the index Y is w(Y)={i|Y i =*}; r Y εZ q is a random number; the first main information k Y corresponds to the index Y and satisfies k Y =g 2 a (g 3 Π iε{1, . . . , N-1}\w(Y) h i Yi ) rY ; g rY is second main information corresponding to the index Y; and the derivation information k Yj corresponds to the index Y and satisfies k Yj =h j rY ; and * indicates an indeterminate character; the index v is v=(v 1 , . . . , V N-1 )εe I=(F q ∪{*}) N-1 ; w(v) is a set corresponding to the index v and w(v)={i|v i =*}; the index u is u=(u 1 , . . . , u N-1 )εI=(F q ∪{*}) N-1 ; w(u) is a set corresponding to the index u and w(u)={i|u i =*}; set w(u)⊂set w(v); and v i =u i (iε{1, . . . , N−1}\w(v)).

10 : The information generation apparatus according to Claim 9 , further comprising a derivation information deriving unit adapted to use the derivation information k vi read from the storage unit and the generated random number r u to calculate derivation information k uj that satisfies k uj i=k vj h j ru for element jεw(u) of the set w(u).

11 : An information generation method comprising:

a random number generation step of generating, in a random number generator, a random number σ Y εZ q and a random number σ Yj εZ q corresponding to each element jεw(Y) of a set w(Y); a main information generation step of using, in a main information generator, the generated random number σ Y to calculate main information k Y that satisfies k Y =σ Y Σ iε{1, . . . , N-1}\w(Y) Y i b i *+b N *; and a derivation information generation step of using, in a derivation information generator, the generated random number σ Yj to calculate derivation information k Yj that satisfies k Yj Σ iε{1, . . . , N-1}\w(Y) Y i b i *+b j * for each element jεw(Y) of the set w(Y); where e is a non-degenerate, bilinear function that outputs one element of a cyclic group G T in response to inputs of N elements γ L (L=1, . . . , N) (N≧2) of a cyclic group G 1 and N elements γ L *(L=1, . . . , N) of a cyclic group G 2 ; b i εG 1 N (i=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 1 as elements; b j εG 2 N (j=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G 2 as elements; a function value obtained when each element of the basis vector b i εG 1 N (i=1, . . . , N) and each element of the basis vector b j *εG 2 N (j=1, . . . , N) are put into the bilinear function e is represented by g T τ·δ(i,j) εG T , using a Kronecker's delta function in which δ(i, j)=1 F when i=j and δ(i, j)=0 F when i≠j; 0 F is an additive unit element of a finite field F q ; 1 F is a multiplicative unit element of the finite field F q ; τ is an element of the finite field F q , other than 0 F ; and g T is a generator of the cyclic group G T ; and * indicates an indeterminate character, an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 , and the set w(Y) corresponds to the index Y and w(Y)={i|Y i =*}.

12 : An information generation method comprising:

a random number generation step of generating, in a random number generator, a random number r Y εZ q ; a first main information generation step of using, in a first main information generator, the generated random number r Y to calculate first main information k Y that satisfies k Y =g 2 a (g 3 Π iε({1, . . . . N-1}\w(Y) h i Yi ) rY ; a second main information generation step of using, in a second main information generator, the generated random number r Y to calculate second main information g rY ; and a derivation information generation step of using, in a derivation information generator, the generated random number r Y to calculate derivation information k Yj that satisfies k Yj =h j rY for each element jεw(Y) of a set w(Y); where G and G T are cyclic groups having a prime number order q; g is a generator of the cyclic group G; the cyclic group G has a pairing function e: G×G→G T , which makes g T =e(g, g) a generator of the cyclic group G T ; a is a random number selected at random from Z p ; and g, g 1 =g a εG, and g 2 , g 3 , h 1 , . . . , h N-1 εG randomly selected from the cyclic group G are made publicly available as public keys; and * indicates an indeterminate character; an index Y is Y=(Y 1 , . . . , Y N-1 )εI=(F q ∪{*}) N-1 ; and the set w(Y) corresponds to the index Y and w(Y)={i|Y i =*}.

13 : An information generation program causing a computer to function as each unit of the information generation apparatus according to one of claims 1 to 10 .

14 : A computer-readable recording medium having stored thereon the information generation program according to Claim 13 .

US13/258,165

2009-04-24

2010-04-23

Information generation apparatus, method, program, and recording medium for deriving a decryption key from another decryption key

Expired - Fee Related

US8619980B2

( en )

Applications Claiming Priority (3)

Application Number

Priority Date

Filing Date

Title

JP2009-106009

2009-04-24

JP2009106009

2009-04-24

PCT/JP2010/057279

WO2010123116A1

( en )

2009-04-24

2010-04-23

Information generating device, information generating method, and information generating program and storage medium thereof

Publications (2)

Publication Number

Publication Date

US20120027206A1

true

US20120027206A1 ( en )

2012-02-02

US8619980B2

US8619980B2 ( en )

2013-12-31

Family

ID=43011230

Family Applications (1)

Application Number

Title

Priority Date

Filing Date

US13/258,165

Expired - Fee Related

US8619980B2

( en )

2009-04-24

2010-04-23

Information generation apparatus, method, program, and recording medium for deriving a decryption key from another decryption key

Country Status (7)

Country

Link

US

( 1 )

US8619980B2

( en )

EP

( 1 )

EP2424155B1

( en )

JP

( 1 )

JP5256342B2

( en )

KR

( 1 )

KR101351787B1

( en )

CN

( 1 )

CN102396178B

( en )

ES

( 1 )

ES2512115T3

( en )

WO

( 1 )

WO2010123116A1

( en )

Cited By (23)

* Cited by examiner, † Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US20130025084A1

( en )

*

2011-07-29

2013-01-31

Pylon Manufacturing Corporation

Wiper blade connector

USD706200S1

( en )

2010-09-22

2014-06-03

Pylon Manufacturing Corporation

Windshield wiper cover

US9108595B2

( en )

2011-07-29

2015-08-18

Pylon Manufacturing Corporation

Windshield wiper connector

US9174609B2

( en )

2011-04-21

2015-11-03

Pylon Manufacturing Corp.

Wiper blade with cover

US9174611B2

( en )

2011-07-28

2015-11-03

Pylon Manufacturing Corp.

Windshield wiper adapter, connector and assembly

US9203622B2

( en )

*

2011-11-18

2015-12-01

Mitsubishi Electric Corporation

Cryptographic processing system, cryptographic processing method, cryptograhpic processing program, and key generation device

EP2824652A4

( en )

*

2012-03-06

2015-12-02

Mitsubishi Electric Corp

ENCRYPTION SYSTEM, ENCRYPTION METHOD, AND ENCRYPTION PROGRAM

US9381893B2

( en )

2011-07-29

2016-07-05

Pylon Manufacturing Corp.

Windshield wiper connector

US9457768B2

( en )

2011-04-21

2016-10-04

Pylon Manufacturing Corp.

Vortex damping wiper blade

US9505380B2

( en )

2014-03-07

2016-11-29

Pylon Manufacturing Corp.

Windshield wiper connector and assembly

USD777079S1

( en )

2014-10-03

2017-01-24

Pylon Manufacturing Corp.

Wiper blade frame

USD787308S1

( en )

2014-10-03

2017-05-23

Pylon Manufacturing Corp.

Wiper blade package

US10077026B2

( en )

2012-02-24

2018-09-18

Pylon Manufacturing Corp.

Wiper blade

US10166951B2

( en )

2013-03-15

2019-01-01

Pylon Manufacturing Corp.

Windshield wiper connector

US10189445B2

( en )

2012-02-24

2019-01-29

Pylon Manufacturing Corp.

Wiper blade

US10363905B2

( en )

2015-10-26

2019-07-30

Pylon Manufacturing Corp.

Wiper blade

US10513246B2

( en )

2016-05-19

2019-12-24

Pylon Manufacturing Corp.

Windshield wiper connector

US10661759B2

( en )

2016-05-19

2020-05-26

Pylon Manufacturing Corporation

Windshield wiper connector

US10717414B2

( en )

2016-05-19

2020-07-21

Pylon Manufacturing Corporation

Windshield wiper blade

US10723322B2

( en )

2012-02-24

2020-07-28

Pylon Manufacturing Corp.

Wiper blade with cover

US10766462B2

( en )

2016-05-19

2020-09-08

Pylon Manufacturing Corporation

Windshield wiper connector

US10829092B2

( en )

2012-09-24

2020-11-10

Pylon Manufacturing Corp.

Wiper blade with modular mounting base

US11040705B2

( en )

2016-05-19

2021-06-22

Pylon Manufacturing Corp.

Windshield wiper connector

Families Citing this family (3)

* Cited by examiner, † Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

JP2020068437A

( en )

*

2018-10-23

2020-04-30

株式会社アメニディ

Access management device and program

US11764940B2

( en )

2019-01-10

2023-09-19

Duality Technologies, Inc.

Secure search of secret data in a semi-trusted environment using homomorphic encryption

EP4169205A1

( en )

*

2020-06-22

2023-04-26

Forctis AG

System and method for controlling access to tokens

Family Cites Families (5)

* Cited by examiner, † Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US7174013B1

( en )

*

1998-10-20

2007-02-06

Lucent Technologies Inc.

Efficient universal hashing method

EP1216536A1

( en )

*

1999-10-01

2002-06-26

France Telecom

Set of particular keys for proving authenticity of an entity or the integrity of a message

US7349538B2

( en )

*

2002-03-21

2008-03-25

Ntt Docomo Inc.

Hierarchical identity-based encryption and signature schemes

US20040086117A1

( en )

*

2002-06-06

2004-05-06

Petersen Mette Vesterager

Methods for improving unpredictability of output of pseudo-random number generators

US8340284B2

( en )

2007-02-13

2012-12-25

Nec Corporation

Key generation device, key derivation device, encryption device, decryption device, method and program

2010

2010-04-23

WO

PCT/JP2010/057279

patent/WO2010123116A1/en

not_active

Ceased

2010-04-23

US

US13/258,165

patent/US8619980B2/en

not_active

Expired - Fee Related

2010-04-23

CN

CN201080016597.9A

patent/CN102396178B/en

not_active

Expired - Fee Related

2010-04-23

JP

JP2011510383A

patent/JP5256342B2/en

not_active

Expired - Fee Related

2010-04-23

KR

KR1020117023782A

patent/KR101351787B1/en

active

Active

2010-04-23

EP

EP10767171.1A

patent/EP2424155B1/en

active

Active

2010-04-23

ES

ES10767171.1T

patent/ES2512115T3/en

active

Active

Cited By (35)

* Cited by examiner, † Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US10543813B2

( en )

2010-02-10

2020-01-28

Pylon Manufacturing Corp.

Wiper blade

USD706200S1

( en )

2010-09-22

2014-06-03

Pylon Manufacturing Corporation

Windshield wiper cover

US9457768B2

( en )

2011-04-21

2016-10-04

Pylon Manufacturing Corp.

Vortex damping wiper blade

US10005431B2

( en )

2011-04-21

2018-06-26

Pylon Manufacturing Corp.

Vortex damping wiper blade

US9174609B2

( en )

2011-04-21

2015-11-03

Pylon Manufacturing Corp.

Wiper blade with cover

US11124158B2

( en )

2011-04-21

2021-09-21

Pylon Manufacturing Corp.

Wiper blade with cover

US10464533B2

( en )

2011-04-21

2019-11-05

Pylon Manufacturing Corp.

Wiper blade with cover

US10457252B2

( en )

2011-07-28

2019-10-29

Pylon Manufacturing Corp.

Windshield wiper adapter, connector and assembly

US9174611B2

( en )

2011-07-28

2015-11-03

Pylon Manufacturing Corp.

Windshield wiper adapter, connector and assembly

US9108595B2

( en )

2011-07-29

2015-08-18

Pylon Manufacturing Corporation

Windshield wiper connector

US9381893B2

( en )

2011-07-29

2016-07-05

Pylon Manufacturing Corp.

Windshield wiper connector

US10597004B2

( en )

2011-07-29

2020-03-24

Pylon Manufacturing Corporation

Windshield wiper connector

US20130025084A1

( en )

*

2011-07-29

2013-01-31

Pylon Manufacturing Corporation

Wiper blade connector

US8806700B2

( en )

*

2011-07-29

2014-08-19

Pylon Manufacturing Corporation

Wiper blade connector

US9203622B2

( en )

*

2011-11-18

2015-12-01

Mitsubishi Electric Corporation

Cryptographic processing system, cryptographic processing method, cryptograhpic processing program, and key generation device

US11180118B2

( en )

2012-02-24

2021-11-23

Pylon Manufacturing Corp.

Wiper blade

US10077026B2

( en )

2012-02-24

2018-09-18

Pylon Manufacturing Corp.

Wiper blade

US10189445B2

( en )

2012-02-24

2019-01-29

Pylon Manufacturing Corp.

Wiper blade

US10723322B2

( en )

2012-02-24

2020-07-28

Pylon Manufacturing Corp.

Wiper blade with cover

US11136002B2

( en )

2012-02-24

2021-10-05

Pylon Manufacturing Corp.

Wiper blade

EP2824652A4

( en )

*

2012-03-06

2015-12-02

Mitsubishi Electric Corp

ENCRYPTION SYSTEM, ENCRYPTION METHOD, AND ENCRYPTION PROGRAM

US10829092B2

( en )

2012-09-24

2020-11-10

Pylon Manufacturing Corp.

Wiper blade with modular mounting base

US10166951B2

( en )

2013-03-15

2019-01-01

Pylon Manufacturing Corp.

Windshield wiper connector

US9889822B2

( en )

2014-03-07

2018-02-13

Pylon Manufacturing Corp.

Windshield wiper connector and assembly

US9505380B2

( en )

2014-03-07

2016-11-29

Pylon Manufacturing Corp.

Windshield wiper connector and assembly

USD787308S1

( en )

2014-10-03

2017-05-23

Pylon Manufacturing Corp.

Wiper blade package

USD777079S1

( en )

2014-10-03

2017-01-24

Pylon Manufacturing Corp.

Wiper blade frame

US10363905B2

( en )

2015-10-26

2019-07-30

Pylon Manufacturing Corp.

Wiper blade

US11155241B2

( en )

2015-10-26

2021-10-26

Pylon Manufacturing Corp.

Windshield wiper blade

US10513246B2

( en )

2016-05-19

2019-12-24

Pylon Manufacturing Corp.

Windshield wiper connector

US10661759B2

( en )

2016-05-19

2020-05-26

Pylon Manufacturing Corporation

Windshield wiper connector

US10717414B2

( en )

2016-05-19

2020-07-21

Pylon Manufacturing Corporation

Windshield wiper blade

US10766462B2

( en )

2016-05-19

2020-09-08

Pylon Manufacturing Corporation

Windshield wiper connector

US11040705B2

( en )

2016-05-19

2021-06-22

Pylon Manufacturing Corp.

Windshield wiper connector

US11554754B2

( en )

2016-05-19

2023-01-17

Pylon Manufacturing Corporation

Windshield wiper blade

Also Published As

Publication number

Publication date

ES2512115T3

( en )

2014-10-23

CN102396178B

( en )

2014-12-10

EP2424155A1

( en )

2012-02-29

KR20110136841A

( en )

2011-12-21

JPWO2010123116A1

( en )

2012-10-25

EP2424155A4

( en )

2012-08-15

JP5256342B2

( en )

2013-08-07

WO2010123116A1

( en )

2010-10-28

KR101351787B1

( en )

2014-01-15

US8619980B2

( en )

2013-12-31

EP2424155B1

( en )

2014-09-03

CN102396178A

( en )

2012-03-28

Similar Documents

Publication

Publication Date

Title

US8619980B2

( en )

2013-12-31

Information generation apparatus, method, program, and recording medium for deriving a decryption key from another decryption key

US8515060B2

( en )

2013-08-20

Encryption apparatus, decryption apparatus, encryption method, decryption method, security method, program, and recording medium

US8897442B2

( en )

2014-11-25

Encryption device, decryption device, encryption method, decryption method, program, and recording medium

US8964982B2

( en )

2015-02-24

Cryptographic system, cryptographic communication method, encryption apparatus, key generation apparatus, decryption apparatus, content server, program, and storage medium

US8995660B2

( en )

2015-03-31

Cryptographic system, cryptographic communication method, encryption apparatus, key generation apparatus, decryption apparatus, content server, program, and storage medium

US8549290B2

( en )

2013-10-01

Secret sharing system, sharing apparatus, share management apparatus, acquisition apparatus, processing methods thereof, secret sharing method, program, and recording medium

Keerthi et al.

2017

Elliptic curve cryptography for secured text encryption

Moldovyan et al.

2010

A new hard problem over non-commutative finite groups for cryptographic protocols

EP2503533A1

( en )

2012-09-26

Cipher processing system, key generating device, key delegating device, encrypting device, decrypting device, cipher processing method, and cipher processing program

EP2523178A1

( en )

2012-11-14

Encryption processing system, key generation device, key devolvement device, encryption device, decoding device, encryption processing method, and encryption processing program

Silverberg

2013

Fully homomorphic encryption for mathematicians

Karbasi et al.

2018

PairTRU: Pairwise non-commutative extension of the NTRU public key cryptosystem

JP5612494B2

( en )

2014-10-22

Timed cryptographic system, timed cryptographic method, apparatus, and program using function encryption

Yeh et al.

2014

P2P email encryption by an identity-based one-way group key agreement protocol

Bahramian et al.

2021

An identity-based encryption scheme using isogeny of elliptic curves

Chillali et al.

2019

Anonymous multi-receiver public key encryption based on third order linear sequences

Zhang

2017

An investigation of some public key exchange cryptosystems

King

2009

A Simple Encryption Scheme for Binary Elliptic Curves

Tiplea et al.

2016

Boneh-Gentry-Hamburg's Identity-based Encryption Schemes Revisited.

Satpathy

2014

Some cryptographic algorithms

Xia et al.

2014

Attribute-based hash proof system

CN115150070A

( en )

2022-10-04

An anonymous identification broadcast encryption method based on state secret SM9

Legal Events

Date

Code

Title

Description

2011-10-18

AS

Assignment

Owner name : NIPPON TELEGRAPH AND TELEPHONE CORPORATION, JAPAN

Free format text : ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SUZUKI, KOUTAROU;NISHIMAKI, RYO;REEL/FRAME:027077/0178

Effective date : 20110924

2013-12-11

STCF

Information on status: patent grant

Free format text : PATENTED CASE

2017-06-20

FPAY

Fee payment

Year of fee payment : 4

2021-06-23

MAFP

Maintenance fee payment

Free format text : PAYMENT OF MAINTENANCE FEE, 8TH YEAR, LARGE ENTITY (ORIGINAL EVENT CODE: M1552); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

Year of fee payment : 8

2025-08-18

FEPP

Fee payment procedure

Free format text : MAINTENANCE FEE REMINDER MAILED (ORIGINAL EVENT CODE: REM.); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

2026-02-02

LAPS

Lapse for failure to pay maintenance fees

Free format text : PATENT EXPIRED FOR FAILURE TO PAY MAINTENANCE FEES (ORIGINAL EVENT CODE: EXP.); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

2026-02-02

STCH

Information on status: patent discontinuation

Free format text : PATENT EXPIRED DUE TO NONPAYMENT OF MAINTENANCE FEES UNDER 37 CFR 1.362

2026-02-24

FP

Lapsed due to failure to pay maintenance fee

Effective date : 20251231

Related documents

• Generating augmented reality experiences utilizing physical objects to … — Meta Platforms Technologies, Llc (US20260037214A1)#653960
• Virtual reality system using multiple force arrays for a solver — DeepMotion, Inc. (US10657696B2)#653961
• Tracking position of device inside-out for virtual reality interactivity — Sony Interactive Entertainment America Llc (US10535153B2)#653962
• Augmented reality system with spatialized audio tied to user manipulated … — Magic Leap, Inc. (US11231770B2)#653963
• Big data-based autonomous flight drone system and autonomous flight method … — Rgblab Co., Ltd. (US20210390867A1)#653964