JPH11340962A - Key delivery method and device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide the key delivery method by which a length of data for having a key jointly is decreased even when many recipients (key users) are in existence and which can cope with conspiracy attacks. SOLUTION: A broadcast station 100 generates finite sets A(= s(ij)|1<=i<=m, 1<=j<=n}) consisting of its own secret information and sets Vj(= X1-Xm}|fj(X1- Xm, s(lj)-s(mj))=0), fj is mapping image from a set (z1-z2m)|zi is an integer} to a set Wj(0 belongs to Wi)). r(X, ij)(1<=i<=m) belongs to Vj is selected at random, and s(X, i)=r(X, γ(i)) (1<=i<=mn) (γis mapping image from a set 1-mn} to the set ij}, a secret of te broadcast station) is used for a secret key of a recipient X. u(ij) is generated as information corresponding to s(ij), and y(i)=u(γ(i)) (1<=i<=mn) is used. Identification information dx of the recipient X is calculated by using the s(x, i), and y(1)-y(mn) and the identification information dx are sent to the recipient X. A recipient X200 uses a proper function (h) to calculate a common key K with K=h(s(x, 1)-s(x, mn), y(1)-y(mn), dx).

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a transmitter (key creator) and a receiver (key user) for encrypting / decrypting transmission data for the purpose of performing broadcast encryption communication. And a key distribution method for sharing a common key.

[0002]

2. Description of the Related Art Conventionally, several methods have been proposed for a broadcast encryption communication (key management) method.

[0003] For example, the document "SJKent: Security requ
irement and protocols for a broadcast scenario, IEE
The copy key method described in E Trans. Commun., COM-29, 6, pp. 778-786 (1981) is basic.

[0004] The copy key method is a simple extension of the conventional one-to-one encrypted individual communication to a broadcast communication. Deliver a copy of one type of key to the sender and multiple legitimate recipients. The sender encrypts the transmission data using the copy key and transmits the data. The authorized receiver decrypts the encrypted transmission data using the same copy key.

[0005] In addition, the document "Koyama: Encryption method of broadcast communication using master key, IEICE (D), J65-D, 9, pp. 11
51-1158 (1982) ”, a broadcast encryption communication method using an RSA individual key substitution master key, and a literature“ Li, Tokiwa et al .: Broadcast communication using multiplexing / demultiplexing method, 1986 ” A key distribution method based on the multiplexing and demultiplexing of information sequences using the Chinese remainder theorem described in "Cryptography and Information Security Symposium," or the document "Mitsuho et al .: Efficient Broadcast Encryption Communication System, Technique ISEC93-34 (1993-10) ".

First, a description will be given of a method of performing a multiplexing / demultiplexing method of an information sequence using the Chinese remainder theorem.

(1) Key generation processing: For recipient i (1 ≦ i ≦ s), disjoint s integers g ₁ , g ₂ ,..., G _S (r ≦ s)
Is created, and g _i is set in advance as the secret information of the receiver i.
Distribute to

[0008] (2) the encryption process: M ₁ the s pieces of information sequence to be multiplexed, M _2, ..., and M _S. Sender can send multiplexed sentence
F

[0009]

(Equation 51)

And F is broadcast. However, G, G _i, A _i is,

[0011]

(Equation 52)

Where A _i is the smallest integer satisfying the above equation.

[0013] (3) decoding: Recipient i uses the g _i from F,

[0014]

(Equation 53)

By this, M _i is separated.

Next, the system described in the document "Mitsuho et al .: Efficient Broadcast Encryption Communication System, IEICE 93-34 (1993-10)" will be described.

(1) Key generation processing: A reliable center
As confidential information,

[0018]

(Equation 54)

Is created, and as public information,

[0020]

[Equation 55]

Is created.

Next, the center determines that σ∈S

[0023]

[Equation 56]

Sσ that satisfies is calculated and distributed as secret information of the receiver Uσ. Where the set S = ｛f | one-to-one mapping f: A
= {1,2, ..., k} → B = {1,2, ..., m}, k <m}.

(2) Key distribution processing: The sender randomly selects an integer r,

[0026]

[Equation 57]

For the purpose of sharing the common key K with the receiver,

[0028]

[Equation 58]

Calculate z _i that satisfies, and broadcast z _i (1 ≦ i ≦ m).

The receiver Uσ is

[0031]

[Equation 59]

Is used to calculate a common key K.

[0033]

In key distribution using a multiplexing method using the Chinese remainder theorem, the length of key distribution data increases in proportion to the number of recipients. This poses a problem in terms of efficiency when targeting a large number of recipients of several millions or more, such as a satellite broadcasting service.

On the other hand, according to the method described in the above-mentioned document “Mitsuho et al .: Efficient Broadcast Encryption Communication System, IEICE 93-34 (1993-10)”, when the number of recipients is large, Even if there is, the length of key distribution data can be shortened. However, this method has a problem in that an appropriate number of recipients can collaborate and exchange secret information with each other to calculate secret information of other recipients (this is described in the document "Nishioka: Broadcast Encryption Communication"). A study on key distribution method, IESC96-4
8 (1996-11) "). Another problem is that key sharing cannot be performed only with recipients belonging to an arbitrary set of recipients.

The present invention has been made in view of the above circumstances, and has as its main object to provide a key distribution method and apparatus having the following features.

(1) Each receiver has individual key information and shares a key.

(2) Even if the number of recipients is large,
The length of key distribution data can be shortened.

(3) Even when an appropriate number of recipients collude and exchange secret information with each other, it is difficult to calculate key information of other recipients and secret information of the key creator.

(4) Key sharing can be performed only with recipients belonging to an arbitrary set of recipients.

[0040]

In order to solve the above problems, the present invention employs the following constitution.

