Secret key generation method, encryption method, and cryptographic communications method and system

• US 7,080,255 B1
• Filed: 05/18/2000
• Issued: 07/18/2006
• Est. Priority Date: 05/19/1999
• Status: Expired due to Fees

• Current Assignee: Murata Machinery Limited (Muratec)
• Original Assignee: Murata Machinery Limited (Muratec)
• Inventors: Murakami, Yasuyuki, Kasahara, Masao, Tsujii, Shigeo
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US09/573,915
• Time in Patent Office: 2,252 Days
• Field of Search: 380/255, 380/259, 380/268, 380277-278, 380/279, 380/282, 380/44, 380 46- 47, 380/28, 380/48, 380/262, 380/280, 713/182, 713200-201, 709223-229
• US Class Current: 713/182
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]
• CPC Class Codes: H04L 9/0847 involving identity based encryption [IBE] schemes

Abstract

A cryptographic communications method is provided which is based on ID-NIKS and is resilient to collusive attack. Centers (1) established in a plurality generate secret keys peculiar to entities (a, b) using division vectors wherein specifying information (ID information) for said entities is divided and personal secret random numbers set differently for each component in the division vectors. The centers (1) then distribute the secret keys to the entities. The entities generate common keys using components, contained in their own peculiar secret keys, that correspond to the division vectors of other entities. Each division vector is configured with codewords of an error correcting code.

Claims

1. A secret key generation method wherein:

secret keys peculiar to entities are generated by using division vectors indicating divided specifying information resulting from division of information specifying said entities into a plurality of blocks, and personal secret random numbers peculiar to said entities, set for each of said divided blocks;

said personal secret random numbers are set with different values for each component in said division vectors;

said secret keys are generated using said personal secret random numbers so set and said division vectors;

when number of divided blocks of said division vectors is taken as J, sizes of said division vectors as M_j (j=1, 2, . . . , J), and personal secret random number for entity e as β

_ej^(v) (v=0, 1, . . . , M_j−

1), where β

is a random number, all J divided blocks are grouped into K groups, with one or a plurality of blocks in each group; and

said secret keys satisfy γ

_eR1+γ

_eR2+ . . . +γ

_eRk=nλ

(N)

where n is an integer, λ

(.) is a Carmichael function, and N=PQ (where P and Q are prime),

where;

R_K is a partial set of universal set U having, as members, natural numbers up to J,

R_p∩

R_q is an empty set for any p and q, and R₁ U R₂

U . . . U R_K is said universal set U; and

γ

_eRk is a constant value obtained by calculating personal secret random numbers and correction terms in each component in division vector corresponding to S_k.

2. A cryptographic communications system wherein:

encrypting processing for encrypting plaintext that is information to be sent into ciphertext and decrypting processing for decrypting ciphertext sent back into original plaintext are performed reciprocally between a plurality of entities;

having;

a plurality of centers that generate secret keys peculiar to said entities, following the formulas given below, using divided specifying information resulting from division of information specifying said entities into a plurality of blocks, using row vectors corresponding to said divided specifying information for said entities, each of said row vectors being selected from a symmetrical matrix peculiar to each block, and the secret keys to the entities; and

a plurality of entities each of which generates common keys employed in said encryption processing and said decryption processing, following the formulas given below, using components, contained in own secret key thereof, sent from said centers, that correspond to divided specifying information of entities to be communicated with, wherein computation formulas for generating said secret keys are as follows,

{right arrow over (s_R,i^(j))}≡

α

_i({right arrow over (h_R,i^(j))}+{right arrow over (γ

_R,i^(j))})(mod λ

(N))

{right arrow over (s_L,i^(j))}≡

β

_i({right arrow over (h_L,i^(j))}+{right arrow over (γ

_L,i^(j))})(mod λ

(N))

Secret keys g^aipbiqcir numbering (T+1)(T+2)/2

where p+q+r=T,

a_i, b_i, and c_i satisfy following relationships

a_i·

α

_i≡

1(mod λ

(N))

b_i·

β

_i≡

1(mod λ

(N))

$\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_i^{\left(j\right)}+c_i=\mathrm{\lambda <br><br>}<br><br>\left(N\right)$

where

vector S_R,i^(j) and vector S_L,i^(j) are two types of secret key corresponding to j'"'"'th divided specifying information for entity i (j=2, 3, . . . , J);

vector h_R,i^(j), vector h_L,i^(j) are key division vector of entity i, vector h_R,i^(j)+vector h_L,i^(j)=vector h_i^(j);

vector h_i^(j) is a vector obtained by extracting one row from a matrix H^(j) corresponding to j'"'"'th divided specifying information for entity i;

H^(j) is a symmetrical 2^Mj×

2^Mj matrix formed of random numbers;

M_j is size of j'"'"'th divided specifying information for entity i;

J is number of block divisions in specifying information for entity i;

α

_i, β

_i are personal secret random numbers for entity i;

where gcd (α

_i, λ

(N))=1,

gcd (β

_i, λ

(N))=1, and

λ

(·

) is Carmichael function;

N is an integer;

γ

_i^(j), c_i are personal secret random numbers for entity i

where γ

i⁽¹⁾+γ

i⁽²⁾+ . . . +γ

i^(J)+c_i=λ

(N)

vector γ

