Encrypted communication system, key delivery server thereof, terminal device, and key sharing method

TECHNICAL FIELD

0001The present invention relates to a cryptographic technique for distribution of a key used for decrypting encrypted information to a subscriber terminal, and particularly to a technique for updating a key in a secure and quick manner.

BACKGROUND ART

0002There are many cases encountered in which in order to establish a system for supplying information to a previously determined group, a key (group key) is distributed only to a subscriber enrolled as a member of the group and then cryptographic communication through a key is performed. The cryptographic technique is useful in many applications such as distribution of contents to a portable telephone, decipherer/reproducer of a DVD player, distribution of software via CDROM interface, police radio communication and local communication between groups in P2P service.

0003In the system described above, in the event a part of a terminal device (decoder) is removed away such as in a theft attempt, it is in danger of leakage of a group key to an unauthorized person other than members of the group. For this reason, the used group key has to be updated to create a new key and the new key has to be shared by the members of the group as quickly as possible.

0004A technique of updating a key has an extremely important role in a system that utilizes a once-established infrastructure for a long period of time.

0005Assume that in this type of system (hereinafter, refer to as a broadcasting type cryptographic communication system) consisting of a plurality of subscriber terminals, messages are distributed to all subscriber terminals excluding a single subscriber terminal or a plurality of subscriber terminals. Note that the term "exclude" means operation for excluding a certain subscriber terminal (or certain subscriber terminals) from a group and that the excluded subscriber terminal is referred to as "a terminal to be excluded," (hereinafter, refer to as a exclusion-target terminal). In general, when excluding an exclusion-target terminal, it is required to distribute a new group key to each of the individual subscriber terminals other than the exclusion-target terminal. For this reason, as the scale of a group increases, the amount of communication and the amount of time delay required to complete operation for making all the subscriber terminals share a new group key increase.

0006Conventionally, in order to reduce the above-described amount of time delay required to update the groups key, a variety of techniques have been conceived. A technique (a first conventional technique) disclosed in Japanese Patent Application 2000-196581 is exemplified as a conventional technique of the above-stated type.

0007The first conventional technique disclosed in the above-stated publication employs an algorithm that makes the amount of communication and the amount of time delay after determination of an exclusion-target terminal not proportional to the number "n" of subscribers as a member of the group. When employing the above-described algorithm and assuming that the maximum number of terminals to be excluded is "k," a number, proportional to "k," of modular exponentiation operations have to be performed by each of the subscriber terminals to calculate the group key. Accordingly, if "k" is far smaller than "n" (k << n), key distribution according to this technique can be made far more effectively than a general distribution of group key. For instance, when assuming that a system (n = 10,000) includes 10,000 subscriber terminals and the number of terminals to be excluded is 100 (k = 100), although the general distribution of group key needs processing to be performed a number of times proportional to the number "10,000," key distribution according to the first conventional technique disclosed in the publication needs processing to be performed a number of times proportional to the number "100."

0008However, in a system (e.g., a system for providing services to mobile terminals such as a portable telephone) including up to some million subscriber terminals and in a similar system, it is required to make the number "k" that represents the maximum number of terminals to be excluded enlarged (e.g., some thousands to some ten thousands) to meet the scale of a group. This makes computation load on a terminal that is poor in its computing ability become considerable, which load is imposed by decryption and is proportional to the number "k." Therefore, it is desirable to perform group key distribution that needs decryption to be performed a number of times not proportional to the number "k," or, if possible, a constant number of times.

0009Japanese Patent Application 2001-203682 is exemplified as a conventional technique (second conventional technique) to solve the above-described problems.

0010The second conventional technique disclosed in the publication realizes decryption by performing modular exponentiation operations only "2" times without depending on the number "n," which represents the total number of subscriber terminals, and the number "k," which represents the maximum number of terminals to be excluded. Accordingly, the second conventional technique allows a system including a very large number of subscriber terminals to make quick distribution of a group key.

0011In a broadcasting type cryptographic communication system, members of a protocol are defined as follows.

0012Key distribution server: A reliable agency for determining system parameters at the time of setup and distributing personal keys to individual subscriber terminals. When going to distribute a group key, the server determines which subscriber terminals are to be excluded and then distributes the group key through broadcast. The key distribution server is denoted by "S."

0013Subscriber terminal: A terminal for receiving a broadcast material from the key distribution server. A subscriber terminal "i" receives a personal key "s_i" from the key distribution server at the time of setup. A set of subscriber terminals is defined as a set Φ = {1 , ··· , n} (n = |Φ| represents the total number of subscriber terminals).