1. In the device of the preparation key creator, a finite set AA = {s (ij) | 1 ≦ i ≦ m, 1 ≦ j ≦ n} composed of the secret information of the key creator, and a set Vj Vj = {(X1, ..., Xm) | fj (X1, ..., Xm, s (1j), ..., s (mj)) =
0} (1 ≦ j ≦ n) (where fj is the set W from the set {(z1, ..., z2m) | zi is an integer)
j (appropriate mapping to (0)).

Next, (r (x, ij)) (1 ≦ i ≦ m) ∈Vj (1 ≦ j ≦
n) is selected at random and s (x, i) = r (x, γ (i)) (1 ≦ i ≦ mn) (where γ is the set {1,2, …, Mn} from the set {ij | 1 ≦ i ≦ m, 1
≦ j ≦ n}, which is to be the secret of the key creator), and distribute this.

2. In the key distribution processing key creator's device,
U (ij) (1 ≦ i ≦ m, 1 ≦ j ≦ n) is created as information corresponding to the secret information s (ij) of the key creator, and y (i) = u (γ (i)) (1 ≦ i ≦ mn).

Next, using the secret key s (x, i) of the key user x, the identification information dx of the key user x is calculated, and y (1),.
(mn) and the identification information dx are transmitted to the key user x.

In response to this, in the device of the key user x, using an appropriate function h, K = h (s (x, 1), ..., s (x, mn), y (1) , ..., y (mn), dx), the common key K shared with the key creator is calculated.

Here, 2. As a key distribution process, in the key creator's device, a random number r is selected, z (i) = g (y (i), r) (1 ≦ i ≦ mn) is calculated by an appropriate function g, and z ( 1), ..., z (mn) is transmitted to the key user x, and K = h (s (x, 1), ... ., s (x, mn), z (1),..., z (mn), dx), the common key K shared with the key creator may be calculated.

By doing so, it is possible to change the shared key K by changing the random number r.

Hereinafter, an example of an implementation method of the present invention will be described.

1. Preparation process In the key creator's device,

[0050]

[Equation 60]

It is assumed that a set of secret information of the key creator
Set KP of KS and public information (Set KP is finite abel (multiplication)
(Including an element that determines the group G) (however, γ
∈ {γ | one-to-one mapping γ: C = {1,2, ..., mn} → D = {ij | 1 ≦
i ≦ m, 1 ≦ j ≦ n}} and ord _G (g) is

[0052]

[Equation 61]

Represents the smallest positive integer x).

Next, an integer r (x, ij) (1 ≦ i ≦ m, 1 ≦ j ≦
n) is selected at random, and s (x, i) = r (x, γ (i)) (1 ≦ i ≦ m
For (n), (s (x, i)) (1 ≦ i ≦ mn) is distributed as a secret key of key user x.

2. Key distribution processing In the key creator's device, an integer ξ _F is randomly selected,

[0056]

(Equation 62)

For the purpose of sharing a key K that satisfies only with key users belonging to an arbitrary subset F of the set of all key users,

[0058]

[Equation 63]

Thus, as broadcast data,

[0060]

[Equation 64]

Y (i) that satisfies

[0062]

[Equation 65]

[0063] Calculate the integer satisfying the d (x, ξ _F), the broadcast data y (i), d (x , ξ F) the broadcasts.

[0064] In response to this, in the apparatus of the key user x (x∈F), the broadcast data y (i), d (x , ξ F) with its own distributed by the key creator (key usage Key information (s (x,
i)) (1 ≦ i ≦ mn)

[0065]

[Equation 66]

(However, f _i (1 ≦ i ≦ mn) is a function published by the key creator, and f _i (s (x, i), y (i)) = c (x, γ (i) , ξ _F )
To calculate the common key K.

Here, when changing the key K shared between the key creator and the key user x, the following processing is performed.

2. As a key distribution process, the key creator's device randomly selects an integer ζ

[0069]

[Equation 67]

For the purpose of sharing a key K that satisfies only with key users belonging to an arbitrary subset F included in the set of all key users, as broadcast data,

[0071]

[Equation 68]

The broadcast data z (i) is broadcast by transmitting z (i) that satisfies the broadcast data z (i), and the broadcast data z (i) is sent to the device of the key user x (x∈F). ) And d previously broadcast
(x, ξ _F ) and the self (key user) distributed by the key creator.
x) key information (s (x, i)) (1 ≦ i ≦ mn)

[0073]

[Equation 69]

Thus, the common key K is calculated.

The following is a more specific description of an example of the above-described realizing method.

1. Preparation process In the key creator's device, as the secret information of the key creator,

[0077]

[Equation 70]

Is created, and as public information,

[0079]

[Equation 71]

(Where 0 <g ₁ , g ₂ <N, and ord _G (g) is

[0081]

[Equation 72]

Represents the smallest positive integer x).

Next, an integer r (x, ij) (1 ≦ i ≦ m, 1 ≦ j ≦
2) is selected at random, and s (x, i) = r (x, γ (i)) (1 ≦ i ≦ 2
For (m), (s (x, i)) (1 ≦ i ≦ 2m) is distributed as key information of the key user x.

2. Key distribution processing In the key creator's device, an integer ξ _F is randomly selected,

[0085]

[Equation 73]

For the purpose of sharing the common key K that satisfies only with key users belonging to an arbitrary subset F of the entire set of key users,

[0087]

[Equation 74]

Thus, as broadcast data,

[0089]

[Equation 75]

Y (i) that satisfies

[0091]

[Equation 76]

An integer d (x, ξ _F ) that satisfies is calculated, and the broadcast data y (i), d (x, 同_F ) are broadcast.

In response to this, in the device of the key user x (x) _F ), the broadcast data y (i), d (x, ξF) and the self (key usage) distributed by the key creator are transmitted. Key information (s (x,
i)) (1 ≦ i ≦ 2m)

[0094]

[Equation 77]

(Where f _i (1 ≦ i ≦ 2m) is a function published by the key creator, f _i (s (x, i), y (i)) = c (x, γ (i),共通_F )) to calculate the common key K.

Here, when changing the key K shared between the key creator and the key user x, the following processing is performed.

2. As a key distribution process, the key creator's device randomly selects an integer ζ

[0098]

[Equation 78]

For the purpose of sharing a common key K that satisfies only with key users belonging to an arbitrary subset F included in the set of all key users, as broadcast data,

[0100]

[Expression 79]

The broadcast data z (i) is broadcast by transmitting z (i) that satisfies the broadcast data z (i), and the broadcast data z (i) is sent to the key user x (x∈F). D (x,
ξ _F ) and itself distributed by the key creator (key user x)
Key information (s (x, i)) (1 ≦ i ≦ 2m),

[0102]

[Equation 80]

Thus, the common key K is calculated.

[0104]

Embodiments of the present invention will be described below.

In each of the embodiments described below, for a positive integer N and a positive integer g, ord _N (g) = m is

[0106]

[Equation 81]

Represents that the minimum positive integer x to be m is m.

First, as a first embodiment of the present invention, a case will be described in which a key distribution method for broadcast encryption communication is applied to an information distribution service system using satellite broadcasting. That is, information (including paid data) such as multimedia information broadcasted and encrypted by a broadcasting station using a satellite.
A key distribution method for sharing a key between a broadcasting station and a receiver so that only a receiver who has viewing qualifications (or a receiver who has agreed to pay a fee) can decrypt the key. I do.

FIG. 1 shows a schematic configuration of a key distribution system to which the first embodiment of the present invention is applied. As shown in FIG. 1, the system according to the present embodiment includes a broadcasting station-side device 100 that is a key creator's device and a plurality of receiver-side devices 200 that are key user's devices. The broadcasting station-side device 100 and the plurality of receiver-side devices 200 are connected to the communication line 3
00 are connected to each other. Broadcast station side device 100
Uses the communication satellite 500 to broadcast and encrypt information such as multimedia information (including paid data). The receiver-side apparatus 200 decrypts the data broadcast and encrypted by the broadcast station-side apparatus 100 using a key shared between the receiver and the broadcast station.

FIG. 2 shows a schematic configuration of the broadcast station side apparatus 100 shown in FIG. As shown in FIG. 2, the broadcast station side device 100 includes a random number generator 101, a prime number generator 102, an arithmetic device 103, a power multiplier 104, a remainder arithmetic device 105,
Key generator 106, encryption / decryption device 107, communication device 10
8, an authentication device 109, a billing device 110, and a memory 111. Here, a random number generator 101, a prime number generator 102, an arithmetic unit 103, a power multiplier 104, a remainder arithmetic unit 105, a key generator 106, an encryption / decryption device 10
7. The authentication device 109 and the billing device 110 may be provided as hardware by combining logic circuits or the like, or may be realized by executing a predetermined program in an information processing device. You may. This predetermined program can be stored in a storage medium such as a CD-ROM.

FIG. 3 shows a schematic configuration of the receiving apparatus 200 shown in FIG. As shown in FIG.
00 is a memory 201, a power multiplier 202, a remainder arithmetic unit 203, an arithmetic unit 204, an authentication unit 205, and a communication unit 2.
06, a key generator 207, an encryption / decryption device 208, and
An IC card connection device 209 is provided. Here, the exponent multiplier 202, remainder arithmetic unit 203, arithmetic unit 204, authentication unit 205, key generator 207, and encryption / decryption unit 208 may be provided as hardware by combining logic circuits or the like. Alternatively, the information processing apparatus may be realized by executing a predetermined program. The predetermined program is a CD-R
It is also possible to store in a storage medium such as OM.

The operation of the key distribution system to which the present embodiment having the above configuration is applied will be described with reference to FIG. FIG. 4 is a diagram for explaining a flow of information in the key distribution system shown in FIG.

1. Preparation Processing The following processing is performed in the broadcast station side apparatus 100.

The arithmetic unit 103 includes a random number generation unit 101, a prime number generation unit 102, a power multiplier 104, and a remainder operation unit 1 in accordance with an instruction from a reliable key creator of the broadcasting station.
The following information will be created with the help of 05.

Secret information:

[0116]

(Equation 82)

Public information:

[0118]

[Equation 83]

[0119] The created secret information is stored in the memory 111. On the other hand, the public information is disclosed by a method of distributing it to the recipient together with the confidential information of the recipient, or distributing it to the recipient by including it in the broadcast data.

Next, the arithmetic unit 103 includes the random number generator 10
1, an integer r (x, ij) (1 ≦ i ≦ m, 1 ≦ j ≦ 2) is selected at random, and s (x, i) = r (x, γ (i)) (1 ≦ i ≦ (2m), (s (x, i)) (1 ≦ i ≦ 2m) is set as the secret key of the key user x. The private key of the recipient x is stored in a storage medium such as a floppy disk, an IC card,
Distributed to x.

2. Key Distribution Processing First, the following processing is performed in the broadcast station side device 100.

[0122] The key generator 106 uses a random number generator 101 to select the integer xi] _F at random. Next, the power multiplier 1
04, with the cooperation of the remainder arithmetic unit 105 and the arithmetic unit 103,

[0123]

[Equation 84]

A common key K that satisfies is generated. Then, for the purpose of sharing the generated common key K only with key users belonging to an arbitrary subset F of the set of all key users,

[0125]

[Equation 85]

Thus, as broadcast data,

[0127]

[Equation 86]

Y (i) that satisfies

[0129]

[Equation 87]

An integer d (x, ξ _F ) that satisfies is calculated.

The encryption / decryption device 107 encrypts transmission data P such as multimedia information using the above-described key K,
Create ciphertext C.

The communication device 108 converts the generated broadcast data y (i) (1 ≦ i ≦ 2m) and d (x, ξ _F ) using the Chinese remainder theorem described in the above-mentioned conventional technique. Multiplexing is performed by a multiplexing method or the like to create multiplexed data W. Then, the created multiplexed data W is broadcasted to the receiver device 200 via the communication satellite 500.

The ciphertext C created by the encryption / decryption device 107 is transmitted via the communication satellite 500 to the receiver device 200.
Broadcast to.

On the other hand, the receiver device 2 of the receiver x (x∈F)
At 00, the following processing is performed.

Communication device 206 receives multiplexed data W and ciphertext C broadcasted via communication satellite 500. Of these, the multiplexed data W is separated and y
(i) (1 ≦ i ≦ 2m) and d (x, ξ _F ) are obtained.

The key generator 207, with the cooperation of the power multiplier 202, the remainder arithmetic unit 203 and the arithmetic unit 204,
Y (i) (1 ≦ i ≦ 2m), d (x,
and xi] _F), are distributed by the broadcast station, because previously the recipient's private key x that is stored in the memory 201 (s (x, i) ) and (1 ≦ i ≦ 2m),

[0137]

[Equation 88]

(However, f _i (1 ≦ i ≦ 2m) is a function published by the key creator, and f _i (s (x, i), y (i)) = c (x, γ (i) , ξ _F )
To calculate the common key K.

The encryption / decryption device 208 decrypts the cipher text C received by the communication device 206 using the common key K generated by the key generator 207, and obtains the original transmission data P.

As described in the above-mentioned conventional technique, as described in the literature "Mitsuho et al .: Efficient Broadcast Encryption Communication System, IEICE93
-34 (1993-10)] is based on the document "Nishioka: A Study on Key Distribution Method in Broadcast Encryption Communication, IEICE IS".
As reported in EC96-48 (1996-11), an appropriate number of recipients can collaborate, share their secret information with each other, and solve predetermined Secret information can be calculated. That is, the collusion attack of the receiver becomes effective.

On the other hand, according to the present embodiment, while the γ used to calculate the secret information of the receiver is kept secret from the receiver as the secret information of the broadcasting station, the common key K is shared. Therefore, the key can be shared between the broadcasting station and the receiver without informing the receiver of information that makes the collusion attack effective. For this reason, the possibility that the confidential information of the receiver leaks to a third party can be further reduced.

[0142] In the present embodiment, by changing the value of xi] _F for generating a random number generator 101 in response to the transmission data P, the identification of the transmission data P, i.e., the transmission data P
, It is possible to set a common key K for decrypting the ciphertext C.

In this embodiment, the transmission data P
When changing the common key K for This can be realized by further performing the following processing in the key distribution processing.

First, the following processing is further performed in the broadcast station side apparatus 100.

The key generator 106 uses the random number generator 101 to randomly select an integer ζ. Next, the power multiplier 10
4. With the cooperation of the remainder arithmetic unit 105 and the arithmetic unit 103,

[0146]

[Equation 89]

A common key K that satisfies is generated. Then, for the purpose of sharing the generated common key K only with key users belonging to an arbitrary subset F of the entire set of key users, as broadcast data,

[0148]

[Equation 90]

Z (i) that satisfies is calculated.

The communication device 108 multiplexes the created broadcast data z (i) (1 ≦ i ≦ 2m) by the multiplexing method using the Chinese remainder theorem described in the above-mentioned conventional technique. , Via the communication satellite 500.

On the other hand, the receiver device 2 of the receiver x (x∈F)
At 00, the following processing is performed.

The communication device 206 receives the multiplexed data broadcasted via the communication satellite 500 and separates the multiplexed data to obtain z (i) (1 ≦ i ≦ 2m).

The key generator 207, with the cooperation of the power multiplier 202, the remainder arithmetic unit 203 and the arithmetic unit 204,
Z (i) (1 ≦ i ≦ 2m) separated by the communication device 206, d (x, ξ _F ) obtained earlier, and the memory 2 distributed by the broadcast station.
01 secret key of recipient x (s (x, i)) stored in 01 (1 ≦ i ≦ 2m)
And from

[0154]

[Equation 91]

(However, f _i (1 ≦ i ≦ 2m) is a function published by the key creator, and f _i (s (x, i), z (i)) = c (x, γ (i) ,
共通_F )) to calculate the common key K.

In this way, the shared key K can be changed by changing the integer ζ.

As described above, the first embodiment of the present invention has been described.

Hereinafter, a second embodiment of the present invention will be described.

In the present embodiment, a method of charging a receiver in the case where the transmission data P is charged in the first embodiment will be described. Here, 2. of the first embodiment. In the key distribution process, the broadcast station side device 100
Instead of multiplexing broadcast data y (i) (1 ≦ i ≦ 2m) and d (x, ξ _F ) and broadcasting them, multiplex only y (i) (1 ≦ i ≦ 2m). And broadcast it. And d (x,
Regarding ξ _F ), an authentication process is performed between the broadcasting station and the receiver, and transmission is performed via the communication line 300 only to the receiver device 200 of the authenticated receiver.

Hereinafter, an authentication process performed between a broadcasting station and a receiver will be described.

First, the broadcast station side apparatus 100 sets the key generator 1
06, the public key p (x) corresponding to the secret key (s (x, i)) (1 ≦ i ≦ 2m) of the receiver x is set to 2.x of the first embodiment. It is created before the key distribution process and stored in the memory 109.

The receiver device 200 of the receiver x (x∈F)
In order to obtain the authority to decrypt the cipher text C of the transmission data P broadcasted by the broadcasting station apparatus 100, the communication apparatus 206 transmits the broadcast station apparatus 100 (or Access the associated device).

When the broadcast station apparatus 100 receives access from the receiver apparatus 200 of the receiver x, the random number generator 10
A random number r is generated by 1. Then, the communication device 108 transmits the data to the receiver device 200 of the receiver x via the communication line 300.

Upon receiving the random number r from the broadcast station side device 100, the receiver side device 200 of the receiver x receives the authentication device 205
By using the secret key (s (x, i)) (1 ≦ i ≦ 2m) of the receiver x previously distributed by the broadcasting station and stored in the memory 201,
Create a signature sgn _X (r) for random number r. Then, the created signature sgn _X (r) is transmitted to the communication line 3 by the communication device 206.
00 to the broadcast station side device 100.

Here, many specific methods for performing the signature are known. For example, the document `` R.
L. Rivest, A. Shamir, L. Adleman .: A method for obtainin
g digital signatures and publickey cryptosystems, C
ommun. of the ACM, Vol.21, No.2, pp.120-126, 198
7. Using the RSA encryption described in “7.
ed Federal Information Processing Standard (DSS),
Federal Register, v.56, n.169,30, pp.42980-42982 (1
991)).

