Cryptography – Key management – Key distribution
Reexamination Certificate
2000-03-07
2003-01-28
Barron, Jr., Gilberto (Department: 2767)
Cryptography
Key management
Key distribution
C380S262000, C713S163000, C713S171000
Reexamination Certificate
active
06512829
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a key distribution method and system in secure broadcast communication.
Up to now, several methods have been proposed in regard to secure broadcast communication (or key management).
For example, a copied key method disclosed by S. J. Kent, “Security requirement and protocols for a broadcast scenario”, IEEE Trans. Commun., COM-29, 6, pp. 778-786 (1981) is fundamental. The copied key method is the simple extension of the conventional one-to-one cryptographic individual communication to a multi-address communication. The copy of one kind of key is distributed to a sender and a plurality of normal receivers. The sender enciphers information by use of the copied key and transmits the enciphered information. The normal receiver deciphers the information by use of the same copied key.
The other methods include (i) a secure broadcast communication method disclosed by K. Koyama, “A Cryptosystem Using the Master Key for Multi-Address Communication”, Trans. IEICE, J65-D, 9, pp. 1151-1158 (1982) which uses a master key alternative to RSA individual key, (ii) a key distribution system disclosed by Lee et al., “A Multi-Address Communication Using a Method of Multiplexing and Demultiplexing”, the Proc. of the 1986 Symposium on Cryptography and Information Security, SCIS86 (1986) which is based on the multiplexing and demultiplexing of information trains using the Chinese reminder theorem, and (iii) a system disclosed by Mambo et al., “Efficient Secure Broadcast Communication Systems”, IEICE Technical Report, ISEC93-34 (October 1993).
According to the system for performing the multiplexing and demultiplexing of information trains by use of the Chinese reminder theorem, the following processes are performed.
(1) Key Generating Process
For a receiver
i
(1≦i≦r) are generated
s
compromise integers g
1
, g
2
, . . . , g
s
(r≦s) and g
i
is distributed to the receiver
i
as confidential information of the receiver
i
beforehand.
(2) Enciphering Process
It is assumed that s information trains to be multiplexed are M
1
, M
2
, . . . , M
s
. A sender calculates a multiplexed transmit sentence F in accordance with
F
=
∑
i
=
1
k
A
i
G
i
M
i
mod
G
and makes the multi-address transmission of F, wherein G, G
i
and A
i
are the least integer A
i
which satisfies
G
=
∏
i
=
1
k
g
i
,
G
i
=G/g
i
,
A
i
G
i
≡1(mod g
i
).
(3) Deciphering Process
The receiver
i
demultiplexes M
i
from F by use of g
i
in accordance with
M
i
=F
mod
g
i
According to the system disclosed by Mambo et al., “Efficient Secure Broadcast Communication Systems”, IEICE Technical Report, ISEC93-34 (October 1993), the following processes are performed.
(1) Key Generating Process
A reliable center generates the following information.
Confidential information:
P=
2
p+
1,
Q=
2
q+
1:prime number (p,q:prime number)
e
i
&egr;Z,
0<
e
i
<L
(1
≦i≦m
)
Public information:
g&egr;Z,
0
<g<N
N=PQ
v
i
=g
ei
mod N
(1
≦i≦m
).
The center calculates s
&sgr;
satisfying
S
σ
=
∑
i
=
1
k
e
σ
(
i
)
≡
1
(
mod
L
)
for &sgr;&egr;S and distributes s
&sgr;
as confidential information of a receiver U
&sgr;
, wherein set S={f|one-to-one map f: A={1, 2, . . . , k}→B={1, 2, . . . , m}, m>k}.
(2) Key Distribution Process
(i) A sender randomly selects an integer
r
to calculate
z
i
=v
i
r
mod N
(1
≦i≦m
)
with the object of sharing a common key
K=g
r
mod N
in common with the receiver and makes the multi-address transmission of z
i
(1≦i≦m).
(ii) The receiver U
&sgr;
calculates the common key K in accordance with
K
=
(
∏
i
=
1
k
z
σ
(
i
)
)
S
σ
mod
N
.
In the above-mentioned key distribution based on the multiplexing method using the Chinese reminder theorem, the length of key distribution data becomes large in proportion to the number of receivers since the key distribution data for individual users are transmitted in a serially arranged manner. This offers a problem from an aspect of efficiency in the case where several millions of receivers are made an object as in a broadcasting satellite service.
On the other hand, in the system disclosed by Mambo et al., “Efficient Secure Broadcast Communication Systems”, IEICE Technical Report, ISEC93-34 (October 1993), the length of key distribution data can be reduced even in the case where the number of receivers is large. However, this system has a problem in security that if receivers conspire with each other, confidential information of another receiver can be calculated. Also, it is not possible to possess a key in common with only receivers which belong to any set of receivers.
SUMMARY OF THE INVENTION
Therefore, a principal object of the present invention is to provide a key distribution method and system for secure broadcast communication having the following features:
(1) receivers possess individual confidential key information to share a data enciphered key between the receivers;
(2) even in the case where the number of receivers is large, it is possible to reduce the length of key distribution data;
(3) even if receivers club their confidential information in conspiracy with each other, it is difficult to calculate key information of another receiver and confidential information of a key generator; and
(4) it is possible to possess the data enciphered key in common with only receivers which belong to any set of receivers.
To that end, a key generator generates a finite set S including a plurality of confidential information of the key generator and a finite set P including public information of the key generator, generates confidential key information s(x) of a receiver
x
from elements of a subset S
x
of the confidential information S on a space determined by a subset V
x
of the set S or P, and distributes the key information s(x) to the receiver
x
. A sender performs an operation of adding random numbers to elements in the public information corresponding to the elements of the set S and makes the multi-address transmission of a set R(P) including the elements which result from the operation. The receiver
x
selects a set R(P, x) of elements corresponding to S
x
from R(P) to calculate a common key between the sender and the receiver from each element of R(P, x) and the confidential key information s(x). The common key corresponds to a data enciphered key.
According to a method for possessing a key in common with only receivers which belong to any set of receivers (in this case, a broadcasting station is a key generator and a sender), the broadcasting station generates confidential key information s(x) of a receiver
x
from a subset S
x
of a finite set S including a plurality of elements and distributes the key information s(x) to the receiver
x
. The broadcasting station performs an operation of adding an arbitrarily selected random number to each element of a set P including values corresponding to the elements of the set S and makes the multi-address transmission of a set R(P) including the elements which result from the operation. The broadcasting station further transmits to only the limited receiver a value t(x) characteristic of the receiver
x
which corresponds to the confidential key information s(x) of the receiver
x
. The receiver
x
selects a set R(P, x) of elements corresponding to S
x
from R(P) to calculate a common key between the broadcasting station and the receiver from the elements of R(P, x), the key information s(x) and the value t(x) of the receiver
x
.
In the following, mention will be made of a specific realizing example of a method in which the length of key distribution data is short even in the case of a large number of receivers and the security against the conspiracy attack of receivers is improved.
As a preparatory process, a key generator generates
Matsui Susumu
Nishioka Mototsugu
Umeki Hisashi
Barron Jr. Gilberto
Callahan Paul E.
Hitach, Ltd.
LandOfFree
Key distribution method and system in secure broadcast... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Key distribution method and system in secure broadcast..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Key distribution method and system in secure broadcast... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3044185