Key distribution method and system in secure broadcast communication

• US 6,041,408 A
• Filed: 06/25/1997
• Issued: 03/21/2000
• Est. Priority Date: 06/28/1996
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Matsui, Susumu, Nishioka, Mototsugu, Umeki, Hisashi
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Callahan, Paul E.
• Application Number:
  US08/882,339
• Time in Patent Office: 1,000 Days
• Field of Search: 713/162, 713/163, 713/171, 380/262, 380/278-280, 380/283, 380/284
• US Class Current: 713/171
• CPC Class Codes: H04L 2209/601 Broadcast encryption
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]

Abstract

A key distribution method and system are disclosed in which a sender and receivers share a common key information for performing a secure broadcast communication. By use of a center side apparatus, a center generates key information of a receiver in association with a subset inclusive of two or more elements of a proper finite set S1 on the basis of a space determined by a subset inclusive of two or more elements of another finite set S2. A sender side apparatus, a sender makes the multi-address transmission of key distribution data W inclusive of data generated corresponding to each element of the finite set S1 and data generated corresponding to a set of plural receivers through a communication network. By use of a receiver side apparatus, a receiver generates common key information between the sender and the receiver from the key distribution data W and the key information of the receiver.

Claims

1. A key distribution system in which a sender and a plurality of receivers use individual key information generated beforehand by a key generator to share a common key information for performing a secure broadcast communication, wherein

(i) the key generator side is provided with:

means for generating confidential information of a receiver in association with a subset inclusive of at least two elements of a first finite set S1 on the basis of a space determined by a subset inclusive of at least two elements of a second finite set S2; and

means for distributing said confidential information to the receiver,

(ii) the sender side is provided with;

means for generating key distribution data corresponding to each element of said first finite set S1; and

communication means for making the multi-address transmission of said key distribution data,

and (iii) the receiver side is provided with;

storage means for storing said confidential information beforehand; and

means for calculating common key information K between the sender and the receiver from the stored confidential information for each receiver and the key distribution data.

5. A key distribution system according to claim 1, wherein

(i) said key generator side comprises:

means for generating

P_i, Q_i ;

prime number (1≦

i≦

m)

L_i =lcm(ord_p.sbsb.i (g), ord_Q.sbsb.i (g)) (1≦

i≦

m)

e_i .di-elect cons.Z, 0<

e_i <

L=lcm(L₁, L₂, . . . , L_m) (1≦

i≦

n)

as confidential information of the key generator;

means for generating

N_i =P_i Q_i (1≦

i≦

m)

g.di-elect cons.Z, 0<

g<

N ##EQU46## as public information of the key generator;

storage means for storing said confidential information and said public information;

means for acquiring key information of the key generator for σ

_x .di-elect cons.S and τ

.di-elect cons.T from said storage means to calculate S_x,τ

=(S_x,τ

(1), S_x,τ

(2), . . . , S_x,τ

(d) satisfying ##EQU47## means for distributing s_x,τ

as key information of the receiver x, wherein

L.sub.σ

=lcm(L.sub.σ

(1), L.sub.σ

(2), . . . , L.sub.σ

(k)) (σ

.di-elect cons.S);

h₁ (X₁, . . . , X_n) (1≦

i≦

M) represents a monomial of X₁, . . . , X_n on Z;

for set S'"'"'={f|one-to-one map f;

A={1, 2, . . . , k}→

B={1, 2, . . . , m}, m>

K}, σ

₁, σ

₂ .di-elect cons.S'"'"', a relation "˜

" on S'"'"' is defined as ##EQU48## and a quotient set of S'"'"' concerning "˜

" is defined as S; and

set T={f|one-to-one map f;

A={1, 2, . . . , d}→

B={1, 2, . . . , M}, M≧

d};

means for randomly selecting for any receiver x an integer r which satisfies

space="preserve" listing-type="equation">0<

K=g.sup.r mod N, ##EQU49## means for calculating

space="preserve" listing-type="equation">z.sub.i =v.sub.i.sup.r mod N (1≦

i≦

M)

as broadcast communication data from the public information of the key generator with the object of possessing K as a common key; and

communication means for making the multi-address transmission of said broadcast communication data, wherein ##EQU50## and (ii) said receiver x side comprises;

means for calculating the common key K from said broadcast communication data and said confidential information S_x,τ

=(S_x,τ

(1), S_x,τ

(2), . . . , S_x,τ

(d)) of the receiver x distributed by the key generator in accordance with ##EQU51## and wherein Z represents a set of the whole of integers;

lcm(a,b) represents the lowest common multiple of integers a and b,

ord_p (g) represents the least integer x which satisfies g^x .tbd.1(mod p); and

min {a₁, a₂, . . . , a_n } represents the least value in a₁, a₂, . . . , a_n (a_i .di-elect cons.Z).

6. A key distribution system according to claim 1, 10 wherein

(i) said key generator side comprises:

means for generating

P_i, Q_i ;

prime number (1≦

i≦

m)

e_i .di-elect cons.Z, 0<

e_i <

L=lcm(L₁, L₂, . . . , L_m) (1≦

i≦

n)

as confidential information of the key generator;

means for generating

N_i =P_i Q_i (1≦

i≦

m)

g_i .di-elect cons.Z, 0<

g_i <

N (1≦

i≦

M) ##EQU52## V=(v_ij), v_ij =g_i^h j.sup.(e.sbsp.1.sup., . . . , e.sbsp.n.sup.) mod N (1≦

i,j≦

M),

as public information of the key generator;

storage means for storing said confidential information and said public information;

means for acquiring key information of the key generator for σ

_x =(σ

_x,1, . . . , σ

_x,a) .di-elect cons.S, σ

'"'"'_x =(σ

'"'"'_x,1, . . . , σ

'"'"'_x,a) .di-elect cons.T from said storage means to calculate S.sub.σ

