Exclusive key sharing method

Abstract

In a set-up phase, the base station formulates the secret key S and holds it in secret. The secret information Si which are obtained by dividing the secret key S are distributed in secret to respective terminals 1 to 5 by using cryptographic communication means. In a preparatory phase, the base station 0 broadcasts the preparatory information C1(=g.sup.k modp), the exclusive information C2(=y5.sup.k modp), the ciphertext C3(=M.times.K modp), and the particular terminal number 5 to all terminals. In a key sharing phase, the terminal 1 calculates a product of C1 (.lambda.(1, .LAMBDA.) modq) modp and C2 (.lambda.(5, .LAMBDA.) modq) modp by using the preparatory information C1 and the exclusive information C2 to obtain K and then calculates M, which are common data to the base station 0, by dividing the ciphertext C3 by K. The terminals 2 to 4 execute similar calculations. As a result, the terminals 1 to 4 can share mutually the common data M.

Claims

What is claimed is:

1. An exclusive key sharing method for a communication system which consists of a base station and N terminals (N is an integer of more than 2) connected to the base station to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, and a number of terminals which can be specified by the base station (referred to as a "particular terminal number" hereinafter) is 1,

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.Si (sum of i.epsilon..LAMBDA. is calculated)

(where Si=S+f1.times.i modq (f1 is a non-zero element of GF(q)), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any two terminals out of the N terminals),

the base station holds (S, p, g, S1, . . . , SN), and

(1) the base station calculates preparatory information

C1=g.sup.k modp

if an element of GF(p) is g and a non-zero element of GF(q) is k,

(2) the base station calculates exclusive information

C2=g (k.times.Sa modq) modp,

based on secret information Sa of a particular terminal a and broadcasts it together with a particular terminal number a and the preparatory information C1 to all terminals,

(3) the base station calculates a common key

K=g (k.times.S modq) modp

which is shared with all terminals j (j.noteq.a) other than the particular terminal a, and

(4) respective terminals j (j.noteq.a) calculate

C1 (Sj.times..lambda.(j, .LAMBDA.) modq).times.C2 (.lambda.(a, .LAMBDA.) modq) modp

which is a product of

C1 (Sj.times..lambda.(j, .LAMBDA.) modq) modp,

which is a power residue value of C1 having a product of Sj and .lambda.(j, .LAMBDA.) to a modulus q as an exponent, and

C2 (.lambda.(a, .LAMBDA.) modq) modp

which is a power residue value of C2 having the .lambda.(a, .LAMBDA.) calculated to the modulus q as an exponent, by using the preparatory information C1, the exclusive information C2, and own secret information Sj to thus obtain the common key K which is common to the base station.

2. An exclusive key sharing system for a communication system which consists of a base station and N terminals (N is an integer of more than 2) connected to the base station to allow broadcast communication,

wherein the base station includes

a first base station side storing portion for holding a modulus p which is a prime number which is larger than a secret key S and the N or a power number of the prime number, an element g of GF(p), and an element k of GF(q) having q as a measure of (p-1),

a second base station side storing portion for holding secret information S1, . . . , SN to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.Si (sum of i.epsilon..LAMBDA. is calculated)

(where Si=S+f1.times.i modq (f1 is a non-zero element of GF(q)), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any two terminals out of the N terminals), and

a third base station side storing portion for holding a secret key S, and

respective terminals i include

a first terminal side storing portion for holding (p, g), and

a second terminal side storing portion for holding the secret information Si in secret, and

(1) the base station also includes a first base station side calculating portion for calculating preparatory information

C1=g.sup.k modp

by using (k, p, q, g) saved in the first base station side storing portion,

(2) the base station also includes

a controlling portion for designating a particular terminal a,

a second base station side calculating portion for outputting secret information Sa saved in the second base station side storing portion under control of the controlling portion and then calculating exclusive information

C2=g (k.times.Sa modq) modp

based on the secret information Sa and the (k, p, q, g), and

a transmitting portion for broadcasting it together with the preparatory information C1 and a particular terminal number a to all terminals,

(3) the base station also includes a third base station side calculating portion for calculating a common key

K=g (k.times.S modq) modp

which is shared with all terminals j (j.noteq.a) other than the particular terminal a by using the (k, p, q) and the secret key S saved in the third base station side storing portion, and

(4) respective terminals j (j.noteq.a) include a terminal side calculating portion for calculating

C1 (Sj.times..lambda.(j, .LAMBDA.) modq).times.C2 (.lambda.(a, .LAMBDA.) modq) modp

which is a product of a power residue value of C1

C1 (Sj.times..lambda.(j, .LAMBDA.) modq) modp

and a power residue value of C2

C2 (.lambda.(a, .LAMBDA.) modq) modp

to thus obtain the common key K which is common to the base station.

3. An exclusive key sharing method for a communication system which consists of a base station and N terminals (N is an integer of more than 2) connected to the base station to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, and a particular terminal number is d (1.ltoreq.d<N-1), and

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.Si (sum of i.epsilon..LAMBDA. is calculated)

(where Si=S+f1.times.i+ . . . +fd.times.i.sup.d modq (f1, . . . , fd are d elements of GF(q), fd.noteq.0), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals),

the base station holds (S, p, g, S1, . . . , SN), and

(1) the base station calculates preparatory information

C1=g.sup.k modp (k is a non-zero element of GF(q)),

(2) the base station calculates exclusive information

C21=g (k.times.Si1 modq) modp, . . . ,

C2d=g (k.times.Sid modq) modp

based on secret information Si1, . . . , Sid of d particular terminals i1, . . . , id, and then broadcasts them together with the preparatory information C1 and particular terminal numbers i1, . . . , id to all terminals,

(3) the base station calculates a common key

K=g (k.times.S modq) modp

which is shared with all terminals j (j.noteq.i1, . . . , id) other than the particular terminals i1, . . . , id, and

(4) respective terminals j (j.noteq.i1, . . . , id) calculate

.lambda.(i, .LAMBDA.), .lambda.(i1, .LAMBDA.), . . . , .lambda.(id, .LAMBDA.)

where .LAMBDA.={j, i1, . . . , id}, and calculate

C1 (Sj.times..lambda.(j, .LAMBDA.) modq).times.C21 (.lambda.(i1, .LAMBDA.) modq).times. . . . .times.C2d (.lambda.(id, .LAMBDA.) modq) modp

by using the preparatory information C1, the exclusive information C21, . . . , C2d, and own secret information Sj to thus obtain the common key K which is common to the base station.

4. An exclusive key sharing method for a communication system which consists of a base station and N terminals (N is an integer of more than 2) connected to the base station to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, a particular terminal number is d (1.ltoreq.d<N-1), and a number D of terminals specified actually by the base station (referred to as "actual particular terminal number" hereinafter) in sharing a key is set to a number which is smaller than the particular terminal number d but more than 1, and

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.Si (sum of i.epsilon..LAMBDA. is calculated)

