Patent Publication Number: US-2022224520-A1

Title: Key exchange system, communication apparatus, key exchange method and program

Description:
TECHNICAL FIELD 
     The present invention relates to a key exchange system, a communication device, a key exchange method, and a program. 
     BACKGROUND ART 
     In recent years, Internet of Things (IoT) devices have become ubiquitous, and highly important communications have become common even for IoT devices. Thus, authentication techniques for confirming whether the correct devices are being used during communication have become important even for IoT devices. 
     While passwords, electronic certificates, and the like are known in the art as authentication techniques for IoT devices, there has been a demand for the introduction of a more secure authenticated key exchange protocol in recent years. An authenticated key exchange protocol is a protocol that generates a key (shared key) that is common to each other upon successful authentication and enables encrypted communication with that shared key. As one such authenticated key exchange protocol, an authenticated key exchange protocol using an ID based encryption is known. 
     A model, called the id-eCK model, is known as a model of security that the authenticated key exchange protocol using the ID based encryption should meet, and is known as a model that requires very strong security. 
     The authenticated key exchange protocol using the ID based encryption is generally implemented by using a bilinear group in an elliptic curve on a finite field. Such a bilinear group is also referred to as a pairing group, and can be classified into a symmetric pairing group and an asymmetric pairing group. In recent years, such an asymmetric pairing group is often used in terms of efficiency and security in a case of using a pairing group for encryption. As an authenticated key exchange protocol using the ID based encryption implemented on an asymmetric pairing group, Fujioka-Suzuki-Ustaoglu (FSU), also standardized in International Organization for Standardization/International Electrotechnical Commission (ISO/IEC) is known (see NPL 1). 
     CITATION LIST 
     Non Patent Literature 
     
         
         NPL 1: Fujioka, Hoshino, Kobayashi, Suzuki, Ustaoglu, Yoneyama, “id-eCK Secure ID-Based Authenticated Key Exchange on Symmetric and Asymmetric Pairing”, IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol. E96-A No. 6 pp. 1139-1155, 2013. 
       
    
     SUMMARY OF THE INVENTION 
     Technical Problem 
     However, in FSU, a group operation called a pairing operation needs to be performed four times. Because a computational cost of the pairing operation is generally high, in a case where a device with limited computational resources such as an IoT device performs key exchange by FSU, the key exchange may be time-consuming. 
     An embodiment of the present invention has been made in view of the points described above, and an object of the present invention is to reduce the computational costs of the authenticated key exchange protocol using the ID based encryption. 
     Means for Solving the Problem 
     In order to achieve the object described above, a key exchange system according to an embodiment of the present invention is a key exchange system for generating a shared key for performing encrypted communication between a plurality of communication devices by an authenticated key exchange protocol using an ID based encryption, the key exchange system including the plurality of communication devices, wherein each of the plurality of communication devices includes a first generation unit configured to generate a short term private key by using a private key of the communication device, a second generation unit configured to generate a short term public key of the communication device on a pairing group G 1  of one of asymmetric pairing groups G 1  and G 2  used for the ID based encryption, by using the short term private key, and a third generation unit configured to generate a shared key for performing encrypted communication with another communication device by performing a first pairing operation using a private key of the communication device generated on the pairing group G 2  being another one of the asymmetric pairing groups G 1  and G 2  and a short term public key generated in the other communication device, and performing a second pairing operation using the short term private key of the communication device and public information used in generating a private key of the other communication device. 
     Effects of the Invention 
     The computational costs of the authenticated key exchange protocol using the ID based encryption can be reduced. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  is a diagram illustrating an example of an overall configuration of a key exchange system according to an embodiment of the present invention. 
         FIG. 2  is a diagram illustrating an example of a hardware configuration of a key issuing device according to the embodiment of the present invention. 
         FIG. 3  is a diagram illustrating an example of a hardware configuration of a communication device according to the embodiment of the present invention. 
         FIG. 4  is a diagram illustrating an example of a functional configuration of the key exchange system according to the embodiment of the present invention. 
         FIG. 5  is a flowchart illustrating an example of key issuing processing according to the embodiment of the present invention. 
         FIG. 6  is a sequence diagram illustrating an example of key exchange processing according to the embodiment of the present invention. 
     
    
    
     DESCRIPTION OF EMBODIMENTS 
     Hereinafter, an embodiment of the present invention will be described. The embodiment of the present invention describes a key exchange system  1  in which computational costs are reduced in an authenticated key exchange protocol using ID based encryption by reducing the number of times of pairing operation. 
     Overall Configuration 
     First, an overall configuration of the key exchange system  1  according to the embodiment of the present invention will be described with reference to  FIG. 1 .  FIG. 1  is a diagram illustrating an example of the overall configuration of the key exchange system  1  according to the embodiment of the present invention. 
     As illustrated in  FIG. 1 , the key exchange system  1  according to the embodiment of the present invention includes a key issuing device  10  and a plurality of communication devices  20 . The key issuing device  10  and each of the communication devices  20  are communicatively connected through a communication network N such as the Internet, for example. 
     The key issuing device  10  is a computer or computer system that functions as a Key Generation Center (KGC). The key issuing device  10  uses a master private key to generate a master public key in advance and publishes the master public key. In a case where the key issuing device  10  receives an identifier of a communication device  20 , the key issuing device  10  generates a user private key from the identifier and distributes the user private key to the communication device  20  corresponding to the identifier. 
     Note that any identifier can be used as the identifier of the communication device  20 . For example, a manufacture unique number, an Internet Protocol (IP) address, a physical address, and the like of the communication device  20  can be used as the identifier. In addition to these, for example, a user ID of the user of the communication device  20 , the name of the user of the communication device  20 , the mail address of the user of the communication device  20 , or the like can be used as the identifier. 
     The communication device  20  is a variety of IoT devices such as, for example, various sensor devices, embedded devices, wearable devices, digital appliances, monitoring cameras, lighting devices, medical devices, industrial devices, and the like. The communication device  20  uses the user private key distributed from the key issuing device  10  to perform authentication (i.e., verification of legitimacy) with the authenticated key exchange protocol using the ID based encryption with another communication device  20  to exchange (generate) a key (shared key) for encrypted communication. Hereinafter, in a case where the plurality of communication devices  20  are expressed separately, the communication devices  20  are expressed as a “communication device  20 A”, a “communication device  20 B”, and the like. 
     Note that in the embodiment of the present invention, an IoT device is assumed as each communication device  20 , and the computational resources of the communication device  20  are limited (i.e., the processing performance of the processor and the capacity of the memory are poor compared to a typical computer or the like, for example). However, no such limitation is intended, and the embodiment of the present invention can be similarly applied even if the communication device  20  is other than an IoT device (for example, a personal computer (PC), a server device, a smartphone, a tablet terminal, or the like). 
     The configuration of the key exchange system  1  illustrated in  FIG. 1  is an example, and other configurations may be employed. For example, a terminal transmitting an identifier of each communication device  20  to the key issuing device  10  may be included in the key exchange system  1 . 
     Hardware Configuration 
     Next, a hardware configurations of the key issuing device  10  and the communication device  20  according to the embodiment of the present invention will be described. 
     Key Issuing Device  10   
     Hereinafter, a hardware configuration of the key issuing device  10  according to the embodiment of the present invention will be described with reference to  FIG. 2 .  FIG. 2  is a diagram illustrating an example of the hardware configuration of the key issuing device  10  according to the embodiment of the present invention. 
     As illustrated in  FIG. 2 , the key issuing device  10  according to the embodiment of the present invention includes an input device  11 , a display device  12 , a Random Access Memory (RAM)  13 , a Read Only Memory (ROM)  14 , a processor  15 , an external I/F  16 , a communication I/F  17 , and an auxiliary storage device  18 . The pieces of hardware are communicably connected through a bus  19 . 
     The input device  11  is, for example, a keyboard, a mouse, a touch panel, and the like, and is used by the user to enter various operations. The display device  12  is, for example, a display and the like, and is used to display results of various processes and the like to the user. Note that the key issuing device  10  may not include at least one of the input device  11  and the display device  12 . 
     The RAM  13  is a volatile semiconductor memory that temporarily retains a program and data. The ROM  14  is a non-volatile semiconductor memory that can retain a program and data even when the power is turned off. The processor  15  is, for example, a Central Processing Unit (CPU) and the like, and reads a program or data from the ROM  14 , auxiliary storage device  18  and the like to the RAM  13  to execute a process. 
     The external I/F  16  is an interface to an external device. The external device is a recording medium  16   a  and the like. Examples of the recording medium  16   a  include a Compact Disc (CD), a Digital Versatile Disk (DVD), a Secure Digital memory card (SD memory card), and a Universal Serial Bus (USB) memory card. Note that one or more programs and the like that achieve each function of the key issuing device  10  may be recorded in the recording medium  16   a.    
     The communication I/F  17  is an interface for connecting the key issuing device  10  to the communication network N. The key issuing device  10  can perform data communication with the communication device  20  through the communication I/F  17 . 
     The auxiliary storage device  18  is a non-volatile storage device such as a Hard Disk Drive (HDD) and a Solid State Drive (SSD), for example. One or more programs and the like that achieve each function of the key issuing device  10  are stored in the auxiliary storage device  18 . 
     The key issuing device  10  according to the embodiment of the present invention has the hardware configuration illustrated in  FIG. 2  and thus can implement key issuing processing described below. Note that while the key issuing device  10  according to the embodiment of the present invention is implemented with a single device (computer) in  FIG. 2 , the present invention is not limited to this. The key issuing device  10  according to the embodiment of the present invention may be implemented with a plurality of devices (computers). The single device (computer) may include a plurality of processors  15 , and a plurality of memories (for example, the RAM  13 , the ROM  14 , the auxiliary storage device  18  and the like). 
     Communication Device  20   
     Hereinafter, a hardware configuration of the communication device  20  according to the embodiment of the present invention will be described with reference to  FIG. 3 .  FIG. 3  is a diagram illustrating an example of the hardware configuration of the communication device  20  according to the embodiment of the present invention. 
     As illustrated in  FIG. 3 , the communication device  20  in the embodiment of the present invention includes a processor  21 , a memory device  22 , and a communication I/F  23 . The pieces of hardware are communicatively connected through a bus  24 . 
     The processor  21  is, for example, a Micro Processing Unit (MPU), a CPU, or the like, and is an arithmetic device that reads a program or data from the memory device  22  to execute processing. 
     The memory device  22  is, for example, a RAM, ROM, flash memory, or the like, and stores various pieces of data, programs, and the like. One or more programs and the like that achieve each function of the communication device  20  according to the embodiment of the present invention are stored in the memory device  22 . 
     The communication I/F  23  is an interface for connecting the communication device  20  to the communication network N. The communication device  20  can perform data communication with other communication devices  20 , the key issuing device  10 , or the like through the communication I/F  23 . 
     The communication device  20  according to the embodiment of the present invention has the hardware configuration illustrated in  FIG. 3  and thus can implement key exchange processing described below. 
     Functional Configuration 
     Next, a functional configuration of the key exchange system  1  according to the embodiment of the present invention will be described with reference to  FIG. 4 .  FIG. 4  is a diagram illustrating an example of the functional configuration of the key exchange system  1  according to the embodiment of the present invention. 
     Key Issuing Device  10   
     As illustrated in  FIG. 4 , the key issuing device  10  according to the embodiment of the present invention includes a communication unit  101  and a key issuing processing unit  102 . These units are achieved by processes that one or more programs installed in the key issuing device  10  cause the processor to execute. 
     The key issuing device  10  according to the embodiment of the present invention includes a storage unit  103 . The storage unit  103  can be implemented using, for example, the auxiliary storage device  18  or the like. Note that the storage unit  103  may be implemented using, for example, a storage device connected to the key issuing device  10  via the communication network N. 
     The communication unit  101  performs various communications with the communication device  20  and the like. In a case where the key issuing processing unit  102  receives the identifier of the communication device  20 , the key issuing processing unit  102  generates a user private key from the identifier and distributes the user private key to the communication device  20  corresponding to the identifier. The storage unit  103  stores various pieces of data (e.g., a master public key, a master private key, and the like). 
     Communication Device  20   
     As illustrated in  FIG. 4 , the communication device  20  according to the embodiment of the present invention includes a communication unit  201  and a key exchange processing unit  202 . 
     The communication unit  201  performs various communications with other communication devices  20 , the key issuing device  10 , and the like. The key exchange processing unit  202  uses the user private key distributed from the key issuing device  10  to perform authentication with another communication device  20  by the authenticated key exchange protocol using the ID based encryption to exchange the shared key. The storage unit  203  stores various pieces of data (e.g., a user private key, or the like). 
     Details of Processing of Key Exchange System  1   
     Next, details of processing of the key exchange system  1  according to the embodiment of the present invention will be described. 
     Definition of Symbols 
     First, the symbols used hereinafter are defined as follows. 
     ID A : Identifier of communication device  20 A
 
