Conference session key distribution method on an id-based cryptographic system

0001The present invention relates to a data transmission method, and more particularly, to a method of distributing a conference session key which is shared in order to encrypt data between a plurality of parties.

0002As computers are greatly developed, networks connecting the computers become more important and useful. However, recently abuses of the computers and networks have increased. So, there is a need to implement network security techniques.

0003An inter-party key sharing protocol is a protocol used for keeping secrecy of data transmitted through the networks. A standard protocol is Diffie-Hellman type protocol, which is based on difficulty in solving an elliptic curve cryptographic discrete logarithm problem. The Diffie-Hellman type protocol is based on a public key infrastructure (PKI) encryption. However, the PKI encryption has shortcomings that it is necessarily involved in a participation of a reliable authentication center, since integrity of a public key must be guaranteed by the authentication center.

0004Because of the shortcomings of the PKI encryption, much research has been paid on an ID-based key sharing protocol which is not based on the PKI encryption. Unfortunately, conventional ID-based key sharing protocols have problems that they are vulnerable to a disguised attack and can not provide a forward secrecy.

0005According to an aspect of the present invention, there is provided a method of distributing a session shared key for encryption from a session initiating party to a plurality of session participating parties in a single conference session on an ID-based cryptographic system, the method comprising the steps of: (a) generating two temporary secret keys for the session initiating party, two temporary public keys for the session initiating party, and a signature value obtained by applying a predetermined signature function to the keys; (b) transporting to the session participating parties a message including ID information of the session initiating party, the temporary public keys for the session initiating party, and the signature value; (c) receiving from the session participating parties messages inducting the temporary public keys for the session participating parties and determining validity of the messages; (d) generating shared key generation variables for the session participating parties which have sent valid messages; (e) generating the session shared key and encrypting the ID information of the session initiating party by using the session shared key; and (f) transporting a message including the shared key generation variables and the encrypted ID information to the session participating parties which have sent valid messages.

0006According to another aspect of the present invention, there is provided a method of distributing a session shared key for encryption from a session initiating party to session participating parties in a single conference session on an ID-based cryptographic system, the method comprising the steps of: (a) receiving from the session participating party a message including ID information, a temporary public key, and a predetermined signature value of the session initiating party and determining validity of the message; (b) generating two temporary secret keys for the session participating parties, two temporary public keys for the session participating parties, and a signature value obtained by applying a predetermined signature function to the keys; (c) transporting to the session initiating party a message including the temporary public keys for the session participating parties and the signature value; (d) receiving from the session initiating party a message including a shared key generation variable and encrypted ID information of the session initiating party; (e) generating a session shared key by using the shared key generation variable and the temporary secret keys for the session participating parties; and (f) decrypting the encrypted ID information of the session initiating party by using the session shared key, and determining that the session shared key is valid.

0007The present invention provides a conference session key distribution method capable of resisting a disguised attack and providing a forward secrecy.

0008The present invention also provides a computer-readable storage medium containing a program by which a conference session key distribution method is executed in a computer.

0009The above and other features and advantages of the present invention will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings in which: <ul id="ul0001" list-style="none" compact="compact"><li>FIG. 1 is a conceptual diagram illustrating a cryptographic system using a discrete logarithm problem in a finite field; and</li><li>FIG. 2 is a flowchart illustrating steps of a conference session key distribution method according to the present invention.</li></ul>

0010The present invention and operational advantages thereof can be fully understood by referring to the accompanying drawings and explanations thereof.

0011Now, a conference session shared key distribution method according to the present invention will be described with reference to the accompanying drawings in detail.

0012FIG. 1 is a conceptual diagram illustrating a cryptographic system using a discrete logarithm problem in a finite field.

0013The cryptographic system according to the present invention is based on difficulty in solving a discrete logarithm problem in an elliptic curve cryptographic group. The discrete logarithm in the elliptic curve cryptographic group is a logarithm using an elliptic curve additive group defined in a finite field, that is, its domain of definition. It is known that a problem involved in the discrete logarithm function in the finite field rather than real number field is very difficult to solve, because the estimation using a simple magnitude comparison is not available. In the present invention, the encryption of data is performed by using the difficulty in solving the discrete logarithm problem.

0014In the cryptographic system using the finite field discrete logarithm problem, parties which participate the data encryption share two variables p and g. The variable p is a sufficiently large prime number determined depending on a secrecy of the cryptographic system. The variable g is a generation source of the finite field multiplicative group which has a divisor q of p-1 as an order. Two parties A and B select their own secret keys x_a and x_b, integers between 1 and q-1. The parties calculate their own public keys y_a and y_b by using their own secret keys, as represented by the following Equations 1 and 2.<maths id="math0001" num=""><math display="block"><mrow><mtext>[Equation 1]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">y</mtext></mrow><mrow><mtext mathvariant="italic">a</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">g</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">a</mtext></mrow></msub></mrow></msup><mtext> mod </mtext><mtext mathvariant="italic">p</mtext></mrow></math><img file="EP1526676A1_D0001.tif" /></maths><maths id="math0002" num=""><math display="block"><mrow><mtext>[Equation 2]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">y</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">g</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow></msub></mrow></msup><mtext> mod </mtext><mtext mathvariant="italic">p</mtext></mrow></math><img file="EP1526676A1_D0002.tif" /></maths>