.sbsb.x =((Sσ

.sbsb.x,1.sub.(1), S.sub.σ

.sbsb.x,1.sub.(2), . . . , S.sub.σ

.sbsb.x,1.sub.(k)), . . . , (S.sub.σ

.sbsb.x,a.sub.(1), S.sub.σ

.sbsb.x,a.sub.(2), . . . , S.sub.σ

.sbsb.x,a.sub.(k))) satisfying ##EQU53## means for distributing s.sub.σ

.sbsb.x and ##EQU54## as key information of the receiver x, wherein ##EQU55## (1≦

i≦

M) represents a monomial of X₁, . . . , X_n on Z;

for set S'"'"'(M)={σ

=(σ

₁, . . . , σ

_a)|one-to-one map σ

_i ;

A={1, 2, . . . , k}→

B={1, 2, . . . , M}(i=1, . . . , a), σ

₁ (A) U . . . Uσ

_a (A)=B, M=ak}, σ

=(σ

₁, . . . , σ

_a), σ

'"'"'=(σ

'"'"'₁, . . . , σ

'"'"'_a) .di-elect cons.S'"'"' (M), a relation of ##EQU56## is defined and a quotient set of S'"'"'(M) concerning "˜

" is defined as S; and

a quotient set of m=ad, S'"'"'(m) concerning "˜

" is defined as T;

means for randomly selecting for any receiver x an integer r which satisfies ##EQU57## means for calculating broadcast communication data

space="preserve" listing-type="equation">W=(w.sub.ij), w.sub.ij =v.sub.ij.sup.r mod N (1≦

i,j≦

M)

from the public information of the key generator with the object of possessing K as a common key; and

communication means for making the multi-address transmission of said broadcast communication data, and (ii) said receiver x side comprises;

means for calculating the common key K from said broadcast communication data and said confidential information S.sub.σ

.sbsb.x of the receiver x distributed by the key generator in accordance with ##EQU58## wherein ##EQU59## and wherein Z represents a set of the whole of integers;

lcm(a,b) represents the lowest common multiple of integers a and b; and

ord_N (g) represents the least integer x which satisfies g^x .tbd.1(mod N) for integers N and g.

9. A key distribution system according to claim 5, wherein said key generator side further comprises means for selecting the key information s_x,τ

of the receiver x to satisfy a condition of

space="preserve" listing-type="equation">π

.sub.x ≠

g

for any receiver x.

10. A key distribution system according to claim 6, wherein said key generator side further comprises means for selecting the key information s.sub.σ

.sbsb.x of the receiver x to satisfy so that ##EQU74## is satisfied.

2. A key distribution system in a limited secure broadcast communication in which a broadcasting station as a sender communicates with only receivers limited beforehand from among a plurality of receivers, wherein

(i) the sender side is provided with:

means for generating confidential information of a receiver in association with a subset inclusive of at least two elements of a finite set S;

means for distributing said confidential information to the receiver;

means for generating key distribution data corresponding to each element of said finite set S;

communication means for making the multi-address transmission of said key distribution data;

means for generating individual information for each receiver to be transmitted to only said limited receivers; and

communication means for transmitting said individual information for each limited receiver x,

and (ii) the receiver x side is provided with;

means for storing said confidential information; and

means for calculating common key information K between the sender side and the receiver from said confidential information s_x for each receiver distributed by said sender side, said key distribution data and said individual information.

3. A key distribution system according to claim 2, wherein said sender side is further provided wilt means for changing said key distribution data to change the value of said common key.

4. A key distribution system according to claim 2, wherein said receiver x side is provided with authentication means for making the authentication for the sender side by use of said confidential information s_x in the case where transmit data is onerous indicating that a fee is charged, and said sender side is provided with communication means for transmitting said individual information V_x if the authentication requested from the receiver side is materialized.

7. A key distribution system according to claim 2, wherein

(i) said broadcasting station side comprises:

means for generating

P_i, Q_i ;

prime number (1≦

i≦

m)

L_i =lcm(ord_p.sbsb.i (g), ord_Q.sbsb.i (g)) (1≦

i≦

m)

e_i .di-elect cons.Z, 0<

e_i <

L=lcm (L₁, L₂, . . . , L_m) (1≦

i≦

n)

as confidential information of the broadcasting station;

means for generating ##EQU60## as public information of the broadcasting station;

storage means for storing said confidential information and said public information;

means for generating random numbers r'"'"' (0<

r'"'"'<

L);

means for acquiring key information of the broadcasting station for σ

_x .di-elect cons.S and τ

.di-elect cons.T from said storage means to calculate S_x,τ

=(S_x,τ

(1), S_x,τ

(2), . . . , S_x,τ

(d)), U_x,τ

=(U_x,τ

(1), U_x,τ

(2), . . . , U_x,τ

d)) satisfying ##EQU61## means for distributing s_x,τ

as key information of the receiver x, wherein L.sub.σ

=lcm (L.sub.σ

(1), L.sub.σ

(2), . . . , L.sub.σ

(k)) (σ

.di-elect cons.S);

h_i (X₁, . . . , X_n) (1≦

i≦

M) represents a monomial of X₁, . . . , X_n on Z;

for set S'"'"'={f|one-to-one map f;

A={1, 2, . . . , k}→

B={1, 2, . . . , m), m≧

K}, σ

₁, σ

₂ .di-elect cons.S'"'"', a relation "˜

" on S'"'"' is defined as σ

₁ ˜

σ

₂ ##EQU62## and a quotient set of S'"'"' concerning "˜

" is defined as S; and

set T={f|one-to-one map f;

A={1, 2, . . . , d}→

B={1, 2, . . . , M}, M≧

d};

means for randomly selecting for any receiver x an integer r (0≦

r≦

L) which satisfies

<

K=g^rr'"'"' mod N, ##EQU63## means for acquiring the key information of the broadcasting station from said storage means of said broadcasting station side to calculate