(where Si=S+f1.times.i+ . . . +fd.times.i.sup.d modq (f1, . . . , fd are d elements of GF(q), fd.noteq.0), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and

the base station holds secret information SN+1, . . . , SN+d-1 which are divided by calculating

SN+1=S+f1.times.(N+1)+ . . . +fd.times.(N+1).sup.d modq, . . . ,

SN+d-1=S+f1.times.(N+d-1)+ . . . +fd.times.(N+d-1).sup.d modq,

secret information S1, . . . , SN, the secret key S, the modulus p, and the element g of GF(p), and then

(1) the base station calculates preparatory information

C1=g.sup.k modp (k is a non-zero element of GF(q)),

(2) the base station calculates exclusive information

C21=g (k.times.Si1 modq) modp, . . . ,

C2D=g (k.times.SiD modq) modp,

C2b1=g (k.times.Sb1 modq) modp, . . . ,

C2bv=g (k.times.Sbv modq) modp,

based on secret information Si1, . . . , SiD of D particular terminals i1, . . . , iD and any v (=d-D) secret information Sb1, . . . , Sbv out of the secret information SN+1, . . . , SN+d-1, and then broadcasts the exclusive information C21, . . . , C2D, and C2b1, . . . , C2bv, the preparatory information C1, particular terminal numbers i1, . . . , iD, and numbers b1, . . . , bv of the secret information Sb1, . . . , Sbv to all terminals,

(3) the base station calculates a common key

K=g (k.times.S modq) modp

which is shared with all terminals j (j.noteq.i1, . . . , iD) other than the particular terminals i1, . . . , iD, and

(4) respective terminals j (j.noteq.i1, . . . , iD) calculate .lambda. (j, .LAMBDA.), .lambda.(i1, .LAMBDA.), . . . , .lambda.(iD, .LAMBDA.), .lambda.(ib1, .LAMBDA.), . . . , .lambda.(ibv, .LAMBDA.) where .LAMBDA.={j, i1, . . . , iD, b1, . . . , bv}, and calculate a product

C1 (Sj.times..lambda.(j, .LAMBDA.) modq).times.C21 (.lambda.(i1, .LAMBDA.) modq).times. . . . .times.C2D (.lambda.(iD, .LAMBDA.) modq).times.Cb1 (.lambda.(b1, .LAMBDA.) modq).times. . . . .times.Cbv (.lambda.(bv, .LAMBDA.) modq) modp

of a power residue value C1 (Sj.times..lambda.(j, .LAMBDA.) modq) and a power residue value

C21 (.lambda.(i1, .LAMBDA.) modq).times. . . . .times.C2D (.lambda.(iD, .LAMBDA.) modq).times.Cb1 (.lambda.(b1, .LAMBDA.) modq).times. . . . .times.Cbv (.lambda.(bv, .LAMBDA.) modq) modp

by using the preparatory information C1, the exclusive information C21, . . . , C2D, C2b1, . . . , C2bv, and own secret information Sj to thus obtain the common key K which is common to the base station.

5. An exclusive key sharing method according to claim 3, wherein the base station holds e sets of secret information which are obtained by dividing the secret key S into any e particular terminals d1, . . . , de (e is an integer) respectively,

the respective terminals hold e pieces of secret information out of respective sets which correspond to own terminal number, and

when key sharing is carried out to exclude the particular terminals, the base station and the respective terminals j select a particular terminal number dw (1.ltoreq.w.ltoreq.e) which is equal to the actual particular terminal number D from the particular terminals d1, . . . , de, and then the base station broadcasts the preparatory information and the exclusive information by using a set of secret information corresponding to the selected particular terminal number dw to obtain a common key K shared with the terminals, while the respective terminals j obtain the common key K shared with the base station by using the secret information corresponding to the particular terminal number dw.

6. An exclusive key sharing method according to claim 1, wherein the secret key S is set as a secret key for all terminals, and a power residue value of the g

y=g.sup.S modp

which has S as the exponent and p as the modulus is set as a public key for all terminals, and

the base station holds divided secret information S1, S2, . . . , SN of all terminals in secret, and

(1) the base station generates arbitrarily an integer k, and calculates preparatory information

C1=g.sup.k modp (k is a non-zero element of GF(q))

as a power residue value of the element g which has k as the exponent and p as the modulus

(2) the base station calculates a product of the secret information Sa of the particular terminal a and the k, and then calculates exclusive information

C2=g (k.times.Sa modq) modp

which has this information as the exponent, p as the modulus, and g as a base,

(3) the base station calculates a common key

K=y.sup.k modp

as a power residue value of the public key y for all terminals which has k as the exponent and p as the modulus and simultaneously generates arbitrarily common data M to the respective terminals j (j.noteq.a), then calculates a product of M and the common key K to the modulus p (referred to as a "ciphertext" hereinafter)

C3=M.times.K modp,

and then broadcasts this ciphertext together with the preparatory information C1 and the particular terminal number a to all terminals,

(4) the respective terminals j (j.noteq.a) calculate .lambda.(j, .LAMBDA.) and .lambda.(a, .LAMBDA.) where .LAMBDA.={j,a}, then calculate a product

K=C1 (Sj.times..lambda.(j, .LAMBDA.) modq).times.C2 (.lambda.(a, .LAMBDA.) modq) modp

of a power residue value

C1 (Sj.times..lambda.(j, .LAMBDA.) modq) modp

which has a product of Sj and .lambda.(j, .LAMBDA.) to the modulus q as an exponent and the C1 as the base and a power residue value

C2 (.lambda.(a, .LAMBDA.) modq) modp

which has .lambda.(a, .LAMBDA.) to the modulus q as the exponent and the C2 as the base by using the preparatory information C1, the exclusive information C2, and own secret information Sj, and then calculate a value which is obtained by dividing the ciphertext C3 by K to the modulus p

C3/K modp=M.times.K/K modp

as the common data M to the base station.

7. An exclusive key sharing method according to claim 1, wherein a power residue value of the g

y=g.sup.s modp

which has a secret key S for all terminals as an exponent and p as the modulus is set as a public key for all terminals, and

the base station can use public information

y1=g.sup.S1 modp, y2=g.sup.S2 modp, . . . , yN=g.sup.SN modp

as power residue values of g which have divided secret information S1, S2, . . . , SN of all terminals as the exponent respectively and p as the modulus, and

(1) the base station generates arbitrarily an integer k and then calculates preparatory information

C1=g.sup.k modp (k is a non-zero element of GF(q))

as a power residue value of g which has k as the exponent and p as the modulus

(2) the base station calculates exclusive information

C2=ya.sup.k modp

as a power residue value of the public information ya of the particular terminal a which has k as the exponent and p as the modulus,

(3) the base station calculates a common key

K=y.sup.k modp=g (S.times.k) modp

as a power residue value of the public key y for all terminals which has k as the exponent and p as the modulus, and simultaneously generates arbitrarily common data M to the respective terminals j (j.noteq.a), then calculates a ciphertext

C3=M.times.K modp,

as a product of M and the K to the modulus p, and then broadcasts this ciphertext together with the preparatory information C1 and the particular terminal number a to all terminals,

(4) the respective terminals j (j.noteq.a) calculate .lambda.(j, .LAMBDA.) and .lambda.(a, .LAMBDA.) where .LAMBDA.={j,a}, then calculate a product

K=C1 (Sj.times..lambda.(j, .LAMBDA.) modq).times.C2 (.lambda.(a, .LAMBDA.) modq) modp

of a power residue value of C1

C1 (Sj.times..lambda.(j, .LAMBDA.) modq) modp

which has a product of Sj and .lambda.(j, .LAMBDA.) to the modulus q as an exponent and a power residue value of C2

C2 (.lambda.(a, .LAMBDA.) modq) modp

which has .lambda.(a, .LAMBDA.) to the modulus q as the exponent by using the preparatory information C1, the exclusive information C2, and own secret information Sj, and then calculate a value which is obtained by dividing the ciphertext C3 by K to the modulus p

C3/K=M.times.K/K modp

as the common data M to the base station.

8. An exclusive key sharing method according to claim 1, wherein the secret key S is set as a secret key for the base station, and a power residue value of the g

y=g.sup.S modp

which has the S as an exponent and p as the modulus is set as a public key for the base station (this public key is not opened for terminals), and

the respective terminals hold one of divided secret information S1, S2, . . . , SN of the secret key S of the base station in secret,

the base station can use public information

y1=g.sup.S1 modp, y2=g.sup.S2 modp, . . . , yN=g.sup.SN modp

as power residue values of g which have divided secret information S1, S2, . . . , SN of all terminals as the exponent respectively and p as the modulus, and

(1) the base station

(1-a) generates arbitrarily an integer k, and calculates a power residue value of g

C0=g (-k modq) modp

which has (-k) calculated to the modulus q as the exponent and the p as the modulus,

(1-b) generates common data M to all terminals j (j.noteq.a) other than the particular terminal a, and then calculates a product of the M and the C0 to the modulus p

r=M.times.C0 modp,

(1-c) calculates a residue obtained by dividing the r by the q

r'=r modq,

(1-d) calculates a value s to satisfy

k=s-r'.times.S modq

by using R', k, the secret key S of the base station,

(1-e) calculates preparatory information

C1=g (-r modq) modp

as a power residue value of g which has (-r) calculated to the modulus q as the exponent and p as the modulus,

(1-f) calculates exclusive information

C2=ya (-r modq) modp

as a power residue value of ya which has (-r) calculated to the modulus q as the exponent and p as the modulus by using a public information ya of the particular terminal a, and

(1-g) broadcasts (r,s) together with C1, C2 to all terminals as a signature of M,

(2) the respective terminals j (j.noteq.a) calculate .lambda.(j, .LAMBDA.) and .lambda.(a, .LAMBDA.) where .LAMBDA.={j,a}, then calculate a product

K=C1 (Sj.times..lambda.(j, .LAMBDA.) modq).times.C2 (.lambda.(a, .LAMBDA.) modq) modp

of a power residue value of C1

C1 (Sj.times..lambda.(j, .LAMBDA.) modq) modp

which has a product of Sj and .lambda.(j, .LAMBDA.) to the modulus q as an exponent and a power residue value of C2

C2 (.lambda.(a, .LAMBDA.) modq) modp

which has .lambda.(a, .LAMBDA.) to the modulus q as the exponent by using the preparatory information C1, the exclusive information C2, and own secret information Sj, and then calculate a product of a power residue value of g having s as the exponent, r, and K to the modulus p

r.times.g.sup.s.times.K modp

to obtain the common data M.

9. An exclusive key sharing method according to claim 1, wherein a power residue value of the g

y=g.sup.S modp

which has a secret key S for all terminals as an exponent and p as the modulus is set as a public key for all terminals, and

the base station can use public information

y1=g.sup.S1 modp, y2=g.sup.S2 modp, . . . , yN=g.sup.SN modp

as power residue values of g which have divided secret information S1, S2, . . . , SN of all terminals as the exponent respectively and p as the modulus, and

(1) the base station generates arbitrarily an integer k and then calculates preparatory information

C1=g.sup.k modp (k is a non-zero element of GF(q))

as a power residue value of the g which has k as the exponent and p as the modulus,

(2) the base station calculates exclusive information

C2=ya.sup.k modp

as a power residue value of the public information ya of the particular terminal a which has k as the exponent and p as the modulus,

(3) the base station calculates a power residue value of the public key y for all terminals, which has k as the exponent and p as the modulus, as a common key

K=y.sup.k modp

to all terminals j (j.noteq.a) other than the particular terminal a,

(4) the respective terminals j calculate a product of a power residue value of C1, which has a product of Sj and .lambda.(j, .LAMBDA.) to the modulus q as an exponent, and a power residue value of C2, which has .lambda.(a, .LAMBDA.) calculated to the modulus q as the exponent

C1 (Sj.times..lambda.(j, .LAMBDA.) modq).times.C2 (.lambda.(a, .LAMBDA.) modq) modp,

by using the preparatory information C1, the exclusive information C2, and own secret information Sj to thus obtain the common key K to the base station.

10. An exclusive key sharing method according to claim 1, wherein the respective terminals hold secret information S1, . . . , SN in secret, and a set of any t terminals (t is more than 2) out of the N terminals is assumed as .LAMBDA., and

(1) the base station calculates preparatory information

C1=g.sup.k modp

which has an integer k as the exponent, p as the modulus, and g as a base,

(2) the base station calculates shared information Xij which satisfy a following expression for any ij (j=1, . . . , t) of t particular terminals i1, . . . , it,

Xij=.PI.(g (Su.times.k))modp (product of u.epsilon..LAMBDA.-{ij} is calculated)

and then broadcasts all shared information Xij and the preparatory information C1 to all terminals,

(3) the base station calculates K which satisfies a following expression by using secret information Si1, . . . , Sit of the particular terminals

K=g.sup.x modp

x=k.times..SIGMA.Sij modq (sum of j=1 to t is calculated)

and then sets it as a common key K to the t particular terminals, and

(4) the particular terminals ij calculate a product of Xij and a power residue value of C1

Xij.times.C1.sup.Sij modp,

which has p as the modulus and own secret information Sij as the exponent, to the modulus p to thus obtain the common key K to the base station.

11. An exclusive key sharing method according to claim 1, wherein the base station executes division of the secret key S and then distributes divided the secret keys to corresponding terminals via cipher communicating means which are provided previously between the base station and the terminals.

12. An exclusive key sharing method according to claim 9, wherein a third party which is different from the base station executes division of the secret key S, calculation and publication of a power residue value and public information y1, y2, . . . , yN, and allocation of corresponding Sa to the terminal a.

13. An exclusive key sharing method according to claim 1, wherein the respective terminals i (1.ltoreq.i.ltoreq.N) hold the secret information Si in secret, the respective terminals i can use power residue values of g which has integers f0(=S), f1, . . . , fd as the exponent respectively and p as the modulus (referred to as "verification information" hereinafter) g.sup.f0, g.sup.f1, . . . , g.sup.fd, and the respective terminals a execute following calculation

g.sup.Si =.PI.(g (fj.times.a.sup.j)) modp (product of j=0 to d is calculated)

by using the verification information and own secret information Si, and then check validity of own secret information Si by deciding whether or not both sides are equal to each other.

14. An exclusive key sharing method according to claim 1, wherein new terminal numbers I (I>N) are set to terminals which newly enter into the communication system which can execute the broadcast communication, and then secret information SI which are obtained by calculating

SI=S+f1.times.I

are held in new terminal in secret.

15. An exclusive key sharing method according to claim 1, wherein the terminal i saves in secret a power residue of C1 (=C1.sup.Si modp) which has p in place of the secret information Si as the modulus and Si as the exponent.

16. An exclusive key sharing method according to claim 1, wherein the base station calculates .lambda.(j, .LAMBDA.) for all .LAMBDA.'s including the particular terminals, then calculates a power residue value of the exclusive information C2

C2 (.lambda.(i, .LAMBDA.) modq) modp

which has .lambda.(i, .LAMBDA.) calculated to the modulus q as the exponent and p as the modulus, then broadcasts it in sharing the key, and

all terminals j (j.noteq.a) except the particular terminal a obtain the common key K by using the power residue value

C2 (.lambda.(i, .LAMBDA.) modq) modp

in response to the .LAMBDA.'s including the j.

17. An exclusive key sharing method according to claim 1, wherein all terminals j (j.noteq.a) except the base station and the particular terminal a generate a new common key K2 based on the shared common key K and the common key K1 shared at a time of previous key sharing.

18. An exclusive key sharing method according to claim 1, wherein a digital signature of the base station is added to data which are distributed from the base station by a digital signature means provided previously to the base station and the terminals.

19. An exclusive key sharing method according to claim 2, wherein areas of the first, second, and third base station side storing portions of the base station and the first and second terminal side storing portions of the terminals are not observed and modified from an outside.

20. An exclusive key sharing method according to claims 1 or 10, wherein it can be selected automatically that the exclusive key sharing method set forth in claim 1 is applied if a scale of constituting groups exceeds half of all terminals and the exclusive key sharing method set forth in claim 10 is applied unless the scale of constituting groups exceeds half of all terminals.

21. An exclusive key sharing method according to claim 1, wherein a number of secret information held by the terminals is increased and decreased in response to authority of the terminals.

22. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal (to which any terminal can be appointed) is 1,

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.Si (sum of i.epsilon..LAMBDA. is calculated)

(where Si=S+f1.times.i modq (f1 is a non-zero element of GF(q)), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any two terminals out of the N terminals), and

the base station can use a public key for all terminals

y=g.sup.S modp,

and public information

y1=g.sup.S1 modp, y2=g.sup.S2 modp, . . . , yN=g.sup.SN modp,

and

(1) the chairman terminal generates arbitrarily a non-zero element k of GF(q) and then calculates preparatory information

C1=g.sup.k modp,

(2) the chairman terminal calculates exclusive information

C2=ya.sup.k modp

based on the public information ya of the particular terminal a, and broadcasts this exclusive information together with the particular terminal number a and the preparatory information C1 to all terminals,

(3) the chairman terminal calculates a common key

K=y.sup.k modp,

(4) the respective terminals j (j.noteq.a) calculate .lambda.(j, .LAMBDA.) and .lambda.(a, .LAMBDA.) where .LAMBDA.={j,a}, and calculate

C1 (Sj.times..lambda.(j, .LAMBDA.) modq).times.C2 (.lambda.(a, .LAMBDA.) modq) modp

by using the preparatory information C1, the exclusive information C2, and own secret information Sj to thus obtain a common key K.

23. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, and elements of GF(p) are g,

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.Si (sum of i.epsilon..LAMBDA. is calculated)

(where Si=S+f1.times.i modq (f1 is a non-zero element of GF(q)), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any two terminals out of the N terminals), and can use a public key for all terminals

y=g.sup.S modp,

public keys for respective terminals

y1=g.sup.S1 modp, y2=g.sup.S2 modp, . . . , yN=g.sup.SN modp,

and

(1) a certain terminal a generates arbitrarily a non-zero element k of GF(q) and then calculates preparatory information

C1=g.sup.k modp,

(2) the certain terminal a calculates exclusive information

C2=ya.sup.k modp

based on own public key ya, and broadcasts this exclusive information together with a terminal number a and the preparatory information C1 to all terminals,

(3) the certain terminal a calculates a common key

K=y.sup.k modp,

(4) the respective terminals j (j.noteq.a) calculate .lambda.(j, .LAMBDA.) and .lambda.(a, .LAMBDA.) where .LAMBDA.={j,a}, and calculate

C1 (Sj.times..lambda.(j, .LAMBDA.) modq).times.C2 (.lambda.(a, .LAMBDA.) modq) modp

by using the preparatory information C1, the exclusive information C2, and own secret information Sj to thus obtain the common key K.

24. An exclusive key sharing method according to claim 22, wherein respective terminals hold all public keys other than own public key.

25. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)}(product of L.epsilon..LAMBDA.-{i} is calculated)

S.sub.i =S+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use a public key of the system

y=g.sup.S modp,

public information

y1=g.sup.S1 modp, y2=g.sup.S2 modp, . . . , yN=g.sup.SN modp,

the prime number p, the measure q and the elements g, and

(1) the chairman terminal generates arbitrarily a non-zero element k of GF(q) and then calculates exclusive information

C2.sub.i1 =y.sub.i1.sup.k modp, . . . , C2.sub.id =y.sub.id.sup.k modp

based on the public information y.sub.i1, . . . , y.sub.id of the d terminals i.sub.1, . . . , i.sub.d,

(2) the chairman terminal calculates a signature

Z=C2.sub.i1.times. . . . .times.C2.sub.id.times.(-S.sub..phi.)+k modq

by using own secret information S.sub..phi., and broadcasts the signature Z together with the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal numbers i.sub.1, . . . , i.sub.d and own terminal number .phi. to all terminals,

(3) the chairman terminal calculates a common key

K=y.sup.k modp,

(4) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate

C1=g.sup.z.times.y.sub..phi. (C2.sub.i1.times. . . . .times.C2.sub.id modq) modp

(if a signer is surely the chairman terminal .phi. and also the signature Z, the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal numbers i.sub.1, . . . , i.sub.d, and the terminal number .phi. of the chairman terminal are not tampered, C1=g.sup.k modp is calculated) by using the public information y.sub..phi. of the chairman terminal,

(5) the respective terminals j calculate .lambda.(j, .LAMBDA.) and .lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.d, .LAMBDA.) where .LAMBDA.={j, i.sub.1, . . . , i.sub.d }, and calculate C1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq).times.C2.sub.i1 (.lambda.(i.sub.1, .LAMBDA.) modq).times. . . . .times.C2.sub.id (.lambda.(i.sub.d, .LAMBDA.) modq) modp by using the C1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and own secret information S.sub.j to thus obtain the common key K.

26. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication, according to claim 25, wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d.ltoreq.N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

S.sub.i =S+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use a public key of the system

y=g.sup.S modp,

public information

y1=g.sup.S1 modp, y2=g.sup.S2 modp, . . . , yN=g.sup.SN modp,

a Hash function hash ( ), the prime number p, the measure q, and the elements g, and

(1) the chairman terminal generates arbitrarily a non-zero element k of GF(q) and then calculates exclusive information

C2.sub.i1 =y.sub.i1.sup.k modp, . . . , C2.sub.id =y.sub.id.sup.k modp

based on the public information y.sub.i1, . . . , y.sub.id of the d terminals i.sub.1, . . . , i.sub.d,

(2) the chairman terminal calculates a hash value

H=hash(C2.sub.i1, . . . , C2.sub.id)

which is obtained by compressing the exclusive information C2.sub.i1, . . . , C2.sub.id by using the Hash function hash( ),

(3) the chairman terminal calculates a signature

Z=H.times.(-S.sub..phi.)+k modq

by using own secret information S.sub..phi., and then broadcasts the signature Z together with the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal numbers i.sub.1, . . . , i.sub.d and own terminal number .phi. to all terminals,

(4) the chairman terminal calculates a common key

K=y.sup.k modp,

(5) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate a hash value H' which is obtained by compressing the exclusive information C2.sub.i1, . . . , C2.sub.id by using the Hash function hash ( ),

(6) the respective terminals j calculate

C1=g.sup.z.times.y.sub..phi..sup.H' modp

(if a signer is surely the chairman terminal .phi. and also the signature Z, the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal numbers i.sub.1, . . . , i.sub.d, and the terminal number .phi. of the chairman terminal are not tampered, C1=g.sup.k modp and H'=H are calculated) by using the public information y.sub..phi. of the chairman terminal,

(7) the respective terminals j calculate .lambda.(j, .LAMBDA.) and .lambda.(i.sub.1, .LAMBDA.). . . .lambda.(i.sub.d, .LAMBDA.) where .LAMBDA.={j, i.sub.1, . . . , i.sub.d }, and calculate C1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq).times.C2.sub.i1 (.lambda.(i.sub.1, .LAMBDA.) modq).times. . . . .times.C2.sub.id (.lambda.(i.sub.d, .LAMBDA.) modq) modp by using the C1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and own secret information S.sub.j to thus obtain the common key K.

27. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication, according to claims 25 or 26, wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1), and a number D of terminals which the chairman terminal actually specifies in sharing a key (referred to as an "actual particular terminal number" hereinafter) is a number which is smaller than the particular terminal number but larger than 1,

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..lambda. is calculated)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

S.sub.1 =S+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use secret information S.sub.N+1, . . . , S.sub.N+d-1 which are divided by calculating

S.sub.N+1 =S+f.sub.1.times.(N+1)+ . . . +f.times.(N+1).sup.d modq, . . . ,

S.sub.N+d-1 =S+f.sub.1.times.(N+d-1).sup.1 + . . . +f.sub.d.times.(N+d-1).sup.d modq,

public information

y.sub.1 =g.sup.S1 modp, . . . , y.sub.N =g.sup.SN modp, . . . ,

y.sub.N+1 =g.sup.SN+1 modp, . . . , y.sub.N+d-1 =g.sup.SN+d-1 modp,

which are calculated by the secret information S.sub.1, . . . , S.sub.N, a public key of the system

y=g.sup.s modp,

the prime number p, the measure q, and the elements g, and

(1) the chairman terminal calculates exclusive information

C2.sub.i1 =y.sub.i1.sup.k modp, . . . , C2.sub.iD =y.sub.iD.sup.k modp,

C2.sub.b1 =y.sub.b1.sup.k modp, . . . , C2.sub.bv =y.sub.bv.sup.k modp

(k is a non-zero element of GF(q))

based on the public information y.sub.i1, . . . , y.sub.iD of the D particular terminals i.sub.1, . . . , i.sub.D, and any v(=d-D) public information y.sub.b1, . . . , y.sub.bv out of the public information y.sub.N+1, . . . , y.sub.N+d-1,

(2) the chairman terminal calculates a signature

Z=C2.sub.i1.times. . . . .times.C2.sub.iD.times.C2.sub.b1.times. . . . .times.C2.sub.bv.times.(-S.sub..phi.)+k modq

by using own secret information S.sub..phi., and then broadcasts the signature Z together with the exclusive information C2.sub.i1, . . . , C2.sub.iD, C2.sub.b1, . . . , C2.sub.bv the particular terminal numbers i.sub.1, . . . , i.sub.D, the terminal numbers b.sub.1, . . . , b.sub.v, and own terminal number .phi. to all terminals,

(3) the chairman terminal calculates a common key

K=y.sup.k modp

which is shared with all terminals j (j.noteq.i.sub.1, . . . , i.sub.D, b.sub.1, . . . , b.sub.v, .phi.) except the particular terminals i.sub.1, . . . , i.sub.D,

(4) the respective terminals j calculate

C1=g.sup.z.times.y.sub..phi. (C2.sub.i1.times. . . . .times.C2.sub.iD.times.C2.sub.b1.times. . . . .times.C2.sub.bv modq) modp

(if a signer is surely the chairman terminal .phi. and also the signature Z, the exclusive information C2.sub.i1, . . . , C2.sub.iD, C2.sub.b1, . . . , C2.sub.bv, the particular terminal numbers i.sub.1, . . . , i.sub.D, the terminal numbers b.sub.1, . . . , b.sub.v corresponding to the public information y.sub.b1, . . . , y.sub.bv, and the terminal number .phi. of the chairman terminal are not tampered, C1=g.sup.k modp is calculated) by using the public information y.sub..phi. of the chairman terminal,

(5) the respective terminals j calculate .lambda.(j, .LAMBDA.), .lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.D, .LAMBDA.), .lambda.(b.sub.1, .LAMBDA.), . . . , .lambda.(b.sub.v, .LAMBDA.) where .LAMBDA.={j, i.sub.1, . . . , i.sub.d, b.sub.1, . . . , b.sub.v }, and calculate a product C1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq).times.C2.sub.i1 (.lambda.(i.sub.1, .LAMBDA.) modq).times. . . . .times.C2.sub.iD (.lambda.(i.sub.D, .LAMBDA.) modq).times.C2.sub.b1 (.lambda.(b.sub.1, .LAMBDA.) modq).times. . . . .times.C2.sub.bv (.lambda.(i, .LAMBDA.) modq) modp of a power residue value C1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq) and a power residue value C2.sub.i1 (.lambda.(i.sub.1, .LAMBDA.) modq).times. . . . .times.C2.sub.iD (.lambda.(i.sub.D, .LAMBDA.) modq).times.C2.sub.b1 (.lambda.b.sub.1, .LAMBDA.) modq).times. . . . .times.C2.sub.bv (.lambda.(i.sub.v, .LAMBDA.) modq) to the modulus p by using the C1, the exclusive information C2.sub.i1, . . . , C2.sub.id, C2.sub.b1, . . . , C2.sub.bv, and own secret information S.sub.j to thus obtain the common key K which is shared with the base station.

28. An exclusive key sharing method according to claims 25 or 26, wherein the chairman terminal can use public information formulated based on .theta. sets of secret information, which are derived by dividing the secret key S to the .theta. particular terminal numbers d.sub.1, . . . , d.sub..theta. (.theta. is any integer) respectively, and the terminal holds .theta. pieces of secret information, which correspond to own terminal number, out of respective sets, and

when key sharing is carried out to exclude the particular terminals, the chairman terminal and the respective terminals j select a particular terminal number d.sub.w (1.ltoreq.w.ltoreq..theta.), which is equal to the actual particular terminal number D, from the particular terminals d.sub.1, . . . , d.sub.0, and then the chairman terminal broadcasts the signature, the exclusive information, the particular terminal number, and the own terminal number, by using a set of public information corresponding to the selected particular terminal number d.sub.w to obtain a common key K which is shared with the terminals, and the terminals j verify the signature and obtain the common key K which is shared with the chairman terminal by using the secret information corresponding to the d.sub.w.

29. An exclusive key sharing method for a communication system which consists of base station and N terminals (N is an integer of more than 2) connected to the base station to allow broadcast communication, according to claims 25 or 26, wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

S.sub.1 =S+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1)terminals out of the N terminals),

the base station .mu. holds all secret information S.sub.i in secret,

the respective terminals i and the base station .mu. can use public information of the base station

y.sub..mu. =g.sup.S.mu. modp,

the prime number p, the measure q, and the elements g, and

(1) the base station generates arbitrarily a non-zero element k of GF(q), and calculates exclusive information

C2.sub.i1 =y.sub.i1.sup.k modp, . . . , C2.sub.id =y.sub.id.sup.k modp

based on the public information y.sub.i1, . . . , y.sub.id of the d particular terminals i.sub.1, . . . , i.sub.d,

(2) the base station calculates a signature

Z=C2.sub.i1.times. . . . .times.C2.sub.id.times.(-S.sub..mu.)+k modq

by using own secret information S.sub..mu., and broadcasts the signature Z together with the exclusive information C2.sub.i1, . . . , C2.sub.id and the particular terminal numbers i.sub.1, . . . , i.sub.d to all terminals,

(3) the base station calculates a common key

K=g (k.times.S modq) modp,

(4) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate

C1=g.sup.z.times.y.sub..mu. (C2.sub.i1.times. . . . .times.C2.sub.id modq) modp

(if a signer is surely the base station .mu. and also the signature Z, the exclusive information C2.sub.i1, . . . , C2.sub.id, and the particular terminal numbers i.sub.1, . . . , i.sub.d are not tampered, C1=g.sup.k modp is calculated) by using the public information y.sub..mu. of the base station,

(5) the respective terminals j calculate .lambda.(j, .LAMBDA.) and .lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.d, .LAMBDA.) where .LAMBDA.={j, i.sub.1, . . . , i.sub.d }, and calculate C1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq).times.C2.sub.i1 (.lambda.(i.sub.1, .LAMBDA.) modq).times. . . . .times.C2.sub.id (.lambda.(i.sub.d, .LAMBDA.) modq) modp by using the C1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and own secret information S.sub.j to thus obtain the common key K.

30. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication, according to claim 25, wherein secret keys are .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma., a prime number which is larger than .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma. and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g1, g2, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma..sub.i in secret to satisfy

.alpha.1=.SIGMA..lambda.(i, .LAMBDA.).times..alpha.1.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .alpha.1.sub.i =.alpha.1+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.alpha.2=.SIGMA..lambda.(i, .LAMBDA.).times..alpha.2.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .alpha.2.sub.i =.alpha.2+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.beta.1=.SIGMA..lambda.(i, .LAMBDA.).times..beta.1.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .beta.1.sub.i =.beta.1+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.beta.2=.SIGMA..lambda.(i, .LAMBDA.).times..beta.2.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .beta.2.sub.i =.beta.2+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.gamma.=.SIGMA..lambda.(i, .LAMBDA.).times..gamma..sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .gamma..sub.i =.gamma.+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use public keys of the system

A=g.sub.1.sup..alpha.1 g.sub.2.sup..alpha.2 modp, B=g.sub.1.sup..beta.1 g.sub.2.sup..beta.2 modp, .GAMMA.=g.sub.1.sup..gamma. modp,

public information

A.sub.1 =g.sub.1.sup..alpha.11 g.sub.2.sup..alpha.21 modp, . . . , A.sub.N =g.sub.1.sup..alpha.1N g.sub.2.sup..alpha.2N modp,

B.sub.1 =g.sub.1.sup..beta.11 g.sub.2.sup..beta.21 modp, . . . , B.sub.N =g.sub.1.sup..beta.1N g.sub.2.sup..beta.2N modp,

.GAMMA..sub.1 =g.sub.1.sup..gamma.1 modp, . . . , .GAMMA..sub.N =g.sub.1.sup..gamma.N modp

which are calculated by the secret information .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma..sub.i, the prime number p, the measure q, the elements g1, g2, and a Hash function hash ( ), and

(1) the chairman terminal generates arbitrarily a non-zero element k of GF(q), and calculates preparatory information

C1.sub.1 =g.sub.1.sup.k modp, C1.sub.2 =g.sub.2.sup.k modp

(2) the chairman terminal calculates exclusive information

C2.sub.i1 =.GAMMA..sub.i1.sup.k modp, . . . , C2.sub.iD =.GAMMA..sub.iD.sup.k modp,