When receiving the signature sgn _X (r) from the receiver device 200 of the receiver x, the broadcast station device 100 receives the authentication device 1.
At 09, the validity of the signature sgn _X (r) is confirmed using the public key p (x) of the receiver x stored in the memory 109. Then, only if the validity is confirmed, d (x, ξ _F )
Is transmitted to the receiver apparatus 200 of the receiver x via the communication line 300. Further, the charging device 110 charges the receiver x.

In this embodiment, as described above, the key can be shared between the broadcasting station and the receiver without informing the receiver of the information that makes the collusion attack effective. Therefore, in order for a third party to decrypt the ciphertext C of the transmission data P, that is, in order to obtain the common key K, the secret key of the receiver x from the receiver x (s (x, i)) It is estimated that (1 ≦ i ≦ 2m) must be obtained (that is, a cross flow is required).

In this embodiment, only when the recipient x is authenticated using the secret key (s (x, i)) (1 ≦ i ≦ 2m),
The authority to decrypt the ciphertext C of the transmission data P is given. Therefore, the secret key (s (x, i)) (1
≤ i ≤ 2m), the secret key (s (x,
i)) When the authentication process is performed using (1 ≦ i ≦ 2m) and the user is authorized to decrypt the ciphertext C of the transmission data P by impersonating the recipient x, the charge for the transmission data P is diverted. Will be performed for the recipient x who has done this. in this way,
By constructing the system so that the recipient x who performed the distribution is disadvantaged, the unauthorized recipient can distribute the secret information to a third party who does not have the authority to view the transmitted data, and illegally Transfer of the viewing authority can be prevented.