_R,i^(j), vector γ

_L,i^(j) are random number division vectors of entity i, vector γ

_R,im^(j)+vector γ

_L,im^(j)=γ

_i^(j) vector 1 for entity m (where vector 1=(1, 1, . . . ,

     1);

g is an integer mutually prime with N; and

T is degree of exponent portion, and wherein,

$\begin{array}{c}{K}_{\mathrm{im}}\equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br><br><br>{\left({}_{g}a_i^p<br><br>b_i^q<br><br>c_i^r\right)}^{S_{R,\mathrm{im}}^p<br><br>S_{L,\mathrm{im}}^q<br><br>\frac{T!}{p!<br><br>q!<br><br>r!}}\\ \equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br>{\hspace{0.17em}<br><br>}_g<br><br>\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r\\ \equiv <br><br><br><br>{\hspace{1em}<br><br>}_g<br><br>\underset{p+q+r=T}{\sum <br><br>}<br><br><br><br>\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r\\ \equiv <br><br><br><br>{}_g\left(X_{R,\mathrm{im}}+X_{L,\mathrm{im}}+c_i\right)^T\\ \equiv <br><br><br><br>{}_g\left\{\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>\left(h_{R,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{R,{\mathrm{im}}_j^{\left(j\right)}}+h_{L,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{L,{\mathrm{im}}_j^{\left(j\right)}}\right)+c_i\right\}^T\\ \equiv <br><br><br><br>{\hspace{1em}<br><br>}_g<br><br>{\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}+\mathrm{\lambda <br><br>}<br><br>\left(N\right)\right)}^T\\ \equiv <br><br><br><br>{}_g\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}\right)^T\\ \equiv <br><br><br><br>K_{\mathrm{mi}}<br><br>\left(\mathrm{mod}<br><br>N\right)\end{array}$

where

S_R,im is a sum on the integer ring of components S_R,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_R,i^(j) for entity i, expressed as given below;

S_L,im is a sum on the integer ring of components S_L,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_L,i^(j) for entity i, expressed as given below; and

K_im is a common key generated by one entity i for another entity m, and wherein,

$\begin{array}{c}{S}_{R,\mathrm{im}}=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{R,{\mathrm{im}}_j^{\left(j\right)}}\\ =<br><br>{\mathrm{\alpha <br><br>}}_i<br><br>X_{R,\mathrm{im}}\end{array}$

where . . .