space="preserve" listing-type="equation">z.sub.i =v.sub.i.sup.r mod N (1≦

i≦

M)

with the object of sharing a key K in common with the limited receivers;

communication means for making the multi-address transmission of z_i (1≦

i≦

M), wherein ##EQU64## and communication means for transmitting u_x,τ

=(u_x,τ

(1), u_x,τ

(2), . . . , u_x,τ

(d)) to the limited receivers, and (ii) said receiver x side comprises;

means for calculating the common key K from the broadcast communication data, said confidential information s_x,τ

the receiver x distributed by the broadcasting station and u_x,τ

in accordance with ##EQU65## and wherein Z represents a set of the whole of integers;

lcm(a,b) represents the lowest common multiple of integers a and b; and

ord_p (g) represents the least integer x which satisfies g^x .tbd.1(mod p).

8. A key distribution system according to claim 2, wherein

(i) said broadcasting station side comprises:

means for generating

P_i, Q_i ;

prime number (1≦

i≦

m)

e_i .di-elect cons.Z, 0<

e_i <

L=lcm(L₁, L₂, . . . , L_m) (1≦

i≦

n)

as confidential information of the broadcasting station;

means for generating

N_i =P_i Q_i (1≦

i≦

m)

g_i .di-elect cons.Z, 0<

g_i <

N (1≦

i≦

M) ##EQU66## V=(v_ij), v_ij =g_i^h j.sup.(e.sbsp.1, . . . , e.sbsp.n) mod N (1≦

i,j≦

M)

as public information of the broadcasting station;

storage means for storing said confidential information and said public information of the broadcasting station;

means for generating random numbers r'"'"' (0<

r'"'"'<

L);

means for acquiring key information of the broadcasting station for σ

_x =(σ

_x,1, . . . , σ

_x,a) .di-elect cons.S, σ

'"'"'_x =(σ

'"'"'_x,1, . . . , σ

'"'"'_x,a) .di-elect cons.T from said storage means of said broadcasting station side to calculate S.sub.σ

.sbsb.x =((S.sub.σ

.sbsb.x,1.sub.(1), S.sub.σ

.sbsb.x,1.sub.(2), . . . , S.sub.σ

.sbsb.x,1.sub.(1)), . . . , (S.sub.σ

.sbsb.x,a.sub.(1), S.sub.σ

.sbsb.x,a.sub.(2), . . . , S.sub.σ

.sbsb.x,a.sub.(k))), U.sub.σ

.sbsb.x =((U.sub.σ

.sbsb.x,1.sub.(1), U.sub.σ

.sbsb.x,1.sub.(2), . . . , U.sub.σ

.sbsb.x,1.sub.(k)), U.sub.σ

.sbsb.x,a.sub.(1), U.sub.σ

.sbsb.x,a.sub.(2), . . . , U.sub.σ

.sbsb.x,a.sub.(k))) satisfying ##EQU67## means for distributing s_x,τ and

##EQU68## as key information of the receiver x, wherein ##EQU69## h_i (X₁, . . . , X_n) (1≦

i≦

M) represents a monomial of X₁, . . . , X_n on Z;

for set S(M)={σ

=(σ

₁, . . . , σ

_a)|one-to-one map σ

_i ;

A={1, 2, . . . , k}→

B={1, 2, . . . , M}(i=1, . . . , a), σ

₁ (A) U . . . Uσ

_a (A)=(B), M=ak}, σ

=(σ

₁, . . . , σ

_a), σ

'"'"'=(σ

'"'"'₁, . . . , σ

'"'"'_a) .di-elect cons.S(M), a relation of ##EQU70## . . . , σ