0014Subscriber terminal excluded: A subscriber terminal being excluded by the key distribution server. A set of "d" (< k) subscriber terminals to be excluded when the key distribution server distributes a group key in a first round is defined as a subset Λ_l (⊂ Φ). Once being excluded, the subscriber terminal is not able to decrypt a group key after the round in which the terminal is excluded and therefore, is never repeatedly excluded in a plurality of rounds. That is, the intersection of two sets, Λ_l∩ Λ_l' = {0} (l ≠ l'). Furthermore, assume that the number, which represents the total number of excluded subscriber terminals, never exceeds the number "k" throughout the rounds (i. e., |∪Λ_l| ≦ k).

0015Effective subscriber terminal: A subscriber terminal being not excluded. Assume that a set of subscriber terminals effective in the first round of distribution of group key is defined as a set Ω₁ (= Φ\U¹_j=1Λ_j).

0016In the broadcasting type cryptographic communication system thus defined, U₁ is distributed to the effective subscriber terminals Ω₁ among the entire subscriber terminals Φ in the first round. Encrypting messages using U₁ allows a cryptographic communication of the type used for broadcasting within the group Ω₁. That is, the cryptographic communication is performed as follows. <ul id="ul0001" list-style="none" compact="compact"><li>1. Let Ω₀ = Φ. The key distribution server distributes a group key "U₀" and a personal key key_i to each subscriber "i" (i ∈ Φ) through a point-to-point and key distribution protocol connection.</li><li>2. For each of l ≧ 1, the following processings are repeatedly performed (hereinafter, performing the following processings one time is referred to as "l round"). <ul id="ul0002" list-style="none" compact="compact"><li>(a) Key distribution server determines Λ_l ⊂ Ω_l-1.</li><li>(b) If k ≧ Σ¹_j=1|Λ_j|, Φ: = Ω_1-1, U₀: = U_1-1 and then return to l.</li><li>(c) Key distribution server distributes a header H_l to Ω_l to make Ω_l calculate U_l.</li><li>(d) v ∈ Ω_l calculates U_l using H_l and key_v.</li><li>(e) Key distribution server and Ω_l perform broadcasting type cryptographic communication using U_l.</li></ul></li></ul>

