JP3283202B2 - Encryption communication method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to the contents of the information about the safety high encrypted communication how to communicate to encrypt the information so that it does not know the other party.

[0002]

2. Description of the Related Art In a modern society called an advanced information society, important documents and image information in business are transmitted, communicated, and processed in the form of electronic information based on a computer network. Such electronic information has a property that it can be easily copied and it is difficult to distinguish a copy from an original, and thus the importance of information security is emphasized. In particular, "sharing of computer resources",
The realization of a computer network that satisfies the elements of “multi-access” and “wide area” is indispensable for the establishment of an advanced information society, but this includes elements inconsistent with the problem of information security between the parties. As an effective method for resolving such inconsistency, cryptographic technology that has been used mainly in military and diplomatic aspects in the past history of humankind has attracted attention.

[0003] Encryption means exchanging information so that the meaning of the information cannot be understood by anyone other than the parties. In encryption, it is encryption to convert an original sentence (plaintext) that anyone can understand into a sentence (ciphertext) whose meaning is unknown to a third party, and decryption is to return the ciphertext to plaintext. The entire process of encryption and decryption is collectively called an encryption system. In the encryption process and the decryption process, secret information called an encryption key and a decryption key are used, respectively. Since a secret decryption key is required at the time of decryption, only a person who knows the decryption key can decrypt the ciphertext, and the encryption can maintain the confidentiality of the information.

[0004] The encryption key and the decryption key may be the same or different. A cryptosystem in which both keys are equal,
It is called a common key cryptosystem and is adopted by the U.S. Department of Commerce
ES (Data Encryption Standards) is a typical example. As an example of an encryption system in which both keys are different, an encryption system called a public key encryption system has been proposed. In this public key cryptosystem, each user (entity) using the cryptosystem creates a pair of an encryption key and a decryption key, publishes the encryption key in a public key list, and keeps only the decryption key secret. It is an encryption system that does. In the public key cryptosystem, the pair of the encryption key and the decryption key are different, and a characteristic is that the decryption key cannot be determined from the encryption key by using the one-way function.

The public key cryptosystem is an epoch-making cryptosystem that discloses an encryption key, and conforms to the above three elements necessary for establishing an advanced information society. The research has been actively conducted in order to use the RSA encryption system in the field and the like, and an RSA encryption system has been proposed as a typical public key encryption system. This RSA encryption system is realized by utilizing the difficulty of factorization as a one-way function. In addition, various methods have been proposed for a public key cryptosystem utilizing the difficulty of solving the discrete logarithm problem (discrete logarithm problem).

[0006] Further, an encryption system using ID (Identity) information for specifying an individual such as an address and a name of each entity has been proposed. In this encryption system, a common encryption key is generated between the transmitting and receiving parties based on the ID information. Further, the encryption technique based on the ID information includes (1) a method that requires preliminary communication between the transmitting and receiving parties before ciphertext communication, and (2) a preliminary communication between the transmitting and receiving parties before ciphertext communication. There is a method that does not require. In particular, since the method (2) does not require a preliminary communication, the convenience of the entity is high, and it is considered that it will be the center of the future cryptosystem.

The encryption system according to the method (2) uses an ID-
NIKS (ID-based non-interactive key sharing sch
eme), and employs a method of sharing an encryption key without performing preliminary communication using ID information of a communication partner. The ID-NIKS is a method in which there is no need to exchange a public key and a secret key between a sender and a receiver, and does not require a key list or a service by a third party, and secure communication can be performed between arbitrary entities.

FIG. 12 is a diagram showing the principle of this ID-NIKS system. Assuming the existence of a reliable center, a shared key generation system is configured around this center. In FIG. 12, ID information such as the name, address, and telephone number of the entity X is represented by h (ID _X ) using a hash function h (·). The center sends the center public information {PC _i }, center secret information {SC _i }, and the ID information h (ID
_X ), the secret information S _Xi is calculated as follows,
Distribute to Entity X secretly. S _Xi = F _i ({SC _i }, {PC _i }, h (ID _X ))

The entity X exchanges a shared key K _XY for encryption and decryption with any other entity Y by using the secret information {S _Xi } of the entity X itself, the center public information {PC _i }, and the other party. ID information h of the previous entity Y
It is generated as follows using (ID _Y ). K _XY = f ({S _Xi }, {PC _i }, h (ID _Y )) Similarly, the entity Y also generates a shared key K _YX as a key to the entity X. If the relationship of K _XY = K _YX always holds, the keys K _XY and K _YX can be used as the encryption key and the decryption key between the entities X and Y.