0015The two parties <b>A</b> and <b>B</b> exchange the public keys, and share a shared key K obtained from the counter parties' public keys and their own secret keys by using the following Equation 3.<maths id="math0003" num=""><math display="block"><mrow><mtext>[Equation 3]</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">K</mtext><mtext>=</mtext><mtext mathvariant="italic">g</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">a</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow></msub></mrow></msup><mtext> mod </mtext><mtext mathvariant="italic">p</mtext></mrow></math><img file="EP1526676A1_D0003.tif" /></maths>

0016The party A calculates the shared key K by using its own secret key x_a and the public key x_b of the party <b>B</b>, as represented by the following Equation 4. The party <b>B</b> calculates the shared key K by using its own secret key x_b and the public key x_a of the party <b>A</b>, as represented by the following Equation 5.<maths id="math0004" num=""><math display="block"><mrow><mtext>[Equation 4]</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">K</mtext><mtext> = </mtext><mtext mathvariant="italic">y</mtext><msubsup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">a</mtext></mrow></msub></mrow></msubsup><mtext> = </mtext><mfenced open="(" close=")"><mrow><mtext mathvariant="italic">g</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow></msub></mrow></msup></mrow></mfenced><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">a</mtext></mrow></msub></mrow></msup><mtext> = </mtext><mtext mathvariant="italic">g</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">a</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow></msub></mrow></msup><mtext> mod </mtext><mtext mathvariant="italic">p</mtext></mrow></math><img file="EP1526676A1_D0004.tif" /></maths><maths id="math0005" num=""><math display="block"><mrow><mtext>[Equation 5]</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">K</mtext><mtext> = </mtext><mtext mathvariant="italic">y</mtext><msubsup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow></msub></mrow></msubsup><mtext> = </mtext><mfenced open="(" close=")"><mrow><mtext mathvariant="italic">g</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">a</mtext></mrow></msub></mrow></msup></mrow></mfenced><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow></msub></mrow></msup><mtext> = </mtext><mtext mathvariant="italic">g</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">a</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow></msub></mrow></msup><mtext> mod </mtext><mtext mathvariant="italic">p</mtext></mrow></math><img file="EP1526676A1_D0005.tif" /></maths>

0017Although any attacker knows the public key, he must solve the discrete logarithm problem in the cryptographic system. Therefore, the user's secret key is not revealed.

0018In the Diffie-Hellmann method which basically utilizes the system illustrated in FIG. 1, both users have to temporarily generate their own secret keys and public keys at every event of communication in a practical application. Therefore, it is involved in the inconvenience that an authentication center authenticates the users at every event of communication.

0019Harn and Yang have proposed a cryptographic system to solve the inconvenience by sharing a temporary key at every communication session by using identification (ID) information. The system is called an ID-based cryptographic system.

0020In addition, Xu and Tilborg have proposed a multi-party key sharing protocol using the Harn and Yang's method. The multi-party key sharing protocol is a protocol which implements key sharing among more than three parties and includes a key distribution protocol and a key agreement protocol. The key distribution protocol is a protocol in which a session initiating party generates a key and securely distributes the key into the other parties as a shared key. The key agreement protocol is a protocol where a common key to all the participating parties is commonly processed to be used as a session shared key.

0021The Xu and Tilburg's method is a key distribution protocol comprising an ID-based cryptographic system implementation step and a key sharing protocol step. The ID-based cryptographic system utilizes the Harn and Yang's method.

0022The parties participating each conference session are classified into a session initiating party A and session participating parties B and C.

0023In the ID-based cryptographic system implementation step, a key authentication center (KAC) provides its own public key y. The parties i (i = A, B, C) participating the session know public key parameters G, p, α, y and f. The parameter G is a multiplicative group GF(P)* of a finite field comprising modulo p integers. The parameter p is a sufficiently large prime number. The "modulo p" is an operator of which result is a remainder in division of p. The group G has the parameter α as its generation source. The parameter f is a hash function. Each party i has a secret s_i and a public key r_i provided by KAC.

0024The steps of the Xu and Tilborg's key sharing protocol are as follows.

0025Step 1) The party A selects an integer v₁, which is coprime to p-1, between integers 1 and p-1.

0026Step 2) The party A generates temporary public keys w₁ and η₁ represented by the following Equations 6 and 7, respectively.<maths id="math0006" num=""><math display="block"><mrow><mtext>[Equation 6]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">y</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext>ν</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0006.tif" /></maths><maths id="math0007" num=""><math display="block"><mrow><mtext>[Equation 7]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">η</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = (</mtext><mtext mathvariant="italic">f</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">ID</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>,</mtext><mtext mathvariant="italic">time</mtext><mtext>) - </mtext><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>)</mtext><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>-1)</mtext></mrow></math><img file="EP1526676A1_D0007.tif" /></maths>