_a (A)}={σ

'"'"'₁ (A), . . . , σ

'"'"'_a (A)} is defined and a quotient set of S(M) concerning "˜

" is defined as S; and

a quotient set of m=ad, S(m) concerning "˜

" is defined as T;

means for randomly selecting for any receiver x an integer r (0≦

r≦

L) which satisfies ##EQU71## (i=1, . . . a)

means for acquiring the key information of the broadcasting station from said storage means of said broadcasting station side to calculate

space="preserve" listing-type="equation">W=(w.sub.ij), w.sub.ij =v.sub.ij =ij.sup.r mod N (1≦

i,j≦

M)

with the object of sharing a key K in common with the limited receivers;

communication means for making the multi-address transmission of W; and

communication means for transmitting U.sub.σ

.sbsb.x =((u.sub.σ

.sbsb.x,1.sub.(1), u.sub.σ

.sbsb.x,1.sub.(2), . . . , u.sub.σ

.sbsb.x,1.sub.(k)), . . . , (u.sub.σ

.sbsb.x,a.sub.(1), u.sub.σ

.sbsb.x,a.sub.(2), . . . , u.sub.σ

.sbsb.x,a.sub.(k))) to the limited receivers;

and (ii) said receiver x side comprises;

means for calculating the common key K from the broadcast communication data, said confidential information s.sub.σ

.sbsb.x of the receiver x distributed by the broadcasting station and u.sub.σ

.sbsb.x in accordance with ##EQU72## wherein ##EQU73## and wherein Z represents a set of the whole of integers;

lcm(a,b) represents the lowest common multiple of integers a and b; and

ord_N (g) represents the least integer x which satisfies g^x .tbd.1(mod N) for integers N and g.

11. A key distribution system according to claim 8, wherein said broadcasting station side further comprises means for selecting the key information s.sub.σ

x of the receiver x to satisfy so that ##EQU75## is satisfied.

12. A key distribution system according to claim 7, wherein said broadcasting station side further comprises means for changing the value of the common key K by changing the value of r of the common key K=g^rr'"'"' mod N.

13. A key distribution system according to claim 7, wherein said broadcasting station side further comprises means for identifying transmit data by taking the value of r'"'"' of the common key K=g^rr'"'"' mod N as a value characteristic of the transmit data.

14. A key distribution system according to claim 7, wherein the limited receiver x side comprises authentication means for making the authentication for the broadcasting station side by use of the confidential information s_x,τ

and means for receiving u_x,τ

after the authentication is made by said authentication means, and wherein the broadcasting station side comprises accounting means by which in the case where data P enciphered using the common key K is onerous indicating that a fee is charged, a process for account of a charge for P to the receiver x is performed.

15. A key distribution system according to claim 7, wherein in the case where the receiver x possesses a storage medium with a computing function having the confidential key s_x,τ

and connects said storage medium to a receiving unit having a higher computing function to calculate the common key ##EQU76## said receiving unit comprises;

means for performing the calculation of

space="preserve" listing-type="equation">ξ

.sub.x'"'"'τ

(i) =z.sub.τ

(i).sup.u.sbsp.x,τ

(i) mod N (1≦

i≦

d);

means for outputting ξ

_x,τ

(i) (1≦

i≦

d) to said storage medium; and

means for performing the calculation of ##EQU77## on the basis of information from said storage medium, and said storage medium comprises;

means for performing the calculation of

space="preserve" listing-type="equation">η

.sub.x,τ

(i) =ξ

.sub.x,τ

(i).sup.s x,τ

(i) mod N (1≦

i≦

d)

on the basis of information from said receiving unit; and

means for outputting η

_x,τ

(i) (1≦

i≦

d) to said receiving unit.

16. A key distribution system according to claim 8, wherein in the case where the receiver x possesses a storage medium with a computing function having the confidential key s.sub.σ

.sbsb.x and connects said storage medium to a receiving unit having a higher computing function to calculate the common key K, said storage medium comprises means for performing a calculation using confidential information, and said receiving unit comprises means for means for performing a calculation using no confidential information.

17. A key distribution system according to claim 2, wherein

(i) said broadcasting station side comprises:

means for generating

P_i, Q_i ;

prime number

e_i .di-elect cons.Z, 0<

e_i <

L=lcm(P-1, Q-1) (1≦

i≦

m)

as confidential information of the broadcasting station;

means for generating

N=PQ

as public information of the broadcasting station;

storage means for storing said confidential information and said public information;

means for generating random numbers r .di-elect cons.Z, π

=(π

₁, . . . , π

_l) .di-elect cons.R_k,n ;

means for acquiring key information of the broadcasting station for σ

=(σ

₁, . . . , σ

_l) .di-elect cons.S_k,n from said storage means of said broadcasting station side to calculate S_x,τ

(π

,σ

) =(S_x,π

.sbsb.1.sub.(1), . . . , S_x,π

.sbsb.1.sub.(h), . . . , S_x,π

.sbsb.l.sub.(1), . . . , S_x,π

.sbsb.l.sub.(h)), r_x,(π

,σ

) =(r_x,π

.sbsb.1.sub.(1), . . . , r_x,π

.sbsb.1.sub.(h), . . . , r_x,π

.sbsb.l.sub.(1), . . . , r_x,π

.sbsb.l.sub.(h)) satisfying ##EQU78## means for distributing s_x,(π

,σ

) as key information of the receiver x, wherein ##EQU79## when σ

=(σ

(σ

₁, . . . , σ

_l), (σ

'"'"'₁, . . . , σ

'"'"'_l), .di-elect cons.S'"'"'_k,n for n=kl, set R_k,n ={π

=(π

₁, . . . , π

_l)|one-to-one map π

_i ;

{1, 2, . . . , h}→

{1, 2, . . . , m}(1≦

i≦

l,1≦

h≦

m)}, set S'"'"'_k,n ={σ

=(σ

₁, . . . , σ

_l)|one-to-one map σ

_i ;

A={1, 2, . . . , k}→

B={1, 2, . . . , n}(1≧

i≧

l), σ

₁ (A) U . . . Uσ

_l (A)=B}, a relation of ##EQU80## is defined in regard to proper permutation τ

on a set {1, 2, . . . , l}, "˜

" representing an equivalent relation on S and S'"'"'_k,n being S_k,n =S'"'"'_k,n /˜

;

means for randomly selecting r.di-elect cons.Z for g_i .di-elect cons.Z (0<

g_i <

N, 1≦

i≦

n=kl) in said storage means of said broadcasting station side;

means for calculating ##EQU81## means for acquiring the key information of the broadcasting station from said storage means of said broadcasting station side to calculate

space="preserve" listing-type="equation">y.sub.ij =u.sub.ij.sup.r mod N (1≦

i≦

m, 1≦

j≦

n)

with the object of sharing a key K in common with only the limited receivers;

means for making the multi-address transmission of y_ij (1≦

i≦

m, 1≦

j≦

n); and

means for transmitting r_x,(π

,σ

) =(r_x,π

.sbsb.1.sub.(1), . . . , r_x,π

.sbsb.1.sub.(h), . . . , r_x,π

.sbsb.l.sub.(1), . . . , r_x,π

.sbsb.l.sub.(h)) to the limited receivers x,

and (ii) said receiver x side comprises;

means for calculating the common key K from the broadcast communication data, said confidential information s_x,(π

,σ

) of the receiver x distributed by the broadcasting station and r_x,(π

,σ

) in accordance with ##EQU82## and wherein Z represents a set of the whole of integers;

lcm(a,b) represents the lowest common multiple of integers a and b; and

ord_N (g) represents the least positive integer x which satisfies g^x .tbd.1(mod N) for integers N and g.

18. A key distribution system according to claim 7, wherein said broadcasting station side further comprises means for selecting the key information s_x,τ

of the receiver x to satisfy a condition of

space="preserve" listing-type="equation">π

.sub.x ≠

g

for any receiver x.

19. A key distribution system according to claim 8, wherein said broadcasting station side further comprises means for changing the value of the common key K by changing the value of r of the common key K=g^rr'"'"' mod N.

20. A key distribution system according to claim 8, wherein said broadcasting station side further comprises means for identifying transmit data by taking the value of r'"'"' of the common key K=g^rr'"'"' mod N as a value characteristic of the transmit data.

21. A key distribution system according to claim 8, wherein the limited receiver x side comprises authentication means for making the authentication for the broadcasting station side by use of the confidential information s.sub.σ

x'"'"' and means for receiving u.sub.σ

x, after the authentication is made by said authentication means, and wherein the broadcasting station side comprises accounting means by which in the case where data P enciphered using the common key K is onerous indicating that a fee is charged, a process for account of a charge for P to the receiver x is performed.

22. A key distribution method in which a sender and a plurality of receivers use individual key information generated beforehand by a key generator to share a common key information for performing a secure broadcast communication, wherein

(i) the key generator side is provided with the steps of:

generating confidential information of a receiver in association with a subset inclusive of at least two elements of a first finite set SI on the basis of a space determined by a subset inclusive of at least two elements of a second finite set S2; and

distributing said confidential information to the receiver,

(ii) the sender side is provided with;

generating key distribution data corresponding to each element of said first finite set S1; and

making the multi-address transmission of said key distribution data,

and (iii) the receiver side is provided with the steps of;

storing said confidential information beforehand; and

calculating common key information K between the sender and the receiver from the stored confidential information for each receiver and the key distribution data.

26. A key distribution method according to claim 22, wherein

(i) as a preparatory process,

said key generator side is provided with the steps of:

generating

P_i, Q_i ;

prime number (1≦

i≦

m)

L_i =lcm(ord_p.sbsb.i (g), ord_Q.sbsb.i (g)) (1≦

i≦

m)

e_i .di-elect cons.Z, 0<

e_i <

L=lcm(L₁, L₂, . . . , L_m) (1≦

i≦

n)

as confidential information of the key generator;

generating ##EQU83## as public information of the key generator;

storing said confidential information and said public information of said key generator into storage means;

acquiring key information of the key generator for σ

_x .di-elect cons.S and τ

_x .di-elect cons.T from said storage means to calculate S_x,τ

=(S_x,τ

(1), S_x,τ

(2), . . . , S_x,τ

(d)), satisfying ##EQU84## distributing s_x,τ

as key information of the receiver x, wherein L.sub.σ

=lcm (L.sub.σ

(1), L.sub.σ

(2), . . . , L.sub.σ

(k)) (σ

.di-elect cons.S);

h_i (X₁, . . . , X_n) (1≦

i≦

M) represents a monomial of X₁, . . . , X_n on Z;

for set S'"'"'={f|one-to-one map f;

A={1, 2, . . . , k}→

B={1, 2, . . . , m}, m≧

K}, σ