In the above-mentioned public key cryptosystem, for example, RSA
In the case of an encryption system, the length of the public key is ten and several times the current telephone number, which is extremely complicated. On the other hand, ID-
In NIKS, if each ID information is registered in the form of a list, a shared key can be generated with an arbitrary entity by referring to the list. Therefore, if the ID-NIKS system shown in FIG. 12 is safely realized, a convenient encryption system can be constructed on a computer network to which many entities subscribe. For these reasons, ID-NIKS is expected to be the center of future encryption systems.

The ID-NIKS using a separable operation using a symmetric matrix is classified into the following four types according to a method of calculating a secret key of a center and a public key between an entity and the presence or absence of a random number. (1) Product-sum type NIKS (2) Random number addition product-sum type NIKS (3) Power product type NIKS (4) Random number addition random product type NIKS

A brief description of each of these types of NIKS will be given below. Before that, the definition of the operation and various theorems based on the definition will be shown.

A = (a _ij ), B = (b _ij ), C =
When (c _ij ) is a matrix of an appropriate size, the following operations (definitions 1 to 3) are defined.

[0014]

(Equation 3)

According to the above definition, the following theorems (theorems 1 to 5) hold. Here, t means transposition.

[0016]

(Equation 4)

In any of the above modes (1) to (4), the center secretly performs the following preparations. Generate an appropriate n × n symmetric matrix T. A public hash function h (·) for converting the ID of the entity requesting registration into an appropriate vector having n components is generated.

(1) The center requested to register the product-sum type NIKS entity x registers a public information (public key) vector v _x (= h (ID _x )) of the entity x represented by a hash function and a symmetric matrix Using T and the following calculation, a secret information (secret key) vector s _x of the entity x is obtained and secretly sent to the entity x.

[0019]

(Equation 5)

According to the following calculation, the entity i
Shared key K with entity j_ijAnd the entity j is
Shared key K with entity i_jiAsk for. Obviously K_ij
= K _jiBecomes

[0021]

(Equation 6)

(2) The center requested to be registered by the random number addition product-sum type NIKS entity x is a vector v _x (= h (ID _x )), a symmetric matrix T, and a random number vector r
_{Using x} and the following calculation, a vector s _x is obtained and sent to the entity x secretly. However, ○ indicates an appropriate algorithm.

[0023]

(Equation 7)

In order for the entity i to share a key with the entity j, the following calculation is performed. Here, the shared key can be shared by deleting the random number term by an appropriate method.

[0025]

(Equation 8)

(3) The center requested to register the product-type NIKS entity x uses the vector v _x (= h (ID _x )) and the symmetric matrix T to convert the vector s _x according to the following calculation. Asks and sends it secretly to entity x.

[0027]

(Equation 9)

According to the following calculation, the entity i obtains a shared key K _ij with the entity j, and the entity j obtains a shared key K _ji with the entity i. From Theorem 1 of the power product operation described above, K _ij = K _ji .

[0029]

(Equation 10)

(4) Random number addition The center requested to be registered by the random product NIKS entity x is a vector v _x (= h (ID _x )), a symmetric matrix T, and a random number vector r
_{Using x} and the following calculation, a vector s _x is obtained and sent to the entity x secretly. However, ○ indicates an appropriate algorithm.

[0031]

[Equation 11]

In order for the entity i to share a key with the entity j, the following calculation is performed. Here, the shared key can be shared by deleting the random number term by an appropriate method.

[0033]

(Equation 12)

[0034]

In an ID-NIKS in which a shared key serving as an encryption key and a decryption key is shared with each other without performing preliminary communication using ID information of a communication partner, a plurality of entities are required. It is desired to be sufficiently secure against attacks such as collusion. However, in the above-mentioned ID-NIKS, attack methods have been studied,
This involves the problem that the secret parameters of the center are exposed if an appropriate number of entities collude. Whether it is possible to construct a cryptographically secure ID-NIKS is an important issue for a highly information-oriented society, and a search for a more ideal encryption system is being pursued.

The present invention has been made in view of the above circumstances, and a new ID-NIKS with extremely high security is obtained even if an entity is colluded, without exposing the secret parameter of the center and without decrypting the ciphertext. and an object thereof is to <br/> providing encrypted communications how by.

[0036]