C2.sub.b1 =.GAMMA..sub.b1.sup.k modp, . . . , C2.sub.bv =.GAMMA..sub.bv.sup.k modp,

based on the public information .GAMMA..sub.i1, . . . , .GAMMA..sub.iD of the D particular terminals i.sub.1, . . . , i.sub.D, and any v(=d-D) public information .GAMMA..sub.b1, . . . , .GAMMA..sub.bv out of the public information .GAMMA..sub.N+1, . . . , .GAMMA..sub.n+d-1,

(3) the chairman terminal calculates verification information

v=A.sup.k B {(c.times.k) modq} modp (c=hash(C1.sub.1, C1.sub.2) modq),

v.sub.i1 =A.sub.i1.sup.k B.sub.i1 {(c.times.k) modq} modp, . . . ,

v.sub.iD =A.sub.iD.sup.k B.sub.iD {(c.times.k) modq} modp

v.sub.b1 =A.sub.b1.sup.k B.sub.b1 {(c.times.k) modq} modp, . . . ,

v.sub.bv =A.sub.bv.sup.k B.sub.bv {(c.times.k) modq} modp

and then broadcasts the verification information v, v.sub.i1, . . . , v.sub.iD, v.sub.b1, . . . , v.sub.bv together with the exclusive information C2.sub.i1, . . . , C2.sub.iD, C2.sub.b1, . . . , C2.sub.bv, the particular terminal numbers i.sub.1, . . . , i.sub.D, and the terminal numbers b.sub.1, . . . , b.sub.v corresponding to the public information .GAMMA..sub.b1, . . . , .GAMMA..sub.bv to all terminals,

(4) the chairman terminal calculates a common key

K=.GAMMA..sup.k modp

(5) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.D, b.sub.1, . . . , b.sub.v, .phi.) calculate .lambda.(j, .LAMBDA.), .lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.D, .LAMBDA.), .lambda.(b.sub.1, .LAMBDA.), . . . , .lambda.(b.sub.v, .LAMBDA.) where .LAMBDA.={j, i.sub.1, . . . , i.sub.D, b.sub.1, . . . , b.sub.v }, and then calculate a verification equation

{C1.sub.1 ((.alpha.1.sub.j +.beta.1.sub.j.times.c).lambda.(j, .LAMBDA.) modq)}{C1.sub.2 ((.alpha.2.sub.j +.beta.2.sub.j.times.c).lambda.

(j, .LAMBDA.) modq)}.times.v.sub.i1 {.lambda.(i.sub.1, .LAMBDA.) modq}.times. . . . .times.v.sub.iD {.lambda.(i.sub.D, .LAMBDA.) modq} modp=v(c=hash (C1.sub.1, C1.sub.2) modq)

by using the public keys A, B of the system and own secret information .alpha.1.sub.j, .alpha.2.sub.j, .beta.1.sub.j, .beta.2.sub.j, and then stop key sharing unless the verification equation is satisfied and, if the verification equation is satisfied,

(6) the respective terminals j calculate

C1.sub.1 {.gamma..sub.j.times.(.lambda.(j, .LAMBDA.) modq)}.times.C2.sub.i1 (.lambda.(i.sub.1, .LAMBDA.) modq).times. . . . .times.C2.sub.id (.lambda.(i.sub.d, .LAMBDA.) modq) modp

by using the .lambda.(j, .LAMBDA.), (.lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.d, .LAMBDA.), the preparatory information C1.sub.1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and the own secret information .gamma..sub.j to thus obtain the common key K.

31. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication, according to claims 25 or 30, wherein secret keys are .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma., a prime number which is larger than .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma. and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g1, g2, a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1), and a number D of terminals which the chairman terminal actually specifies in sharing the keys (referred to as an "actual particular terminal number" hereinafter) is a number which is smaller than the particular terminal number d but larger than 1,

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma..sub.i in secret to satisfy

.alpha.1=.SIGMA..lambda.(i, .LAMBDA.).times..alpha.1.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .alpha.1.sub.i =.alpha.1+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.alpha.2=.SIGMA..lambda.(i, .LAMBDA.).times..alpha.2.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .alpha.2.sub.i =.alpha.2+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.beta.1=.SIGMA..lambda.(i, .LAMBDA.).times..beta.1.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .beta.1.sub.i =.beta.1+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.beta.2=.SIGMA..lambda.(i, .LAMBDA.).times..beta.2.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .beta.2.sub.i =.beta.2+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.gamma.=.SIGMA..lambda.(i, .LAMBDA.).times..gamma..sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .gamma..sub.i =.gamma.+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use public keys of the system

A=g.sub.1.sup..alpha.1 g.sub.2.sup..alpha.2 modp, B=g.sub.1.sup..beta.1 g.sub.2.sup..beta.2 modp, .GAMMA.=g.sub.1.sup..gamma. modp,

public information

A.sub.N+1 =g.sub.1.sup..alpha.1N+1 g.sub.2.sup..alpha.2N+1 modp,

A.sub.N+d-1 =g.sub.1.sup..alpha.1N+d-1 g.sub.2.sup..alpha.2N+d-1 modp

B.sub.N+1 =g.sub.1.sup..beta.1N+1 g.sub.2.sup..beta.2N+1 modp, . . . ,

B.sub.N+d-1 =g.sub.1.sup..beta.1N+d-1 g.sub.2.sup..beta.2N+d-1 modp

.GAMMA..sub.N+1 =g.sub.1.sup..gamma.N+1 modp, . . . ,

.GAMMA..sub.N+d-1 =g.sub.1.sup..gamma.N+d-1 modp,

which are calculated by the secret information .alpha.1.sub.N+1, . . . , .alpha.1.sub.N+d-1, .alpha.2.sub.N+1, . . . , .alpha.2.sub.N+d-1, .beta.1.sub.N+1, . . . , .beta.1.sub.N+d-1, .beta.2.sub.N+1, . . . , .beta.2.sub.N+d-1, .gamma..sub.N+1, . . . , .gamma..sub.N+d- 1, which are divided by calculating

.alpha.1.sub.N+1 =.alpha.1+f.sub.1.times.(N+1).sup.1 + . . . , +f.sub.d.times.(N+1).sup.d modq, . . . ,

.alpha.1.sub.N+d-1 =.alpha.1+f.sub.1.times.(N+d-1).sup.1 + . . . , +f.sub.d.times.(N+d-1).sup.d modq,

.beta.1.sub.N+1 =.beta.1+f.sub.1.times.(N+1).sup.1 + . . . , +f.sub.d.times.(N+1).sup.d modq, . . . ,

.beta.1.sub.N+d-1 =.beta.1+f.sub.1.times.(N+d-1).sup.1 + . . . , +f.sub.d.times.(N+d-1).sup.d modq,

.gamma..sub.N+1 =.gamma.+f.sub.1.times.(N+1).sup.1 + . . . , +f.sub.d.times.(N+1).sup.d modq, . . . ,

.gamma..sub.N+d-1 =.gamma.+f.sub.1.times.(N+d-1).sup.1 + . . . , +f.sub.d.times.(N+d-1).sup.d modq,

.alpha.2.sub.N+1 =.alpha.1+f.sub.1.times.(N+1).sup.1 + . . . , +f.sub.d.times.(N+1).sup.d modq, . . . ,

.alpha.2.sub.N+d-1 =.alpha.1+f.sub.1.times.(N+d-1).sup.1 + . . . , +f.sub.d.times.(N+d-1).sup.d modq,

.beta.2.sub.N+1 =.beta.1+f.sub.1.times.(N+1).sup.1 + . . . , +f.sub.d.times.(N+1).sup.d modq, . . . ,

.beta.2.sub.N+d-1 =.beta.1+f.sub.1.times.(N+d-1).sup.1 + . . . , +f.sub.d.times.(N+d-1).sup.d modq,

public information

A.sub.1 =g.sub.1.sup..alpha.11 g.sub.2.sup..alpha.21 modp, . . . , A.sub.N =g.sub.1.sup..alpha.1N g.sub.2.sup..alpha.2N modp

B.sub.1 =g.sub.1.sup..beta.11 g.sub.2.sup..beta.21 modp, . . . , B.sub.N =g.sub.1.sup..beta.1N g.sub.2.sup..beta.2N modp

.GAMMA..sub.1 =g.sub.1.sup..gamma.1 modp, . . . , .GAMMA..sub.N =g.sub.1.sup..gamma.N modp

which are calculated by the secret information .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma..sub.i, the prime number p, the measure q, the elements g1, g2, and a Hash function hash ( ), and

(1) the chairman terminal generates arbitrarily a non-zero element k of GF(q), and calculates preparatory information

C1.sub.1 =g.sub.1.sup.k modp, C1.sub.2 =g.sub.2.sup.k modp

(2) the chairman terminal calculates exclusive information

C2.sub.i1 =.GAMMA..sub.i1.sup.k modp, . . . , C2.sub.id =.GAMMA..sub.id.sup.k modp

based on the public information .GAMMA..sub.i1, . . . , .GAMMA..sub.id of the d particular terminals i.sub.1, . . . , i.sub.d,

(3) the chairman terminal calculates verification information

v=A.sup.k B {(c.times.k) modq} modp (c=hash(C1.sub.1, C1.sub.2) modq),

v.sub.i1 =A.sub.i1.sup.k B.sub.i1 {(c.times.k) modq} modp, . . . ,

v.sub.id =A.sub.i1.sup.k B.sub.id {(c.times.k) modq} modp

and then broadcasts them together with the exclusive information C2.sub.i1, . . . , C2.sub.id and the particular terminal numbers i.sub.1, . . . , i.sub.d to all terminals,

(4) the chairman terminal calculates a common key

K=.GAMMA..sup.k modp

(5) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate .lambda.(j, .LAMBDA.), .lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.d, .LAMBDA.) where .LAMBDA.={j, i.sub.1, . . . , i.sub.d }, and calculate a verification equation

{C1.sub.1 ((.alpha.1.sub.j +.beta.1.sub.j.times.c).lambda.(j, .LAMBDA.) modq)}{C1.sub.2 ((.alpha.2.sub.j +.beta.2.sub.j.times.c).lambda.

(j, .LAMBDA.) modq)}.times.v.sub.i1 {.lambda.(i.sub.1, .LAMBDA.) modq}.times. . . . .times.v.sub.id {.lambda.(i.sub.d, .LAMBDA.) modq} modp=v(c=hash (C1.sub.1, C1.sub.2) modq)

by using the public keys A, B of the system and own secret information .alpha.1.sub.j, .alpha.2.sub.j, .beta.1.sub.j, .beta.2.sub.j, and then stop key sharing unless the verification equation is satisfied and, if the verification equation is satisfied,

(6) the respective terminals j calculate

C1.sub.1 {.gamma..sub.j.times.(.lambda.(j, .LAMBDA.) modq)}.times.C2.sub.i1 (.lambda.(i.sub.1, .LAMBDA.) modq).times. . . . .times.

C2.sub.id (.lambda.(i.sub.d, .LAMBDA.) modq).times.C2.sub.b1 {(.lambda.(b.sub.1, .LAMBDA.) modq)}.times. . . . .times.

C2.sub.bv (.lambda.(b.sub.v, .LAMBDA.) modq) modp

by using .lambda.(j, .LAMBDA.), (.lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.D, .LAMBDA.), .lambda.(b.sub.1, .LAMBDA.), . . . , .lambda.(b.sub.v, .LAMBDA.), the preparatory information C1.sub.1, the exclusive information C2.sub.i1, . . . , C2.sub.iD, C2.sub.b1, . . . , C2.sub.bv, and the own secret information .gamma..sub.j to thus obtain the common key K.

32. An exclusive key sharing method according to claims 25 or 26, wherein the chairman terminal can use public information formulated based on .theta. sets of secret information, which are derived by dividing the secret keys .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma. to the .theta. particular terminal numbers d.sub.1, . . . , d.sub.0 (.theta. is any integer) respectively, and the terminal holds .theta. pieces of secret information, which correspond to own terminal number, out of respective sets, and

when key sharing is carried out to exclude the particular terminals, the chairman terminal and the respective terminals j select a particular terminal number d.sub.w (1.ltoreq.w.ltoreq..theta.), which is equal to the actual particular terminal number D, from the particular terminals d.sub.1, . . . , d.sub..theta., and then the chairman terminal broadcasts the verification information, the exclusive information, the particular terminal number, and the own terminal number, by using a set of public information corresponding to the selected particular terminal number d.sub.w to obtain a common key K which is shared with the terminals, and the terminals j confirm the verification equation and obtain the common key K which is shared with the chairman terminal by using the secret information corresponding to the d.sub.w.

33. An exclusive key sharing method for a communication system which consists of a base station and N terminals (N is an integer of more than 2) connected to the base station to allow broadcast communication, according to claims 25 or 30, wherein secret keys are .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma., a prime number which is larger than .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma. and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g1, g2, and a particular terminal number is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma..sub.i in secret to satisfy

.alpha.1=.SIGMA..lambda.(i, .LAMBDA.).times..alpha.1.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .alpha.1.sub.i =.alpha.1+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.alpha.2=.SIGMA..lambda.(i, .LAMBDA.).times..alpha.2.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .alpha.2.sub.i =.alpha.2+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.beta.1=.SIGMA..lambda.(i, .LAMBDA.).times..beta.1.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .beta.1.sub.i =.beta.1+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.beta.2=.SIGMA..lambda.(i, .LAMBDA.).times..beta.2.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .beta.2.sub.i =.beta.2+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.gamma.=.SIGMA..lambda.(i, .LAMBDA.).times..gamma..sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .gamma..sub.i =.gamma.+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use public keys of the system