₁, σ

₂ .di-elect cons.S'"'"', a relation "˜

" on S'"'"' is defined as ##EQU85## and a quotient set of S'"'"' concerning "˜

" is defined as S; and

set T={f|one-to-one map f;

A={1, 2, . . . , d}→

B={1, 2, . . . , M), M≧

d},

and (ii) as a key distribution process,

(1) the sender side is provided with the steps of;

randomly selecting for any receiver x an integer r which satisfies

space="preserve" listing-type="equation">0<

K=g.sup.r mod N, ##EQU86## calculating

space="preserve" listing-type="equation">z.sub.i =v.sub.i.sup.r mod N (1≦

i≦

M)

as broadcast communication data from the public information of the key generator with the object of possessing K as a common key; and

making the multi-address transmission of said broadcast communication data, wherein ##EQU87## and (2) said receiver x side is provided with;

a step of calculating the common key K from said broadcast communication data and said confidential information S_x,τ

=(S_x,τ

(1), S_x,τ

(2), . . . , S_x,τ

(d)) of the receiver x distributed by the key generator in accordance with ##EQU88## and wherein Z represents a set of the whole of integers;

lcm(a,b) represents the lowest common multiple of integers a and b;

ord_p (g) represents the least integer x which satisfies g^x .tbd.1(mod p); and

min {a₁, a₂, . . . , a_n } represents the least value in a₁, a₂, . . . , a_n (a_i .di-elect cons.Z).

27. A key distribution method according to claim 22, wherein

(i) as a preparatory process,

said key generator side is provided with the steps of:

generating

P_i, Q_i ;

prime number (1≦

i≦

m)

e_i .di-elect cons.Z, 0<

e_i <

L=lcm(L₁, L₂, . . . , L_m) (1≦

i≦

n)

as confidential information of the key generator;

generating

N_i =P_i Q_i (1≦

i≦

m)

g_i .di-elect cons.Z, 0<

g<sub>i<

N</sub> ( 1≦

i≦

M) ##EQU89## V=(v_ij), v_ij =g_i^h i.sup.(e.sbsp.1.sup., . . . , e.sbsp.n.sup.) mod N (1≦

i,j≦

M)

as public information of the key generator;

storing said confidential information and said public information of the key generator into storage means;

acquiring key information of the key generator for σ

_x =(σ

_x,1, . . . , σ

_x,a) .di-elect cons.S, σ

'"'"'_x =(σ

'"'"'_x,1, . . . , σ

'"'"'_x,a) .di-elect cons.T from said storage means to calculate S.sub.σ

.sbsb.x =((S.sub.σ

.sbsb.x,1.sub.(1), S.sub.σ

.sbsb.x,1.sub.(2), . . . , S.sub.σ

.sbsb.x,1.sub.(k)), . . . , (S.sub.σ

.sbsb.x,a.sub.(1), S.sub.σ

.sbsb.x,1.sub.(1), S.sub.σ

.sbsb.x,a.sub.(k))) satisfying ##EQU90## and distributing s.sub.σ

.sbsb.x and ##EQU91## as key information of the receiver x, wherein ##EQU92## (i=1, . . . , a);

h_i (X₁, . . . , X_n) (1≦

i≦

M) represents a monomial of X₁, . . . , X₂ on Z;

for set S'"'"'(M)={σ