According to a first aspect of the present invention, there is provided an encryption communication method, wherein an encryption key unique to each entity is sent from a center device to each of a plurality of entity devices , and one of the entity devices is sent from the center device . The plaintext is encrypted into ciphertext using the encryption key unique to the entity and the public key of the other entity and transmitted to the other entity device, and the transmitted ciphertext is transmitted to the other entity device. A cryptographic communication method for performing information communication between entity devices by decrypting the original plaintext using the encryption key unique to the entity sent from the center device and the public key of the one entity that has been disclosed. at the center device, the first key and the center device of each entity unique published as the public key management
Based on and a symmetric matrix (2) which, varying the first key
Generating a second key for each entity unique private represented by a first function with several, second and each entity-specific random number
A first secret key is generated from the second key based on equation (3),
Generating a second secret key from the random number based on equation (4);
The generated first secret key and second secret key are stored in each entity device.
To the first private key at one of the entity devices.
And the second secret key and the first key of the other entity
And its own second key and the other party's first key are two variables .
A third key, which is expressed by a second function and shared between both entities when encrypting a plaintext into a ciphertext and when decrypting a ciphertext into a plaintext, is based on the equations (5) and (6). Generate
Then, communication of the encrypted information is performed between the entity devices using the first key, the second key, and the third key .
However , a third function obtained by substituting the first function for the second function and having the first key of the self and the other party as a variable is defined by the equation (1) for each variable. It is characterized by setting to a non-separable function. f (x + y) ≠ f (x) ○ f (y) (1) However, if an appropriate commutative algorithm is represented by 、 and the function f (・) satisfies the following equation, the function f (・) is the algorithm Define as inseparable by ○.

[0037]

(Equation 13)

[0038]

[Equation 14]

[0039]

[0040]

[0041]

[0042]

[0043]

[0044]

[0045]

[0046]

[0047]

[0048]

[0049]

[0050]

Hereinafter, the ID in the encryption communication method of the present invention will be described.
-The concept of NIKS will be described.

First, the concept of linearity is generalized, and separability in a function is defined as follows. When an appropriate commutative algorithm is represented by ○ and the function f (（) satisfies the following relational expression, the function f (（) is defined as being separable by the algorithm ○. f (x + y) = f (x) ○ f (y) for example, f (x) = ax, f (x) = a x is separable as shown below. f (x + y) = a (x + y) = ax + ay = f (x) +
f (y) f (x + y) = a x + y = a x · a y = f (x) · f
(Y)

The definition of the matrix product operation is A,
Assuming that B and C are m × l, l × n, and m × n matrices, respectively, as described above, the following is obtained.

[0054]

(Equation 15)

The right power product and the left power product of the 2 × 2 matrix are specifically exemplified as follows.

[0056]

(Equation 16)

Next, conditions for realizing NIKS and conditions for secure NIKS will be considered. Where i, j, k, 1, y and z represent entities, and s
_i is the private key of the entity i (the second key in the claims), v _i is the public key of the entity i (the first key in the claims), which is often a hash value of the ID, K
_ij is a shared key (third key in the claims) with entity j obtained by entity i.

To realize NIKS, the following three conditions are required. [Condition 1 (secret key generation condition)] The center is the entity i
It is possible to find the secret key s _i corresponding to the public key v _i of.

[0059]

[Equation 17]

[Condition 2 (Shared Key Generation Condition)] A shared key K _ij can be generated from the secret key s _i of the entity _i and the public key v _{j of the} entity j.

[Condition 3 (Key Sharing Condition)] Entity i
Generates a shared key K _ij for entity j and a shared key K generated for entity j for entity i
It is equal to _ji . K _ij = K _ji

Further, the following five conditions are necessary for secure NIKS. [Condition 4 (safety of the secret key)] not required to own secret key s _i from the public key v _i of any entity i own.

[0063]

(Equation 18)

[Condition 5 (Security of Shared Key)] The shared key _Kyz between the entities y and z cannot be obtained from the public keys v _y and v _z of the two entities y and z.

[0065]

[Equation 19]

[Condition 6 (Security of private key against collusion)
Gender)] by collusion of a plurality of entities i, j, ...
Public key v_i, V_j, ... and secret key s_i, S_j, ...
, The secret key s of any other entity z _z
Can not be asked.

[0067]

(Equation 20)

[Condition 7 (Security of Shared Key Against Collusion)] By collusion of a plurality of entities i, j,.
Public key v _i, v _j, ... and a secret key s _i, s _j, ... and also attracted much, and not be asked to share key K _yz between any other entity y, z. Note that a plurality of entities i,
By the collusion of j, k, ..., entities i, j, k,
No matter how many shared keys K _ij , K _ik , K _jk,.
The condition that the shared key _Kyz between any other entities y and z cannot be obtained is also included.

[0069]

(Equation 21)