0027In Equation 7, ID₁ denotes ID information of the party A and <i>time</i> denotes time information on the time of generating Equation 7. '

0028Step 3) The party A generates a message (ID₁, r₁, w₁, η₁, <i>time)</i> and transports the message to the session participating parties B and C.

0029Step 4) The session participating parties B and C receive the message (ID₁, r₁, w₁, η₁, <i>time</i>) and determine that the message satisfies the following Equation 8.<maths id="math0008" num=""><math display="block"><mrow><mtext>[Equation 8]</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">y</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">f</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">ID</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>, </mtext><mtext mathvariant="italic">time</mtext><mtext>)</mtext></mrow></msup><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext>(α</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">EID</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>-</mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>η</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext>(mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0008.tif" /></maths>

0030In Equation 8, EID₁ = f(ID₁).

0031If the message is sent by a valid session initiating party, it satisfies Equation 8. If the message is sent by an invalid session initiating party, it does not satisfy Equation 8. Therefore, the validity of the message sent by the party A can be completely determined by using Equation 8. In case of Equation 8 being satisfied, the protocol proceeds to the next step. Otherwise, the protocol is terminated.

0032Step 5) The session participating parties B and C select integers V_B and V_c, which are coprime to p-1, between integers 1 and p-1, respectively.

0033Step 6) The session participating parties B and C generate their own parameters w_j, n_j, and η_j by using the selected integer v_j (j = B, C), as represented by the following Equations 9 to 11.<maths id="math0009" num=""><math display="block"><mrow><mtext>[Equation 9]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">y</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext>ν</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0009.tif" /></maths><maths id="math0010" num=""><math display="block"><mrow><mtext>[Equation 10]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext>ν</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0010.tif" /></maths><maths id="math0011" num=""><math display="block"><mrow><mtext>[Equation 11]</mtext><mspace linebreak="newline" /><msub><mrow><mtext> η</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> = (</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msub><mrow><mtext> - ν</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)</mtext><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext>(mod </mtext><mtext mathvariant="italic">p</mtext><mtext>-1)</mtext></mrow></math><img file="EP1526676A1_D0011.tif" /></maths>

0034Step 7) The session participating parties B and C generate their own messages (ID_j, r_j, w_j, n_j, η_j) and transport the messages to the session initiating party A.

0035Step 8) The session initiating party A determines that the messages satisfy the following Equation 12 by using the variables received from the session participating parties B and C<maths id="math0012" num=""><math display="block"><mrow><mtext>[Equation 12]</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">y</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><mtext>(α</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">EID</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><msub><mrow><mtext>r</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>-</mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><mtext>)</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext>η</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0012.tif" /></maths>

0036In Equation 12, EID_j = f(ID_j).

0037If the message is sent by a valid session participating party, it satisfies Equation 12. If the message is sent by an invalid session participating party, it does not satisfy Equation 12. Therefore, the validity of the message sent by the session participating parties B and C can be completely determined by using Equation 12. In case of Equation 12 being satisfied, the protocol proceeds to the next step. Otherwise, the protocol is terminated.

0038Step 9) The session initiating party A selects an integer r between 1 and p-1 and generates a shared key K_c and a variable z_j represented by the following Equations 13 and 14, respectively.<maths id="math0013" num=""><math display="block"><mrow><mtext>[Equation 13]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></msub><mtext> = </mtext><msup><mrow><mtext mathvariant="italic">y</mtext></mrow><mrow><mtext mathvariant="italic">r</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0013.tif" /></maths><maths id="math0014" num=""><math display="block"><mrow><mtext>[Equation 14]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext>ν</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext mathvariant="italic">r</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0014.tif" /></maths>

0039Step 10) The session initiating party A generates E_Kc(ID₁) by encrypting its own ID information ID₁ with the shared key K_c. Herein, the symbol E denotes an encryption algorithm.

0040Step 11) The session initiating party A transports a message (z_j, E_Kc(ID₁)) to the parties which have sent the massages satisfying Equation 12.