A=g.sub.1.sup..alpha.1 g.sub.2.sup..alpha.2 modp, B=g.sub.1.sup..beta.1 g.sub.2.sup..beta.2 modp, .GAMMA.=g.sub.1.sup..gamma. modp,

the prime number p, the measure q, the elements g1, g2, and a Hash function hash ( ), and the base station holds secret information .alpha.1.sub.1, . . . , .alpha.1.sub.N, .alpha.2.sub.1, . . . , .alpha.2.sub.N, .beta.1.sub.1, . . . , .beta.1.sub.N, .beta.2.sub.1, . . . , .beta.2.sub.N, .gamma..sub.1, . . . , .gamma..sub.N, and

(1) the base station generates arbitrarily a non-zero element k of GF(q), and calculates preparatory information

C1.sub.1 =g.sub.1.sup.k modp, C1.sub.2 =g.sub.2.sup.k modp

(2) the base station calculates exclusive information

C2.sub.i1 =g.sub.1 {.gamma..sub.i1.times.k modq} modp, . . . ,

C2.sub.id =g.sub.1 {.gamma..sub.id.times.k modq} modp

based on the secret information .gamma..sub.i1, . . . , .gamma..sub.id of the d particular terminals i.sub.1, . . . , i.sub.d,

(3) the base station calculates verification information

v=A.sup.k B {(c.times.k) modq} modp (c=hash(C1.sub.1, C1.sub.2) modq),

v.sub.i1 =(g.sub.1.sup..alpha.1i1 g.sub.2.sup..alpha.2i1).sup.k (g.sub.1.sup..beta.1i1 g.sub.2.beta..sup.2i1) {(c.times.k) modq} modp, . . . ,

v.sub.id =(g.sub.1.sup..alpha.1id g.sub.2.sup..alpha.2id).sup.k (g.sub.1.sup..beta.1id g.sub.2.beta..sup.2id) {(c.times.k) modq} modp, . . . ,

and then broadcasts them together with the exclusive information C2.sub.i1, . . . , C2.sub.id, and the particular terminal numbers i.sub.1, . . . , i.sub.d to all terminals,

(4) the base station calculates a common key

K=.GAMMA..sup.k modp,

(5) the respective terminals j (j.noteq.i.sub.1, . . . i.sub.d) calculate .lambda.(j, .LAMBDA.), .lambda.(i, .LAMBDA.), . . . , .lambda.(i.sub.d, .LAMBDA.) where .LAMBDA.={j, i.sub.1, . . . , i.sub.d }, and then calculate a verification equation

{C1.sub.1 ((.alpha.1.sub.j +.beta.1.sub.j.times.c).lambda.

(j, .LAMBDA.) modq)}{C1.sub.2 ((.alpha.2.sub.j +.beta.2.sub.j.times.c).lambda.(j, .LAMBDA.) modq)}.times.v.sub.i1 {.lambda.(i.sub.1, .LAMBDA.) modq}.times. . . . .times.v.sub.id {.lambda.(i.sub.d, .LAMBDA.) modq} modp=v(c=hash (C1.sub.1, C1.sub.2) modq)

by using the public keys A, B of the system and own secret information .alpha.1.sub.j, .alpha.2.sub.j, .beta.1.sub.j, .beta.2.sub.j, and then stop key sharing unless the verification equation is satisfied and, if the verification equation is satisfied,

(6) the respective terminals j calculate

C1.sub.1 {.gamma..sub.j.times.(.lambda.(j, .LAMBDA.) modq)}.times.C2.sub.i1 (.lambda.(i.sub.1, .LAMBDA.) modq).times. . . . .times.C2.sub.id (.lambda.(i.sub.d, .LAMBDA.) modq) modp

by using .lambda.(j, .LAMBDA.),(.lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.d, .LAMBDA.), the preparatory information C1.sub.1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and the own secret information .gamma..sub.j to thus obtain the common key K.

34. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication, according to claims 25 or 30, wherein secret keys are .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma., a prime number which is larger than .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma. and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g1, g2, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma..sub.i in secret, and can use public keys of the system

A=g.sub.1.sup..alpha.1 g.sub.2.sup..alpha.2 modp, B=g.sub.1.sup..beta.1 g.sub.2.sup..beta.2 modp, .GAMMA.=g.sub.1.sup..gamma. modp,

public information

A.sub.1 =g.sub.1.sup..alpha.11 g.sub.2.sup..alpha.21 modp, . . . , A.sub.N =g.sub.1.sup..alpha.1N g.sub.2.sup..alpha.2N modp,

B.sub.1 =g.sub.1.sup..beta.11 g.sub.2.sup..beta.21 modp, . . . , B.sub.N =g.sub.1.sup..beta.1N g.sub.2.sup..beta.2N modp,

.GAMMA..sub.1 =g.sub.1.sup..gamma.1 modp, . . . , .GAMMA..sub.N =g.sub.1.sup..gamma.N modp

which are calculated by the secret information .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma..sub.i, the prime number p, the measure q, the elements g1, g2, and a Hash function hash ( ), and

(1) the chairman terminal generates arbitrarily a non-zero element k of GF(q), and calculates preparatory information

C1.sub.1 =g.sub.1.sup.k modp,

C1.sub.2 =g.sub.2.sup.k modp

(2) the chairman terminal calculates exclusive information

C2.sub.i1 =.GAMMA..sub.i1.sup.k modp, . . . , C2.sub.id =.GAMMA..sub.id.sup.k modp

based on the public information .GAMMA..sub.i1, . . . , .GAMMA..sub.id of the d particular terminals i.sub.1, . . . , i.sub.d,

(3) the chairman terminal calculates a common key

K=.GAMMA..sup.k modp,

(4) the chairman terminal generates any group key M and formulates a ciphertext

C=M.times.K modp

by using the common key K,

(5) the chairman terminal calculates verification information

v=A.sup.k B {c.times.k modq} modp (c=hash(C1.sub.1, C1.sub.2) modq),

v.sub.i1 =A.sub.i1.sup.k B.sub.i1 {c.times.k modq} modp, . . . ,

v.sub.id =A.sub.i1.sup.k B.sub.id {c.times.k modq} modp

and then broadcasts the ciphertext C and the verification information v, v.sub.i1, . . . , v.sub.id together with the exclusive information C2.sub.i1, . . . , C2.sub.id and the particular terminal numbers i.sub.1, . . . , i.sub.d to all terminals,

(6) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate .lambda.(j, .LAMBDA.), .lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.d, .LAMBDA.) where .LAMBDA.={j, i.sub.1, . . . , i.sub.d }, and then calculate a verification equation

{C1.sub.1 ((.alpha.1.sub.j +.beta.1.sub.j.times.c).lambda.

(j, .LAMBDA.) modq)}{C1.sub.2 ((.alpha.2.sub.j +.beta.2.sub.j.times.c).lambda.(j, .LAMBDA.) modq)}.times.v.sub.i1 {.lambda.(i.sub.1, .LAMBDA.) modq}.times. . . . .times.v.sub.id {.lambda.(i.sub.d, .LAMBDA.) modq} modp=v(c=hash (C, C1.sub.1, C1.sub.2) modq)

by using the public keys A, B of the system and own secret information .alpha.1.sub.j, .alpha.2.sub.j, .beta.1.sub.j, .beta.2.sub.j, and then stop key sharing unless the verification equation is satisfied and, if the verification equation is satisfied,

(7) the respective terminals j calculate

C1.sub.1 {.gamma..sub.j.times.(.lambda.(j, .LAMBDA.) modq)}.times.C2.sub.i1 (.lambda.(i.sub.1, .LAMBDA.) modq).times. . . . .times.C2.sub.id (.lambda.(i.sub.d, .LAMBDA.) modq) modp

by using .lambda.(j, .LAMBDA.),(.lambda.(i.sub.d, .LAMBDA.), . . . , .lambda.(i.sub.d, .LAMBDA.), the preparatory information C1.sub.1, C1.sub.2, the exclusive information C2.sub.i1, . . . , C2.sub.id, and the own secret information .gamma..sub.j to thus obtain the common key K,

(8) the respective terminals j calculate the group key M=C/K modp by the common key K and the ciphertext C.

35. An exclusive key sharing method according to claims 25 or 30, wherein the base station executes division of the secret key S or .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma.1, .gamma.2, calculation and publication of the public key y or A, B, .GAMMA., the public information y.sub.1, y.sub.2, . . . , y.sub.N or A.sub.1, . . . , A.sub.N, B.sub.1, . . . , B.sub.N, .GAMMA..sub.1, . . . , .GAMMA..sub.N, and allocation of the secret information S.sub.i or .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma.1.sub.i, .gamma.2.sub.i corresponding to the terminal i.

36. An exclusive key sharing method according to claim 9, wherein a third party which is different from the base station executes division of the secret key S or .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma.1, .gamma.2, calculation and publication of the public key y or A, B, .GAMMA., the public information y.sub.1, y.sub.2, y.sub.N or A.sub.1, . . . , A.sub.N, B.sub.1, . . . , B.sub.N, .GAMMA..sub.1, . . . , .GAMMA..sub.N, and allocation of the secret information S.sub.i or .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma.1.sub.i, .gamma.2.sub.i corresponding to the terminal i.

37. An exclusive key sharing method according to claims 25 or 30, wherein new terminal numbers I (I>N) are set to terminals which newly enter into the communication system which can execute the broadcast communication, and then secret information S.sub.i or

.alpha.1.sub.1 =.alpha.1+f.sub.1.times.I.sup.1 + . . . +f.sub.d.times.I.sup.d modq

.alpha.2.sub.1 =.alpha.2+f.sub.1.times.I.sup.1 + . . . +f.sub.d.times.I.sup.d modq

.beta.1.sub.1 =.beta.1+f.sub.1.times.I.sup.1 + . . . +f.sub.d.times.I.sup.d modq

.beta.2.sub.1 =.beta.2+f.sub.1.times.I.sup.1 + . . . +f.sub.d.times.I.sup.d modq

.gamma.1.sub.1 =.gamma.1+f.sub.1.times.I.sup.1 + . . . +f.sub.d.times.I.sup.d modq

.gamma.2.sub.1 =.gamma.2+f.sub.1.times.I.sup.1 + . . . +f.sub.d.times.I.sup.d modq

which are obtained by calculating

S.sub.1 =S+f.sub.1.times.I.sup.1 + . . . +f.sub.d.times.I.sup.d modq

are held in secret in new terminals.

38. An exclusive key sharing method according to claims 25 or 30, wherein the terminal i saves in secret a power residue of Ci or C1.sub.1, C1.sub.2 (=C1.sup.Si modp or C1.sub.1.sup..alpha.1i C1.sub.2.sup..alpha.2i modp, C1.sub.1.sup..beta.1i C1.sub.2.sup..beta.2i modp, C1.sub.1.sup..gamma.1i C1.sub.2.sup..gamma.2i modp) which has p in place of the secret information S.sub.i or .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma.1.sub.i, .gamma.2.sub.i as the modulus and S.sub.i or .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma.1.sub.i, .gamma.2.sub.i as the exponent.

39. An exclusive key sharing method according to claims 1 or 6, wherein the chairman terminal or the base station calculates .lambda.(j, .LAMBDA.) for all .LAMBDA.'s including the particular terminals, then calculates a power residue value of the exclusive information C2.sub.i

C2.sub.i (.lambda.(i, .LAMBDA.) modq) modp

which has .lambda.(i, .LAMBDA.) calculated to the modulus q as the exponent and p as the modulus, then broadcasts it in sharing the key, and

all terminals j except the particular terminal obtain the common key K by using the power residue value in answer to the .LAMBDA.'s including the j.

40. An exclusive key sharing method according to claims 25 or 30, wherein all terminals j except the base station and the particular terminal generate a new common key K2 based on the shared common key K and the common key K1 shared at a time of previous key sharing.

41. An exclusive key sharing method according to claim 30, wherein a digital signature of the base station is added to data which are distributed from the base station by a digital signature means provided previously to the base station and the terminals.

42. An exclusive key sharing method according to claims 25 or 30, wherein a number of secret information held by the terminals is increased and decreased in response to authority of the terminals.

43. An exclusive key sharing method according to claims 25 or 30, wherein the chairman terminal and the base station select only own terminal as the particular terminal, and broadcast information necessary for the key sharing by using an encrypted communication path using the common key K.

44. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication, according to claim 25, wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

S.sub.i =S+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use a public key of the system managed by a system manager

y=g.sup.s modp,

public information

y.sub.1 =g.sup.S1 modp, y.sub.2 =g.sup.S2 modp, . . . , y.sub.N =g.sup.SN modp,

the prime number p, the measure q, and the elements g, and

(1) the chairman terminal generates arbitrarily a non-zero element k of GF(q), and calculates exclusive information

C2.sub.i1 =y.sub.i1.sup.k modp, . . . , C2.sub.id =y.sub.id.sup.k modp

based on the public information y.sub.i1, . . . , y.sub.id of the d particular terminals i.sub.1, . . . , i.sub.d,

(2) the chairman terminal calculates a signature

Z=C2.sub.i1.times. . . . .times.C2.sub.id.times.(-S.sub..phi.)+k modq

by using own secret information S.sub..phi., and broadcasts the signature Z together with the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal numbers i.sub.1, . . . , i.sub.d, and own terminal number .phi. to all terminals,

(3) the chairman terminal calculates a common key

K=y.sup.k modp,

(4) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate

C1=g.sup.z.times.y.sub..phi. (C2.sub.i1.times. . . . .times.C2.sub.id modq) modp

(if a signer is surely the chairman terminal .phi. and also the signature Z, the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal numbers i.sub.1, . . . , i.sub.d, and the terminal number .phi. of the chairman terminal are not tampered, C1=g.sup.k modp is calculated) by using the public information y.sub..phi. of the chairman terminal,

(5) the respective terminals j calculate .lambda.(j, .LAMBDA.) and .lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.d, .LAMBDA.) where .LAMBDA.={j, i.sub.1, . . . , i.sub.d } and calculate C1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq).times.C2.sub.i1 (.lambda.(i.sub.1, .LAMBDA.) modq).times. . . . .times.C2.sub.id (.lambda.(i.sub.d, .LAMBDA.) modq) modp by using the C1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and own secret information S.sub.j to thus obtain the common key K, and