[Condition 8 (Security of Center Secret)] The center secret is not required by any attack.

The above-mentioned conditions 1 to 5 correspond to conditions 9 to
It is the same value as 13. [Condition 9] The center is a function for generating a secret key (secret key generation function: a first function in the claims) f (·)
Can be calculated. s _i = f (v _i )

[Condition 10] Function for Generating Shared Key (Shared Key Generation Function: Second Function in Claims) F
(•) can be represented by a two-variable function. The corresponding secret key s _i can be obtained from K _ij = F (s _i , v _j ).

[Condition 11] A function that uses a public key as a variable and is obtained by substituting a secret key generation function f (•) into a shared key generation function F (•) (shared key public function: 3
)) F _p (·) is a symmetric function. _{F p (v i, v j} ) = F p (v j, v i) _{However, F p (v i, v} j) = F (f (v i), v j) = F (s
_i v _j )

[Condition 12] Each entity cannot calculate the secret key generation function f (•).

[Condition 13] Each entity cannot calculate the shared key public function F _p (•).

In order to satisfy the above conditions 6 and 7, the linear attack cannot be applied, or the following conditions 14 and 15 must be satisfied, respectively.

[Condition 14] The secret key generation function f (•) is an inseparable function. f (x + y) ≠ f (x) ○ f (y) If the function is separable, it can be broken by a collusion attack using a secret key accompanying the collusion of an entity. For example, if the entities i and j are collaboratively expressed as v _z = v _i + v _j , the secret keys s _i and s _{j of} both entities i and _j
Is prepared, the secret key s _z of the entity z can be obtained as follows. _{s z = f (v z)} = f (v i) ○ f (v j) = s i ○ s j

[Condition 15] The public key public function F _p (•) is an inseparable function. F _p (a, x + y) ≠ F _p (a, x) Ｆ F _p (a, y) From Condition 11, since F _p (•) is a symmetric function,
The following equation also holds. F _p (x + y, a) ≠ F _p (x, a) ○ F _p (y, a) If the function is separable, it will be broken by a collusion attack using a shared key accompanying the collusion of entities. When the entities i and j are collaboratively expressed as v _z = v _i + v _j , K _iy (= F (s _i , v _y ) = F _p (v _i , v
_y )) and K _zy = (F (s _j , v _y ) = F _p (v _j , v
_{If y} )) is prepared, the shared key _Kyz between the entities y and z can be obtained as follows. K _yz = F _p (v _y , v _z ) = F _p (v _y , v _i + v _j ) = F _p (v _y , v _i ) ○ F _p (v _y , v _j ) = F _p (v _{i , v y) ○ F p (} v j, v y) = K iy ○ K jy _{Further, v y = v i + v} j, when expressed as v _z = v _k + v _l is, K _ik, K _il , if preparing a K _jk and K _jl, as follows, it can be obtained K _{yz. K yz = F p (v y} , v z) = F p (v i, v z) ○ F p (v j, v z) = F p (v i, v k) ○ F p (v i, v _l ) ○ F _p (v _j , v _k ) ○ F _p (v _j , v _l ) = K _ik ○ _Kil ○ K _jk ○ K _jl

This condition is severe, and regardless of the calculation in the middle,
Condition 15 only because the last key agreement type is the power product type
Does not satisfy

By the way, in order that the linear attack cannot be applied, for example, the following condition 16 may be satisfied. [Condition 16] The public key of the attack target entity cannot be represented by a linear combination of the public keys of the colluded entities. Although represented by a linear combination, the reverse calculation of ○ cannot be performed. That is, in the following equation, the inverse of f (y) with respect to the algorithm ○ cannot be obtained. f (xy) = f (x) ○ (f (y)) ^{-1 The} entity cannot know its own secret key.

By satisfying such condition 16,
There is a possibility that a safe NIKS should be realized. However, at present, there is no method that satisfies the condition 16, and it is known that the method that attempts to satisfy the condition 16 is broken by the Euclidean attack even if the inverse matrix of the collusion matrix is not obtained. Therefore, it is considered that an approach that satisfies the condition 16 is effective.

Based on the above considerations, the I
In the D-NIKS cryptosystem, the above-described shared key public function is set to an inseparable function (condition 15). Also, by introducing a personal random number, the secret key of each entity cannot be determined,
This random number is also considered to be secret, so that the above-described secret key generation function can be regarded as an inseparable function (condition 14). Furthermore,
Each entity is prevented from knowing its own secret key (condition 16). In this way, an ID that is secure against collusion of any number of entities
-NIKS can be realized.