0017Furthermore, in the description hereinafter set forth, the following parameters are employed. "p" and "q" are a large prime number satisfying q|p-1 and "g" is an element of the order "q" on finite field Z_p. The size of "p" and "q" is determined so that discrete logarithm problems on a group GF(q), which group consists of "g" as a generating element, becomes computationally difficult. In the following explanation, unless otherwise noted, calculations are all made using modulo p arithmetic. Note that though not described in detail, order "p" can be defined on arbitrary group GF(p) so that solving a discrete logarithm problem becomes computationally difficult, in addition to the definition different from that used in defining order "p" at a prime on group GF(q). For instance, a group constructed by (1) making multiplication operations on an element of order "p" correspond to addition operations on curves such as an elliptical curve on an arbitrary finite field or (2) by letting a prime number "p'" be an exponent instead of a prime number "p" and then performing arithmetic operations on an extension field GF(p') instead of performing remainder operations using a prime number "p'" as a modulus.

0018E (key, message) indicates message encryption that uses symmetric key encryption. "n" denotes the total number of subscriber terminals and "k" (k &lt; n) denotes the maximum number of terminals to be excluded.

0019Under the above-described assumption, the broadcasting type cryptographic communication system is required to satisfy the following four requirements in terms of security and efficiency. <ul id="ul0003" list-style="none" compact="compact"><li>1. An effective subscriber terminal v ∈ Ω_l is able to independently decrypt a group key U₁ (in polynomial time).</li><li>2. Even when using a personal key that each of the "k" excluded subscriber terminals owns, any person cannot decrypt a group key (in probabilistic polynomial time) after the round in which the subscriber terminals are excluded.</li><li>3. The length of a header used in distribution of group key and the size of personal key that each subscriber terminal owns do not depend on the number that represents the total number of subscriber terminals.</li><li>4. When a number of modular exponentiation operations are performed over a time interval over which the header is received to calculate the group key and the decryption of group key (decryption) is completed, the number does not depend on "n" and "k."</li></ul>

0020The requirement 1 is a requirement requiring that a subscriber terminal effectively be able to independently perform decryption. In a broadcasting type cryptographic communication system, it is important not to place additional traffic on the network when the subscriber terminal needs not to communicate with other terminals upon decryption.

0021The requirement 2 is a requirement that has to be satisfied to prevent an excluded subscriber terminal from trying to decrypt a session key in conspiracy with other excluded terminals.

0022The requirement 3 is a requirement that has to be satisfied to prevent significant increase in the amount of processing when the system includes a very large number of subscriber terminals.

0023The requirement 4 is a requirement that has to be satisfied to decrypt a group key requiring an amount of processing, which amount does not depend on "n" and "k," when "k" needs to be determined large in proportion to the scale of a large group.

0024So-called "Spare Shadow Attack" and "r publish attack" are included in the requirement 2. A protocol using a time threshold essentially cannot address the problem caused by "Secret Publish Attack." Not that when assuming the number of attackers who reveal a secret is "w," if the number of unauthorized persons is not greater than "k-w," security can be maintained. Accordingly, evaluating the security of protocol under the condition that the total number of unauthorized subscriber terminals, which are in conspiracy with other unauthorized subscriber terminals, is not greater than "k" allows discussion about security within the same field as that of the requirement 2.

0025The aforementioned conventional technique 1 satisfies the above-stated requirements 1, 2 and 3. The length of an encrypted message to be distributed corresponds to a constant time interval O(k) and the size of a personal key to be distributed corresponds to O(l), meaning that those factors produce extreme efficiency. However, since the number, which represents the number of modular exponentiation operations to be performed to decrypt a group key, equals to O(k) and further, the modular exponentiation operations cannot be placed in pre-calculation prior to reception of the group key, the conventional technique 1 does not satisfy the requirement 4.

0026The conventional technique 2 focuses its attention on the necessity for the requirement 4 and then provides an algorithm that satisfies the requirement 4. However, the conventional technique 2 does not satisfy the requirement 2, which is most important in terms of security, for the reason resulting from the following analysis. That is, when a group key is distributed finite times, the subscriber terminals being not excluded is able to require secret information about an entire system and further to cancel excluding operation to be performed after the key is distributed finite times (e.g., if k ≧ 5, an attack on the system is possible after the group key is distributed three times).

0027How the conventional technique 2 does not satisfy the requirement 2 will be shown below. First, the algorithm that the conventional technique 2 employs for a broadcasting type cryptographic communication will be explained.

1. Setup

0028A key distribution server determines the number "k" that represents the maximum number of terminals to be excluded and randomly selects a k^th degree polynomial Z_q represented by the following numerical expression 1.<maths id="math0001" num=""><img file="EP1501237A1_D0001.tif" /></maths><maths id="math0002" num=""><img file="EP1501237A1_D0002.tif" /></maths>

0029F(0) = S and G(0) = T(mod q) are secret keys that only the key distribution server knows. The key distribution server distributes key_i = (s_i, f_i) = (F(i), g^G(i)/F(i))(i = 1, ···, n) to each subscriber terminal "i" via a secret communication path. In addition, the key distribution server randomly selects an element U₀ ∈ GF(q) and broadcasts the same.

2. Encryption of group key

0030The group key U_l to be distributed in the "l" (≧ 1) round is distributed in the following manner. Randomly select an element r_l ∈ Z_q and determine X_l = g^rl. Then, determine a set Λ_l for "d" subscriber terminals to be excluded. Select "(k-d)" pieces of integers from between "n + k(R-l)" and "n + kR," and determine a set Θ₁ consisting of the "(k-d)" pieces of integers. The key distribution server determines M_l1, ···, M_lk based on the following numerical expression 2.<maths id="math0003" num=""><math display="block"><mrow><mtext>[Numerical expression 2]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext mathvariant="italic">ij</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext mathvariant="italic">F</mtext><mtext>(</mtext><mtext mathvariant="italic">j</mtext><mtext>)+</mtext><mtext mathvariant="italic">G</mtext><mtext>(</mtext><mtext mathvariant="italic">j</mtext><mtext>) mod</mtext><mtext mathvariant="italic">q</mtext><mtext> (</mtext><mtext mathvariant="italic">j</mtext><msub><mrow><mtext>∈Λ</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><msub><mrow><mtext>∪Θ</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1501237A1_D0003.tif" /></maths>

0031Finally, the key distribution server determines E(U_l-1, B_l) = E(U_l-1, X_l∥[(j, M_lj)|j ∈ Λ_l ∪Θ₁]) and then broadcasts the same. The group key that is shared in the "l" round is U_l = g^rlS+T.

3. Decryption of group key

0032Since the effective subscriber terminal, i.e., an element v ∈ Ω_l, in the "l" round is an element v ∈ Ω_l-1, the subscriber terminal obtains U_l-1 in the round "l-1." The subscriber terminal "v" decrypts B_l in the received encrypted message E(U_l-1, B_l) using U_l-1. Then, using the information about B_l, the terminal calculates the group key U_l based on the numerical expression 3.<maths id="math0004" num=""><math display="block"><mrow><mtext>[Numerical expression 3]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">U</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext> = (</mtext><msub><mrow><mtext mathvariant="italic">X</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext mathvariant="italic">v</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">W</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext><mtext>1</mtext></mrow></msub></mrow></msup><mtext mathvariant="italic">g</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">W</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext><mtext>2</mtext></mrow></msub></mrow></msup></mrow></math><img file="EP1501237A1_D0004.tif" /></maths>    where,<maths id="math0005" num=""><img file="EP1501237A1_D0005.tif" /></maths>

0033Furthermore, L(j) is an interpolation coefficient given by Lagrange polynomial, represented by the following numerical expression 5.<maths id="math0006" num=""><img file="EP1501237A1_D0006.tif" /></maths>

0034Subsequently, how the algorithm employed in the conventional technique 2 does not satisfy the requirement 2 will be shown. How the effective and optional subscriber terminal ∀_v, i.e., an element ∀_v ∈ Ω_R, in the "R" round calculates and determines the secret information "S" and "T" that only the key distribution server should know will be shown in detail. The terminal "v" obtains (j, M_lj) (l = 1, ..., R, j = 1, ···, k) in the rounds 1 to R and the obtained (j, M_lj) satisfies the relationship represented by the following numerical expression 6.<maths id="math0007" num=""><img file="EP1501237A1_D0007.tif" /></maths>

0035Note that since "j" is known, the "kR" pieces of equations are obtained for "2k + 2 + R" pieces of variables, a₀, ···, a_k, b₀, ···, b_k, r₁, ···, r_R. That is, when "R" satisfies the following numerical expression 7, all the secret keys, i.e., "S" (= a₀) and "T" (= b₁₀), that the key distribution server owns can be calculated.<maths id="math0008" num=""><math display="block"><mrow><mtext>[Numerical expression 7]</mtext><mspace linebreak="newline" /><mtext> 2</mtext><mtext mathvariant="italic">k</mtext><mtext> + 2 + </mtext><mtext mathvariant="italic">R≤ R</mtext><mtext> ⇔ </mtext><mtext mathvariant="italic">R</mtext><mtext> ≥</mtext><mfrac><mrow><mtext>2(</mtext><mtext mathvariant="italic">k</mtext><mtext> + 1)</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext><mtext> - 1</mtext></mrow></mfrac></mrow></math><img file="EP1501237A1_D0008.tif" /></maths>

0036For instance, if k ≧ 5, all the effective subscriber terminals can calculate in the 3 round the secret key (such as "S" and "T") that the key distribution server owns. This indicates that the conventional technique 2 does not satisfy the requirement 2.

DISCLOSURE OF THE INVENTION

0037Therefore, an object of the present invention is to provide a method for updating a group key in a highly secure and sufficiently quick manner while satisfying the aforementioned four requirements.

0038Furthermore, in addition to the above-mentioned object, the present invention has been conceived to provide a highly secure and highly efficient broadcasting type cryptographic communication.

0039In order to achieve the above described objects, the present invention is realized as a cryptographic communication system including a key distribution server for distributing a key used to decrypt encrypted information and a specific number of subscriber terminals making use of the information. The cryptographic communication system according to the first aspect of the present invention is characterized in that the key distribution server is constructed such that the key distribution server distributes: an encrypted first group key used to decrypt the information; individual decryption information corresponding to the specific number of subscriber terminals and used to perform decryption of the first group key; and individual key update information corresponding to the specific number of subscriber terminals and used to perform a part of decryption of a second group key that is updated after a group key is updated, and the specific number of subscriber terminals is constructed such that the specific number of subscriber terminals decrypt the first group key distributed from the key distribution server by making use of results obtained by processing operations performed based on the key update information previously obtained and used to decrypt the first group key, and further making use of the decryption information distributed from the key distribution server. Distributing operation, in the time domain, for decrypting the group key reduces the amount of processing at the time of update of the group key.

0040The specific number of subscriber terminals implement a part of decryption of the group key before distribution of the group key. Previously implementing a part of decryption of the group key in the subscriber terminal before distribution of the group key makes it possible to reduce a time interval required to perform processing after distribution of a new group key without losing security at the time of update of group key.

0041Preferably, in the cryptographic communication system, the key distribution server distributes to the specific number of subscriber terminals key update information, used to decrypt the first group key, together with a third group key that is in a state before the third group key gets updated to the first group key.

0042Furthermore, in the event where the key distribution server updates the group key, the key distribution server determines which subscriber terminals among the specific number of subscriber terminals are to be excluded and distributes to the specific number of subscriber terminals, together with the group key being updated, the decryption information used by remaining subscriber terminals other than the exclusion-target subscriber terminals to make the remaining subscriber terminals able to decrypt the group key being updated.

0043In order to achieve the above described objects, the present invention is additionally realized as a key distribution server, constructed as described below, for distributing a key used to decrypt encrypted information. The key distribution server is characterized by including: means for generating a first group key used to decrypt the information and encrypting the first group key; means for generating individual decryption information used to perform decryption of the first group key and corresponding to subscriber terminals; means for generating individual key update information used to perform a part of decryption of a second group key, the second group key being updated after a group key is updated, and corresponding to the subscriber terminals; and means for distributing the first group key, the decryption information and the key update information to the subscriber terminals.

0044In order to achieve the above described objects, the present invention is also realized as a terminal device constructed as described below. The terminal device is characterized by including: means for retrieving from a specific key distribution server a group key encrypted to decrypt encrypted information and decryption information used to decrypt the group key; means for performing a part of decryption of the group key before distribution of the group key; and means for decrypting the group key by making use of results obtained by processing operations performed based on a part of decryption of the group key and the decryption information retrieved from the key distribution server.

0045Moreover, the present invention is also realized as a program for controlling a computer and then making the computer operate as the above-described key distribution server and/or terminal device. The program can be provided such that the program is stored on a magnetic disk, an optical disk and/or other storage media such as a semiconductor memory, and then those media are handed over or distributed via a network.

0046Additionally, the present invention is realized as a key sharing method, constructed as described below, for making a specific number of terminals using the information share a key used to decrypt encrypted information. That is, the key sharing method is characterized in that the method includes: a step of making the specific number of terminals perform a part of decryption of an encrypted group key used to decrypt the information before distribution of the group key; a step of distributing to the specific number of terminals the group key and individual decryption keys used to perform a part of remaining decryption other than the part of decryption of the group key and corresponding to the specific number of terminals; and a step of making the specific number of terminals perform decryption of the group key using the decryption information being distributed and results obtained by performing a part of decryption of the group key, the part of decryption previously being performed.

BRIEF DESCRIPTION OF DRAWINGS

0047<ul id="ul0004" list-style="none" compact="compact"><li>Fig. 1 is a diagram explaining the general configuration of a broadcasting type cryptographic communication system, according to the embodiment.</li><li>Fig. 2 is a flow chart explaining how cryptographic communication is performed according to the embodiment.</li><li>Fig. 3 is a diagram explaining the configuration of a peer-to-peer network system employing the embodiment.</li><li>Fig. 4 is a diagram explaining the configuration of a real time contents distribution system employing the embodiment.</li><li>Fig. 5 is a diagram explaining the configuration of a system, employing the embodiment, for providing services to portable telephones.</li><li>Fig. 6 is a diagram explaining the configuration of a system, employing the embodiment, for distributing multimedia contents.</li><li>Fig. 7 is a diagram explaining the configuration of a secret broadcasting system employing the embodiment.</li></ul>

BEST MODE FOR CARRYING OUT THE INVENTION

0048The present invention will be explained in detail below based on an embodiment depicted in the attached drawings.

0049FIG. 1 is a diagram illustrating the general configuration of a broadcasting type cryptographic communication system according to the embodiment.

0050Referring to FIG. 1, the broadcasting type cryptographic communication system according to the embodiment comprises a key distribution server 10 for generating a group key used to perform cryptographic communication and distributing the key, and subscriber terminals 20 for obtaining the group key distributed from the key distribution server 10 and performing cryptographic communication using the key.

0051The key distribution server 10 is realized by employing a workstation, a personal computer or other computing devices having networked function and determines system parameters at the time of setup, and then, distributes a personal key to each of the subscriber terminals 20. When distributing a group key, the server determines which subscriber terminals 20 are to be excluded and then decrypts the group key, and thereafter, distributes the key as a broadcast material. Processing such as generation, distribution, etc., of the personal key and the group key is realized, for example, as a function of a program-controlled CPU.

0052The subscriber terminal 20 is realized by employing a workstation, a personal computer, a portable telephone, a Personal Digital Assistant (PDA) or other information terminal equipments having networked function and receives a broadcast material from the key distribution server 10. The subscriber terminal "i" (i-th subscriber terminal 20) receives a personal key s_i from the key distribution server 10 at the time of setup. Then, the terminal decrypts the encrypted group key using the personal key s_i and further, decrypts a specific message using the group key and then makes use of the message. Those processing is realized by employing, for example, a program-controlled processor. Assume that a set of the subscriber terminals 20 is defined as a set Φ = {1, ···, n} (n = |Φ| represents the total number of the subscriber terminals 20).

0053The entire subscriber terminals 20 constitute a group Φ that performs cryptographic communication using the group key distributed from the key distribution server 10. Although the individual subscriber terminals 20 constituting the group are initially "effective subscriber terminals" that are able to participate in cryptographic communication, after one or more subscriber terminal becomes an "excluded subscriber terminal" for some reason, the excluded terminal is never able to participate in the cryptographic communication. That is, the excluded terminal is never able to decrypt the group key using the personal key.

0054A communication configuration employed in the embodiment may be a client/server system in which information is communicated between the key distribution server 10 or a specific server and the subscriber terminals 20, or may be a Peer to Peer system in which information is communicated between the subscriber terminals 20. That is, a supplier who supplies a message (contents) used by the subscriber terminal 20 may exist at a location separated from the key distribution server 10.

0055The cryptographic communication using a group key and performed within the broadcasting type cryptographic communication system includes four phases, i.e., group key setup, information encryption using a group key, information decryption using a group key and key updating.

0056FIG. 2 is a flow chart diagram explaining how the cryptographic communication is performed in accordance with the present invention.

0057In the embodiment, a part of calculation, which part depends on the number "k," which represents the maximum number of excluded-target terminals, is separated as a pre-calculation (key updating) during the decryption of encrypted group key. This allows security to be maintained in an authenticated manner and further permits decryption of group key, except for key updating, to be performed at high speed, with modular exponentiation operations being executed two times. How a cryptographic communication protocol is constructed in accordance with the embodiment will be explained below. Note that in the following explanation, a receiver means a user who uses the subscriber terminal 20 and a subscriber itself.

1. Setup

0058Randomly selects a "k"th order polynomial with one variable in Z_q represented by the following numerical expression 8.<maths id="math0009" num=""><img file="EP1501237A1_D0009.tif" /></maths>

0059F(0) = S and G_l(0) = T_l are made to be a secret key the key distribution server 10. The key distribution server 10 secretly distributes key_i = (s_i, f_li) = (F(i), g^Gl(i)/F(i)) as a decryption key for a receiver "i" in the first round to each subscriber terminal i ∈ {1, ···, n}. A group key U₀ ∈ GF(q), is distributed to all of the subscriber terminals 20 (step 201).

2. Encryption of group key in the l-th round

0060The key distribution server 10 randomly selects an element r_l ∈ Z_q and determines X_l: = g^rl. Then, the server determines a set Λ_l for "d" subscriber terminals 20 to be excluded (step 202). The server selects "(k-d)" pieces of integers from between "n + k(R-l)" and "n + kR" and determines a set Θ_l consisting of the "(k-d)" pieces of integers. The key distribution server 10 determines M_l1, ···, M_lk based on the following numerical expression 9.<maths id="math0010" num=""><math display="block"><mrow><mtext>[Numerical expression 9]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext mathvariant="italic">lj</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext mathvariant="italic">F</mtext><mtext>(</mtext><mtext mathvariant="italic">j</mtext><mtext>) + </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">j</mtext><mtext>) mod</mtext><mtext mathvariant="italic">q</mtext><mtext> (</mtext><mtext mathvariant="italic">j</mtext><msub><mrow><mtext>∈Λ</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><msub><mrow><mtext>∪Θ</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1501237A1_D0010.tif" /></maths>

0061Furthermore, Ω_l (hereinafter, referred to as a subscriber terminal Ω_l), which is an effective subscriber terminal 20, calculates header information H_l needed to calculate a distribution key U_l in the "l" round, using the following numerical expression 10 (step 203).<maths id="math0011" num=""><img file="EP1501237A1_D0011.tif" /></maths><maths id="math0012" num=""><math display="block"><mrow><mtext>[Numerical expression 10]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext> = 〈</mtext><msub><mrow><mtext mathvariant="italic">X</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>∥{(</mtext><mtext mathvariant="italic">j</mtext><mtext>,</mtext><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext mathvariant="italic">lj</mtext></mrow></msub><mtext>)|</mtext><mtext mathvariant="italic">j</mtext><msub><mrow><mtext>∈Λ</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><msub><mrow><mtext>∪Θ</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>}〉</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">H</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">E</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">U</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>-1</mtext></mrow></msub><mtext>,</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1501237A1_D0012.tif" /></maths>

0062Note that the group key shared by the effective subscriber terminal "Ω_l" in the "l" round is represented by U_l = g^rS+Tl.

0063Subsequently, the server generates key update information in order to distribute the group key in the "l+1" round (that is, the subscriber terminal 20 uses the information to update a key upon decryption of the group key in the "l+1" round). The key distribution server 10 randomly selects an element b_l+1,j ∈ Z_q (j = 0, ···, k) and determines an equation (u_l0, ···, u_lk) = (g^bl+1,0, ···, g^bl+1,k), and based on the following numerical expression 11, encrypts the equation using the group key U_l to determine C_l (step 204).<maths id="math0013" num=""><math display="block"><mrow><mtext>[Numerical expression 11]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">E</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">U</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">,u</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>∥...∥</mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">lk</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1501237A1_D0013.tif" /></maths>

0064Then, the key distribution server 10 distributes (H_l, C_l) as a broadcast material to all of the subscriber terminals 20 (i.e., Φ) (step 205).

3. Decryption of group key in the "l" round

0065The subscriber terminal "v," i.e., an element v(∈ Ω_l), which is the subscriber terminal 20 capable of performing decryption in the "l" round, performs decryption in the "l" round based on the following numerical expression 12 (step 206).<maths id="math0014" num=""><img file="EP1501237A1_D0014.tif" /></maths> here,<maths id="math0015" num=""><img file="EP1501237A1_D0015.tif" /></maths>

0066That is, in this round, the subscriber terminal "v" decrypts the group key "U_l" in the "l" round using f_lv, which is previously calculated based on the information distributed in the "l-1" round, and "B_l," which is to be decrypted using H_l distributed in the step 205.

4. Key updating for the "l+1" round (pre-calculation)

0067Based on the following numerical expression 13, the subscriber terminal "v," i.e., an element v ∈ Ω_l, performs key updating as pre-calculation (i.e., processing prior to distribution of the group key in the "l+1" round) using the key update information contained in C_l, which is distributed from the key distribution server 10 (step 207).<maths id="math0016" num=""><img file="EP1501237A1_D0016.tif" /></maths>

0068Additionally, the key distribution server 10 performs pre-calculation of the following numerical expression 14 prior to generation of group key in the "l+1" round.<maths id="math0017" num=""><img file="EP1501237A1_D0017.tif" /></maths>

0069Key updating (pre-calculation) should be performed by the subscriber terminal 20 and the key distribution server 10 using the information distributed along with the group key in the "1" round until before distribution of group key in the "l+1" round.

0070Whether the broadcasting type cryptographic communication system constructed as described above in accordance with the embodiment satisfies the four requirements in terms of security and efficiency will be identified.

0071First, it is apparent that the embodiment satisfies the requirement 1 because it does not need communication between the subscriber terminals 20.

0072Furthermore, the embodiment is constructed such that the length of an encrypted message to be distributed equals to O(k) and the size of a personal key to be distributed equals to O(1), also satisfying the requirement 3.

0073Additionally, the embodiment is constructed such that decryption is performed by executing modular exponentiation operations two times, also satisfying the requirement 4.

0074Subsequently, how the embodiment also satisfies the remaining requirement 2 will be shown.

0075First, model an attacker who "uses personal keys that "k" excluded subscriber terminals own," is described in the requirement 2. The behavior of the attacker can be modeled as an algorithm M_l that determines a group key in the "R" round in polynomial time based on the decryption keys owned by "k" members who have been excluded until the "R" round and information received until the "R" round. Assume that the ("k") excluded subscriber terminals 20 are defined as subscriber terminals "i" (i= 1, ···, k) without losing generality. An input to M₁ is (g, p, q, k, U₀, (s₁, ···, S_k), (f₁₁, ···, f_1k), (H₁, C₁), ···, (H_R, C_R)〉

0076When the behavior of the attacker is modeled as described above, the requirement 2 can alternatively be described as follows using Decision Diffie-Hellman (DDH) Problem.

(Proposition)

0077"As long as an algorithm in polynomial time for solving DDH problem does not exist, M₁ never exists."

0078DDH problem is a judgment problem that D = (g, h, g^a, h^a〉 (this form is referred to as "Diffie-Hellman pair") and R = (g, h, g^a, h^a〉 are discriminated on GF(q) with a significant probability when randomly selecting elements g, h from a set GF(q), and elements a, b ∈ Z_q. An algorithm that solves DDH problem in polynomial time has not yet been known. That is, this problem is a mathematical problem, which can be assumed so that solving the problem is difficult in computational complexity, and M_l does not exist based on the above-described proposition. Accordingly, the embodiment satisfies the requirement 2.

0079As described above, using the method for sharing a group key in the broadcasting type cryptographic communication system according to the embodiment, security can be maintained in an authenticated manner when a group key is updated and decryption can be performed by implementing a part of decryption for the group key as pre-calculation before distribution of the group key and further performing modular exponentiation operations only two times without depending on the number "n," which represents the number of subscriber terminals, and the number "k," which represents the maximum number of excluded-target terminals, after distribution of the updated group key. Accordingly, the method is effective particularly in a network system including a very large number of the subscriber terminals 20 therein.

0080Subsequently, examples constructed by applying the broadcasting type cryptographic communication system according to the embodiment to a variety of network systems will be explained below.

[Management of group member in Peer to Peer system]

0081The embodiment can be employed in a Peer to Peer (P2P) network system to perform communication within a group in a secure manner and at high speed. That is, all the peers within a group in a network system share one key (group key) and perform broadcasting type cryptographic communication.

0082FIG. 3 is a diagram explaining the configuration of a peer-to-peer network system employing the embodiment. As shown in FIG. 3, a group manager in problem in the network system constitutes the key distribution server 10 of the embodiment and the individual peers within the group constitute the subscriber terminals 20.

0083In the above-described network system, when a specific peer leaves the group in the same manner as that in the case where a member leaves "jxta" using "leave" command, in order to perform secure communication within the group after the peer leaves the group, the remaining peers are required to again share a new group key as quickly as possible. At the same time, since a variety of terminals are able to be a peer in the peer-to-peer network system, the system needs to be constructed such that even a terminal whose computing ability is extremely limited can easily obtain the group key. The embodiment can be employed in such peer-to-peer network system to manage the members within the group.

0084When employing the embodiment, since decryption of group key can completely be performed by executing modular exponentiation multiplication 2 times, the terminal within the group is not required to have large computing ability. Furthermore, even when applying the embodiment to a large scale network, a group key can be updated at a high speed without losing efficiency to be available.

[Real time contents distribution system]

0085As a game machine becomes increasingly sophisticated, an advanced on-line game emerges by configuring a peer-to-peer network, each game machine being defined as a peer. That is, a server corresponding to a group manager supplies game contents to individual game machines and then the user plays the game by performing peer-to-peer communication through the game machine.

0086FIG. 4 is a diagram explaining the configuration of a real time contents distribution system employing the embodiment. As shown in FIG. 4, a server for distributing game contents constitutes the key distribution server 10 of the embodiment and the individual game machines constitute the subscriber terminals 20.

0087Under such environment, although it is expected that broadcasting type cryptographic communication needs to frequently be performed within a group, it is also expected that leave from the membership of group frequently occurs. For instance, a user who falls behind in his/her membership charge has to be disconnected from the group. Accordingly, reducing time to perform decryption for sharing a group key with the remaining members, which is required when a member leaves the group, ensures high availability of application.

0088The broadcasting type cryptographic communication system according to the embodiment achieves high-speed decryption capability and can be available for a large scale network, and therefore, can be applied to distribution of contents in the system shown in FIG. 4. That is, the system of the embodiment allows the group key to be shared at high speed and permits the contents encrypted by the group key to be decrypted simultaneously upon reception of the contents, i.e., in real time. Furthermore, time consuming key updating can be performed after reception of the contents using excess processing capability upon execution of the contents. Note that although an example in which communication is performed such that contents are distributed to execute an on-line game is explained, it is needless to say that the broadcasting type cryptographic communication according to the embodiment can be applied to the case where a variety of contents, excluding game contents, to be executed in real time are distributed.

[Distribution of data to portable telephone subscriber]

0089In recent years, portable telephones have drastically been spreading and are now owned and used by over half the people in the country. Then, assume the case where a cryptographic group communication service is provided to some million portable telephone subscribers. For instance, the case includes a case where a specific service is provided to terminals constituting a group.

0090FIG. 5 is a diagram illustrating the configuration of a service supply system for portable telephones, to which system the embodiment is applied. As shown in FIG. 5, a server for supplying services constitutes a key distribution server 10 and portable telephones registered with the service constitute subscriber terminals 20.

0091In the network system thus configured, when a subscriber falls behind in his/her membership charge or has his/her terminal lost or robbed, permissions to access a group, which permissions are given to specific terminals, have to be destroyed. According to the embodiment, even a portable telephone having poor computing ability is able to perform the broadcasting type cryptographic communication by applying the present invention thereto.

[Multimedia contents distribution system]

0092In recent years, a multimedia contents distribution system using a DVD has explosively been spreading.

0093FIG. 6 is a diagram illustrating the configuration of a multimedia contents distribution system constructed in accordance with the embodiment. As shown in FIG. 6, a contents provider who provides multimedia contents constitutes the key distribution server 10 and reproduction machines for reproducing the multimedia contents constitute the subscriber terminals 20.

0094In the system, a DVD medium is distributed storing encrypted digital contents (e.g., movie, music and software) therein. The encrypted contents are decrypted using a decryption key stored within a decipher/reproducer incorporated in the reproduction machine. The decryption key is different depending on individual makers and is stored in a secure memory area of the decipher/reproducer. However, there is danger that the decryption key is leaked, which is observed when crackers analyse the encryption key or a maker fails to correctly make up the key. In this case, it is required to provide a cryptographic algorithm that makes some encryption keys unavailable.

0095When employing the embodiment, security can be maintained in an authenticated manner and updating of the decryption key can be performed in order to make some encryption keys unavailable.

[Secret broadcasting system to address problem of loss/theft of police radio transceiver]

0096Police radio is a typical example of a confidential communication within a group. In this case, a system used for confidential communication needs to be constructed such that even when using a radio receiver except the transceiver owned by a police officer, the communications cannot be monitored.

0097FIG. 7 is a diagram illustrating the configuration of a secret broadcasting system employing the embodiment. As shown in FIG. 7, a broadcasting station for secret broadcasting constitutes the key distribution server 10 and individual radio receivers constitute the subscriber terminals 20.

0098As described above, secret broadcasting such as police radio communication should be performed such that even when using a radio receiver except the transceiver owned by a police officer, communications cannot be monitored. However, in the event a police officer has his/her transceiver lost or robbed, the transceiver lost or robbed is excluded from the group (Φ) consisting of the subscriber terminals 20 and then a new group key is shared by the remaining subscriber terminals in accordance with the embodiment, thereby making the lost transceiver unavailable.

INDUSTRIAL APPLICABILITY

0099As described so far, according to the present invention, a method for updating a group key in a highly secure manner and at a high speed can be provided.

0100Furthermore, according to the present invention, highly secure and highly efficient broadcasting type cryptographic communication can be achieved.