0041Step 12) The party j calculates an inverse element v<maths id="math0015" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>-1</mtext></mrow><mrow><mtext>j </mtext></mrow></mfrac></mrow></math><img file="EP1526676A1_D0015.tif" /></maths>of the integer v_j in modulo p-1 and the shared key Kc by using the inverse element v<maths id="math0016" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>-1</mtext></mrow><mrow><mtext>j</mtext></mrow></mfrac></mrow></math><img file="EP1526676A1_D0016.tif" /></maths>, as represented by the following Equation 15.<maths id="math0017" num=""><math display="block"><mrow><mtext>[Equation 15]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></msub><mtext> =(</mtext><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>-1</mtext></mrow></msup></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0017.tif" /></maths>

0042E_Kc(ID₁) is decrypted with the shared key K_c obtained from Equation 15, and it is determined that ID₁ is valid. If ID₁ is valid, the encryption protocol using the shared key Kc proceeds. If not, the protocol is terminated.

0043Unfortunately, the Xu and Tilborg's multi-party key sharing protocol performed through the aforementioned steps can not have performances of preventing a disguised attack and ensuring a forward secrecy, which are important in a multi-party key sharing protocol.

0044The disguised attack is made by an attacker who utilizes ID information of a party participating the session to intervene the protocol. In this case, it is necessary to perceive and prevent the disguised attack. However, the Xu and Tilborg's protocol can not perceive the disguised attack. This is because the following Equation 16 is satisfied by using the parameters w_j and n_j with the same variable v_j, as represented by Equations 9 and 10.<maths id="math0018" num=""><math display="block"><mrow><mtext>[Equation 16]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msub><mrow><mtext> = w</mtext></mrow><mrow><mtext>j</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup></mrow></math><img file="EP1526676A1_D0018.tif" /></maths>

0045The attacker generates a shared key K_c' and a variable z_j' represented by the following Equations 17 and 18, respectively, in Step 9, encrypts ID information ID₁ by using the shared key K_c' and variable z_j' and transports a message (z_j', E_Kc'(ID₁)) to the session participating parties.<maths id="math0019" num=""><math display="block"><mrow><mtext>[Equation 17]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></msub><mtext>'= </mtext><msup><mrow><mtext mathvariant="italic">y</mtext></mrow><mrow><mtext mathvariant="italic">r</mtext></mrow></msup><mtext>(mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0019.tif" /></maths><maths id="math0020" num=""><math display="block"><mrow><mtext>[Equation 18]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>'= </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext mathvariant="italic">r'</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0020.tif" /></maths>

0046The session participating parties perform the protocol while mistaking the message for a valid message. This is because the shared key K_c' is calculated by using the following Equation 19 and the ID information ID₁ is obtained by decrypting E_Kc'(ID₁) by using the shared key K_c'.<maths id="math0021" num=""><math display="block"><mrow><mtext>[Equation 19]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></msub><mtext>'=(</mtext><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>')</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>-1</mtext></mrow></msup></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0021.tif" /></maths>

0047In addition, the attacker calculates the shared key K_c' and the variable z_j' represented by the following Equations 20 and 21, respectively, in Step 9, encrypts ID information ID₁ by using the shared key K_c' and variable z_j' and transports a message (z_j', E_Kc'(ID₁)) to the session participating parties.<maths id="math0022" num=""><math display="block"><mrow><mtext>[Equation 20]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></msub><mtext>'= </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext mathvariant="italic">r</mtext><mtext>'</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0022.tif" /></maths><maths id="math0023" num=""><math display="block"><mrow><mtext>[Equation 21]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>'= </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext mathvariant="italic">r</mtext><mtext>'</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0023.tif" /></maths>

0048The session participating parties perform the protocol while mistaking the message for a valid message. This is because the shared key K_c' is calculated by using the following Equation 22 and the ID information ID₁ is obtained by decrypting E_Kc'(ID₁) by using the shared key K_c'<maths id="math0024" num=""><math display="block"><mrow><mtext>[Equation 22]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></msub><mtext>'=(</mtext><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>')</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>-1</mtext></mrow></msup></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0024.tif" /></maths>

0049The reason that the session participating parties can not perceive the attacker's disguised attack is that the parties receiving the variables z_j generates the session shared keys by using only its own selected integer v_j irrespective of the session initiating party's selected integer v₁. Accordingly, there is a need to improve the method of generating the variables z_j.

0050The forward secrecy is a secray that, when permanent secret keys (long term keys) s_i (i = A, B, C) for more than one party participating the protocol are revealed, the attacker can not know information on keys to the past sessions by using the revealed long term keys. If a permanent secret key is revealed in a cryptographic system of which the forward secrecy is not ensured, all the data in the past encryption session may be revealed even in case of constructing the system by generating a new secret key.

0051In the Xu and Tilborg's protocol, the secret value v_j used to obtain the shared key in Equation 15 is used in Equation 11, as it is. In case of the secret key s_j of the session participating party j being revealed, if the attacker obtains messages transported at the past session, he can calculate the secret value v_j by using Equation 11 with the known values of the parameters w_j, n_j, and η_j, and the past shared key by using Equation 15. As a result, the secrecy for the data encrypted at the past session cannot be ensured.

0052In addition, there is a potentially weak point in the Xu and Tilborg's protocol in which the signature for authentication may be forged. Comparing Equations 9 and 11 with the Schnorr's signature generation method, the parameter n_j corresponds to a message and the parameters w_j and η_j correspond to signature values, respectively. In general, the signature value generation performed by applying a hash function to the message at the time of writing the signature is considered an indispensable procedure in order to prevent signature forgeries.

0053On the other hand, when the attacker knows the values of the parameters w_j, n_j, and η_j, the parameters w_j', n_j', and η_j' satisfying Equation 12 can be generated, as represented by Equations 23 through 25. In this case, there is a potentially weak point that an attacker can be disguised although he cannot share the key,<maths id="math0025" num=""><math display="block"><mrow><mtext>[Equation 23]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>'= (</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext mathvariant="italic">t</mtext></mrow></msup><mtext>(mod </mtext><mtext mathvariant="italic">p</mtext><mtext>-1)</mtext></mrow></math><img file="EP1526676A1_D0025.tif" /></maths><maths id="math0026" num=""><math display="block"><mrow><mtext>[Equation 24]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>'= </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic"> t w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></math><img file="EP1526676A1_D0026.tif" /></maths><maths id="math0027" num=""><math display="block"><mrow><mtext>[Equation 25]</mtext><mspace linebreak="newline" /><msub><mrow><mtext> η</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msub><mrow><mtext>'= η</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic"> t w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></math><img file="EP1526676A1_D0027.tif" /></maths>

0054FIG. 2 is a flowchart illustrating steps of a conference session key distribution method according to the present invention. The parties involved in the key distribution method are classified into a session initiating party A and session participating parties B, C , D, ···. In the protocol, the session initiating party is sometimes called a chairperson because the session initiating party seems to preside a conference.

0055In the ID-based cryptographic system, a conference session key distribution protocol comprises an ID-based cryptographic system implementation step and a key sharing protocol step. The ID-based cryptographic system is constructed with a signature providing system. In the system, if a public key can be derived from personal ID information or is previously provided, the transportation of the public key may be omitted. On the other hand, in case of the public key information being needed such as a case where a signature is to be authenticated, the public key is transported.

0056Now, the exemplary embodiments of the key sharing protocol used in the ID-based cryptographic system proposed by Harn and Yang will be described.

0057All the parties participating the session know public key parameters G, p, q, α, y and f. The parameter G, which is a partial group of a group GF(P)* , is a finite group having the sufficiently large prime number p as an order. The parameter q is a sufficiently large prime number and the associated integer q-1 has p as its factor. In the embodiment, an operation with respect to the group G is represented with a multiplication. The group G has the parameter α as its generation source. The parameter y is a public key of KAC. The parameter f is a hash function.. Each party i (i = A, B, C, ···) has a secret key s_i and a public key r_i provided by KAC.

0058In the Harn and Yang's cryptographic system, the ID information, the public key and the secret key satisfy the following Equation 26.<maths id="math0028" num=""><math display="block"><mrow><mtext>[Equation 26]</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">y</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">S</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub></mrow></msup><mtext> = α</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">f</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">ID</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext>)</mtext></mrow></msup><mtext> (</mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub></mrow></msup><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext> mod </mtext><mtext mathvariant="italic">q</mtext></mrow></math><img file="EP1526676A1_D0028.tif" /></maths>

0059The steps of the shared key distribution method according to the present invention are as follows.

0060The party A randomly selects two numbers u₁ and v₁ between integers 1 and p-1. The two numbers u₁ and v₁ become temporary secret keys for the session. In a case where operational time interval of the random function is longer than that of the hash function, a value obtained by hashing the temporary secret key u₁ may be used as the temporary secret key v₁ in order to reduce the operational time interval.

0061The temporary public keys w₁ and n₁ represented by the following Equations 27 and 28, respectively, are generated by using the temporary secret keys u₁ and v₁ (S100). These are temporary public keys in the session.<maths id="math0029" num=""><math display="block"><mrow><mtext>[Equation 27]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">y</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">q</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0029.tif" /></maths><maths id="math0030" num=""><math display="block"><mrow><mtext>[Equation 28]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">q</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0030.tif" /></maths>

0062The signature value η₁ represented by the following Equation 29 is generated by using the temporary secret keys, the temporary public keys, a permanent secret key, the ID information ID₁ of the party A, and time information <i>time</i> (S110). The function applied to Equation 29 is referred to as a signature function.<maths id="math0031" num=""><math display="block"><mrow><mtext>[Equation 29]</mtext><mspace linebreak="newline" /><msub><mrow><mtext> η</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = (</mtext><mtext mathvariant="italic">f</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>,</mtext><msub><mrow><mtext mathvariant="italic">ID</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>,</mtext><mtext mathvariant="italic">time</mtext><mtext>) - </mtext><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>)</mtext><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0031.tif" /></maths>

0063The party A generates a message (ID₁, r₁, w₁, n₁,η₁, <i>time</i>) 5 and transports the message 5 to the session participating parties (S120).

0064The session participating parties receive the message (ID₁, r₁, w₁, n₁,η₁, <i>time)</i> 5 and determine that the message 5 satisfies the following Equation 30 (S200).<maths id="math0032" num=""><math display="block"><mrow><mtext>[Equation 30]</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">y</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">f</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>,</mtext><msub><mrow><mtext mathvariant="italic">ID</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>,</mtext><mtext mathvariant="italic">time</mtext><mtext>)</mtext></mrow></msup><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext>(α</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">EID</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext></mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>-</mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext>)</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext>η</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">q</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0032.tif" /></maths>

0065In Equation 30, EID₁ = f(ID₁).

0066If the message 5 is sent by a valid session initiating party, it satisfies Equation 30. If the message 5 is sent by an invalid session initiating party, it does not satisfy Equation 30. Therefore, the validity of the message sent by the party A can be completely determined by using Equation 30. In case of Equation 30 being satisfied, the protocol proceeds to the next step. Otherwise, the protocol is terminated (S21 0).

0067Each session participating party randomly selects two integers u_j and v_j (j = B, C, D, ...) between integers 1 and p-1. The two integers become temporary secret keys of the corresponding session participating party. In a case where operational time interval of the random function is longer than that of the hash function, a value obtained by hashing the temporary secret key u_j may be used as the temporary secret key v_j in order to reduce the operational time interval.

0068The temporary public keys w_j and n_j represented by the following Equations 31 and 32, respectively, are generated by using the temporary secret keys u_j and v_j of each session participating party (S220). These temporary public keys become parameter used for generating session keys.<maths id="math0033" num=""><math display="block"><mrow><mtext>[Equation 31]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> = </mtext><msup><mrow><mtext mathvariant="italic">y</mtext></mrow><mrow><mtext>ν</mtext></mrow></msup><mtext mathvariant="italic">j</mtext><mtext> (mod </mtext><mtext mathvariant="italic">q</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0033.tif" /></maths><maths id="math0034" num=""><math display="block"><mrow><mtext>[Equation 32]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">q</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0034.tif" /></maths>

0069The signature value η_j represented by the following Equation 33 is generated by applying the temporary secret keys, the temporary public keys, a permanent secret key, and the ID information ID_j of the party j (j = B, C, D, ···) to the signature function (S230).<maths id="math0035" num=""><math display="block"><mrow><mtext>[Equation 33]</mtext><mspace linebreak="newline" /><msub><mrow><mtext> η</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> =(</mtext><mtext mathvariant="italic">f</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msub><mrow><mtext>)-ν</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)</mtext><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext>(mod </mtext><mtext mathvariant="italic">p</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0035.tif" /></maths>

0070Each session participating party generates its own message (ID_j, r_j, w_j, n_j, η_j) 10 and transports the massage 10 to the session initiating party A (S240).

0071The session initiating party A receives the massages 10 and determines that the messages 10 satisfy the following Equation 34 by using the received variables (S300).<maths id="math0036" num=""><math display="block"><mrow><mtext>[Equation 34]</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">y</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">f</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)</mtext></mrow></msup><msub><mrow><mtext> = w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><mtext>(α</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">EID</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><msub><mrow><mtext>r</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>-</mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><mtext>)</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext>η</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">q</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0036.tif" /></maths>

0072In Equation 34, E ID_j = f(ID_j).

0073If the message 10 is sent by a valid session participating party, it satisfies Equation 34. If the message 10 is sent by an invalid session participating party, it does not satisfy Equation 34. Therefore, the validity of the message sent by each session participating party can be completely determined by using Equation 34. In case of Equation 34 being satisfied, the protocol proceeds to the next step. Otherwise, the protocol is terminated (S310).

0074The session initiating party A generates a shared key K_c and a variable z_j, which is used for generating the shared keys in the session participating parties, represented by the following Equations 35 and 36, respectively (S320). The session initiating party A generates E_Kc(ID₁) by encrypting its own ID information ID₁ with the shared key K_c (S330). Herein, the symbol E denotes an encryption algorithm.<maths id="math0037" num=""><math display="block"><mrow><mtext>[Equation 35]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">q</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0037.tif" /></maths><maths id="math0038" num=""><math display="block"><mrow><mtext>[Equation 36]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> = (</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">q</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0038.tif" /></maths>

0075The session initiating party A transports the message (z_j, E_Kc(ID₁)) 15 to the session participating parties which have sent the massages 10 determined to be valid in Step S310 (S340).

0076The session participating parties receiving the messages 15 calculate shared keys K_c represented by the following Equation 37 (S400).<maths id="math0039" num=""><math display="block"><mrow><mtext>[Equation 37]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic"> = Z</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext mathvariant="italic"> ·</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> </mtext><msup><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msup><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext>(mod </mtext><mtext mathvariant="italic">q</mtext><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0039.tif" /></maths>

0077The ID information is obtained by decrypting E_Kc(ID₁) with the shared key K_c obtained from Equation 37 (S410), and it is determined that ID₁ is identical to the ID information ID₁ received in the message 15 (S420). If the ID information of the session initiating party A is identical, the encryption protocol using the shared key K_c proceeds. If not, the protocol is terminated.

0078Now, the exemplary embodiments of the key sharing protocol according to the present invention used in the ID-based cryptographic system using a Weil Pairing function defined in an elliptic curve encryption group will be described.

0079All the parties participating the session know public key parameters G, p, q, α, y, e, f₁, f₂, and f₃. The parameter G is a finite group having a sufficiently large prime number p as an order. The group G has the parameter α as its generation source. The parameter y is a public key of KAC. The parameter e is a Weil Pairing function defined in an elliptic curve. The parameters f₁ and f₂ are hash functions defined in the integer field. The parameter f₃ is a hash function defined in the group G. In the embodiment, an operation with respect to the group G is represented with an addition. The expression [x]y denotes a value of x-times addition on the element y of the group G.

0080Each party i (i = A, B, C, ...) has a secret key s_i and a public key r_i provided by KAC. The public key r_i is a value derived from the ID information ID_i of each party i. The secret key s_i is calculated by using the following Equation 38.<maths id="math0040" num=""><math display="block"><mrow><mtext>[Equation 38]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">S</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext> = [</mtext><mtext mathvariant="italic">S</mtext><mtext>] · </mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub></mrow></math><img file="EP1526676A1_D0040.tif" /></maths>

0081The value s in Equation 38 is known to only the KAC and satisfies the following Equation 39.<maths id="math0041" num=""><math display="block"><mrow><mtext>[Equation 39]</mtext><mspace linebreak="newline" /><mtext> y = [s]α</mtext></mrow></math><img file="EP1526676A1_D0041.tif" /></maths>

0082Steps of the shared key distribution method according to the present invention are as follows.

0083The party A randomly selects two numbers u₁ and v₁ between 1 and p-1. The two numbers u₁ and v₁ become temporary secret keys for the session. In a case where operational time interval of the random function is longer than that of the hash function, a value obtained by hashing the temporary secret key u₁ may be used as the temporary secret key v₁ in order to reduce the operational time interval.

0084The temporary public keys w₁ and n₁ represented by the following Equations 40 and 41, respectively, are generated by using the temporary secret keys u₁ and v₁ (S100).<maths id="math0042" num=""><math display="block"><mrow><mtext>[Equation 40]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> = [ν</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>]α</mtext></mrow></math><img file="EP1526676A1_D0042.tif" /></maths><maths id="math0043" num=""><math display="block"><mrow><mtext>[Equation 41]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> =[</mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>]</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></math><img file="EP1526676A1_D0043.tif" /></maths>

0085The signature value η₁ represented by the following Equation 42 is generated by using the temporary secret keys, the temporary public keys, a permanent secret key, the ID information ID₁ of the party A, and time information <i>time</i> (S110).<maths id="math0044" num=""><math display="block"><mrow><mtext>[Equation 42]</mtext><mspace linebreak="newline" /><msub><mrow><mtext> η</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> = [ν</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext>]([</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>),</mtext><msub><mrow><mtext mathvariant="italic">ID</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>,</mtext><mtext mathvariant="italic">time</mtext><mtext>)]α + [</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>)]</mtext><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0044.tif" /></maths>

0086The party A generates a message (ID₁, w₁, n₁,η₁, <i>time)</i> 5 and transports the message 5 to the session participating parties (S120).

0087The session participating parties receive the message (ID₁, w₁, n₁,η₁, <i>time</i>) 5 and determine that the message 5 satisfies the following Equation 43 (S200).<maths id="math0045" num=""><math display="block"><mrow><mtext>[Equation 43]</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">e</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>,η</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>) = </mtext><mtext mathvariant="italic">e</mtext><mtext>(α,[</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext> (</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>),</mtext><msub><mrow><mtext mathvariant="italic">ID</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>,</mtext><mtext mathvariant="italic">time</mtext><mtext>)]α)· </mtext><mtext mathvariant="italic">e</mtext><mtext>(</mtext><mtext mathvariant="italic">y</mtext><mtext>,[</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>)]</mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0045.tif" /></maths>

0088If the message 5 is sent by a valid session initiating party, it satisfies Equation 43. If the message 5 is sent by an invalid session initiating party, it does not satisfy Equation 43. Therefore, the validity of the message sent by the party A can be completely determined by using Equation 43. In case of Equation 43 being satisfied, the protocol proceeds to the next step. Otherwise, the protocol is terminated (S210).

0089Each session participating party randomly selects two integers u_j and v_j (j = B, C, D, ...) between 1 and p-1 as its temporary secret keys, and generates its temporary public keys w_j and n_j represented by the following Equations 44 and 45, respectively (S220). The temporary public keys become parameters used for generating the session key. In a case where operational time interval of the random function is longer than that of the hash function, a value obtained by hashing the temporary secret key u_j may be used as the temporary secret key v_j in order to reduce the operational time interval.<maths id="math0046" num=""><math display="block"><mrow><mtext>[Equation 44]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msub><mrow><mtext> =[ν</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>]α</mtext></mrow></math><img file="EP1526676A1_D0046.tif" /></maths><maths id="math0047" num=""><math display="block"><mrow><mtext>[Equation 45]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> =[</mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>]</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></math><img file="EP1526676A1_D0047.tif" /></maths>

0090The signature value η_j represented by the following Equation 46 is generated by applying the temporary secret keys, the temporary public keys, a permanent secret key, and the ID information ID_j of the party j (j = B, C, D, ...) to the signature function (S230).<maths id="math0048" num=""><math display="block"><mrow><mtext>[Equation 46]</mtext><mspace linebreak="newline" /><msub><mrow><mtext> η</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext mathvariant="italic"> =</mtext><msub><mrow><mtext> [ν</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msup><mrow><mtext> </mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><mtext>]([</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)]α + [</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)]</mtext><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0048.tif" /></maths>

0091Each session participating party generates its own message (ID_j, w_j, n_j, η_j) 10 and transports the massage 10 to the session initiating party A (S240).

0092The session initiating party A receives the massages 10 and determines that the messages satisfy the following Equation 47 by using the received variables (S300).<maths id="math0049" num=""><math display="block"><mrow><mtext>[Equation 47]</mtext><mspace linebreak="newline" /><mtext mathvariant="italic">e</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msub><mrow><mtext>,η</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>) = </mtext><mtext mathvariant="italic">e</mtext><mtext>(α,[</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)]α)·</mtext><mtext mathvariant="italic">e</mtext><mtext>(</mtext><mtext mathvariant="italic">y</mtext><mtext>,[</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)]</mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0049.tif" /></maths>