[0083]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments of the present invention will be specifically described below.

FIG. 1 illustrates an embodiment of an encryption communication method according to the present invention.
FIG. 1 is a schematic diagram showing a configuration of a system for performing the above. A center 1 that can trust the concealment of information is set.
For example, a public organization of society can be applicable. The center 1 is connected to a plurality of entities a, b,..., Z as users who use the cryptosystem by secret communication paths 2a, 2b,. 2a, 2b,...
The secret key information is transmitted from the center 1 to each entity a, b,..., Z via 2z. In addition, communication paths 3ab, 3az, 3
bz,... are provided, and the communication paths 3ab, 3az, 3b
The cipher text obtained by encrypting the communication information via z,... is transmitted between the entities.

Hereinafter, an embodiment of the ID-NIKS of the present invention will be described. First, the cryptosystem of the present invention will be described in the order of (preparation processing at the center), (entity registration processing), and (shared key generation processing between entities).

(Preparation processing at the center) The center prepares the following public key and private key, and publishes the public key.

Here, λ (·) is a Carmichael function.
Also, a hash function h (·) for calculating an n-dimensional public key vector v from the ID information of the entity is also made public. The hash function is a function for converting a data sequence into another data sequence, and is generally a function for converting a long data sequence into a short data sequence. However, when the public key vector v is calculated using this hash function, the sum of all components is set to e. Specifically, the public key vector v
Is a binary vector, the Schalkwijk algorithm may be used. In general, (n-1) components are obtained by a hash value, and the sum of the last one component is e. You can ask for it.

[0088]

(Equation 22)

(Entity Registration Processing) The center requested to register by the entity i performs the following calculation using the prepared key and the public key vector v _i (= h (ID _i )) of the entity i. , The vector x of the entity i
_i (the first secret key in the claims) and y _i (the second secret key in the claims), transmit the obtained vectors x _i and y _i to the entity i in secret, and register Complete. At this time, the secret key s _i is not sent directly to the entity i.

[0090]

(Equation 23)

(Generation of Shared Key Between Entities) In order to share a key with the entity j, the entity i obtains k _ij and the shared key K _ij by performing the following calculation.

[0092]

(Equation 24)

[0093] The k _ij, the method of actual calculation for obtaining the K _ij, if the vector v _j is generally a multi-valued vector, if the components of the vector v _j is relatively small,
The special case where the vector v _j is a binary vector is shown below.

[0094]

(Equation 25)

Next, communication of information between entities in the above-described cryptographic system will be described. FIG.
It is a schematic diagram which shows the communication state of information between human entities a and b. The example of FIG. 2 is a case where the entity a encrypts a plaintext (message) M into a ciphertext C and transmits it to the entity b, and the entity b decrypts the ciphertext C into the original plaintext (message) M. Is shown.

[0096] entity a side inputs the personal identification information ID _b entity b, or public key generator 11 to obtain a vector v _b (public key) by using a hash function, the secret is sent from the center vector x _a and y _a the public key is a public key from the generator 11 vector v _b and the shared key K to the entity a seek entity b based on
_ab , and encrypts the plaintext (message) M into a ciphertext C using the shared key _Kab, and
And an encryptor 13 for outputting to 0. Also,
The entity b side, enter the personal identification information ID _a entities a, vector v _a using a hash function
A public key generator 21 for obtaining a (public key), and an entity a required by an entity b based on secret vectors x _b and y _b sent from the center and a vector v _a being a public key from the public key generator 21 shared key and the shared key generator 22 for generating the K _ba, feature a decoder 23 which decodes the ciphertext C input from the channel 30 to the plaintext (message) M outputs using the shared key K _ba and Have been.

FIG. 3 shows the shared key generators 12 and 22 of FIG.
FIG. 3 is a diagram showing an internal configuration of the device. Shared key generators 12 and 22
Is a first register 41 for storing the vector x sent from the center, a second register 42 for storing each component of the vector x, and a third register 43 for storing the vector v sent from the public key generators 11 and 21. A fourth register 44 for storing each component of the vector v, a fifth register 45 for storing a natural number N, and a second, fourth and fifth register 4
A first high-speed exponent calculator 46 for performing an exponent operation according to the outputs of 2, 44 and 45;
A register 47, a multiplier 48 for multiplying the outputs of the first high-speed exponent calculator 46 and the sixth register 47, a seventh register 49 for storing y sent from the center, and an eighth register 50 for storing a natural number P. , A second high-speed exponent calculator 51 that performs an exponent operation in accordance with the outputs of the sixth, seventh, and eighth registers 47, 49, and 50 and outputs a shared key K.