(i) the system manager generates arbitrarily a non-zero element.epsilon. of GF(q), and broadcasts the.epsilon. to all terminals,

(ii) the system manager calculates a new element

g'=g {(1/.epsilon.) modq} modp,

and replaces the managed element g with it,

(iii) the respective terminals i calculate new secret information

S.sub.i '=S.sub.i.times..epsilon. modq

(at this time, (g').sup.Si' modp=(g).sup.Si modp is satisfied).

45. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication, according to claim 30, wherein secret keys are .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma.1, .gamma.2, a prime number which is larger than .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma.1, .gamma.2, and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g1, g2, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma.1.sub.i, .gamma.2.sub.i in secret to satisfy

.alpha.1=.SIGMA..lambda.(i, .LAMBDA.).times..alpha.1.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .alpha.1.sub.i =.alpha.1+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.alpha.2=.SIGMA..lambda.(i, .LAMBDA.).times..alpha.2.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .alpha.2.sub.i =.alpha.2+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.beta.1=.SIGMA..lambda.(i, .LAMBDA.).times..beta.1.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .beta.1.sub.i =.beta.1+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.beta.2=.SIGMA..lambda.(i, .LAMBDA.).times..beta.2.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .beta.2.sub.i =.beta.2+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.gamma.1=.SIGMA..lambda.(i, .LAMBDA.).times..gamma.1.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .gamma.1.sub.i =.gamma.1+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.gamma.2=.SIGMA..lambda.(i, .LAMBDA.).times..gamma.2.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .gamma.2.sub.i =.gamma.2+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0 and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use public keys of the system

A=g.sub.1.sup..alpha.1 g.sub.2.sup..alpha.2 modp,

B=g.sub.1.sup..beta.1 g.sub.2.sup..beta.2 modp,

.GAMMA.=g.sub.1.sup..gamma.1 g.sub.2.sup..gamma.2 modp,

which are managed by a system manager, public information

A.sub.1 =g.sub.1.sup..alpha.11 g.sub.2.sup..alpha.21 modp, . . . , A.sub.N =g.sub.1.sup..alpha.1N g.sub.2.sup..alpha.2N modp

B.sub.1 =g.sub.1.sup..beta.11 g.sub.2.sup..beta.21 modp, . . . , B.sub.N =g.sub.1.sup..beta.1N g.sub.2.sup..beta.2N modp

.GAMMA..sub.1 =g.sub.1.sup..gamma.11 g.sub.2.sup..gamma.21 modp, . . . , .GAMMA..sub.N =g.sub.1.sup..gamma.1N g.sub.2.sup..gamma.2N modp

which are calculated by the secret information .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma.1.sub.i, .gamma.2.sub.i, the prime number p, the measure q, the elements g1, g2, and a Hash function hash ( ), and

(1) the chairman terminal generates arbitrarily a non-zero element k of GF(q), and calculates preparatory information

C1.sub.1 =g.sub.1.sup.k modp, C1.sub.2 =g.sub.2.sup.k modp,

(2) the chairman terminal calculates exclusive information

C2.sub.i1 =.GAMMA..sub.i1.sup.k modp, . . . , C2.sub.id =.GAMMA..sub.id.sup.k modp

based on the public information .GAMMA..sub.i1, . . . .GAMMA..sub.id of the d particular terminals i.sub.1, . . . , i.sub.d,

(3) the chairman terminal calculates verification information

v=A.sup.k B {(c.times.k) modq} modp (c=hash(C1.sub.1, C1.sub.2) modq),

v.sub.i1 =A.sub.i1.sup.k B.sub.i1 {(c.times.k) modq} modp, . . . ,

v.sub.id =A.sub.i1.sup.k B.sub.id {(c.times.k) modq} modp

and then broadcasts them together with the exclusive information C2.sub.i1, . . . , C2.sub.id and the particular terminal numbers i.sub.1, . . . , i.sub.d to all terminals,

(4) the chairman terminal calculates a common key

K=.GAMMA..sup.k modp

(5) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate .lambda.(j, .LAMBDA.), .lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.d, .LAMBDA.) where .LAMBDA.={j, i.sub.1, . . . , i.sub.d }, and calculate a verification equation

{C1.sub.1.sup..alpha.1j C1.sub.2.sup..alpha.2j (C1.sub.1.sup..beta.1j C1.sub.2.sup..beta.2j).sup.C) {.lambda.(j, .LAMBDA.) modq}.times.

v.sub.i1 {.lambda.(i.sub.1, .LAMBDA.) modq}.times. . . . .times.v.sub.id {.lambda.(i.sub.d, .LAMBDA.) modq} modp=v (c=hash (C1.sub.1, C1.sub.2) modq)

by using the public keys A, B of the system and own secret information .alpha.1.sub.j, .alpha.2.sub.j, .beta.1.sub.j, .beta.2.sub.j, and then stop key sharing unless the verification equation is satisfied and, if the verification equation is satisfied,

(6) the respective terminals j calculate

(C1.sub.1.sup..gamma.1j C1.sub.2.sup..gamma.2j) {(j, .LAMBDA.) modq}.times.C2.sub.i1 {.lambda.(i.sub.1, .LAMBDA.) modq}.times. . . . .times.C2.sub.id (.lambda.(i.sub.d, .LAMBDA.) modq) modp

by using .lambda.(j, .LAMBDA.), (.lambda.(i.sub.1, .LAMBDA.), . . . , .lambda.(i.sub.d, .LAMBDA.) the preparatory information C1.sub.1, C1.sub.2, the exclusive information C2.sub.i1, . . . , C2.sub.id, and the own secret information .gamma.1.sub.j, .gamma.2.sub.j, to thus obtain the common key K which is shared with the chairman terminal, and

(i) the system manager generates arbitrarily a non-zero element.epsilon. of GF(q), and broadcasts the.epsilon. to all terminals,

(ii) the system manager calculates new elements

g.sub.1 '=g.sub.1 {(1/.epsilon.) modq} modp, g.sub.2 '=g.sub.2 {(1/.epsilon.) modq} modp

and replaces the managed element g with them,

(iii) the respective terminals i calculate new secret information

.alpha.1.sub.i '=.alpha.1.sub.i.times..epsilon. modq

.alpha.2.sub.i '=.alpha.2.sub.i.times..epsilon. modq

.beta.1.sub.i '=.beta.1.sub.i.times..epsilon. modq

.beta.2.sub.i '=.beta.2.sub.i.times..epsilon. modq

.gamma.1.sub.i '=.gamma.1.sub.i.times..epsilon. modq

.gamma.2.sub.i '=.gamma.2.sub.i.times..epsilon. modq

(at this time, (g').sup..alpha.1i' modp=(g).sup..alpha.1i modp

(g').sup..alpha.2i' modp=(g).sup..alpha.2i modp

(g').sup..beta.1i' modp=(g).sup..beta.1i modp

(g').sup..beta.2i' modp=(g).sup..beta.2i modp

(g').sup..gamma.1i' modp=(g).sup..gamma.1i modp and

(g').sup..gamma.2i' modp=(g).sup..gamma.2i modp are satisfied).

46. An exclusive key sharing method according to claims 44 or 45, wherein the chairman terminal or the base station broadcasts an encrypted.epsilon. which is encrypted by using the common key K to all terminals.

47. An exclusive key sharing method according to claims 25 or 30, wherein only the chairman terminal can use the public information of respective terminals.

48. An exclusive key sharing method according to claims 25 or 30, wherein respective terminals hold all public information other than own public information.

49. An exclusive key sharing method for a communication system which consists of a base station and N terminals (N is an integer of more than 2) connected to the base station to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, and a number of terminals which can be specified by the base station (referred to as a "particular terminal number" hereinafter) is 1,

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where S.sub.i =S+f.sub.1.times.i modq (f1 is a non-zero element of GF(q)), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any two terminals out of the N terminals), and

the base station holds (S, p, g, S.sub.1, . . . , S.sub.N),

the base station calculates preparatory information

C.sub.1 =g.sup.k modp

where an element of GF(p) is g and a non-zero element of GF(q) is k,

the base station calculates exclusive information

C.sub.2 =g (k.times.S.sub.a modq) modp,

based on the secret information S.sub.a of the particular terminal a, and broadcasts the exclusive information together with the particular terminal number a and the preparatory information C.sub.1 to all terminals, and

the base station calculates a common key

K=g (k.times.S modq) modp

which is shared with all terminals j (j.noteq.a) except the particular terminal a,

the respective terminals j (j.noteq.a) calculate a product

C.sub.1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq).times.C.sub.2 (.lambda.(a, .LAMBDA.) modq) modp

of a power residue value of C.sub.1

C.sub.1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq) modp

which uses a product of Si and .lambda.(j, .LAMBDA.) to the modulus q as an exponent and a power residue value of C.sub.2

C.sub.2 (.lambda.(a, .LAMBDA.) modq) modp

which uses .lambda.(a, .LAMBDA.) calculated to the modulus p as the exponent by using the preparatory information C.sub.1, the exclusive information C.sub.2, and own secret information S.sub.j to thus obtain the common key K which is shared with the base station, and

(i) the base station generates arbitrarily a non-zero element e of GF(q), and broadcasts the e to all terminals,

(ii) the base station calculates a new element

g'=g.sup.1/e modq modp

and replaces the managed element g with it,

(iii) the respective terminals i calculate new secret information

S.sub.i '=S.sub.i.times.e modq

(at this time, (g').sup.Si' modp=(g).sup.Si modp is satisfied).

50. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal (to which any terminal can be appointed) is 1,

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where S.sub.i =S+f.sub.1.times.i modq (f1 is a non-zero element of GF(q)), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any two terminals out of the N terminals), and can use the prime number p, the measure q, and the elements g, which are managed by a system manager, a public key for all terminals which is managed by the system manager

y=g.sup.S modp,

and public information

y.sub.1 =g.sup.S1 modp, y.sub.2 =g.sup.S2 modp, . . . , y.sub.N =g.sup.SN modp

which are managed by the system manager, and

the chairman terminal generates arbitrarily a non-zero element k of GF(q) and calculates preparatory information

C.sub.1 =g.sup.k modp,

the chairman terminal calculates exclusive information

C.sub.2 =y.sub.a.sup.k modp,

based on the public information y.sub.a of the particular terminal a, and broadcasts the exclusive information together with the particular terminal number a and the preparatory information C.sub.1 to all terminals, and

the chairman terminal calculates a common key

K=y.sup.k modp,

and

the respective terminals j (j.noteq.a) calculate .lambda.(j, .LAMBDA.) and .lambda.(a, .LAMBDA.) where .LAMBDA.={j, a} and calculate

C.sub.1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq).times.C.sub.2 (.lambda.(a, .LAMBDA.) modq) modp

by using the preparatory information C.sub.1, the exclusive information C.sub.2, and own secret information S.sub.j to thus obtain the common key K which is shared with the chairman terminal, and

(i) the system manager generates arbitrarily a non-zero element e of GF(q), and broadcasts the e to all terminals,

(ii) the system manager calculates a new element

g'=g.sup.1/e modq modp

and replaces the managed element g with it, and

(iii) the respective terminals i calculate new secret information

S.sub.i '=S.sub.i.times.e modq

(at this time, (g').sup.Si' modp=(g).sup.Si modp is satisfied).

51. An exclusive key sharing method for a communication system which consists of a base station and N terminals (N is an integer of more than 2) connected to the base station to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, and a number of terminals which can be specified by the base station (referred to as a "particular terminal number" hereinafter) is 1,

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where S.sub.i =S+f.sub.1.times.i modq (f1 is a non-zero element of GF(q)), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any two terminals out of the N terminals), and

the base station holds (S, p, g, S.sub.1, . . . , S.sub.N),

the base station calculates preparatory information

C.sub.1 =g.sup.k modp

where an element of GF(p) is g and a non-zero element of GF(q) is k,

the base station calculates exclusive information

C.sub.2 =g (k.times.S.sub.a modq) modp,

based on the secret information S.sub.a of the particular terminal a, and broadcasts the exclusive information together with the particular terminal number a and the preparatory information C.sub.1 to all terminals, and

the base station calculates a common key

K=g (k.times.S modq) modp

which is shared with all terminals j (j.noteq.a) except the particular terminal a, and

the respective terminals j (j.noteq.a) calculate a product

C.sub.1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq).times.C.sub.2 (.lambda.(a, .LAMBDA.) modq) modp

of a power residue value of C.sub.1

C.sub.1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq) modp

which uses a product of Si and .lambda.(j, .LAMBDA.) to the modulus q as an exponent and a power residue value of C.sub.2

C.sub.2 (.lambda.(a, .LAMBDA.) modq) modp

which uses .lambda.(a, .LAMBDA.) calculated to the modulus p as the exponent by using the preparatory information C.sub.1, the exclusive information C.sub.2, and own secret information S.sub.j to thus obtain the common key K which is shared with the base station, and

(i) the base station generates arbitrarily a non-zero element e of GF(q), and broadcasts an encrypted e which is encrypted by using the common key K to all terminals,

(ii) the base station calculates a new element

g'=g.sup.1/e modq modp

and replaces the element g with it,

(iii) the respective terminals j decrypt the encrypted e by using the common key K, and calculate new secret information

S.sub.j '=S.sub.j.times.e modq

(at this time, (g').sup.Sj' modp=(g).sup.Sj modp is satisfied).

52. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal (to which any terminal can be appointed) is 1,

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where S.sub.i =S+f.sub.1.times.i modq (f1 is a non-zero element of GF(q)), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any two terminals out of the N terminals), and can use a public key for all terminals

y=g.sup.S modp

and public information

y.sub.1 =g.sup.S1 modp, y.sub.2 =g.sup.S2 modp, . . . , y.sub.N =g.sup.SN modp,

the chairman terminal generates a non-zero element k of GF(q) and calculates preparatory information

C.sub.1 =g.sup.k modp,

the chairman terminal calculates exclusive information

C.sub.2 =y.sub.a.sup.k modp

based on the public information y.sub.a of the particular terminal a, and broadcasts the exclusive information together with the particular terminal number a and the preparatory information C.sub.1 to all terminals, and

the chairman terminal calculates a common key

K=y.sup.k modp,

the respective terminals j (j.noteq.a) calculate .lambda.(j, .LAMBDA.) and .lambda.(a, .LAMBDA.) where .LAMBDA.={j, a}, and calculate

C.sub.1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq).times.C.sub.2 (.lambda.(a, .LAMBDA.) modq) modp