$\hspace{1em}<br><br>\begin{array}{c}{X}_{R,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{R,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{R,i}<br><br>m_j^{\left(j\right)}\\ \hspace{1em}<br><br>S_{L,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{L,i}<br><br>m_j^j\\ =<br><br>{\mathrm{\beta <br><br>}}_i<br><br>X_{L,i}<br><br>m\end{array}$

where . . .

$X_{L,i}<br><br>m=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{L,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{L,i}<br><br>m_j^{\left(j\right)}$

3. A computer-readable medium for recording a program designed to cause a computer, at an entity end, to generate a common key used in encryption processing from plaintext to ciphertext and in decryption processing from ciphertext to plaintext in a cryptographic communications system, wherein

said program comprises:

first program code means for causing said computer to select components corresponding to divided specifying information for another entity to be communicated with from a secret key peculiar to said entity produced according to formulas below for each divided specifying information resulting from division of specifying information for said entity into a plurality of blocks; and

second program code means for causing said computer to generate said common key according to formulas below using said selected components, wherein

{right arrow over (s_R,i^(j))}≡

α

_i({right arrow over (h_R,i^(j))}+{right arrow over (γ

_R,i^(j))})(mod λ

(N))

{right arrow over (s_L,i^(j))}≡

β

_i({right arrow over (h_L,i^(j))}+{right arrow over (γ

_L,i^(j))})(mod λ

(N))

Secret keys g^aipbiqcir numbering (T+1)(T+2)/2

where p+q+r=T,

a_i, b_i, and c_i satisfy following relationships

a_i·

α

_i≡

1(mod λ

(N))

b_i·

β

_i≡

1(mod λ

(N))

$\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_i^{\left(j\right)}+c_i=\mathrm{\lambda <br><br>}<br><br>\left(N\right)$

where

vector S_R,i^(j) and vector S_L,i^(j) are two types of secret key corresponding to j'"'"'th divided specifying information for entity i (j=2, 3, . . . , J);

vector h_R,i^(j), vector h_L,i^(j) are key division vector of entity i, vector h_R,i^(j)+vector h_L,i^(j)=vector h_i^(j);

vector h_i^(j) is a vector obtained by extracting one row from a matrix H^(j) corresponding to j'"'"'th divided specifying information for entity i;

H^(j) is a symmetrical 2^Mj×

2^Mj matrix formed of random numbers;

M_j is size of j'"'"'th divided specifying information for entity i;

J is number of block divisions in specifying information for entity i;

α

_i, β

_i are personal secret random numbers for entity i

where gcd (α

_i, λ

(N))=1,

gcd (β

_i, λ

(N))=1, and

λ

(·

) is Carmichael function;

N is an integer;

γ

i^(j), c_i are personal secret random numbers for entity i

where γ

i⁽¹⁾+γ

i⁽²⁾+ . . . +γ

i^(J)+c_i=λ

(N)

vector γ

_R,i^(j), vector γ

_L,i^(j) are random number division vectors of entity i, vector γ

_R,im^(j)+vector γ

_L,im^(j)=γ

_i^(j) vector 1 for entity m (where vector 1=(1, 1, . . . ,

     1);

g is an integer mutually prime with N; and

T is degree of exponent portion, and wherein,

$\begin{array}{c}{K}_{\mathrm{im}}\equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br><br><br>{\left({}_{g}a_i^p<br><br>b_i^q<br><br>c_i^r\right)}^{S_{R,\mathrm{im}}^p<br><br>S_{L,\mathrm{im}}^q<br><br>\frac{T!}{p!<br><br>q!<br><br>r!}}\\ \equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br>{\hspace{0.17em}<br><br>}_g<br><br>\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r\\ \equiv <br><br><br><br>{\hspace{1em}<br><br>}_g<br><br>\underset{p+q+r=T}{\sum <br><br>}<br><br><br><br>\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r\\ \equiv <br><br><br><br>{}_g\left(X_{R,\mathrm{im}}+X_{L,\mathrm{im}}+c_i\right)^T\\ \equiv <br><br><br><br>{}_g\left\{\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>\left(h_{R,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{R,{\mathrm{im}}_j^{\left(j\right)}}+h_{L,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{L,{\mathrm{im}}_j^{\left(j\right)}}\right)+c_i\right\}^T\\ \equiv <br><br><br><br>{\hspace{1em}<br><br>}_g<br><br>{\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}+\mathrm{\lambda <br><br>}<br><br>\left(N\right)\right)}^T\\ \equiv <br><br><br><br>{}_g\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}\right)^T\\ \equiv <br><br><br><br>K_{\mathrm{mi}}<br><br>\left(\mathrm{mod}<br><br>N\right)\end{array}$

where

S_R,im is a sum on the integer ring of components S_R,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_R,i^(j) for entity i, expressed as given below;

S_L,im is a sum on the integer ring of components S_L,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_L,i^(j) for entity i, expressed as given below; and

K_im is a common key generated by one entity i for another entity m, and wherein

$\begin{array}{c}{S}_{R,i<br><br><br><br>m}=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{R,i<br><br><br><br>m_j^{\left(j\right)}}\\ ={\mathrm{\alpha <br><br>}}_i<br><br>X_{R,i<br><br><br><br>m}\end{array}$

where . . .

$\hspace{1em}<br><br>\begin{array}{c}{X}_{R,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{R,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{R,i}<br><br>m_j^{\left(j\right)}\\ S_{L,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{L,i}<br><br>m_j^{\left(j\right)}\\ =<br><br>{\mathrm{\beta <br><br>}}_i<br><br>X_{L,i}<br><br>m\end{array}$

where . . .

$X_{L,i}<br><br>m=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{L,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{L,i}<br><br>m_j^{\left(j\right)}$

4. A computer data signal embodied in a carrier wave for transmitting a program comprising:

first program code means for causing said computer to select components corresponding to divided specifying information for another entity to be communicated with from secret keys peculiar to said entity produced according to formulas below for each divided specifying information of said entity resulting from division of specifying information for said entity into a plurality of blocks; and

second program code means for causing said computer to generate a common key according to formulas below using said selected components, wherein

{right arrow over (s_R,i^(j))}≡

α

_i({right arrow over (h_R,i^(j))}+{right arrow over (γ

_R,i^(j))})(mod λ

(N))

{right arrow over (s_L,i^(j))}≡

β

_i({right arrow over (h_L,i^(j))}+{right arrow over (γ

_L,i^(j))})(mod λ

(N))

Secret keys g^aipbiqcir numbering (T+1)(T+2)/2

where p+q+r=T

a_i, b_i, and c_i satisfy following relationships

a_i·

α

_i≡

1(mod λ

(N))

b_i·

β

_i≡

1(mod λ

(N))

$\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{i<br><br>}^{\left(j\right)}+c_i=\mathrm{\lambda <br><br>}<br><br>\left(N\right)$

where

vector S_R,i^(j) and vector S_L,i^(j) are two types of secret key corresponding to j'"'"'th divided specifying information for entity i (j=2, 3, . . . , J);

vector h_R,i^(j), vector h_L,i^(j) are key division vector of entity i, vector h_R,i^(j)+vector h_L,i^(j)=vector h_i^(j);

vector h_i^(j) is a vector obtained by extracting one row from a matrix H^(j) corresponding to j'"'"'th divided specifying information for entity i;

H^(j) is a symmetrical 2^Mj×

2^Mj matrix formed of random numbers;

M_j is size of j'"'"'th divided specifying information for entity i;

J is number of block divisions in specifying information for entity i;

α

_i, β

_i are personal secret random numbers for entity i

where gcd (α

_i, λ

(N))=1,

gcd (β

_i, λ

(N))=1, and

λ

(·

) is Carmichael function;

N is an integer;

γ

i^(j), c_i are personal secret random numbers for entity i

where γ

i⁽¹⁾+γ

i⁽²⁾+ . . . α

γ

i^(J)+c_i=λ

(N)

vector γ

_R,i^(j), vector γ

_L,i^(j) are random number division vectors of entity i, vector γ

_R,im^(j)+vector γ

_L,im^(j)=γ

_i^(j) vector 1 for entity m (where vector 1=(1, 1, . . . ,

     1);

g is an integer mutually prime with N; and

T is degree of exponent portion, and wherein

$\begin{array}{c}{K}_{i<br><br><br><br>m}\equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br><br><br>{\left(g^{a_i^p<br><br>b_i^q<br><br>c_i^r}\right)}^{S_{R,\mathrm{im}}^p<br><br>S_{L,\mathrm{im}}^q<br><br>\frac{T!}{p!<br><br>q!<br><br>r!}}\\ \equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br>g^{\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r}\\ \equiv <br><br><br><br>g<br><br>\underset{p+q+r=T}{\sum <br><br>}<br><br><br><br>\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r\\ \equiv <br><br><br><br>{g<br><br>\left(X_{R,\mathrm{im}}+X_{L,\mathrm{im}}+c_i\right)}^T\\ \equiv <br><br><br><br>g<br><br>{\left\{\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>\left(h_{R,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{R,{\mathrm{im}}_j^{\left(j\right)}}+h_{L,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{L,{\mathrm{im}}_j^{\left(j\right)}}\right)+c_i\right\}}^T\\ \equiv <br><br><br><br>{g<br><br>\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}+\mathrm{\lambda <br><br>}<br><br>\left(N\right)\right)}^T\\ \equiv <br><br><br><br>{g<br><br>\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}\right)}^T\\ \equiv <br><br><br><br>K_{m<br><br><br><br>i}<br><br>\left(\mathrm{mod}<br><br><br><br>N\right)\end{array}$

where

S_R,im is a sum on the integer ring of components S_R,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_R,i^(j) for entity i, expressed as given below;

S_L,im is a sum on the integer ring of components S_L,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_L,i^(j) for entity i, expressed as given below; and

K_im is a common key generated by one entity i for another entity m, and wherein,

$\begin{array}{c}{S}_{R,i<br><br><br><br>m}=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{R,i<br><br><br><br>m_j^{\left(j\right)}}\\ ={\mathrm{\alpha <br><br>}}_i<br><br>X_{R,i<br><br><br><br>m}\end{array}$

where . . .

$\hspace{1em}<br><br>\begin{array}{c}{X}_{R,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{R,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{R,i}<br><br>m_j^{\left(j\right)}\\ S_{L,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{L,i}<br><br>m_j^{\left(j\right)}\\ =<br><br>{\mathrm{\beta <br><br>}}_i<br><br>X_{L,i}<br><br>m\end{array}$

where . . .

$X_{L,i}<br><br>m=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{L,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{L,i}<br><br>m_j^{\left(j\right)}$

5. An encryption method wherein:

specifying information of an entity is divided into a plurality of blocks of divided specifying information, a plurality of row vectors corresponding to said plurality of blocks of divided specifying information are prepared, with each of said row vectors being selected from a symmetrical matrix peculiar to each block;

secret keys peculiar to said entity are generated using said plurality of row vectors;

plaintext is encrypted to ciphertext using a common key generated using components contained in said secret keys, said components corresponding to said plurality of blocks of divided specifying information of another entity that is destination of said ciphertext; and

computation formulas for generating said secret keys are as follows,

{right arrow over (s_R,i^(j))}≡

α

_i({right arrow over (h_R,i^(j))}+{right arrow over (γ

_R,i^(j))})(mod λ

(N))

{right arrow over (s_L,i^(j))}≡

β

_i({right arrow over (h_L,i^(j))}+{right arrow over (γ

_L,i^(j))})(mod λ

(N))

Secret keys g^aipbiqcir numbering (T+1)(T+2)/2

where p+q+r=T,

a_i, b_i, and c_i satisfy following relationships

a_i·

α

_i≡

1(mod λ

(N))

b_i·

β

_i≡

1(mod λ

(N))

$\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{i<br><br>}^{\left(j\right)}+c_i=\mathrm{\lambda <br><br>}<br><br>\left(N\right)$

where

vector S_R,i^(j) and vector S_L,i^(j) are two types of secret key corresponding to j'"'"'th divided specifying information for entity i (j=1, 2, . . . , J);

vector h_R,i^(j), vector h_L,i^(j) are key division vector of entity i,

vector h_R,i^(j)+vector h_L,i^(j)=vector h_i^(j);

vector h_i^(j) is a vector obtained by extracting one row from a matrix H^(j), corresponding to j'"'"'th divided specifying information for entity i;

H^(j) is a symmetrical 2^Mj×

2^Mj matrix formed of random numbers;

M_j is size of j'"'"'th divided specifying information for entity i;

J is number of block divisions in specifying information for entity i;

α

_i, β

_i are personal secret random numbers for entity i

where gcd (α

_i, λ

(N))=1,

gcd (β

_i, λ

(N))=1, and

λ

(·

) is Carmichael function;

N is an integer;

γ

i^(j), c_i are personal secret random numbers for entity i

where γ

i⁽¹⁾+γ

i⁽²⁾+ . . . +γ

i^(J)+c_i=λ

(N)

vector γ

_R,i^(j), vector γ

_L,i^(j) are random number division vectors of entity i, vector γ

_R,im^(j)+vector γ

_L,im^(j)=γ

_i^(j) vector 1 for entity m (where vector 1=(1, 1, . . . ,

     1));

g is an integer mutually prime with N;

T is degree of exponent portion; and

wherein computation formulas for generating said secret keys are as follows;

$\begin{array}{c}{K}_{i<br><br><br><br>m}\equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br><br><br>{\left(g^{a_i^p<br><br>b_i^q<br><br>c_i^r}\right)}^{S_{R,\mathrm{im}}^p<br><br>S_{L,\mathrm{im}}^q<br><br>\frac{T!}{p!<br><br>q!<br><br>r!}}\\ \equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br>g^{\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r}\\ \equiv <br><br><br><br>g<br><br>\underset{p+q+r=T}{\sum <br><br>}<br><br><br><br>\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r\\ \equiv <br><br><br><br>{g<br><br>\left(X_{R,\mathrm{im}}+X_{L,\mathrm{im}}+c_i\right)}^T\\ \equiv <br><br><br><br>g<br><br>{\left\{\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>\left(h_{R,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{R,{\mathrm{im}}_j^{\left(j\right)}}+h_{L,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{L,{\mathrm{im}}_j^{\left(j\right)}}\right)+c_i\right\}}^T\\ \equiv <br><br><br><br>{g<br><br>\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}+\mathrm{\lambda <br><br>}<br><br>\left(N\right)\right)}^T\\ \equiv <br><br><br><br>{g<br><br>\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}\right)}^T\\ \equiv <br><br><br><br>K_{m<br><br><br><br>i}<br><br>\left(\mathrm{mod}<br><br><br><br>N\right)\end{array}$

where

S_R,im is a sum on the integer ring of components S_R,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_R,i^(j) for entity i;

this sum is expressed as given below;

S_L,im is a sum on the integer ling of components S_L,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_L,i^(j) for entity I;

this sum is expressed as given below; and

K_im is a common key generated by one entity i for another entity m, and wherein,

$\begin{array}{c}{S}_{R,i<br><br><br><br>m}=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{R,i<br><br><br><br>m_j^{\left(j\right)}}\\ ={\mathrm{\alpha <br><br>}}_i<br><br>X_{R,i<br><br><br><br>m}\end{array}$

where . . .

$\hspace{1em}<br><br>\begin{array}{c}{X}_{R,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{R,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{R,i}<br><br>m_j^{\left(j\right)}\\ S_{L,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{L,i}<br><br>m_j^{\left(j\right)}\\ =<br><br>{\mathrm{\beta <br><br>}}_i<br><br>X_{L,i}<br><br>m\end{array}$

where . . .

$X_{L,i}<br><br>m=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{L,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{L,i}<br><br>m_j^{\left(j\right)}$

6. An encryption method wherein:

specifying information of an entity is divided into a plurality of blocks of divided specifying information, a plurality of row vectors corresponding to said plurality of blocks of divided specifying information are prepared, with each of said row vectors being selected from a symmetrical matrix peculiar to each block;

secret keys peculiar to said entity are generated using said plurality of row vectors;

plaintext is encrypted to ciphertext using a common key generated using components contained in said secret keys, said components corresponding to said plurality of blocks of divided specifying information of another entity that is destination of said ciphertext; and

computation formulas for generating said secret keys are as follows,

{right arrow over (s_R,i^(j))}≡

α

_i({right arrow over (h_R,i^(j))}+{right arrow over (γ

_R,i^(j))})(mod λ

(N))

{right arrow over (s_L,i^(j))}≡

β

_i({right arrow over (h_L,i^(j))}+{right arrow over (γ

_L,i^(j))})(mod λ

(N))

Secret keys g^aipbiqcir numbering (T+1)(T+2)/2

where p+q+r=T

a_i, b_i, and c_i satisfy following relationships

a_i·

α

_i≡

1(mod λ

(N))

b_i·

β

_i≡

1(mod λ

(N))

$\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{i<br><br>}^{\left(j\right)}+c_i=\mathrm{\lambda <br><br>}<br><br>\left(N\right)$

where

vector S_R,i^(j) and vector S_L,i^(j) are two types of secret key corresponding to j'"'"'th divided specifying information for entity i (j=1, 2, . . . , J);

vector h_R,i^(j), vector h_L,i^(j) are key division vector of entity i,

vector h_R,i^(j)+vector h_L,i^(j)=vector h_i^(j);

vector h_i^(j) is a vector obtained by extracting one row from a matrix H^(j), corresponding to j'"'"'th divided specifying information for entity i;

H^(j) is a symmetrical 2^Mj×

2^Mj matrix formed of random numbers;

M_j is size of j'"'"'th divided specifying information for entity i;

J is number of block divisions in specifying information for entity i;

α

_i, β

_i are personal secret random numbers for entity i

where gcd (α

_i, λ

(N))=1, gcd (β

_i, λ

(N))=1, and

λ

(·

) is Carmichael function;

N is an integer;

γ

i^(j), c_i are personal secret random numbers for entity i where γ

i⁽¹⁾+γ

i⁽²⁾+ . . . +γ

i^(J)+c_i=λ

(N)

vector γ

_R,i^(j), vector γ

_L,i^(j) are random number division vectors of entity i, vector γ

_R,im^(j)+vector γ

_L,im^(j)=γ

_i^(j) vector 1 for entity m (where vector 1=(1, 1, . . . ,

     1));

g is an integer mutually prime with N;

T is degree of exponent portion;

wherein either said N is such that N=PQ (where P and Q are prime), or said N is prime, and said g is a maximum generating element having modulo N; and

wherein computation formulas for generating said secret keys are as follows;

$\begin{array}{c}{K}_{i<br><br><br><br>m}\equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br><br><br>{\left(g^{a_i^p<br><br>b_i^q<br><br>c_i^r}\right)}^{S_{R,\mathrm{im}}^p<br><br>S_{L,\mathrm{im}}^q<br><br>\frac{T!}{p!<br><br>q!<br><br>r!}}\\ \equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br>g^{\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r}\\ \equiv <br><br><br><br>g<br><br>\underset{p+q+r=T}{\sum <br><br>}<br><br><br><br>\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r\\ \equiv <br><br><br><br>{g<br><br>\left(X_{R,\mathrm{im}}+X_{L,\mathrm{im}}+c_i\right)}^T\\ \equiv <br><br><br><br>g<br><br>{\left\{\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>\left(h_{R,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{R,{\mathrm{im}}_j^{\left(j\right)}}+h_{L,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{L,{\mathrm{im}}_j^{\left(j\right)}}\right)+c_i\right\}}^T\\ \equiv <br><br><br><br>{g<br><br>\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}+\mathrm{\lambda <br><br>}<br><br>\left(N\right)\right)}^T\\ \equiv <br><br><br><br>{g<br><br>\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}\right)}^T\\ \equiv <br><br><br><br>K_{m<br><br><br><br>i}<br><br>\left(\mathrm{mod}<br><br><br><br>N\right)\end{array}$

where S_R,im is a sum on the integer ring of components S_R,im^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_R,i^(j) for entity i, expressed as given below;

S_L,im is a sum on the integer ring of components S_L,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_L,i^(j) for entity i, expressed as given below; and

K_im is a common key generated by one entity i for another entity m, and wherein

$\begin{array}{c}{S}_{R,i<br><br><br><br>m}=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{R,i<br><br><br><br>m_j^{\left(j\right)}}\\ ={\mathrm{\alpha <br><br>}}_i<br><br>X_{R,i<br><br><br><br>m}\end{array}$

where . . .

$\hspace{1em}<br><br>\begin{array}{c}{X}_{R,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{R,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{R,i}<br><br>m_j^{\left(j\right)}\\ S_{L,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{L,i}<br><br>m_j^{\left(j\right)}\\ =<br><br>{\mathrm{\beta <br><br>}}_i<br><br>X_{L,i}<br><br>m\end{array}$

where . . .

$X_{L,i}<br><br>m=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{L,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{L,i}<br><br>m_j^{\left(j\right)}$

7. A cryptographic communications method wherein:

specifying information of one entity is divided into a first plurality of blocks of divided specifying information, a first plurality of row vectors are provided for the first plurality of blocks of divided specifying information respectively, each of said row vectors being selected from a symmetrical matrix peculiar to each block;

specifying information of another entity is divided into a second plurality of blocks of divided specifying information, a second plurality of row vectors are provided for the second plurality of blocks of divided specifying information respectively, each of said row vectors being selected from a symmetrical matrix peculiar to each block;

a plurality of centers are deployed such that said plurality of centers generate first secret keys for said first plurality of row vectors respectively using said first plurality of row vectors, the first secret keys being peculiar to said one entity, and send the first secret keys to said one entity, and generate second secret keys for said second plurality of row vectors respectively using said second plurality of row vectors, the second secret keys being peculiar to said another entity, and send the second secret keys to said another entity;

said one entity encrypts plaintext to ciphertext using a first common key divided from the first secret keys, said first common key being generated using components contained in the first secret keys, said components corresponding to said second plurality of blocks of divided specifying information, and sends the ciphertext to said another entity;

said another entity decrypts said ciphertext so sent using a second common key identical to said first common key, said second common key being derived from the second secret keys, said second common key being generated using components contained in said second secret keys, said components corresponding to said first plurality of divided specifying information of said one entity; and

computation formulas for generating said first and second secret keys are as follows;

{right arrow over (s_R,i^(j))}≡

α

_i({right arrow over (h_R,i^(j))}+{right arrow over (γ

_R,i^(j))})(mod λ

(N))

{right arrow over (s_L,i^(j))}≡

β

_i({right arrow over (h_L,i^(j))}+{right arrow over (γ

_L,i^(j))})(mod λ

(N))

Secret keys g^aipbiqcir numbering (T+1)(T+2)/2

where p+q+r=T,

a_i, b_i, and c_i satisfy following relationships

a_i·

α

_i≡

1(mod λ

(N))

b_i·

β

_i≡

1(mod λ

(N))

$\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{i<br><br>}^{\left(j\right)}+c_i=\mathrm{\lambda <br><br>}<br><br>\left(N\right)$

where

vector S_R,i^(j) and vector S_L,i^(j) are two types of secret key corresponding to j'"'"'th divided specifying information for entity i G=2, 3, . . . , J);

vector h_R,i^(j), vector h_L,i^(j) are key division vector of entity i, vector h_R,i^(j)+vector h_L,i^(j)=vector h_i^(j);

vector h_i^(j) is a vector obtained by extracting one row from a matrix H^(j) corresponding to j'"'"'th divided specifying information for entity i;

H^(j) is a symmetrical 2^Mj×

2^Mj matrix formed of random numbers;

M_j is size of j'"'"'th divided specifying information for entity i;

J is number of block divisions in specifying information for entity i;

α

_i, β

_i are personal secret random numbers for entity i

where gcd (α

_i, λ

(N))=1,

gcd (β

_i, λ

(N))=1, and

λ

(·

) is Carmichael function;

N is an integer;

γ

i^(j), c_i are personal secret random numbers for entity i

where γ

i⁽¹⁾+γ

i⁽²⁾+ . . . +γ

i^(J)+c_i=λ

(N)

vector γ

_R,i^(j), vector γ

_L,i^(j) are random number division vectors of entity i, vector γ

_R,im^(j)+vector γ

_L,im^(j)=γ

_i^(j) vector 1 for entity m (where vector 1=(1, 1, . . . ,

     1);

g is an integer mutually prime with N;

T is degree of exponent portion; and

wherein computation formulas for generating said secret keys peculiar to entities are as follows;

$\begin{array}{c}{K}_{i<br><br><br><br>m}\equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br><br><br>{\left(g^{a_i^p<br><br>b_i^q<br><br>c_i^r}\right)}^{S_{R,\mathrm{im}}^p<br><br>S_{L,\mathrm{im}}^q<br><br>\frac{T!}{p!<br><br>q!<br><br>r!}}\\ \equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br>g^{\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r}\\ \equiv <br><br><br><br>g<br><br>\underset{p+q+r=T}{\sum <br><br>}<br><br><br><br>\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r\\ \equiv <br><br><br><br>{g<br><br>\left(X_{R,\mathrm{im}}+X_{L,\mathrm{im}}+c_i\right)}^T\\ \equiv <br><br><br><br>g<br><br>{\left\{\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>\left(h_{R,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{R,{\mathrm{im}}_j^{\left(j\right)}}+h_{L,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{L,{\mathrm{im}}_j^{\left(j\right)}}\right)+c_i\right\}}^T\\ \equiv <br><br><br><br>{g<br><br>\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}+\mathrm{\lambda <br><br>}<br><br>\left(N\right)\right)}^T\\ \equiv <br><br><br><br>{g<br><br>\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}\right)}^T\\ \equiv <br><br><br><br>K_{m<br><br><br><br>i}<br><br>\left(\mathrm{mod}<br><br><br><br>N\right)\end{array}$

where

S_R,im is a sum on the integer ring of components S_R,imj^(j) corresponding to the divided specifying information for entity

m, extracted from the secret key vector S_R,i^(j) for entity i, expressed as given below;

S_L,im is a sum on the integer ring of components S_L,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_L,i^(j) for entity i, expressed as given below; and

K_im is a common key generated by one entity i for another entity m, and wherein

$\begin{array}{c}{S}_{R,i<br><br><br><br>m}=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{R,i<br><br><br><br>m_j^{\left(j\right)}}\\ ={\mathrm{\alpha <br><br>}}_i<br><br>X_{R,i<br><br><br><br>m}\end{array}$

where . . .

$\hspace{1em}<br><br>\begin{array}{c}{X}_{R,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{R,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{R,i}<br><br>m_j^{\left(j\right)}\\ S_{L,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{L,i}<br><br>m_j^{\left(j\right)}\\ =<br><br>{\mathrm{\beta <br><br>}}_i<br><br>X_{L,i}<br><br>m\end{array}$

where . . .

$X_{L,i}<br><br>m=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{L,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{L,i}<br><br>m_j^{\left(j\right)}$

8. A cryptographic communications method wherein:

specifying information of one entity is divided into a first plurality of blocks of divided specifying information, a first plurality of row vectors are provided for the first plurality of blocks of divided specifying information respectively, each of said row vectors being selected from a symmetrical matrix peculiar to each block;

specifying information of another entity is divided into a second plurality of blocks of divided specifying information, a second plurality of row vectors are provided for the second plurality of blocks of divided specifying information respectively, each of said row vectors being selected from a symmetrical matrix peculiar to each block;

a plurality of centers are deployed such that said plurality of centers generate first secret keys for said first plurality of row vectors respectively using said first plurality of row vectors, the first secret keys being peculiar to said one entity, and send the first secret keys to said one entity, and generate second secret keys for said second plurality of row vectors respectively using said second plurality of row vectors, the second secret keys being peculiar to said another entity, and send the second secret keys to said another entity;

said one entity encrypts plaintext to ciphertext using a first common key divided from the first secret keys, said first common key being generated using components contained in the first secret keys, said components corresponding to said second plurality of blocks of divided specifying information, and sends the ciphertext to said another entity;

said another entity decrypts said ciphertext so sent using a second common key identical to said first common key, said second common key being derived from the second secret keys, said second common key being generated using components contained in said second secret keys, said components corresponding to said first plurality of divided specifying information of said one entity; and

computation formulas for generating said first and second secret keys are as follows;

{right arrow over (s_R,i^(j))}≡

α

_i({right arrow over (h_R,i^(j))}+{right arrow over (γ

_R,i^(j))})(mod λ

(N))

{right arrow over (s_L,i^(j))}≡

β

_i({right arrow over (h_L,i^(j))}+{right arrow over (γ

_L,i^(j))})(mod λ

(N))

Secret keys g^aipbiqcir numbering (T+1)(T+2)/2

where p+q+r=T,

a_i, b_i, and c_i satisfy following relationships

a_i·

α

_i≡

1(mod λ

(N))

b_i·

α

_i≡

1(mod λ

(N))

$\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{i<br><br>}^{\left(j\right)}+c_i=\mathrm{\lambda <br><br>}<br><br>\left(N\right)$

where

vector S_R,i^(j) and vector S_L,i^(j) are two types of secret key corresponding to j'"'"'th divided specifying information for entity i G=2, 3, . . . , J);

vector h_R,i^(j), vector h_L,i^(j) are key division vector of entity i, vector h_R,i^(j)+vector h_L,i^(j)=vector h_i^(j);

vector h_i^(j) is a vector obtained by extracting one row from a matrix H^(j) corresponding to j'"'"'th divided specifying information for entity i;

H^(j) is a symmetrical 2^Mj×

2^Mj matrix formed of random numbers;

M_j is size of j'"'"'th divided specifying information for entity i;

J is number of block divisions in specifying information for entity i;

α

_i, β

_i are personal secret random numbers for entity i

where gcd (α

_i, λ

(N))=1,

gcd (β

_i, λ

(N))=1, and

λ

(·

) is Carmichael function;

N is an integer;

γ

i^(j), c_i are personal secret random numbers for entity i

where γ

i⁽¹⁾+γ

i⁽²⁾+ . . . +γ

i^(J)+c_i=λ

(N)

vector γ

_R,i^(j), vector γ

_L,i^(j) are random number division vectors of entity i, vector γ

_R,im^(j)+vector γ

_L,im^(j)=γ

_i^(j) vector 1 for entity m (where vector 1=(1, 1, . . . ,

     1);

g is an integer mutually prime with N;

T is degree of exponent portion;

wherein either said N is such that N=PQ (where P and Q are prime), or said N is prime, and said g is a maximum generating element having modulo N; and

wherein computation formulas for generating said secret keys peculiar to entities are as follows;

$\begin{array}{c}{K}_{i<br><br><br><br>m}\equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br><br><br>{\left(g^{a_i^p<br><br>b_i^q<br><br>c_i^r}\right)}^{S_{R,\mathrm{im}}^p<br><br>S_{L,\mathrm{im}}^q<br><br>\frac{T!}{p!<br><br>q!<br><br>r!}}\\ \equiv <br><br><br><br>\underset{p+q+r=T}{\prod <br><br>}<br><br>g^{\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r}\\ \equiv <br><br><br><br>g<br><br>\underset{p+q+r=T}{\sum <br><br>}<br><br><br><br>\frac{T!}{p!<br><br>q!<br><br>r!}<br><br>X_{R,\mathrm{im}}^p<br><br>X_{L,\mathrm{im}}^q<br><br>c_i^r\\ \equiv <br><br><br><br>{g<br><br>\left(X_{R,\mathrm{im}}+X_{L,\mathrm{im}}+c_i\right)}^T\\ \equiv <br><br><br><br>g<br><br>{\left\{\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>\left(h_{R,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{R,{\mathrm{im}}_j^{\left(j\right)}}+h_{L,{\mathrm{im}}_j^{\left(j\right)}}+{\mathrm{\gamma <br><br>}}_{L,{\mathrm{im}}_j^{\left(j\right)}}\right)+c_i\right\}}^T\\ \equiv <br><br><br><br>{g<br><br>\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}+\mathrm{\lambda <br><br>}<br><br>\left(N\right)\right)}^T\\ \equiv <br><br><br><br>{g<br><br>\left(\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{i_j<br><br>m_j^{\left(j\right)}}\right)}^T\\ \equiv <br><br><br><br>K_{m<br><br><br><br>i}<br><br>\left(\mathrm{mod}<br><br><br><br>N\right)\end{array}$

where

S_R,im is a sum on the integer ring of components S_R,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_R,i^(j) for entity i, expressed as given below;

S_L,im is a sum on the integer ring of components S_L,imj^(j) corresponding to the divided specifying information for entity m, extracted from the secret key vector S_L,i^(j) for entity i, expressed as given below; and

K_im is a common key generated by one entity i for another entity m,

where

$\hspace{1em}<br><br>\begin{array}{c}{S}_{R,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{R,i}<br><br>m_j^{\left(j\right)}\\ =<br><br>{\mathrm{\alpha <br><br>}}_i<br><br>X_{R,i}<br><br>m\end{array}$

where . . .

$\begin{array}{c}{X}_{R,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{R,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{R,i}<br><br>m_j^{\left(j\right)}\\ S_{L,i}<br><br>m=<br><br>\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>s_{L,i}<br><br>m_j^j\\ =<br><br>{\mathrm{\beta <br><br>}}_i<br><br>X_{L,i}<br><br>m\end{array}$

where . . .

$X_{L,i}<br><br>m=\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>h_{L,i}<br><br>m_j^{\left(j\right)}+\underset{j=1}{\overset{J}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_{L,i}<br><br>m_j^{\left(j\right)}$