Since the natural numbers N and P have a relationship of P = N + 1, the one created by setting the least significant bit of the fifth register 45 to 1 may be used as the eighth register 50. . Also, each component of the vector x and y,
By switching between each component of the vector v and each input of k, mod N, and mod P, a configuration using only one high-speed exponent calculator is also possible.

Next, the operation will be described. If you from the entity a intends to transmit information to an entity b, firstly, the entity personal identification information ID _b of b is input vector v _b (public key) is obtained public key generator 11, resulting vector v _b is sent to the shared key generator 12. Furthermore, the vector x _a and y _a which is determined in accordance with the center (B) is input to the common key generator 12. The shared key generator 12 having the configuration shown in FIG. 3 _{obtains the} shared key _Kab according to (C) , and sends it to the encryptor 13. In the encryptor 13, the plaintext (message) M is encrypted into the ciphertext C using the shared key _Kab , and the ciphertext C
Is transmitted via the communication path 30. The ciphertext C transmitted through the communication path 30 is input to the decryptor 23 of the entity b. Personal identification information ID _a of the entity a is input to the public key generator 21 vector v _a (public key) is obtained,
The resulting vector v _a is sent to the common key generator 22.
Also, a vector x obtained from the center according to (B)
_b and y _b are input to the shared key generator 22. The shared key generator 22 having the configuration shown in FIG. 3 _{obtains the} shared key K _{ba in} accordance with (C) and _sends it to the decryptor 23. The decryption unit 23 decrypts the ciphertext C into a plaintext (message) M using the shared key _Kba .

Next, it will be verified that such an encryption system of the present invention can realize secure ID-NIKS, that is, it satisfies the above conditions 1 to 7.

(Condition 1) Secret key generation function f
(•) is defined by the following equation, and the center can find the corresponding private key from the public key of the entity.

[0102]

(Equation 26)

(Condition 2) Shared key generation function F
(•) is defined by the following equation, and a shared key can be generated from the private key of one entity and the public key of the other entity.

[0104]

[Equation 27]

(Condition 3) Shared key public function F
_{Since p} (•) is defined by the following equation, and T is a symmetric matrix, as shown in the following equation, F _p (•) is a symmetric function, and the shared key generated by each entity is Become equal.

[0106]

[Equation 28]

(Condition 4) Each entity cannot calculate its own secret key unless it knows the symmetric matrix T that is the center secret.

(Condition 5) Each entity cannot calculate the shared key between the entities unless it knows the symmetric matrix T that is the center secret.

(Condition 6) The encryption method of the present invention is as follows.
Although condition 14 is not directly satisfied, but condition 16 is satisfied, condition 6 is also satisfied. For example, in the case of a vector v _z ≡ vector v _i + vector v _j, without sending becomes a vector s _z ≡ vector s _i · vector s _j, direct the vector s _i of the secret key of the entity to entity, because you have to send from a vector x _i with personal random number r _i, not equal to the vector x _z and the vector x _i · vector x _j, it is impossible to determine the private secret vector x _z. Note that the entity cannot know its own personal random number, but this personal random number is deleted when the shared key is generated.

(Condition 7) Shared key public function F
_{Since p} (•) is an inseparable function as shown by the following formula, by collusion of multiple entities,
No matter how many public and private keys you collect, you cannot ask for a shared key between any other entities.

[0111]

(Equation 29)

(Condition 8) Center secret (p, q,
d, L, r _i , g, and T) are not exposed when multiple entities collude. P, q, d, in the center secret
L, evidence that does not r _i and g is exposed is as follows. p, q: difficulty d of factoring, L: the safety of the RSA encryption system r _i: the discrete logarithm problem difficulty g: r _i unknown due to safety

Next, the security of the symmetric matrix T against collusion attacks will be described. If there is no personal random number in the encryption system of the present invention, i.e., a vector v _i, the vector s
If an attack using _i , vector v _j , vector s _j ,... is possible, n expressions are obtained for one colluder.
Even if m people collaborate, mn linearly independent expressions cannot be obtained.

Since T is a symmetric matrix, the first colluder 1
A person obtains at most n linearly independent equations, and the second person collaborates to obtain at most (n-1) new linearly independent equations. Thereafter, similarly, as the number of entities to be newly consigned one by one increases, the newly obtained linearly independent expression decreases. Therefore, if n entities collude, at most n + (n-1) +... + 2 + 1 =
{N (n + 1) / 2} linearly independent equations are obtained. On the other hand, since the number of center secret variables is {n (n + 1) / 2}, the symmetric matrix T can be solved by collusion of n entities.