=(σ

₁, . . . , σ

_a)|one-to-one map σ

_i ;

A={1, 2, . . . , k}→

B={1, 2, . . . , M}(i=1, . . . , a), σ

₁ (A) U . . . Uσ

_a (A)=B, M=ak}, σ

=(σ

₁, . . . , σ

_a), σ

'"'"'=(σ

'"'"'₁, . . . , σ

'"'"'_a) .di-elect cons.S'"'"'(M), a relation of ##EQU93## . . . , σ

_a (A)}={σ

'"'"'₁ (A), . . . , σ

'"'"'_a (A)} is defined and a quotient set of S'"'"'(M) concerning "˜

" is defined as S; and

a quotient set of m=ad, S'"'"'(m) concerning "˜

" is defined as T;

and (ii) as a key distribution process,

(1) the sender side is provided with the steps of;

randomly selecting for any receiver x an integer r which satisfies ##EQU94## calculating broadcast communication data

space="preserve" listing-type="equation">W=(w.sub.ij), w.sub.ij =v.sub.ij mod N (1≦

i≦

M)

from the public information of the key generator with the object of possessing K as a common key; and

making the multi-address transmission of said broadcast communication data,

and (2) said receiver x side is provided with;

calculating the common key K from said broadcast communication data and said confidential information s.sub.σ

.sbsb.x of the receiver x distributed by the key generator in accordance with ##EQU95## wherein ##EQU96## and wherein Z represents a set of the whole of integers;

lcm(a,b) represents the lowest common multiple of integers a and b; and

ord_N (g) represents the least integer x which satisfies g^x .tbd.1(mod N) for integers N and g.

30. A key distribution method according to claim 26, wherein said key generator side is further provided with a step of selecting the key information s_x,t of the receiver x to satisfy a condition of

31. A key distribution method according to claim 26, wherein said key generator side is further provided with a step of selecting the key information s.sub.σ

.sbsb.x of the receiver x to satisfy so that ##EQU111## is satisfied.

23. A key distribution method for sharing common key information in a limited secure broadcast communication in which a broadcasting station as a sender communicates wits only receivers limited from among a plurality of receivers, wherein

(i) the sender side is provided with the steps of:

generating confidential information of a receiver in association with a subset inclusive of at least two elements of a finite set S;

distributing said confidential information to the receiver;

generating key distribution data corresponding to each element of said finite set S;

making the multi-address transmission of said key distribution data;

generating individual information for each receiver to be transmitted to only said limited receivers; and

transmitting said individual information for each limited receiver x,

and (ii) the receiver x side is provided with;

a step of calculating common key information K between the sender side and the receiver from said confidential information s_x for each receiver distributed by said sender side, said key distribution data and said individual information.

24. A key distribution method according to claim 23, wherein said sender side is further provided with a step of changing said key distribution data to change the value of said common key.

25. A key distribution method according to claim 23, wherein said receiver x side is provided with a step of for making the authentication for the sender side by use of said confidential information s_x in the case where transmit data is onerous indicating that a fee is charged, and said sender side is provided with a step of transmitting said individual information V_x if the authentication requested from the receiver side is materialized.

28. A key distribution method according to claim 23, wherein

(i) as a preparatory process, said broadcasting station side is provided with the steps of:

generating

P_i, Q_i ;

prime number (1≦

i≦

m)

L_i =lcm (ord_p.sbsb.i (g), ord_Q.sbsb.i (g)) (1≦

i≦

m)

e_i .di-elect cons.Z, 0<

e_i <

L=lcm (L₁, L₂, . . . , L_m) (1≦

i≦

n)

as confidential information of the broadcasting station;

generating ##EQU97## as public information of the broadcasting station;

storing said confidential information and said public information into storage means;

generating random numbers r'"'"' (0<

r'"'"'<

L);

acquiring key information of the broadcasting station for σ

_x .di-elect cons.S and τ

.di-elect cons.T from said storage means to calculate S_x,t =(S_x,τ

(1), S_x,τ

(2), . . . , S_x,τ

(d)), u_x,τ

=(u_x,τ

(1), u_x,τ

(2), . . . , u_x,τ

(d)) satisfying ##EQU98## and distributing s_x,τ

as key information of the receiver x, wherein L.sub.σ

=1cm (L.sub.σ

(1), L.sub.σ

(2), L.sub.σ

(k)) (σ

.di-elect cons.S);

h_i (X₁, . . . , X_n) (1≦

i≦

M) represents a monomial of X₁, . . . , X_n on Z;

for set S'"'"'={f|one-to-one map f;

A={1, 2, . . . , k}→

B={1, 2, . . . , m}, m≧

K}, σ

₁, σ

₂ .di-elect cons.S'"'"', a relation "˜

" on S'"'"' is defined as ##EQU99## and a quotient set of S'"'"' concerning "˜

" is defined as S, and set T={f|one-to-one map f;

A={1, 2, . . . , d}→

B={1, 2, . . . , M}, M≧

d},

and (ii) as a key distribution process,

(1) said broadcasting station side is provided with the steps of;

randomly selecting for any receiver x an integer r (0<

r<

L) which satisfies

space="preserve" listing-type="equation">0<

K=g.sup.rr'"'"' mod N, ##EQU100## acquiring the key information of the broadcasting station from said storage means of said broadcasting station side to calculate

space="preserve" listing-type="equation">z.sub.i =v.sub.i.sup.r mod N (1≦

i≦

M)

with the object of sharing a key K in common with the limited receivers;

making the multi-address transmission of z_i (1≦

i≦

M), wherein ##EQU101## and transmitting u_x,τ

=(u_x,τ

(1), u_x,τ

(2), . . . , u_x,τ

(d)) to the limited receivers,

and (2) said receiver x side is provided with;

a step of calculating the common key K from the broadcast communication data, said confidential information s_x,τ

of the receiver x distributed by the broadcasting station and u_x,τ