ID B : Identifier of the communication device  20 B
 
D A : User private key of the communication device  20 A
 
D B : User private key of the communication device  20 B
 
k: Security parameter
 
p, q: Prime numbers satisfying p≠q
 
G 1 : Partial group of a group E(F p ) on an elliptic curve E 1 , where the elliptic curve E1 is an elliptic curve on finite field F p  
 
G 2 : Partial group of a group expressed by Math. 1 on an elliptic curve E 2 , where the elliptic curve E 2  is an ellipse curve on k-th extension field of finite field F p 
 
     
       
         
           
             
               
                 
                   E 
                   ⁡ 
                   
                     ( 
                     
                       F 
                       
                         p 
                         k 
                       
                     
                     ) 
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     1 
                   
                   ] 
                 
               
             
           
         
       
     
     g 1 : Generator of G 1  
 
g 2 : Generator of G 2  
 
Z q : Residue class modulo q
 
Z∈Z q : Master private key
 
Z=zg 1 : Master public key
 
H 1 : Function generating an element on G 2  from a string (e.g., an octet sequence)
 
H 2 : Function generating an element on Z q  from a string
 
H: Key derivation function
 
e: Pairing operation defined on G 1 *G 2  
 
Here, among each of the symbols defined above, the symbols other than the master private key z, and the user private keys D A  and D B  are assumed to be publicly available information. Note that G 1  and G 2  may be reversed. In a case that an element of the group or an element on the Z q  are input to a function, a string representing the element is assumed to be input to the function.
 
     Key Issuing Processing 
     First, key issuing processing for generating a user private key will be described with reference to  FIG. 5 .  FIG. 5  is a flowchart illustrating an example of the key issuing processing according to the embodiment of the present invention. Hereinafter, as an example, a case in which the user private key D A  and the user private key D B  are issued will be described. 
     The key issuing processing unit  102  receives the identifier ID A  of the communication device  20 A and the identifier ID B  of the communication device  20 B (step S 101 ). The identifier of the communication device  20  may, for example, be transmitted from the communication device  20 , may be transmitted from a terminal or the like connected to the key issuing device  10  via the communication network N, or may be input from the input device  11  included in the key issuing device  10 . 
     Next, the key issuing processing unit  102  generates the user private key D A  and the user private key D B  as described below (step S 102 ). 
     
       
         
           
             
               Q 
               A 
             
             = 
             
               
                 
                   H 
                   1 
                 
                 ⁡ 
                 
                   ( 
                   
                     ID 
                     A 
                   
                   ) 
                 
               
               ∈ 
               
                 G 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 2 
               
             
           
         
       
       
         
           
             
               D 
               A 
             
             = 
             
               z 
               ⁢ 
               
                 Q 
                 A 
               
             
           
         
       
       
         
           
             
               Q 
               B 
             
             = 
             
               
                 
                   H 
                   1 
                 
                 ⁡ 
                 
                   ( 
                   
                     ID 
                     B 
                   
                   ) 
                 
               
               ∈ 
               
                 G 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 2 
               
             
           
         
       
       
         
           
             
               D 
               B 
             
             = 
             
               zQ 
               B 
             
           
         
       
     
     Here, Q A  and Q B  may be generated by the communication device  20  or by the key issuing device  10 . That is, for example, in generating the user private key D A , the communication device  20  may generate the Q A  and publish the Q A  to the key issuing device  10  or the key issuing device  10  may generate the Q A . Similarly, for example, in generating the user private key D B , the communication device  20  may generate the Q B  and publish the Q B  to the key issuing device  10  or the key issuing device  10  may generate the Q B . Note that it is convenient to respectively generate the Q A  and Q B  at the communication device  20 A and the communication device  20 B, but it is preferable to generate the QA and QB at the key issuing device  10 , for example, in a case where computational resources of the communication devices  20  are limited, and many computational resources are required in the calculation of H 1 . 
     Next, the key issuing processing unit  102  distributes the user private key D A  to the communication device  20 A and the user private key D B  to the communication device  20 B (step S 103 ). Note that the key issuing processing unit  102  may distribute the user private key in any manner. For example, the key issuing processing unit  102  may distribute the user private key by transmitting, by the communication unit  101 , a corresponding user private key to each communication device  20  in response to a distribution request for the user private key from the communication device  20 . Alternatively, the user private key may be recorded in a recording medium or the like and then distributed to the communication device  20 . In this way, each communication device  20  can obtain a user private key that is used in exchanging (generating) a shared key with other communication devices  20 . 
     Key Exchange Processing 
     Next, key exchange processing for exchanging a shared key by performing authentication between the communication devices  20  by an authenticated key exchange protocol using the ID based encryption will be described with reference to  FIG. 6 .  FIG. 6  is a sequence diagram illustrating an example of the key exchange processing according to the embodiment of the present invention. Hereinafter, as an example, a case in which the shared key is exchanged (generated) between the communication device  20 A and the communication device  20 B will be described. 
     The key exchange processing unit  202  of the communication device  20 A randomly selects r A ∈Z q  and then generates a short term private key 
     
       
         
           
             
               
                 
                   
                     
                       x 
                       A 
                     
                     = 
                     
                       
                         H 
                         2 
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             D 
                             A 
                           
                           ⁢ 
                           
                              
                              
                           
                           ⁢ 
                           
                             r 
                             A 
                           
                         
                         ) 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     where 
                     , 
                     
                       
                          
                          
                       
                       : 
                       
                         string 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         coupling 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     2 
                   
                   ] 
                 
               
             
           
         
       
     
     and generates a short term public key X A =x A g 1  (step S 201 ). Note that the short term private key x A  and the short term public key X A  are stored in the storage unit  203  of the communication device  20 A. 
     Similarly, the key exchange processing unit  202  of the communication device  20 B randomly selects r B  ∈Z q  and then generates a short term private key 
     
       
         
           
             
               
                 
                   
                     x 
                     B 
                   
                   = 
                   
                     
                       H 
                       2 
                     
                     ⁡ 
                     
                       ( 
                       
                         
                           D 
                           B 
                         
                         ⁢ 
                         
                            
                            
                         
                         ⁢ 
                         
                           r 
                           B 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     3 
                   
                   ] 
                 
               
             
           
         
       
     
     and generates a short term public key X B =x B g 1  (step S 202 ). Note that the short term private key x B  and the short term public key X B  are stored in the storage unit  203  of the communication device  20 B. 
     Next, the communication unit  201  of the communication device  20 A transmits the identifier ID A  and the short term public key X A  to the communication device  20 B (step S 203 ). Similarly, the communication unit  201  of the communication device  20 B transmits the identifier ID B  and the short term public key X B  to the communication device  20 B (step S 204 ). In this way, the identifiers and the short term public keys are exchanged between the communication devices  20 . 
     Next, the key exchange processing unit  202  of the communication device  20 A deletes the short term private key x A  generated in step S 201  described above from the storage unit  203  (step S 205 ). Similarly, the key exchange processing unit  202  of the communication device  20 B deletes the short term private key x B  generated in step S 202  described above from the storage unit  203  (step S 206 ). 
     Note that while the short term private key x A  and the short term private key x B  have been deleted in step S 205  and step S 206  described above, it is to prevent the short term private keys from leaking before receiving the identifier and the short term public key from the other communication device  20 . That is, for example, after the communication device  20 A transmits the identifier ID A  and the short term public key X A  to the communication device  20 B, a certain amount of time may be required before the time that the communication device  20 A receives the identifier ID B  and the short term public key X B  from the communication device  20 B. Thus, in order to prevent the short term private key x A  from leaking during this time, the communication device  20 A deletes the short term private key x A  after transmitting the identifier ID A  and the short term public key X A  to the communication device  20 B. This similarly applies to why the short term private key x B  is deleted. 
     Subsequently, the key exchange processing unit  202  of the communication device  20 A regenerates a short term private key 
     
       
         
           
             
               
                 
                   
                     x 
                     A 
                   
                   = 
                   
                     
                       H 
                       2 
                     
                     ⁡ 
                     
                       ( 
                       
                         
                           D 
                           A 
                         
                         ⁢ 
                         
                            
                            
                         
                         ⁢ 
                         
                           r 
                           A 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     4 
                   
                   ] 
                 
               
             
           
         
       
     
     (step S 207 ). Note that the short term private key x A  is stored in the storage unit  203  of the communication device  20 A. 
     Similarly, the key exchange processing unit  202  of the communication device  20 B regenerates a short term private key 
     
       
         
           
             
               
                 
                   
                     x 
                     B 
                   
                   = 
                   
                     
                       H 
                       2 
                     
                     ⁡ 
                     
                       ( 
                       
                         
                           D 
                           B 
                         
                         ⁢ 
                         
                            
                            
                         
                         ⁢ 
                         
                           r 
                           B 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     5 
                   
                   ] 
                 
               
             
           
         
       
     
     (step S 208 ). Note that the short term private key x B  is stored in the storage unit  203  of the communication device  20 B. 
     Next, the key exchange processing unit  202  of the communication device  20 A calculates a shared value σ 1 , a shared value σ 2 , and a shared value σ 3  as described below (step S 209 ). 
     
       
         
           
             
               σ 
               1 
             
             = 
             
               e 
               ⁡ 
               
                 ( 
                 
                   
                     X 
                     B 
                   
                   , 
                   
                     D 
                     A 
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
               σ 
               2 
             
             = 
             
               e 
               ⁡ 
               
                 ( 
                 
                   
                     
                       x 
                       A 
                     
                     ⁢ 
                     Z 
                   
                   , 
                   
                     Q 
                     B 
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
               σ 
               3 
             
             = 
             
               
                 x 
                 A 
               
               ⁢ 
               
                 X 
                 B 
               
             
           
         
       
     
     Similarly, the key exchange processing unit  202  of the communication device  20 B calculates a shared value σ 1 , a shared value σ 2 , and a shared value σ 3  as described below (step S 210 ). 
     
       
         
           
             
               σ 
               1 
             
             = 
             
               e 
               ⁡ 
               
                 ( 
                 
                   
                     
                       x 
                       B 
                     
                     ⁢ 
                     Z 
                   
                   , 
                   
                     Q 
                     A 
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
               σ 
               2 
             
             = 
             
               e 
               ⁡ 
               
                 ( 
                 
                   
                     X 
                     A 
                   
                   , 
                   
                     D 
                     B 
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
               σ 
               3 
             
             = 
             
               
                 x 
                 B 
               
               ⁢ 
               
                 X 
                 A 
               
             
           
         
       
     
     Next, the key exchange processing unit  202  of the communication device  20 A calculates an sid as described below (step S 211 ). Note that the sid refers to a session ID. 
     
       
         
           
             
               
                 
                   sid 
                   = 
                   
                     
                       ( 
                       
                         ID 
                         A 
                       
                        
                     
                     ⁢ 
                     
                        
                       
                         ID 
                         B 
                       
                        
                     
                     ⁢ 
                     
                        
                       
                         X 
                         A 
                       
                        
                     
                     ⁢ 
                     
                        
                       
                         X 
                         B 
                       
                       ) 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     6 
                   
                   ] 
                 
               
             
           
         
       
     
     Similarly, the key exchange processing unit  202  of the communication device  20 B calculates an sid as described below (step S 212 ). 
     
       
         
           
             
               
                 
                   sid 
                   = 
                   
                     
                       ( 
                       
                         ID 
                         A 
                       
                        
                     
                     ⁢ 
                     
                        
                       
                         ID 
                         B 
                       
                        
                     
                     ⁢ 
                     
                        
                       
                         X 
                         A 
                       
                        
                     
                     ⁢ 
                     
                        
                       
                         X 
                         B 
                       
                       ) 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     7 
                   
                   ] 
                 
               
             
           
         
       
     
     Note that in step S 211  and step S 212  described above, it is necessary for the sids to be the same between the communication device  20 A and the communication device  20 B, and thus, for example, the sids may be the same by predetermining the sender as ID A  and the receiver as ID B , or the like, in performing encrypted communication, or the sids may be the same by sorting and coupling ID A , ID B , X A , and X B  in alphabetical order. At this time, in addition to ID A , ID B , X A , and X B , for example, a master public key Z may be added, or a protocol name, an algorithm name, or the like may be added. 
     Finally, the key exchange processing unit  202  of the communication device  20 A generates a shared key K as described below (step S 213 ). 
     
       
         
           
             
               
                 
                   K 
                   = 
                   
                     
                       H 
                       ( 
                       
                         σ 
                         1 
                       
                        
                     
                     ⁢ 
                     
                        
                       
                         σ 
                         2 
                       
                        
                     
                     ⁢ 
                     
                        
                       
                         σ 
                         3 
                       
                        
                     
                     ⁢ 
                     
                        
                       sid 
                       ) 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     8 
                   
                   ] 
                 
               
             
           
         
       
     
     Note that the shared key K is stored in the storage unit  203  of the communication device  20 A. 
     Similarly, the key exchange processing unit  202  of the communication device  20 B generates a shared key K as described below (step S 214 ). 
     
       
         
           
             
               
                 
                   K 
                   = 
                   
                     
                       H 
                       ( 
                       
                         
                           σ 
                           1 
                         
                         ⁢ 
                         
                            
                            
                         
                         ⁢ 
                         
                           σ 
                           2 
                         
                       
                        
                     
                     ⁢ 
                     
                        
                       
                         σ 
                         3 
                       
                        
                     
                     ⁢ 
                     
                        
                       sid 
                       ) 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     9 
                   
                   ] 
                 
               
             
           
         
       
     
     Note that the shared key K is stored in the storage unit  203  of the communication device  20 B. 
     As a result, the shared key K is shared between the communication device  20 A and the communication device  20 B. Thus, the shared key K can be used to perform encrypted communication between the communication device  20 A and the communication device  20 B. 
     As described above, in the embodiment of the present invention, protocols are designed to enable the technology of a secure NAXOS protocol in an eCK model in a normal authenticated key exchange to be applied to an authenticated key exchange protocol using the ID based encryption. Note that the eCK model is a model of security in a normal authenticated key exchange and is an original model of the id-eCK model. 
     Meanwhile, a pairing operation is not required in a normal authenticated key exchange, and the NAXOS protocol is a protocol on a normal cyclic group. Thus, it is necessary to configure the protocol on a pairing group in order to perform an authenticated key exchange using the ID based encryption, and there is a problem of how to apply the NAXOS technology because there are two cyclic groups G 1  and G 2  in an asymmetric pairing group. In contrast, in the embodiment of the present invention, G 1  is used for operation on temporary keys (i.e., a short term private key and a short term public key) and G 2  is used for an element of the user private key to achieve security (i.e., security that meets the id-eCK model). Note that the NAXOS protocol is an authenticated key exchange protocol with a higher security than security in the CK model, using the technique of computing a hash function value with the user private key and the short term private key as input to create a short term public key. The details of the NAXOS protocol are described in, for example, the reference literature “B. LaMacchia, K. Lauter, and A. Mityagin, “Stronger Security of Authenticated Key Exchange,” in Provable Security, ser. LNCS, vol. 4784. Springer, 2007.” section  4  and the like. 
     In the embodiment of the present invention, the shared key K can be exchanged by simply performing a pairing operation twice by each communication device  20 . Meanwhile, as described above, for example, a pairing operation must be performed four times in the FSU. Thus, in the embodiment of the present invention, each communication device  20  is capable of performing key exchange in about half the time in the known art. Thus, according to the embodiment of the present invention, it is possible to perform an authenticated key exchange protocol using the ID based encryption at high speeds even in, for example, an IoT device with limited computational resources. 
     The present invention is not limited to the specifically disclosed embodiment described above, and various modifications and changes can be made without departing from the scope of the claims. 
     REFERENCE SIGNS LIST 
     
         
           1  Key exchange system 
           10  Key issuing device 
           20  Communication device 
           101  Communication unit 
           102  Key issuing processing unit 
           103  Storage unit 
           201  Communication unit 
           202  Key exchange processing unit 
           203  Storage unit