by using the preparatory information C.sub.1, the exclusive information C.sub.2, and own secret information S.sub.j to thus obtain the common key K which is shared with the chairman terminal, and

(i) the chairman terminal generates arbitrarily a non-zero element e of GF(q), and broadcasts an encrypted e which is encrypted by using the common key K to all terminals,

(ii) the chairman terminal calculates a new element

g'=g.sup.1/e modq modp

and replaces the element g with it,

(iii) the respective terminals j decrypt the encrypted e by using the common key K, and calculate new secret information

S.sub.j '=S.sub.j.times.e modq

(at this time, (g').sup.Sj' modp=(g).sup.Sj modp is satisfied).

53. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal b is 1,

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where S.sub.i =S+f.sub.1.times.i modq (f1 is a non-zero element of GF(q)), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any two terminals out of the N terminals), and

the chairman terminal b can use a public key for all terminals

y=g.sup.S modp

and public information

y.sub.1 =g.sup.S1 modp, y.sub.2 =g.sup.S2 modp, . . . , y.sub.N =g.sup.SN modp,

the chairman terminal b generates a non-zero element k of GF(q) and calculates preparatory information

C1.sub.1 =g.sup.k modp,

the chairman terminal b calculates exclusive information

C.sub.2 =y.sub.a.sup.k modp

based on the public information y.sub.a of the particular terminal a, and broadcasts the exclusive information together with the particular terminal number a and the preparatory information C.sub.1 to all terminals, and

the chairman terminal b calculates a common key

K=y.sup.k modp,

the respective terminals j (j.noteq.a, b) calculate .lambda.(j, .LAMBDA.) and .lambda.(a, .LAMBDA.) where .LAMBDA.={j, a}, and calculate

C.sub.1 (S.sub.j.times..lambda.(j, .LAMBDA.) modq).times.C.sub.2 (.lambda.(a, .LAMBDA.) modq) modp

by using the preparatory information C.sub.1, the exclusive information C.sub.2, and own secret information S.sub.j to thus obtain the common key K.

54. An exclusive key sharing method according to claim 5, wherein all terminals except the chairman terminal b can use public information of the chairman terminal b

y.sub.b =g.sup.Sb modp,

the chairman terminal b adds a digital signature to the particular terminal number a, the preparatory information C.sub.1, the exclusive information C.sub.2, which are delivered to all terminals, by using the secret information Sb of the chairman terminal b, and

the respective terminals j verify the signature by using the public information y.sub.b of the chairman terminal.

55. An exclusive key sharing method according to claim 52 wherein the base station and the chairman terminal delivers the element e to the particular terminal number a, and the particular terminal number a calculates new secret information

S.sub.a '=S.sub.a.times.e modq

(at this time, (g') S.sub.a ' modp=(g) S.sub.a modp is satisfied).

56. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where S.sub.i =S+f.sub.1.times.i+ . . . +f.sub.d.times.i.sup.d modq (f.sub.1, . . . , f.sub.d are d elements of GF(q) where f.sub.d.noteq.0), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and the respective terminals i and the chairman terminal .phi. can use a public key of the system

y=g.sup.S modp

which is a power residue value of g having the secret key S as an exponent and p as a modulus, public information

y.sub.1 =g.sup.S1 modp, y.sub.2 =g.sup.S2 modp, . . . , y.sub.N =g.sup.SN modp

which are power residue values of g having the secret information S.sub.1, S.sub.2, . . . , S.sub.N allocated to terminals as exponents respectively and p as the modulus, and the p, q, and g,

(1) the chairman terminal calculates preparatory information

C1=g.sup.k modp (k is a non-zero element of GF(q)),

(2) the chairman terminal calculates exclusive information

C2.sub.i1 =y.sub.i1 (k.times..lambda.(i.sub.1, .alpha.) modq) modp, . . . ,

C2.sub.id =y.sub.id (k.times..lambda.(i.sub.d, .alpha.) modq) modp

based on a set a of d particular terminals i.sub.1, . . . , i.sub.d, .lambda.(i.sub.1, .alpha.), . . . , .lambda.(i.sub.d, .alpha.), and public information y.sub.i1, . . . , y.sub.id, and broadcasts the exclusive information C2.sub.i1, . . . , C2.sub.id together with the preparatory information C1 and the particular terminal number i.sub.1, . . . , i.sub.d to all terminals, and

(3) the chairman terminal calculates a common key

K=y.sup.k modp

which is shared with all terminals j (j.noteq.i.sub.1, . . . , i.sub.d) except the particular terminals i.sub.1, . . . , i.sub.d,

(4) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate .lambda.(j, .LAMBDA..sub.j), .lambda.(i.sub.1, {j, i.sub.1 }), . . . , .lambda.(i.sub.d, {j, i.sub.d }) and

T.sub.j ={.PI.(j-L)}/j (product of L.epsilon..LAMBDA..sub.j -{j} is calculated)

where .LAMBDA..sub.j ={j, i.sub.1, . . . , i.sub.d }, calculate cession keys ##EQU20##

by using the preparatory information C1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and own secret information S.sub.j, and calculates a power residue value of K.sub.j

K.sub.j {circumflex over ( )}(1/T.sub.j modq) modp

which has 1/T.sub.j as an exponent and p as a modulus to thus obtain the common key K (=g.sup.k.times.S modp).

57. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where S.sub.i =S+f.sub.1.times.i+ . . . +f.sub.d.times.i.sup.d modq (f.sub.1, . . . , f.sub.d are d elements of GF(q) where f.sub.d.noteq.0), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and the respective terminals i and the chairman terminal can use a public key of the system

y=g.sup.S modp

which is a power residue value of g having the secret key S as an exponent and p as a modulus, public information

y.sub.1 =g.sup.S1 modp, y.sub.2 =g.sup.S2 modp, . . . , y.sub.N =g.sup.SN modp

which are power residue values of g having the secret information S.sub.1, S.sub.2, . . . , S.sub.N allocated to terminals as exponents respectively and p as the modulus, and the p, q, and g,

(1) the chairman terminal calculates preparatory information

C1=g.sup.k modp (k is a non-zero element of GF(q)),

(2) the chairman terminal calculates exclusive information

C2.sub.i1 =y.sub.i1.sup.k modp, . . . , C2.sub.id =y.sub.id.sup.k modp

based on public information y.sub.i1, . . . , y.sub.id of the d particular terminals i.sub.1, . . . , i.sub.d, and broadcasts the exclusive information C2.sub.i1, . . . , C2.sub.id together with the preparatory information C1 and the particular terminal number i.sub.1, . . . , i.sub.d to all terminals, and

(3) the chairman terminal calculates a common key

K=y.sup.k modp

which is shared with all terminals j (j.noteq.i.sub.1, . . . , i.sub.d) except the particular terminals i.sub.1, . . . , i.sub.d,

(4) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate inverse elements

F.sub.i1 =C2.sub.i1.sup.(-1) modp, . . . , F.sub.id =C2.sub.id.sup.(-1) modp

of the exclusive information C2.sub.i1, . . . , C2.sub.id, calculate .lambda.(j, .LAMBDA..sub.j), .lambda.(i.sub.1, .LAMBDA..sub.j), . . . , .lambda.(i.sub.d, .LAMBDA..sub.j) where .LAMBDA..sub.j ={j, i.sub.1, . . . , i.sub.d }, calculate cession keys ##EQU21##

by using a positive square root t.sub.j of an absolute value of a product of these denominators, the preparatory information C1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and own secret information S.sub.j, replace .lambda.(i.sub.1, .LAMBDA..sub.j) with .vertline..lambda.(i.sub.1, .LAMBDA..sub.j).vertline. and replace C2.sub.i1 with F.sub.i1 if .lambda.(i.sub.1, .LAMBDA..sub.j)<0 while replace .lambda.(i.sub.d, .LAMBDA..sub.j) with .vertline..lambda.(i.sub.d, .LAMBDA..sub.j).vertline. and replace C2.sub.id with F.sub.id if .lambda.(i.sub.d, .LAMBDA..sub.j)<0, and calculates a power residue value of K.sub.j

K.sub.j (1/t.sub.j modq) modp

which has 1/t.sub.j as an exponent and p as a modulus to thus obtain the common key K (=g.sup.k.times.S modp).

58. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where S.sub.i =S+f.sub.1.times.i+ . . . +f.sub.d.times.i.sup.d modq (f.sub.1, . . . , f.sub.d are d elements of GF(q) where f.sub.d.noteq.0), .lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated), and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and the respective terminals i and the chairman terminal can use a public key of the system

y=g.sup.S modp

which is a power residue value of g having the secret key S as an exponent and p as a modulus, public information

y.sub.1 =g.sup.S1 modp, y.sub.2 =g.sup.S2 modp, . . . , y.sub.N =g.sup.SN modp

which are power residue values of g having the secret information S.sub.1, S.sub.2, . . . , S.sub.N allocated to terminals as exponents respectively and p as the modulus, and the p, q, and g,

(1) the chairman terminal calculates preparatory information

C1=g.sup.k modp (k is a non-zero element of GF(q)),

(2) the chairman terminal calculates exclusive information

C2.sub.i1 =y.sub.i1 (k.times..lambda.(i.sub.1, .alpha.) modq) modp, . . . ,

C2.sub.id =y.sub.id (k.times..lambda.(i.sub.d, .alpha.) modq) modp

based on a set .alpha. of d particular terminals i.sub.1, . . . , i.sub.d, .lambda.(i.sub.1, .alpha.), . . . , .lambda.(i.sub.d, .alpha.), and public information y.sub.i1, . . . y.sub.id, and broadcasts the exclusive information C2.sub.i1, . . . , C2.sub.id together with the preparatory information C1 and the particular terminal number i.sub.1, . . . , i.sub.d to all terminals, and

(3) the chairman terminal calculates a common key

K=y.sup.k modp

which is shared with all terminals j (j.noteq.i.sub.1, . . . , i.sub.d) except the particular terminals i.sub.1, . . . , i.sub.d,

(4) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate inverse elements

F.sub.i1 =C2.sub.i1.sup.(-1) modp, . . . , F.sub.id =C2.sub.id.sup.(-1) modp

of the exclusive information C2.sub.i1, . . . , C2.sub.id, calculate .lambda.(j, .LAMBDA..sub.j), .lambda.(i.sub.1, {j, i.sub.1 }), . . . , .lambda.(i.sub.d, {j, i.sub.d }) and

T.sub.j ={.PI.(j-L)}/j (product of L.epsilon..LAMBDA..sub.j -{j} is calculated)

where .LAMBDA..sub.j ={j, i.sub.1, . . . , i.sub.d }, calculate cession keys

K.sub.j =C1 (S.sub.j.times..lambda.(j, .LAMBDA..sub.j).times.T.sub.j modq)

.times.C2.sub.i1 (.lambda.(i.sub.1, {j,i.sub.1 }).times.T.sub.j modq).times.. . .

.times.C2.sub.id (.lambda.(i.sub.d, {j,i.sub.d }).times.T.sub.j modq)modp