Next, considering the case where a personal random number is added as in the method of the present invention, ｛n
In addition to the (n + 1) / 2} center secret variables, personal random numbers also become center secret variables. Thus, if m entities collude, the center secret variable is ｛n (n
+1) / 2 + m}. As a result, even if an arbitrary number of entities collude, it is impossible to solve the symmetric matrix T. Hereinafter, the reason why this is not possible will be described for each collusion person.

(If less than n entities collude) The number of center secret variables exceeds the number of linearly independent equations obtained by collusion and cannot be solved.

(When n entities collude) The first person can obtain at most n linearly independent equations as in the case where no random numbers are provided. Next, when the second person colludes, the number of terms relating to the personal secret random number is increased by one, so that a maximum of n linearly independent expressions, which is one more than when no random number is provided, are obtained. Further, when the third person colludes, a maximum of (n-1) more linearly independent expressions are obtained, which is one more than when no random number is provided. Thereafter, similarly, as the number of entities to be newly consigned one by one increases, the newly obtained linearly independent expression decreases. Thus, if n entities collude, at most n + n + (n-1) +.
+ 2 = {n (n + 1) / 2 + (n-1)} linearly independent equations are obtained. On the other hand, the center secret variable is ｛n (n +
1) / 2 + n}, the number of linearly independent equations becomes one less than the number of center secret variables, and the symmetric matrix T cannot be solved.

(In the case where (n + 1) entities collude) One new personal secret random number is added compared to the case of n individuals, but the other n terms are linearly dependent, so a new linearly independent equation is obtained. Can only get one. As described above, since the center secret variable increases by one and the linearly independent expression increases by one, if it cannot be solved by collusion of n persons, (n +
1) The symmetric matrix T cannot be solved even by collusion of people.

(In the case where (n + 2) or more entities collude) The symmetric matrix T cannot be solved no matter how many people collaborate.

Thus, the secret matrix T at the center is secure against collusion attacks by any number of entities.

Here, a specific example of the security of the secret matrix T of the center in the case where the personal random number is provided and the case where the personal random number is not provided will be described. FIG. 4 shows a case where a personal random number is not provided and five entities collude. As shown in FIG. 4, since the 5 × 5 matrix T is a symmetric matrix, the number of unknown components is fifteen. Also, as shown in FIG.
The number of linearly independent equations is 5 + 4 + 3 + 2 + 1 = 15.
Therefore, since the number of unknowns and the number of linearly independent equations match, it can be solved, and the secret matrix T of the center is obtained.

On the other hand, FIG. 5 shows a case where personal random numbers are provided and five entities collude. Assuming that the personal random number is also a secret on the center side, as shown in FIG. 5, the unknown number is 15 in total from the matrix T and 5 in total from the random number. Also, as shown in FIG. 5, the number of linearly independent equations is 5+
5 + 4 + 3 + 2 = 19. Therefore, the number of unknowns is larger than the number of linearly independent equations, so that they cannot be solved and the secret of the center cannot be obtained. FIG. 6 shows an equation in this case.

Next, numerical values in the encryption communication method of the present invention will be described.
An example will be described. FIGS. 7 to 9 show first numerical examples (open to the public).
Key vector v is multi-valued). Ma
First, at the center, as shown in FIG.
(P, N, e) and secret key (p, q, L, d, g, T,
r_i, R_j, R_k) Is set. Also, each entity
vector of multi-valued public key based on i, j, k ID
v_i, V_j, V_kIs calculated and set as shown in FIG.
I do. Based on such setting conditions, each entity
vector x of i, j, k_i, X_j, X_kFigure 7
(C), and r_i ^-1, R_j ^-1, R_k ^-1as well as
y_i, Y_j, Y_kIs obtained as shown in FIG.
Then, the shared key K between the entities i and j_ij= K_ji, D
Shared key K between entities i and k_ik= K_ki,entity
Shared key K between j and k_jk= K_kjRespectively correspond to FIG.
(A), (b), and (c). In addition, this
Figure 9 shows the security against collusion attacks in the numerical example of 1.
You. There are 9 unknowns and 8 linearly independent equations
So it cannot be solved and the secret at the center is kept
You.