The second embodiment of the present invention has been described above.

Next, a third embodiment of the present invention will be described.

In this embodiment, in the first embodiment, the receiver x stores its own secret key (s (x, i)) (1 ≦ i ≦ 2m) distributed from the broadcasting station. By using an IC card, it is possible to more efficiently prevent the private key (s (x, i)) (1 ≦ i ≦ 2m) from leaking to a third party while sharing it with the broadcasting station. A method for calculating the common key K will be described.

FIG. 5 is a block diagram showing the I-mode used in the third embodiment of the present invention.
2 shows a schematic configuration of a C card 400.

As shown in FIG. 5, the IC card 400
A power multiplier 401, a memory 402, an arithmetic unit 403, a remainder arithmetic unit 404, an authentication information creation unit 405, and an input / output unit 406 are provided. Here, the power multiplier 40
1, the arithmetic unit 403, the remainder arithmetic unit 404, and the authentication information creating unit 405 may be provided as hardware by combining logic circuits or the like, or
The CPU of the C card may be realized by executing a predetermined program.

The operation of this embodiment is similar to the operation of the receiver side apparatus 200.
Is basically the same as that of the first embodiment, except that the calculation process of the common key K performed in is different.

In the present embodiment, the second embodiment is similar to the second embodiment. In the key distribution process, when the IC card 400 is inserted into the IC card coupling device 209 of the receiver device 200 of the receiver x, the arithmetic device 403 in the IC card 400 makes the cooperation of the power multiplier 401 and the remainder arithmetic device 404. And the secret key (s (x, i)) (1) of the receiver x stored in the memory 402 in advance.
≦ i ≦ 2m) and y (i) or z (i) separated from the multiplexed data W by the communication device 206 of the receiver-side device 200,