0093If the message 10 is sent by a valid session participating party, it satisfies Equation 47. If the message 10 is sent by an invalid session participating party, it does not satisfy Equation 47. Therefore, the validity of the message sent by each session participating party can be completely determined by using Equation 47. In case of Equation 47 being satisfied, the protocol proceeds to the next step. Otherwise, the protocol is terminated (S310).

0094The session initiating party A generates a shared key K_c and a variable z_j, which is used for generating the shared keys in the session participating parties, represented by the following Equations 48 and 49, respectively (S320). The session initiating party A generates E_Kc(ID₁) by encrypting its own ID information ID₁ with the shared key K_c (S330). Herein, the symbol E denotes an encryption algorithm.<maths id="math0050" num=""><math display="block"><mrow><mtext>[Equation 48]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></msub><mtext> = [</mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>]</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></math><img file="EP1526676A1_D0050.tif" /></maths><maths id="math0051" num=""><math display="block"><mrow><mtext>[Equation 49]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> = [</mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>](</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1526676A1_D0051.tif" /></maths>

0095The session initiating party A transports the message (Z_j, E_Kc(ID₁)) 15 to the session participating parties which have sent the massages determined to be valid in Step S310 (S340).

0096The session participating parties receiving the messages 15 calculate shared keys K_c represented by the following Equation 50 (S400).<maths id="math0052" num=""><math display="block"><mrow><mtext>[Equation 50]</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> -[</mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>]</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow></math><img file="EP1526676A1_D0052.tif" /></maths>

0097The ID information is obtained by decrypting E_Kc(ID₁) with the shared key Kc obtained from Equation 50 (S410), and it is determined that ID₁ is identical to the ID information ID₁ received in the message 5 (S420). If the ID information of the session initiating party A is identical, the encryption protocol using the shared key Kc proceeds. If not, the protocol is terminated.

0098According to the exemplary embodiments of the shared key distribution method of the present invention, it is possible to prevent the disguised attack by generating two different temporary secret keys in Steps 100 and 220 in order for the attacker not to know the values of the two temporary secret keys and using the temporary secret keys of the session initiating party at the time of generating the session key generation variables z_j. In addition, it is possible to ensure the forward secrecy by preventing the attacker from calculating the past session shared keys even in a case where the attacker may know the permanent secret keys of the parties participating the session. Besides, it is possible to prevent the attacker from being disguised without sharing keys by solving the potentially weak point in the Xu and Tilborg's protocol. Since there is no increase in calculation amount, the protocol of the present invention is more effective than the conventional protocol.

0099The present invention can be implemented with codes recorded on a computer-readable storage medium. The computer includes all the apparatuses having data processing functions. The computer-readable storage media includes all kinds of recording apparatuses which can be read out by the computers. The examples of the computer-readable apparatuses are ROMs, RAMS, CD-ROMs, magnetic tapes, floppy disks, and optical data storage apparatuses.

0100While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the scope of the present invention as defined by the following claims.

0101According to the shared key distribution method of the present invention, it is possible to provide an effective ID-based cryptographic system capable of preventing a disguised attack and ensuring a forward secrecy by selecting two different temporary secret keys, generating a message and generating session key generation variables by using temporary secret keys of a session initiating party.