FIGS. 10 and 11 show a second numerical example (when the component of the vector v of the public key is binary). First, at the center, as shown in FIG. 10A, the public key (P,
N, e) and a secret key (p, q, L, d, g, T, r _i ,
r _j ). ID of each entity i, j
Calculate the binary public key vectors v _i , v _j based on
The settings are made as shown in FIG. FIG. 10C shows the values of r _i ^-1 and r _j ^-1 and the vectors s _i and s _j of the entities i and j based on the setting conditions. Further, vectors x _i , y _i in entity _i
When the shared key K _ij is obtained, the result is as shown in FIG. 11A. Similarly, the vectors x _j ,
When y _j and the shared key K _ji are obtained, the result is as shown in FIG.

[0125]

As described in detail above, the present invention satisfies the three conditions for realizing the above-mentioned NIKS and the five conditions for ensuring its security. Even so, the secret parameter of the center is not exposed and the ciphertext is not decrypted, so that extremely high security can be achieved.

[Brief description of the drawings]

FIG. 1 is a schematic diagram showing a configuration of a system for implementing an encryption communication method of the present invention.

FIG. 2 is a schematic diagram illustrating a communication state of information between two entities.

FIG. 3 is a diagram showing an internal configuration of a shared key generator of FIG.

FIG. 4 is a diagram illustrating security of secret at a center when no personal random number is provided.

FIG. 5 is a diagram illustrating security of secret at a center when a personal random number is provided.

FIG. 6 is a diagram showing an example of numerical values representing the security of the present invention.

FIG. 7 is a diagram showing a first numerical example of the present invention.

FIG. 8 is a diagram showing a first numerical example of the present invention.

FIG. 9 is a diagram showing a first numerical example of the present invention.

FIG. 10 is a diagram showing a second numerical example of the present invention.

FIG. 11 is a diagram showing a second numerical example of the present invention.

FIG. 12 is a diagram illustrating the principle configuration of an ID-NIKS system.

[Explanation of symbols]

 1 Center 11, 21 Public Key Generator 12, 22 Shared Key Generator 13 Encryptor 23 Decryptor 30 Communication Path

──────────────────────────────────────────────────続 き Continuation of the front page (72) Masao Kasahara 4-153-3, Ao Gaiin, Minoh-shi, Osaka (72) Inventor Atsunori Fujikawa 2-2-8 Nakamachi, Machida-shi, Tokyo (72) Inventor Yasutsu Murakami 51-6 Makishimacho Honashiki, Uji City, Kyoto Prefecture Murata Machinery Co., Ltd. Company Building B Bldg. 602 (56) Reference JP-A-8-8972 (JP, A) New method of ID-based encryption key sharing that does not require preliminary communication (3rd report), IEICE Technical Report, November 29, 1991, Vol. 91, No. 359 (ISEC 91-39), p. 21-24 Common encryption key generation method using ID Proposal of successive addition type random number term elimination method, IEICE Technical Report, December 7, 1992, Vol. 92, No. 355 (ISEC 92-60), p. 29-38 (58) Field surveyed (Int. Cl. ⁷ , DB name) H04L 9/08 JICST file (JOIS)

Claims (1)

(57) [Claims] 1. A plurality of entity devices from the center device
Send each entity encryption key specific to each, by one entity device using the public key of the sent other entities exposed with the entity-specific cryptographic key from said center unit plaintext into ciphertext Encrypted and transmitted to the other entity device , and the other entity device transmits the transmitted ciphertext to the encryption key unique to the entity sent from the center device and the disclosed one entity. In the cryptographic communication method of performing information communication between entity devices by decrypting the original plaintext using a key, the center device includes a first key unique to each entity, which is disclosed as a public key, and Symmetric matrix managed by the center unit
And the first key having the first key as a variable based on the equation (2) .
Secret second key unique to each entity , expressed as a function of
Is generated from the random number unique to each entity and the second key.
Generate a first secret key based on equation (3), and
A second secret key is generated based on equation (4), and the generated first secret key is generated.
The secret key and the second secret key are sent to each entity device, and the first secret key and the second secret key are sent to one entity device.
Using a key and the first key of the other entity as a second function with its own second key and the other party's first key as two variables , when encrypting plaintext into ciphertext And a third key shared between the two entities used when decrypting the ciphertext into plaintext is generated based on equations (5) and (6), and a first key, a second key, and a third key are generated. use, and performs communication of encrypted information between entity device
Is a function obtained by substituting the first function for the second function and using the first key of itself and the other party as a variable as a variable, as defined in equation (1) for each variable. A cryptographic communication method characterized by setting functions that cannot be separated. f (x + y) ≠ f (x) ○ f (y) (1) However, if an appropriate commutative algorithm is represented by 、 and the function f (・) satisfies the following equation, the function f (・) is the algorithm Define as inseparable by ○. (Equation 1) (Equation 2)