by using the preparatory information C.sub.1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and own secret information S.sub.j, replace .lambda.(i.sub.1, {j, i.sub.1 }).times.T.sub.j with .vertline..lambda.(i.sub.1, {j, i.sub.1 }).times.T.sub.j.vertline. and replace C2.sub.i1 with F.sub.i1 if .lambda.(i.sub.1, {j, i.sub.1 }).times.T.sub.j <0 while replace .lambda.(i.sub.d, {j, i.sub.d }).times.T.sub.j.vertline. with .vertline..lambda.(i.sub.d, {j, i.sub.d }).times.T.sub.j.vertline. and replace C2.sub.id with F.sub.id if .lambda.(i.sub.d, {j, i.sub.d }).times.T.sub.j)<0, and calculates a power residue value of K.sub.j

K.sub.j (1/T.sub.j modq) modp

which has 1/T.sub.j as an exponent and p as a modulus to thus obtain the common key K (=g.sup.k.times.S modp).

59. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

S.sub.i =S+f.sub.1.times.i+ . . . +f.sub.d.times.i.sup.d modq

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use a public key of the system

y=g.sup.S modp,

public information

y.sub.1 =g.sup.S1 modp, y.sub.2 =g.sup.S2 modp, . . . , y.sub.N =g.sup.SN modp,

a Hash function hash ( ), and the prime number p, the measure q, and the element g,

(1) the chairman terminal generates arbitrarily a non-zero element k of GF(q), and calculates exclusive information

C2.sub.i1 =y.sub.i1 (k.times..lambda.(i.sub.1, .alpha.) modq) modp, . . . ,

C2.sub.id =y.sub.id (k.times..lambda.(i.sub.d, .alpha.) modq) modp

based on a set .alpha. of d particular terminals i.sub.1, . . . , i.sub.d, .lambda.(i.sub.1, .alpha.), . . . , .lambda.(i.sub.d, .alpha.), and public information y.sub.i1, . . . , y.sub.id, and

(2) the chairman terminal calculates a hash value

H=hash(C2.sub.i1, . . . , C2.sub.id)

which is obtained by compressing the exclusive information C2.sub.i1, . . . , C2.sub.id by using the Hash function hash ( ),

(3) the chairman terminal calculates a signature

Z=H.times.(-S.sub..phi.)+k modq

by using own secret information S.sub..phi., and broadcasts the signature together with the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal number i.sub.1, . . . , i.sub.d, and own terminal number .phi. to all terminals,

(4) the chairman terminal calculates a common key

K=y.sup.k modp,

(5) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.id, .phi.) calculate a hash value H' which is obtained by compressing the exclusive information C2.sub.i1, . . . , C2.sub.id by using the Hash function hash ( ),

(6) the respective terminals j calculate

C1=g.sup.z.times.y.sub..phi..sup.H' modp

(if a signer is surely

the chairman terminal .phi. and also the signature Z, the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal numbers i.sub.1, . . . , i.sub.d, and the terminal number .phi. of the chairman terminal are not tampered, C1=g.sup.k modp and H'=H are calculated) by using public information y.sub..phi. of the chairman terminal,

(7) the respective terminals j calculate .lambda.(j, .LAMBDA..sub.j), .lambda.(i.sub.1, {j, i.sub.1 }), . . . , .lambda.(i.sub.d, {j, i.sub.d }) and

T.sub.j ={.PI.(j-L)}/j (product of L.epsilon..LAMBDA..sub.j -{j} is calculated)

where .LAMBDA..sub.j ={j, i.sub.1, . . . , i.sub.d } calculate cession keys ##EQU22##

by using the preparatory information C1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and own secret information S.sub.j, and calculates a power residue value of K.sub.j

K.sub.j {circumflex over ( )}(1/T.sub.j modq) modp

which has 1/T.sub.j as an exponent and p as a modulus to thus obtain the common key K (=g.sup.k.times.S modp).

60. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

S.sub.i =S+f.sub.1.times.i+ . . . +f.sub.d.times.i.sup.d modq

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use a public key of the system

y=g.sup.S modp,

public information

y.sub.1 =g.sup.S1 modp, y.sub.2 =g.sup.S2 modp, . . . , y.sub.N =g.sup.SN modp,

a Hash function hash ( ), and the prime number p, the measure q, and the element g,

(1) the chairman terminal generates arbitrarily a non-zero element k of GF(q), and calculates exclusive information

C2.sub.i1 =y.sub.i1.sup.k modp, . . . , C2.sub.id =y.sub.id.sup.k modp

based on public information y.sub.i1, . . . , y.sub.id of the d particular terminals i.sub.1, . . . , i.sub.d, and

(2) the chairman terminal calculates a hash value

H=hash(C2.sub.i1, . . . , C2.sub.id)

which is obtained by compressing the exclusive information C2.sub.i1, . . . , C2.sub.id by using the Hash function hash ( ),

(3) the chairman terminal calculates a signature

Z=H.times.(-S.sub..phi.)+k modq

by using own secret information S.sub..phi., and broadcasts the signature Z together with the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal number i.sub.1, . . . , i.sub.d, and own terminal number .phi. to all terminals,

(4) the chairman terminal calculates a common key

K=y.sup.k modp,

(5) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate a hash value H' which is obtained by compressing the exclusive information C2.sub.i1, . . . , C2.sub.id by using the Hash function hash ( ),

(6) the respective terminals j calculate

C1=g.sup.z.times.y.sub..phi..sup.H' modp

(if a signer is surely

the chairman terminal .phi. and also the signature Z, the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal numbers i.sub.1, . . . , i.sub.d, and the terminal number .phi. of the chairman terminal are not tampered, C1=g.sup.k modp and H'=H are calculated) by using public information y.sub..phi. of the chairman terminal,

(7) the respective terminals j calculate inverse elements

F.sub.i1 =C2.sub.i1.sup.(-1) modp, . . . , F.sub.id =C2.sub.id.sup.(-1) modp

of the exclusive information C2.sub.i1, . . . , C2.sub.id, calculate .lambda.(j, .LAMBDA..sub.j), .lambda.(i.sub.1, {j, i.sub.1 }), . . . , .lambda.(i.sub.d, {j, i.sub.d }) where .LAMBDA..sub.j ={j, i.sub.1, . . . , i.sub.d }, calculate cession keys ##EQU23##

by using a positive square root t.sub.j of an absolute value of a product of these denominators, the preparatory information C1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and own secret information S.sub.j, replace .lambda.(i.sub.1, .LAMBDA..sub.j) with .vertline..lambda.(i.sub.1, .LAMBDA..sub.j).vertline. and replace C2.sub.i1 with F.sub.i1 if .lambda.(i.sub.1, .LAMBDA..sub.j)<0 while replace .lambda.(i.sub.d, .LAMBDA..sub.j) with .vertline..lambda.(i.sub.d, .LAMBDA..sub.j).vertline. and replace C2.sub.id with F.sub.id if .lambda.(i.sub.d, .LAMBDA..sub.j)<0, and calculates a power residue value of K.sub.j

K.sub.j (1/t.sub.j modq) modp

which has 1/t.sub.j as an exponent and p as a modulus to thus obtain the common key K (=.sup.k.times.S modp).

61. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are S, a prime number which is larger than S and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information Si in secret to satisfy

S=.SIGMA..lambda.(i, .LAMBDA.).times.S.sub.i (sum of i.epsilon..LAMBDA. is calculated)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

S.sub.i =S+f.sub.1.times.i+ . . . +f.sub.d.times.i.sup.d modq

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use a public key of the system

y=g.sup.S modp,

public information

y.sub.1 =g.sup.S1 modp, y.sub.2 =g.sup.S2 modp, . . . , y.sub.N =g.sup.SN modp,

a Hash function hash ( ), and the prime number p, the measure q, and the element g,

(1) the chairman terminal generates arbitrarily a non-zero element k of GF(q), and calculates exclusive information

C2.sub.i1 =y.sub.i1 (k.times..lambda.(i.sub.1, .alpha.) modq) modp, . . . ,

C2.sub.id =y.sub.id (k.times..lambda.(i.sub.d, .alpha.) modq) modp

based on a set .alpha. of d particular terminals i.sub.1, . . . , i.sub.d, .lambda.(i.sub.1, .alpha.), . . . , .lambda.(i.sub.d, .alpha.), and public information y.sub.i1, . . . , y.sub.id, and

(2) the chairman terminal calculates a hash value

H=hash(C2.sub.i1, . . . , C2.sub.id)

which is obtained by compressing the exclusive information C2.sub.i1, . . . , C2.sub.id by using the Hash function hash ( ),

(3) the chairman terminal calculates a signature

Z=H.times.(-S.sub..phi.)+k modq

by using own secret information S.sub..phi., and broadcasts the signature Z together with the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal number i.sub.1, . . . , i.sub.d, and own terminal number .phi. to all terminals,

(4) the chairman terminal calculates a common key

K=y.sup.k modp,

(5) the respective terminals j (j.noteq.i.sub.1, . . . , i.sub.d, .phi.) calculate a hash value H' which is obtained by compressing the exclusive information C2.sub.i1, . . . , C2.sub.id by using the Hash function hash ( ),

(6) the respective terminals j calculate

C1=g.sup.z.times.y.sub..phi..sup.H' modp

(if a signer is surely

the chairman terminal .phi. and also the signature Z, the exclusive information C2.sub.i1, . . . , C2.sub.id, the particular terminal numbers i.sub.1, . . . , i.sub.d, and the terminal number .phi. of the chairman terminal are not tampered, C1=g.sup.k modp and H'=H are calculated) by using public information y.sub..phi. of the chairman terminal,

(7) the respective terminals j calculate inverse elements

F.sub.i1 =C2.sub.i1.sup.(-1) modp, . . . , F.sub.id =C2.sub.id.sup.(-1) modp

of the exclusive information C2.sub.i1, . . . , C2.sub.id, calculate .lambda.(j, .LAMBDA..sub.j), .lambda.(i.sub.1, {j, i.sub.1 }), . . . , .lambda.(i.sub.d, {j, i.sub.d }) and

T.sub.j ={.PI.(j-L)}/j (product of L.epsilon..LAMBDA..sub.j -{j} is calculated)

where .LAMBDA..sub.j ={j, i.sub.1, . . . , i.sub.d }, calculate cession keys ##EQU24##

by using the preparatory information C1, the exclusive information C2.sub.i1, . . . , C2.sub.id, and own secret information S.sub.j, replace .lambda.(i.sub.1, {j, i.sub.1 }).times.T.sub.j with .vertline..lambda.(i.sub.1, {j, i.sub.1 }).times.T.sub.j.vertline. and replace C2.sub.i1 with F.sub.i1 if .lambda.(i.sub.1, {j, i.sub.1 }).times.T.sub.j <0 while replace .lambda.(i.sub.d, {j, i.sub.d }).times.T.sub.j) with .vertline..lambda.(i.sub.d, {j, i.sub.d }).times.T.sub.j.vertline. and replace C2.sub.id with F.sub.id if .lambda.(i.sub.d, {j, i.sub.d }).times.T.sub.j)<0, and calculates a power residue value of K.sub.j

K.sub.j (1/T.sub.j modq) modp

which has 1/T.sub.j as an exponent and p as a modulus to thus obtain the common key K (=g.sup.k.times.S modp).

62. An exclusive key sharing method for a communication system which consists of N terminals (N is an integer of more than 2) connected mutually to allow broadcast communication,

wherein secret keys are .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma., a prime number which is larger than .alpha.1, .alpha.2, .beta.1, .beta.2, .gamma. and N or a power number of the prime number is p, a measure of (p-1) is q, elements of GF(p) are g1, g2, and a particular terminal number which can be specified by a chairman terminal .phi. (to which any terminal can be appointed) is d (1.ltoreq.d<N-1),

respective terminals i (1.ltoreq.i.ltoreq.N) hold secret information .alpha.1.sub.i, .alpha.2.sub.i, .beta.1.sub.i, .beta.2.sub.i, .gamma..sub.i in secret to satisfy

.alpha.1=.SIGMA..lambda.(i, .LAMBDA.).times..alpha.1.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .alpha.1.sub.i =.alpha.1+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.alpha.2=.SIGMA..lambda.(i, .LAMBDA.).times..alpha.2.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .alpha.2.sub.i =.alpha.2+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.beta.1=.SIGMA..lambda.(i, .LAMBDA.).times..beta.1.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .beta.1.sub.i =.beta.1+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.beta.2=.SIGMA..lambda.(i, .LAMBDA.).times..beta.2.sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .beta.2.sub.i =.beta.2+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.gamma.=.SIGMA..lambda.(i, .LAMBDA.).times..gamma..sub.i (sum of i.epsilon..LAMBDA. is calculated)

(where .gamma..sub.i =.gamma.+f.sub.1.times.i.sup.1 + . . . +f.sub.d.times.i.sup.d modq)

.lambda.(i, .LAMBDA.)=.PI.{L/(L-i)} (product of L.epsilon..LAMBDA.-{i} is calculated)

(where f.sub.1, . . . , f.sub.d are d elements of GF(q), f.sub.d.noteq.0, and .LAMBDA. is a set of any (d+1) terminals out of the N terminals), and can use public keys of the system

A=g.sub.1.sup..alpha.1 g.sub.2.sup..alpha.2 modp, B=g.sub.1.sup..beta.1 g.sub.2.sup..beta.2 modp, .GAMMA.=g.sub.1.sup..gamma. modp,

public information

A.sub.1 =g.sub.1.sup..alpha.11 g.sub.2.sup..alpha.21 modp, . . . , A.sub.N =g.sub.1.sup..alpha.1N g.sub.2.sup..alpha.2N modp