in accordance with ##EQU102## and wherein Z represents a set of the whole of integers;

lcm(a,b) represents the lowest common multiple of integers a and b; and

ord_p (g) represents the least integer x which satisfies g^x .tbd.1(mod p).

29. A key distribution method according to claim 23, wherein

(i) as a preparatory process,

said broadcasting station side is provided with the steps of:

generating

P_i, Q_i ;

prime number (1≦

i≦

m)

e_i .di-elect cons.Z;

0<

ei<

L=lcm (L₁, L₂, . . . , L_m) (1≦

i≦

n)

as confidential information of the broadcasting station;

generating ##EQU103## as public information of the broadcasting station;

storing said confidential information and said public information of the broadcasting station into storage means;

generating random numbers r'"'"' (0<

r'"'"'<

L);

acquiring key information of the broadcasting station for σ

_x =(σ

_x,1, . . . , σ

_x,a) .di-elect cons.S, σ

'"'"'_x,1, . . . , σ

'"'"'_x,a) .di-elect cons.T from said storage means of said broadcasting station side to calculate S.sub.σ

.sbsb.x =((Sσ

.sbsb.x,1.sub.(1), S.sub.σ

.sbsb.x,1.sub.(2), . . . , S.sub.σ

.sbsb.x,1.sub.(k)), . . . , (S.sub.σ

.sbsb.x,a.sub.(1), S.sub.σ

.sbsb.x,a.sub.(2), . . . , S.sub.σ

.sbsb.x,a.sub.(k))), u.sub.σ

.sbsb.x =((u.sub.σ

.sbsb.x,1.sub.(1), u.sub.σ

.sbsb.x,1.sub.(2), . . . , u.sub.σ

.sbsb.x,1.sub.(k)), . . . , (u.sub.σ

.sbsb.x,a.sub.(1), u.sub.σ

.sbsb.x,a.sub.(2), . . . , u.sub.σ

.sbsb.x,a.sub.(k))) satisfying ##EQU104## and distributing s.sub.σ

.sbsb.x and ##EQU105## as key information of the receiver x, wherein ##EQU106## (i=1, . . . , a);

h_i (X₁, . . . , X_n) (1≦

i≦

M) represents a monomial of X₁, . . . , X_n on Z;

for set S(M)={σ

=(σ

₁, . . . , σ

_a)|one-to-one map σ

_i ;

A={1, 2, . . . , k}→

B={1, 2, . . . , M}(i=1, . . . , a), σ

₁ (A) U . . . Uσ

_a (A)=B, M=ak}, σ

=(σ

₁, . . . , σ

_a), σ

'"'"'=(σ

'"'"'₁, . . . , σ

'"'"'_a) .di-elect cons.S(M), a relation of ##EQU107## . . . , σ

_a (A)}={σ

'"'"'₁ (A), . . . , σ

'"'"'_a (A)} is defined and a quotient set of S(M) concerning "˜

" is defined as S; and

a quotient set of m=ad, S(m) concerning "˜

" is defined as T, and (ii) as a key distribution process,

(1) said broadcasting station side is provided with the steps of;

randomly selecting for any receiver x an integer r (0<

r<

L) which satisfies ##EQU108## acquiring the key information of the broadcasting station from said storage means of said broadcasting station side to calculate

space="preserve" listing-type="equation">W=(w.sub.ij), w.sub.ij.sup.r mod N (1≦

i,j≦

M)

with the object of sharing a key K in common with the limited receivers;

making the multi-address transmission of W; and

transmitting u.sub.σ

.sbsb.x =((u.sub.σ

.sbsb.x,1.sub.(1), u.sub.σ

.sbsb.x,1.sub.(2), . . . , u.sub.σ

.sbsb.x,1.sub.(k)), . . . , (u.sub.σ

.sbsb.x,a.sub.(1), u.sub.σ

.sbsb.x,a.sub.(2), . . . , u.sub.σ

.sbsb.x,a.sub.(k))) to the limited receivers,

and (2) said receiver x side is provided with;

a step of calculating the common key K from the broadcast communication data, said confidential information s.sub.σ

.sbsb.x of the receiver x distributed by the broadcasting station and u.sub.σ

.sbsb.x in accordance with ##EQU109## wherein ##EQU110## and wherein Z represents a set of the whole of integers;

lcm(a,b) represents the lowest common multiple of integers a and b; and

ord_N (g) represents the least integer x which satisfies g^x .tbd.1(mod N) for integers N and g.

32. A key distribution method according to claim 29, wherein said broadcasting station side is further provided with a step of selecting the key information s.sub.σ

.sbsb.x of the receiver x to satisfy so that ##EQU112## is satisfied.

33. A key distribution method according to claim 28, wherein said broadcasting station side is further provided with a step of changing the value of the common key K by changing the value of r of the common key K=g^rr'"'"' mod N.

34. A key distribution method according to claim 28, wherein said broadcasting station side is further provided with a step of identifying transmit data by taking the value of r'"'"' of the common key K=g^rr'"'"' mod N as a value characteristic of the transmit data.

35. A key distribution method according to claim 28, wherein the limited receiver x side is provided with a step of making the authentication for the broadcasting station side by use of the confidential information s_x,τ

'"'"' and a step of receiving u_x,τ

, after the authentication is made, and wherein the broadcasting station side is provided with a step in which in the case where data P enciphered using the common key K is onerous indicating that a fee is charged, a process for account of a charge for P to the receiver x is performed.

36. A key distribution method according to claim 28, wherein in the case where the receiver x possesses a storage medium with a computing function having the confidential key s_x,τ

and connects said storage medium to a receiving unit having a higher computing function to calculate the common key ##EQU113## there comprises;

a step of performing the calculation of

space="preserve" listing-type="equation">ξ

.sub.x,τ

(i) =z.sub.τ

(i).sup.u.sbsp.x,τ

(i) mod N (1≦

i≦

d);

by said receiving unit;

a step of outputting ξ

_x'"'"'τ

(i) ( 1≦

i≦

d) from said receiving unit to said storage medium;

a step of performing the calculation of

space="preserve" listing-type="equation">η

.sub.x,τ

(i)=ξ

.sub.x,τ

(i).sup.s.sbsp.x,τ

(i) mod N (1≦

i≦

d)

by said storage medium on the basis of information from said receiving unit;

a step of outputting η

_x,τ

(i) (1≦

i≦

d) from said storage medium to said receiving unit; and

a step of performing the calculation of ##EQU114## by said receiving unit on the basis of information from said storage medium.

37. A key distribution method according to claim 29, wherein in the case where the receiver x possesses a storage medium with a computing function having the confidential key s.sub.σ

.sbsb.x and connects said storage medium to a receiving unit having a higher computing function to calculate the common key K, the transfer of information between said storage medium and said receiving unit is made with a step of performing a calculation using confidential information in said storage medium and a step of performing a calculation using no confidential information in said receiving unit.

38. A key distribution method according to claim 23, wherein

(i) as a preparatory process,

said broadcasting station side is provided with the steps of:

generating

P, Q;

prime number

e_i .di-elect cons.Z, 0<

e_i <

L=lcm(P-1, Q-1) (1≦

i≦

m)

as confidential information of the broadcasting station;

generating

N=PQ

as public information of the broadcasting station;

storing said confidential information and said public information of the broadcasting station into storage means;

generating random numbers r.di-elect cons.Z, π

=(π

₁, . . . , π

_l) .di-elect cons.R_k,n ;

acquiring key information of the broadcasting station for σ

=(σ

1, . . . , σ

_l) .di-elect cons.Sk,n from said storage means of said broadcasting station side to calculate S_x, (.sub.π

,σ

) =(S_x,π

.sbsb.1.sub.(1), . . . , S_x,π

.sbsb.1.sub.(h), . . . , S_x,π

.sbsb.l.sub.(1), . . . , S_x,π

.sbsb.l.sub.(h)), ^r_x, (.sub.π

,σ

) =(^r_x,π

.sbsb.1.sub.(1), . . . , ^r_x,π

.sbsb.1.sub.(h), . . . , ^r_x,π

.sbsb.l.sub.(1), . . . , ^r_x,π

.sbsb.l.sub.(h)) satisfying ##EQU115## and a step of distributing s_x, (.sub.π

,σ

) as key information of the receiver x, wherein ##EQU116## when σ

