INFORMATION GENERATION APPARATUS,METHOD, PROGRAM, AND RECORDING MEDIUM THEREFOR

• US 20120027206A1
• Filed: 04/23/2010
• Published: 02/02/2012
• Est. Priority Date: 04/24/2009
• Status: Active Grant

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Suzuki, Koutarou, Nishimaki, Ryo
• Granted Patent: US 8,619,980 B2
• Time in Patent Office: Days
• US Class Current: 380/44
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/0847 involving identity based encryption [IBE] schemes
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing

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)εZ_q are generated; main information k_v=σ_vΣ_{iε{1, . . . , N-1}\w(v)}v_ib_i*+b_N* is calculated; and derivation information k_vj=σ_vjΣ_{iε{1, . . . , N-1}\w(v)}v_ib_i*+b_j* is calculated for each jεw(v). In information derivation, random numbers σ_u and (σ_uj)_jεw(u)εZ_q are generated; main information k_u=σ_uΣ_iεw(v)\w(u)u_ik_vi+k_v is calculated; and derivation information k_uj=σ_ujΣ_iεw(v)\w(u)u_ik_vi+k_vj is calculated for each jεw(v).

Claims

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Σ

<sub>iε

{1, . . . , N-1}\w(Y)</sub>Y_ib_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Σ

<sub>iε

{1, . . . , N-1}\w(Y)</sub>Y_ib_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₁ and N elements γ

_L* (L=1, . . . , N) of a cyclic group G₂;

b_iε

G₁^N (i=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G₁ as elements;

b_j*ε

G₂^N (j=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G₂ as elements;

a function value obtained when each element of the basis vector b_iε

G₁^N (i=1, . . . , N) and each element of the basis vector b_j*ε

G₂^N (j=1, . . . , N) are put into the bilinear function e is represented by g_T<sup>τ

·

δ

(i,j)</sup>ε

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₁, . . . , 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Σ

<sub>iε

w(v)\w(u)</sub>u_ik_vi+k_v;

where * indicates an indeterminate character;

the index v is v=(v₁, . . . , 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₁, . . . , 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Σ

<sub>iε

w(v)\w(u)</sub>u_ik_vi+k_vj, for each element jε

w(u) of the set w(u).

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.

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=σ

_uZ<sub>iε

w(v)\w(u)</sub>u_ik_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₁ and N elements γ

_L* (L=1, . . . , N) of a cyclic group G₂;

b_iε

G₁^N (i=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G₁ as elements;

b_j*ε

G₂^N (j=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G₂ as elements;

a function value obtained when each element of the basis vector b_iε

G₁^N (i=1, . . . , N) and each element of the basis vector b_j*ε

G₂^N (j=1, . . . , N) are put into the bilinear function e is represented by g_T<sup>τ

·

δ

(i,j)</sup>ε

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₁, . . . , 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Σ

<sub>iε

{1, . . . , N-1}\w(Y)</sub>Y_ib_i*+b_N*; and

the derivation information kyi corresponds to the index Y and satisfies k_Yj=σ

_YjΣ

<sub>iε

{1, . . . , N-1}\w(y)</sub>Y_ib_i*+b_j*;

* indicates an indeterminate character;

the index v is v=(v₁, . . . , V_N-1)ε

I=(F_q∪

{*})^N-1;

the index u is u=(u₁, . . . , 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Σ

<sub>iε

w(v)\w(u)</sub>u_ik_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₂^a(g₃Π

<sub>iε

{1, . . . , N-1}\w(Y)</sub>^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₁=g^aε

G, and g₂, g₃, h₁, . . . , 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₁, . . . , 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(Π

<sub>iε

w(v)\w(u)</sub>k_vi^ui)(g₃Π

<sub>iε

{1, . . . , N-1}\w(v)</sub>h_i^viΠ

<sub>iε

w(v)\w(u)</sub>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₁, . . . , 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₁, . . . , 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_vjh_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(Π

<sub>iε

w(v)\w(u)</sub>k_vi^iu)(g₃Π

<sub>iε

{1 . . . , N-1}\w(v)</sub>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₁=g^aε

G, and g₂, g₃, h₁, . . . , 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₁, . . . , 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₂^a(g₃Π

<sub>iε

{1, . . . , N-1}\w(Y)</sub>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₁, . . . , 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₁, . . . , 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_uji=k_vjh_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Σ

<sub>iε

{1, . . . , N-1}\w(Y)</sub>Y_ib_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Σ

<sub>iε

{1, . . . , N-1}\w(Y)</sub>Y_ib_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₁ and N elements γ

_L*(L=1, . . . , N) of a cyclic group G₂;

b_iε

G₁^N(i=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G₁ as elements;

b_jε

G₂^N (j=1, . . . , N) is an N-dimensional basis vector having N elements of the cyclic group G₂ as elements;

a function value obtained when each element of the basis vector b_iε

G₁^N (i=1, . . . , N) and each element of the basis vector b_j*ε

G₂^N (j=1, . . . , N) are put into the bilinear function e is represented by g_T<sup>τ

·

δ

(i,j)</sup>ε

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₁, . . . , 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₂^a(g₃Π

<sub>iε

({1, . . . . N-1}\w(Y)</sub>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₁=g^aε

G, and g₂, g₃, h₁, . . . , 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₁, . . . , Y_N-1)ε

I=(F_q∪

{*})^N-1; and

the set w(Y) corresponds to the index Y and w(Y)={i|Y_i=*}.