[0176]

(Equation 92)

Alternatively,

[0178]

[Equation 93]

K (x, i) that satisfies is calculated. Result K
(x, i) is input / output device 406 to the recipient device 20
0 via the IC card connection device 209
0 is stored in the memory 201.

In the receiver device 200 of the receiver x,
The key generator 106 includes the remainder arithmetic unit 203 and the arithmetic unit 2
Multiplexed data by the communication device 206 with the cooperation of
D (x, ξ _F ) separated from W and IC card connecting device 2
K (x, i) sent from IC card 400 via 09
And based on

[0181]

[Equation 94]

Alternatively,

[0183]

[Equation 95]

Thus, the common key K is calculated.

In this embodiment, when performing the same authentication processing as in the second embodiment, the IC card 400
The authentication information generating apparatus 405 uses the secret key (s (x, i)) (1 ≦ i ≦ 2m) of the receiver x stored in the memory 402 to change the receiver apparatus 200 to the broadcast station apparatus. A signature sgn _X (r) for the random number r received from 100 is created. And
The created signature sgn _X (r) is transmitted by the communication device 206 of the receiver device 200 to the broadcast station device 100 via the communication line 300. Subsequent authentication processing may be performed between the authentication device 109 of the broadcast station device 100 and the authentication device 205 of the receiver device 200 in the same manner as in the second embodiment.

As described above, each embodiment of the present invention has been described. The present invention is not limited to the above-described embodiments, and various modifications can be made within the scope of the gist.

For example, in each of the above embodiments, f _i (s (x, i), y (i)) and f _i (s
(x, i), as an alternative to z (i)), both the broadcasters and recipient x that can be known, varies according to the value of xi] _F, and,
A value unique to the receiver x may be used. For example, f _i (r _i , ID (x)) generated using the random number r _i (1 ≦ i ≦ 2m) generated by the random number generator 101 of the broadcast station apparatus 100 and transmitted by the communication device 108 It may be used (however, ID (x) is the ID information of the receiver x). Alternatively, a value that is randomly selected and disclosed by the receiver x may be used.

Further, the method of distributing the common key K is not limited to the mathematical formulas described in the above embodiments. The present invention only needs to execute the following processing.

1. Preparation Processing The following processing is performed in the broadcast station side apparatus 100.

A finite set AA = {s (ij) | 1 ≦ i ≦ m, 1 ≦ j ≦ n} consisting of secret information of a broadcasting station and a set Vj Vj = {(X1,..., Xm) | fj (X1, ..., Xm, s (1j), ..., s (mj)) =
0} (1 ≦ j ≦ n) (where fj is the set W from the set {(z1, ..., z2m) | zi is an integer)
j (appropriate mapping to (0)).

Next, (r (x, ij)) (1 ≦ i ≦ m) ∈Vj (1 ≦ j ≦
n) is randomly selected, and s (x, i) = r (x, γ (i)) (1 ≦ i ≦ mn) (where γ is a set {1,2, ...) , mn} from the set {ij | 1 ≦ i ≦ m, 1
≦ j ≦ n}, which is to be the secret of the key creator), and distribute this.

[0192] 2. Key Distribution Processing The following processing is performed in the broadcast station side device 100.

As information corresponding to the secret information s (ij) of the broadcasting station, u (ij) (1 ≦ i ≦ m, 1 ≦ j ≦ n) is created, and y (i) = u (γ (i) ) (1 ≦ i ≦ mn).

Next, using the secret key s (x, i) of the receiver x,
The identification information dx of the receiver x is calculated, and y (1),..., Y (mn) and the identification information dx are transmitted to the receiver x.

In response to this, in the device of the key user x, using an appropriate function h, K = h (s (x, 1), ..., s (x, mn), y (1) , ..., y (mn), dx), the common key K shared with the key creator is calculated.

[0196]

As described above, according to the present invention,
Even in the case where the number of recipients (key users) is large in broadcast encryption communication, the length of key distribution data (broadcast transmission data) can be shortened (constant).

Further, it is possible to make it difficult to perform a collusion attack in which unauthorized recipients share secret information of each other and calculate secret information of other recipients. Thus, key distribution can be performed efficiently and safely.