=(σ

₁, . . . , σ

_l), σ

'"'"'₁ =(σ

'"'"'₁, . . . , σ

'"'"'_l), .di-elect cons.S'"'"'_k,n for n=kl, set R_k,n ={π

=(π

₁, . . . , π

_l)|one-to-one map π

_i ;

{1, 2, . . . , h}→

{1, 2, . . . , m}, (1≦

i≦

l,1≦

h≦

m)}, set S'"'"'_k,n ={σ

=(σ

₁, . . . , σ

_l)|one-to-one map σ

_i ;

A{1, 2, . . . , k}→

B={1, 2, . . . , n}(1≦

i≦

l), σ

₁ (A) U . . . U σ

_l (A)=B}, a relation of ##EQU117## is defined in regard to proper permutation τ

on a set {1, 2, . . . , l}, "˜

" representing an equivalent relation on S'"'"'_k,n and S_kn being S_k,n =S'"'"'_k,n /˜

,

and (ii) as a key distribution process,

(1) said broadcasting station side is provided with the steps of;

randomly selecting r.di-elect cons.Z for g_i .di-elect cons.Z (0<

g_i <

N, 1≦

i≦

n=kl) in said storage means of said broadcasting station side;

calculating ##EQU118## acquiring the key information of the broadcasting station from said storage means of said broadcasting station side to calculate

space="preserve" listing-type="equation">y.sub.ij =u.sub.ij.sup.r mod N (1≦

i≦

m, 1≦

i≦

n)

with the object of sharing a key K in common with only the limited receivers;

making the multi-address transmission of y_ij (1≦

i≦

m, 1≦

j≦

n); and

transmitting r_x,(π

,σ

)=(r_x,π

.sbsb..sub.(1), . . . , r_x,π

.sbsb.1.sub.(h), . . . , r_x,π

.sbsb.l.sub.(1), . . . , r_x,π

.sbsb.l.sub.(h)) to the limited receivers x, and (2) said receiver x side is provided with;

a step of calculating the common key K from the broadcast communication data, said confidential information s_x,(π

,σ

) of the receiver x distributed by the broadcasting station and r_x,(π

,σ

) in accordance with ##EQU119## and wherein Z represents a set of the whole of integers;

lcm(a,b) represents the lowest common multiple of integers a and b; and

ord_N (g) represents the least positive integer x which satisfies g^x .tbd.1(mod N) for integers N and g.

39. A key distribution method according to claim 28, wherein said broadcasting station side is further provided with a step of selecting the key information s_x,τ

of the receiver x to satisfy a condition of

space="preserve" listing-type="equation">π

.sub.x ≠

g

for any receiver x.

40. A key distribution method according to claim 29, wherein said broadcasting station side is further provided with a step of changing the value of the common key K by changing the value of r of the common key K=g^rr'"'"' mod N.

41. A key distribution method according to claim 29, wherein said broadcasting station side is further provided with a step of identifying transmit data by taking the value of r'"'"' of the common key K=g^rr'"'"' mod N as a value characteristic of the transmit data.

42. A key distribution method according to claim 29, wherein the limited receiver x side is provided with a step of making the authentication for the broadcasting station side by use of the confidential information s.sub.σ

x'"'"' and a step of receiving u.sub.σ

x after the authentication is made, and wherein the broadcasting station side is provided with a step in which in the case where data P enciphered using the common key K is onerous indicating that a fee is charged, a process for account of a charge for P to the receiver x is performed.