[Brief description of the drawings]

FIG. 1 is a schematic configuration diagram of a key distribution system to which a first embodiment of the present invention has been applied.

FIG. 2 is a schematic configuration diagram of a broadcasting station side device 100 shown in FIG.

FIG. 3 is a schematic configuration diagram of a receiver-side device 200 shown in FIG.

FIG. 4 is a diagram for explaining a flow of information in the key distribution system shown in FIG.

FIG. 5 is an IC card 40 used in the third embodiment of the present invention.
0 is a schematic configuration diagram.

[Explanation of symbols]

 REFERENCE SIGNS LIST 100 Broadcasting station side device 101 Random number generator 102 Prime number generator 103, 204, 403 Arithmetic unit 104, 202, 401 Exponentiation multiplier 105, 203, 404 Remainder arithmetic unit 106, 207 Key generator 107, 208 Encryption / decryption unit 108 , 206 Communication device 109, 205 Authentication device 110 Billing device 111, 201, 402 Memory 200 Receiver side device 209 IC card connection device 400 IC card 405 Authentication information creation device 406 Input / output device

Claims (32)

[Claims] A key distribution method for a plurality of key users to share common key information for performing cryptographic communication with the key creator by using individual key information created in advance by the key creator. And 1. As a preparation process, in the key creator's device, a finite set AA = {s (ij) | 1 ≦ i ≦ m, 1 ≦ j ≦ n} composed of secret information of the key creator, and a set Vj Vj = {( X1, ..., Xm) | fj (X1, ..., Xm, s (1j), ..., s (mj)) =
0} (1 ≦ j ≦ n) (where fj is the set W from the set {(z1, ..., z2m) | zi is an integer)
j (appropriate mapping to (∋0)) and (r (x, ij)) (1 ≦ i ≦ m) ∈Vj (1 ≦ j ≦ n) are randomly selected, and the key user x S (x, i) = r (x, γ (i)) (1 ≦ i ≦ mn) (where γ is a set {ij | 1 ≦ i ≦ m, 1
≤j≤n}, and distributes this key secret. As a key distribution process, in the key creator device, u (ij) (1 ≦ i ≦ m, 1 ≦ j ≦ n) is created as information corresponding to the secret information s (ij) of the key creator, y (i) = u (γ (i)) (1 ≦ i ≦ mn), and using the secret key s (x, i) of the key user x, the identification information dx of the key user x And transmitting y (1),..., Y (mn) and identification information dx to the key user x. Using h, K = h (s (x, 1), ..., s (x, mn), y (1),…, y (mn), dx) Calculating a key K. 2. The key distribution method according to claim 1, wherein As a key distribution process, a step of selecting a random number r and calculating z (i) = g (y (i), r) (1 ≦ i ≦ mn) by an appropriate function g in the key creator's device; transmitting z (1), ..., z (mn) to key user x;
In the device of the key user x, using an appropriate function h, K = h (s (x, 1), ..., s (x, mn), z (1), ..., z (mn), dx), the key distribution method further comprising the step of calculating a common key K shared with the key creator. 3. A key distribution method for a plurality of key users to share common key information for performing cryptographic communication with the key creator by using individual key information created in advance by the key creator. And 1. As a preparation process, in the key creator's device, A step of creating a set KS of secret information of the key creator and a set KP of public information (the set KP includes elements for determining a finite abel (multiplication) group G) (where γ∈
{γ | one-to-one mapping γ: C = {1,2, ..., mn} → D = {ij | 1 ≦ i
≦ m, 1 ≦ j ≦ n}}, and ord _G (g) is given by And a step of randomly selecting an integer r (x, ij) (1 ≦ i ≦ m, 1 ≦ j ≦ n), and s (x, i) = r (x, γ) (i)) For (1 ≦ i ≦ mn), (s (x, i))
(1 ≦ i ≦ mn) as a secret key of the key user x. As the key distribution process, the key creator's device randomly selects an integer ξ _F , In order to share a key K that satisfies with only key users belonging to an arbitrary subset F of the set of all key users, From, as broadcast data, Y (i) that satisfies and Calculating an integer d (x, ξ _F ) that satisfies the following conditions; and transmitting the broadcast data y (i) and d (x, ξ _F ). ∈F), the broadcast data y (i), d (x, ξ _F ) and its own (key user x) key information (s (x, i)) distributed by the key creator. (1 ≦ i
≤ mn) (However, f _i (1 ≦ i ≦ mn) is a function published by the key creator, and f _i (s (x, i), y (i)) = c (x, γ (i), ξ _F )), A step of calculating a common key K. 4. The key distribution method according to claim 3, wherein: As the key distribution process, an integer ζ is randomly selected in the key creator's device. For the purpose of sharing only the key users belonging to an arbitrary subset F included in the set of the entire key users with the key K satisfying the above, as broadcast data, Further comprising: calculating z (i) that satisfies the following condition; and broadcasting the broadcast data z (i), wherein the device of the key user x (x 装置 F) comprises: D (x, ξ _F ) previously broadcasted with data z (i)
From the key information (s (x, i)) (1 ≦ i ≦ mn) of the own (key user x) distributed by the key creator, A key distribution method, further comprising the step of: 5. The key distribution method according to claim 4, wherein f _i (s (x, i), y (i)) and f _i (s (x, i), z (i)) (1 as an alternative to ≦ i ≦ mn), it is possible to know both the key authors and key users x, varies according to the value of xi] _F, and the key user x
A key distribution method using a value unique to a key. 6. The key distribution method according to claim 5, further comprising the step of transmitting a random number r _i (1 ≦ i ≦ mn) at the key creator device, wherein f _i (s (x, i ), y (i)) and f _i (s (x, i), z (i)) instead of f _i (r _i , ID (x)) (where ID (x) is a key Person x
ID information). 7. The key distribution method according to claim 5, wherein f _i (s (x, i), y (i)) and f _i (s (x, i), z (i)) A key distribution method characterized in that the value is randomly selected and disclosed by the key user x. 8. The key distribution method according to claim 3, 4, 5, 6, or 7, wherein in the device of the key user x, the key user x sends a key to the device of the key creator. Information (s
(x, i)) and performing the authentication process by carrying the (1 ≦ i ≦ mn), only d (x if the authentication is successful, receiving a xi] _F), further comprising a Characteristic key distribution method in cryptographic communication. 9. The key distribution method according to claim 8, wherein in the key creator device, when the authentication processing of the key user x is completed, or d (x,
鍵_F ), further comprising the step of charging the key user x when transmitting. 10. A key distribution method for a plurality of key users to share common key information for performing cryptographic communication with a key creator using individual key information created in advance by the key creator. And 1. As preparation processing, in the key creator's device, as secret information of the key creator, Is created, and as public information, (Where 0 <g ₁ , g ₂ <N and or
d _G (g) is given by And a step of randomly selecting an integer r (x, ij) (1 ≦ i ≦ m, 1 ≦ j ≦ 2), and s (x, i) = r (x, γ) (i)) (1 ≦ i ≦ 2m), then (s (x, i))
(1 ≦ i ≦ 2m) as key information of the key user x. As the key delivery process, in the apparatus of the key author, select the integer ξ _F at random, [number 14] In order to share the common key K that satisfies with only the key users belonging to an arbitrary subset F of the set of the entire key users, , As broadcast data, Y (i) that satisfies and Calculating an integer d (x, ξ _F ) that satisfies the following, and a step of broadcasting the broadcast data y (i), d (x, ξ _F ). ∈F), the broadcast data y (i), d (x, ξ _F ) and its own (key user x) key information (s (x, i)) distributed by the key creator. (1 ≦ i
≦ 2m) (However, f _i (1 ≦ i ≦ 2m) is a function published by the key creator, f _i (s (x, i), y (i)) = c (x, γ (i), ξ _F ) ), A step of calculating a common key K. 11. The key distribution method according to claim 10, wherein: As the key distribution process, an integer ζ is randomly selected in the key creator's device. For the purpose of sharing a common key K satisfying only with key users belonging to an arbitrary subset F included in a set of all key users, as broadcast data, Further comprising: calculating z (i) that satisfies the following condition; and broadcasting the broadcast data z (i), wherein the device of the key user x (x 装置 F) comprises: D (x, ξ _F ) previously broadcasted with data z (i)
From the key information (s (x, i)) (1 ≦ i ≦ 2m) of the self (key user x) distributed by the key creator, A key distribution method, further comprising the step of: 12. The key distribution method according to claim 11, wherein f _i (s (x, i), y (i)) and f _i (s (x, i), z (i)) (1 as an alternative to ≦ i ≦ 2m), it is possible to know both the key authors and key users x, varies according to the value of xi] _F, and the key user x
A key distribution method using a value unique to a key. 13. The key distribution method according to claim 12, further comprising the step of transmitting a random number r _i (1 ≦ i ≦ 2m) in the key creator device, wherein f _i (s (x, i ), y (i)) and f _i (s (x, i), z (i)) instead of f _i (r _i , ID (x)) (where ID (x) is a key Person x
ID information). 14. A key distribution method according to claim 12, wherein f _i (s (x, i), y (i)) and f _i (s (x, i), z (i)) A key distribution method characterized in that the value is randomly selected and disclosed by the key user x. 15. The method of claim 10, 11, 12, 13 or 1.
4. The key distribution method according to claim 4, wherein, in the device of the key user x, the key user x transmits its own key information (s
(x, i)) and performing the authentication process by carrying the (1 ≦ i ≦ 2m), only d (x if the authentication is successful, receiving a xi] _F), further comprising a Characteristic key distribution method. 16. The key distribution method according to claim 15, wherein in the key creator device, when the authentication process of the key user x is completed, or d (x,
鍵_F ), further comprising the step of charging the key user x when transmitting. 17. The method of claim 4, 5, 6, 7, 8, 9, 11,
12. The key distribution method according to 12, 13, 14, 15 or 16, wherein the shared key K is changed by changing the value of ζ. 18. A key distribution program for a plurality of key users to share common key information for performing cryptographic communication with the key creator by using individual key information created in advance by the key creator. Is stored in a storage medium, wherein the key distribution program stores the information in an information processing apparatus, in accordance with claim 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1.
A storage medium storing a key distribution program for executing a step in a key creator's apparatus of the key distribution method according to 1, 12, 13, 14, 15, 16, or 17. 19. A key sharing program for a plurality of key users to share common key information for performing cryptographic communication with the key creator by using individual key information created in advance by the key creator. Wherein the key sharing program is stored in an information processing apparatus by the information processing apparatus.
A storage medium storing a key sharing program for executing the steps in the apparatus of the key user x in the key distribution method according to 1, 12, 13, 14, 15, 16 or 17. 20. A key distribution device for a key creator to share common key information for performing cryptographic communication with a plurality of key users, wherein the finite set includes secret information of the key creator. AA = {s (ij) | 1 ≦ i ≦ m, 1 ≦ j ≦ n｝ and the set Vj Vj = {(X1, ..., Xm) | fj (X1, ..., Xm, s (1j ), ..., s (mj)) =
0} (1 ≦ j ≦ n) (where fj is the set W from the set {(z1, ..., z2m) | zi is an integer)
j (appropriate mapping to ∋0)) and (r (x, ij)) (1 ≦ i ≦ m) ∈Vj (1 ≦ j ≦ n) are randomly selected, and the key user x S (x, i) = r (x, γ (i)) (1 ≦ i ≦ mn) (where γ is a set {ij | 1 ≦ i ≦ m, 1
≤j≤n}, and u (ij) (1≤i) as information corresponding to the secret information s (ij) of the key creator. ≤ m, 1 ≤ j ≤ n), means for obtaining y (i) = u (γ (i)) (1 ≤ i ≤ mn), and a secret key s (x, i) of key user x Means for obtaining the identification information dx of the key user x, and means for transmitting y (1),..., Y (mn) and the identification information dx to the key user x. A key distribution device, characterized in that: 21. The key distribution device according to claim 20, wherein a random number r is selected, and z (i) = g (y (i), r) (1 ≦ i ≦ mn) is determined by an appropriate function g. A key distribution apparatus further comprising: means for calculating; and means for transmitting z (1),..., Z (mn) to a key user x. 22. A key sharing device for a key user x to obtain common key information shared with a key creator based on data transmitted from the key distribution device according to claim 21. Y (1), ..., y (mn) sent from
(Or z (1), ..., z (mn)) and dx, and an appropriate function h based on the secret key s (x, i) of the key user x distributed by the key creator. K = h (s (x, 1), ..., s (x, mn), y (1),…, y (mn), dx) or K = h (s (x, 1 ), ..., s (x, mn), z (1), ..., z (mn), dx) by means of calculating a common key K shared with the key creator. Key sharing device. 23. A key distribution device for sharing a common key information for a key creator to perform cryptographic communication with a plurality of key users, comprising: Means for generating a set KS of secret information of the key creator and a set KP of public information (the set KP includes elements for determining a finite abel (multiplicative) group G) (where γ∈ {γ |
One-to-one mapping γ: C = {1,2, ..., mn} → D = {ij | 1 ≦ i ≦ m,
1 ≦ j ≦ n}}, and ord _G (g) is given by S (x, i) = r (x, γ (i), and a random integer r (x, ij) (1 ≦ i ≦ m, 1 ≦ j ≦ n). )) For (1 ≦ i ≦ mn), (s (x,
i)) using (1 ≦ i ≦ mn) as a secret key of key user x,
An integer ξ _F is randomly selected, and For the purpose of sharing only a key user belonging to an arbitrary subset F of a set of all key users, a common key K satisfying , As broadcast data, Y (i) that satisfies Key distribution means for calculating an integer d (x, ξ _F ) that satisfies the following, and means for broadcasting the broadcast data y (i) and d (x, 、 _F ). apparatus. 24. The key distribution apparatus according to claim 23, wherein an integer ζ is selected at random. For the purpose of sharing the common key K satisfying only with key users belonging to an arbitrary subset F included in the entire set of key users, as broadcast data, A key distribution device further comprising: means for calculating z (i) that satisfies the following condition; and means for broadcasting the broadcast data z (i). 25. A key sharing device, wherein a key user x obtains common key information shared with a key creator based on data transmitted from the key distribution device according to claim 24. The data sent from y (i) (or z
(i)) and d (x, and ξ _F), the secret key (s (x of the key user x that was distributed from the key author, i)) and on the basis of (1 ≦ i ≦ mn), [number 30] Or, (However, f _i (1 ≦ i ≦ mn) is a function published by the key creator, and f _i (s (x, i), y (i)) = c (x, γ (i), ξ _F ) or
f _i (s (x, i), z (i)) = c (x, γ (i), ξ _F )) to provide a means for calculating the common key K shared with the key creator. Characteristic key sharing device. 26. A key distribution device for a key creator to share common key information for performing cryptographic communication with a plurality of key users, wherein the key creator secret information includes: 32] Is created, and as public information, (Where 0 <g ₁ , g ₂ <N and ord
_G (g) is And the integer r (x, ij) (1 ≦ i ≦ m, 1 ≦ j ≦ 2), and s (x, i) = r (x, γ (i )) (1 ≦ i ≦ 2m), then (s (x,
i)) means (1 ≦ i ≦ 2m) as key information of the key user x,
An integer ξ _F is selected at random, and In order to share the common key K that satisfies , As broadcast data, Y (i) that satisfies and Means for calculating an integer d (x, ξ _F) satisfying the broadcast data y (i), d (x , ξ F) key, characterized in that it comprises, means for transmitting broadcast delivery apparatus. 27. The key distribution device according to claim 26, wherein an integer ζ is selected at random. For the purpose of sharing only the key users belonging to an arbitrary subset F included in the set of all key users, a common key K satisfying A key distribution device further comprising: means for calculating z (i) that satisfies the following condition; and means for broadcasting the broadcast data z (i). 28. A key sharing device according to claim 27, wherein the key user x obtains common key information shared with a key creator based on data transmitted from the key distribution device. The data sent from y (i) (or z
(i)) and d (x, ξ _F ) and the secret key (s (x, i)) (1 ≦ i ≦ 2m) of key user x distributed by the key creator, 41] Or, (However, f _i (1 ≦ i ≦ 2m) is a function published by the key creator, and f _i (s (x, i), y (i)) = c (x, γ (i), ξ _F ) or
f _i (s (x, i), z (i)) = c (x, γ (i), ξ _F )) to calculate a common key K shared with the key creator. A key sharing device characterized by the following. 29. A receiving device for receiving data transmitted from the key distribution device according to claim 24, wherein the data d (x, ξ _F ) transmitted from the key distribution device is connected to the receiving device. K (x, i) (where K (x, i) = y (i) ^{S (x, i)} or K (x, i) = z (i ) ^{S (x, i)} (∈G)) Or, (However, f _i (1 ≦ i ≦ mn) is a function published by the key creator, and f _i (s (x, i), y (i)) = c (x, γ (i), ξ _F ) or
f _i (s (x, i), z (i)) = c (x, γ (i), ξ _F )), the key user x finds a common key K shared with the key creator A receiving device comprising: 30. A storage medium with a calculation function configured to be connectable to the receiving apparatus according to claim 29, wherein a secret key (s (x, i)) of a key user x distributed by a key creator. (1
≤ i ≤ mn), and a secret key (s (x, i)) of the key user x stored in the storage means
(1 ≦ i ≦ mn) and data y (i) or z (i) received by the receiving device and transmitted from the key distribution device, Or, Calculating means for determining K (x, i) satisfying the following, and transmitting the K (x, i) to the receiving device. 31. A receiving device for receiving data transmitted from the key distribution device according to claim 27, wherein the data d (x, ξ _F ) transmitted from the key distribution device is connected to the receiving device. K (x, i) (where K (x, i) = y (i) ^{S (x, i)} modN or K (x, i) = z ( i) ^{S (x, i)} modN (∈G)) Or, (However, f _i (1 ≦ i ≦ 2m) is a function published by the key creator, and f _i (s (x, i), y (i)) = c (x, γ (i), ξ _F ) or
f _i (s (x, i), z (i)) = c (x, γ (i), ξ _F )), the key user x finds a common key K shared with the key creator A receiving device comprising: 32. A storage medium with a calculation function configured to be connectable to the receiving apparatus according to claim 31, wherein a secret key (s (x, i)) of a key user x distributed by a key creator. (1
≦ i ≦ 2m), and a secret key (s (x, i)) of the key user x stored in the storage means.
(1 ≦ i ≦ 2m) and data y (i) or z (i) received from the key distribution device and received by the receiving device, Or, Calculating means for determining K (x, i) satisfying the following, and transmitting the K (x, i) to the receiving device.