JP7574791B2 - Authentication key exchange system, method, and program - Google Patents

Description

The present invention relates to an authentication key exchange system , a method , and a program.

In recent years, as IoT (Internet of Things) devices have become more widespread, important communications are also being carried out by IoT devices. For this reason, authentication technology is also required for IoT devices to verify that the devices and servers in communication are correct.

Passwords and electronic certificates have traditionally been known as authentication technologies for IoT devices, but in recent years, there has been a demand for the introduction of authentication key exchange protocols that offer greater security. An authentication key exchange protocol is a protocol in which, if authentication is successful, a mutually shared key (also called a shared key) is generated, enabling encrypted communication using the shared key. One such authentication key exchange protocol is known as an authentication key exchange protocol that uses ID-based encryption.

Authenticated key exchange protocols using ID-based encryption are generally realized using bilinear groups on elliptic curves over finite fields. Such bilinear groups are also called pairing groups, and can be classified into symmetric pairing groups and asymmetric pairing groups. Currently, when pairing groups are used in encryption, asymmetric pairing groups are often used from the standpoint of efficiency and security.

On the other hand, in ID-based encryption, a server called a KGC (Key Generation Center) generates the private key of the terminal, so that the administrator of the IoT device is more likely to operate the KGC in-house rather than using an external KGC service. Therefore, when an IoT device communicates with an external edge server, as in the use case of an edge computing service, the IoT device side may perform authentication based on ID-based encryption, and the edge server side may perform authentication based on a digital certificate. Non-Patent Document 1 describes a cross-domain authentication key exchange protocol in which one device is under an ID-based KGC domain and the other device (server) is under a certain CA (Certificate Authority) domain of a PKI (Public Key Infrastructure).

Ustaoglu, B.: Integrating identity-based and certificate-based authenticated key exchange protocols. Int. J. Inf. Security 10(4), 201-212 (2011)

However, in Non-Patent Document 1, it is necessary to perform a group operation called a pairing operation twice. Since pairing operations are generally computationally expensive, when a device with limited computational resources, such as an IoT device, performs key exchange using the protocol described in Non-Patent Document 1, the key exchange may take time. For example, when a 462-bit pairing operation on a BN (Barret-Naehrig) curve is performed using a processor with an operating clock speed of several hundred MHz, a calculation time of about 600 msec is required per operation.

One embodiment of the present invention has been made in consideration of the above points, and aims to perform efficient authentication key exchange between a device that performs authentication based on ID-based encryption and a device that performs authentication based on electronic certificates.

In order to achieve the above object, an authentication key exchange system according to one embodiment includes a server that functions as a KGC for ID-based encryption, a first device that performs authentication based on the ID-based encryption, and a second device that performs authentication based on an electronic signature, and is an authentication key exchange system that performs authentication key exchange between the first device and the second device, in which the server has a setup unit configured to generate a bilinear group used in the ID-based encryption, a master private key for the ID-based encryption, and a master public key corresponding to the master private key, and a long-term private key generation unit configured to generate a first long-term private key for a first identifier that indicates an identifier of the first device, and the first device has a first temporary key generation unit configured to generate a first temporary private key and a first temporary public key from the first temporary private key and the first long-term private key, a first temporary key transmission unit configured to transmit the first temporary public key and the first identifier to the second device, and a first temporary public key transmission unit configured to transmit at least a second temporary public key and the long-term public key of the second device and a previous and a first session key generation unit configured to generate a session key from the first temporary public key, the second temporary public key, the long-term public key of the second device, the first temporary private key, the first long-term private key, the first identifier, and the second identifier when receiving from the second device a second identifier indicating the identifier of the second device, the second device having a long-term key generation unit configured to generate a second long-term private key and the long-term public key corresponding to the second long-term private key, and a second temporary key generation unit configured to generate the second temporary public key from the second temporary private key and the second long-term private key; a second temporary key transmission unit configured to transmit at least the second temporary public key, the long-term public key, and the second identifier to the first device; and a second session key generation unit configured to generate the session key from the first temporary public key, the second temporary public key, the second temporary private key, the master public key, the first identifier, and the second identifier.

Efficient authentication key exchange can be performed between a device that performs authentication based on ID-based encryption and a device that performs authentication based on electronic certificates.

1 is a diagram illustrating an example of the overall configuration of an authentication 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 generating device according to the present embodiment. FIG. 2 is a diagram illustrating an example of a hardware configuration of a first communication device according to the present embodiment. FIG. 2 is a diagram illustrating an example of a hardware configuration of a second communication device according to the embodiment. FIG. 2 is a diagram illustrating an example of a functional configuration of a key generating device according to the present embodiment. 2 is a diagram illustrating an example of a functional configuration of a first communication device according to the embodiment; FIG. 2 is a diagram illustrating an example of a functional configuration of a second communication device according to the embodiment. FIG. 4 is a diagram for explaining a setup process in the first embodiment. FIG. 4 is a diagram for explaining a long-term private key generation process of the first communication device in the first embodiment. FIG. 11 is a diagram for explaining a long-term key generation process of the second communication device in the first embodiment. FIG. 10 is a diagram for explaining an authentication key exchange process in the first embodiment. FIG. 11 is a diagram for explaining a long-term key generation process of a second communication device in the second embodiment. FIG. 11 is a diagram for explaining an authentication key exchange process in the second embodiment.

The following describes one embodiment of the present invention. In this embodiment, an authentication key exchange system 1 is described that can perform efficient authentication key exchange between a device that performs authentication based on ID-based encryption and a device that performs authentication based on electronic certificates.

＜Preparation＞
The symbols, concepts, algorithms, etc. used in this embodiment will be explained.

Let p be a prime number, and let Z _p be the additive group of cosets modulo p in the additive group of integers.

Let κ be a security parameter. The security parameter κ represents the security strength (in bits) of the authentication key exchange system 1, and can be, for example, κ = 128 or κ = 256.

Bilinear group A bilinear group G = (p, _G1 , _G2 , _GT , _g1 , _g2 , e) is composed of a prime number p, cyclic groups _G1 , _G2 , and _GT of order p, a generator _g1 of _G1 , a generator _g2 of _G2 , and a bilinear mapping e: _G1 × _G2 → _GT that satisfies the following bilinearity and nondegeneracy.

Bilinearity: For any h ₁ ∈ _{G 1} , h ₂ ∈ _{G 2} , a, b ∈ Z _p , e(h ₁ ^a , h ₂ ^b )=e(h ₁ , h ₂ ) ^ab holds.

Non-degenerate: e(g ₁ , g ₂ ) is a generator of G _T .

An example of such a bilinear group is the optimal-ate paring described in Reference 1.

Digital Signature The digital signature is composed of the following three algorithms {KeyGen, Sign, Ver}.

(pk, sk)←KeyGen(1 ^κ ): Generate a public key and private key pair (pk, sk) using 1 ^κ as input, where 1 ^κ is a κ-bit string of 1s.

σ←Sign(sk,m): Generate a signature σ using the private key sk and message m as input.

1/0←Ver(pk,m,σ): Given public key pk, message m, and signature σ, output 1 or 0.

Furthermore, for any (pk, sk)←KeyGen(1 ^κ ), 1=Ver(pk, m, Sign(sk, m)) is satisfied. Examples of digital signatures include ECDSA and RSA-PSS.

<Overall composition>
An example of the overall configuration of an authentication key exchange system 1 according to this embodiment is shown in Fig. 1. As shown in Fig. 1, the authentication key exchange system 1 according to this embodiment includes a key generation device 10, a first communication device 20, and a second communication device 30. The key generation device 10, the first communication device 20, and the second communication device 30 are communicatively connected via a communication network 40 including, for example, the Internet. Each of the key generation device 10, the first communication device 20, and the second communication device 30 is also referred to as an "entity" or the like.

The key generating device 10 is a server that functions as a KGC for ID-based encryption, and executes a setup process for generating public parameters, etc., and generates a long-term private key for the first communication device 20 in response to a request from the first communication device 20. The key generating device 10 may be called, for example, a "key issuing server" or a "key generating server."

The first communication device 20 is a device (e.g., an IoT device, etc.) that performs authentication using ID-based encryption, and exchanges an authentication key for encrypted communication with the second communication device 30. Hereinafter, an identifier that uniquely identifies the first communication device 20 is referred to as ID _C. Note that, as the identifier ID _C , for example, a manufacturing specific number, a user ID, an email address, a telephone number, an IP address, a MAC address, etc. can be used.

The second communication device 30 is a device (e.g., a server, etc.) that performs authentication using an electronic certificate (hereinafter also simply referred to as a "certificate"), and performs authentication key exchange for encrypted communication with the first communication device 20. In other words, the second communication device 30 is a device that performs authentication on a PKI basis. Hereinafter, an identifier that uniquely identifies the second communication device 30 is referred to as ID _S. Note that, for example, a manufacturing specific number, a user ID, an email address, a telephone number, an IP address, a MAC address, etc. can be used as the identifier ID _S.

Here, the second communication device 30 generates its own long-term public key and long-term private key, and requests an external certification authority to issue a certificate for the long-term public key (more precisely, a certificate for the identifier ID _S and the long-term public key), but in this embodiment, it is assumed that the first communication device 20, which is the communication partner of the second communication device 30, trusts the certification authority. In other words, it is assumed that the first communication device 20 holds the public key of the certification authority and a certificate for that public key (a root certificate if the certification authority is a root certification authority, or a certificate issued by a higher-level certification authority if not).

The configuration of the authentication key exchange system 1 shown in FIG. 1 is an example, and is not limited to this. For example, in the example shown in FIG. 1, only one first communication device 20 and one second communication device 30 are shown, but there may be multiple first communication devices 20, and similarly, there may be multiple second communication devices 30. In the following, it is assumed that the first communication device 20 is an IoT device and the second communication device 30 is a server, but this is not limited to this.

<Hardware Configuration>
An example of the hardware configuration of the key generating device 10, the first communication device 20, and the second communication device 30 included in the authentication key exchange system 1 according to this embodiment will be described.

<Key generation device 10>
An example of a hardware configuration of the key generation device 10 according to this embodiment is shown in Fig. 2. As shown in Fig. 2, the key generation device 10 according to this embodiment includes an input device 11, a display device 12, an external I/F 13, a communication I/F 14, a RAM (Random Access Memory) 15, a ROM (Read Only Memory) 16, an auxiliary storage device 17, and a processor 18. Each of these pieces of hardware is connected to each other via a bus 19 so as to be able to communicate with each other.

The input device 11 is, for example, a keyboard, a mouse, a touch panel, various physical buttons, etc. The display device 12 is, for example, a display, a display panel, etc. Note that the key generation device 10 may not have at least one of the input device 11 and the display device 12, for example.

The external I/F 13 is an interface with external devices such as a recording medium 13a. Examples of the recording medium 13a include a CD (Compact Disc), a DVD (Digital Versatile Disk), an SD memory card (Secure Digital memory card), and a USB (Universal Serial Bus) memory card.

The communication I/F 14 is an interface for connecting the key generation device 10 to the communication network 40. The RAM 15 is a volatile semiconductor memory (storage device) that temporarily stores programs and data. The ROM 16 is a non-volatile semiconductor memory (storage device) that can store programs and data even when the power is turned off. The auxiliary storage device 17 is a non-volatile storage device such as an HDD (Hard Disk Drive) or SSD (Solid State Drive) in which programs and data are stored. The processor 18 is a variety of arithmetic devices such as a CPU (Central Processing Unit).

Note that the hardware configuration shown in FIG. 2 is an example, and the key generation device 10 may have other hardware configurations. For example, the key generation device 10 may have multiple auxiliary storage devices 17 and multiple processors 18, or may have various hardware other than the hardware shown in the figure.

<First communication device 20>
An example of the hardware configuration of the first communication device 20 according to this embodiment is shown in Fig. 3. As shown in Fig. 3, the first communication device 20 according to this embodiment has an external I/F 21, a communication I/F 22, a memory device 23, and a processor 24. Each of these pieces of hardware is connected via a bus 25 so as to be able to communicate with each other.

The external I/F 21 is an interface with external devices such as a recording medium 21a. Examples of the recording medium 21a include an SD memory card and a USB memory card.

The communication I/F 22 is an interface for connecting the first communication device 20 to the communication network 40. The memory device 23 is, for example, a storage device such as a flash memory. The processor 24 is, for example, a calculation device such as a CPU or an MPU (Micro-Processing Unit).

Note that the hardware configuration shown in FIG. 3 is an example, and the first communication device 20 may have other hardware configurations. For example, the first communication device 20 may have multiple memory devices 23 and multiple processors 24, or may have various hardware other than that shown in the figure.

<<Second communication device 30>>
An example of the hardware configuration of the second communication device 30 according to this embodiment is shown in Fig. 4. As shown in Fig. 4, the second communication device 30 according to this embodiment has an input device 31, a display device 32, an external I/F 33, a communication I/F 34, a RAM 35, a ROM 36, an auxiliary storage device 37, and a processor 38. Each of these pieces of hardware are connected to each other via a bus 39 so as to be able to communicate with each other.

The input device 31 is, for example, a keyboard, a mouse, a touch panel, various physical buttons, etc. The display device 32 is, for example, a display, a display panel, etc. Note that the second communication device 30 may not have at least one of the input device 31 and the display device 32, for example.

The external I/F 33 is an interface with external devices such as a recording medium 33a. Examples of the recording medium 33a include a CD, a DVD, an SD memory card, and a USB memory card.

The communication I/F 34 is an interface for connecting the second communication device 30 to the communication network 40. The RAM 35 is a volatile semiconductor memory (storage device) that temporarily stores programs and data. The ROM 36 is a non-volatile semiconductor memory (storage device) that can store programs and data even when the power is turned off. The auxiliary storage device 37 is a non-volatile storage device such as an HDD or SSD, in which programs and data are stored. The processor 38 is, for example, a CPU or other type of computing device.

The hardware configuration shown in FIG. 4 is an example, and the second communication device 30 may have other hardware configurations. For example, the second communication device 30 may have multiple auxiliary storage devices 37 and multiple processors 38, or may have various hardware other than the hardware shown in the figure.

<Functional configuration>
An example of the functional configuration of the key generating device 10, the first communication device 20, and the second communication device 30 included in the authentication key exchange system 1 according to this embodiment will be described.

<Key generation device 10>
An example of the functional configuration of the key generation device 10 according to this embodiment is shown in Fig. 5. As shown in Fig. 5, the key generation device 10 according to this embodiment has a setup processing unit 101 and a long-term private key generation unit 102. These units are realized, for example, by a process in which one or more programs installed in the key generation device 10 are executed by the processor 18. The key generation device 10 according to this embodiment also has a storage unit 103. The storage unit 103 is realized, for example, by the auxiliary storage device 17.

The setup processing unit 101 executes the setup process to generate a master private key, public parameters, etc.

In response to a request from a first communication device 20, the long-term private key generation unit 102 generates a long-term private key for the identifier of the first communication device 20.

The memory unit 103 stores various information (e.g., master private keys, public parameters, etc.).

<First communication device 20>
An example of the functional configuration of the first communication device 20 according to this embodiment is shown in Fig. 6. As shown in Fig. 6, the first communication device 20 according to this embodiment has a long-term private key request unit 201, a long-term private key receiving unit 202, a temporary key generating unit 203, a temporary key transmitting unit 204, a temporary key receiving unit 205, and a session key generating unit 206. Each of these units is realized, for example, by a process in which one or more programs installed in the first communication device 20 are executed by the processor 24. The first communication device 20 according to this embodiment also has a storage unit 207. The storage unit 207 is realized, for example, by the memory device 23.

The long-term private key request unit 201 requests the key generating device 10 to generate a long-term private key for its own identifier ID _C. Hereinafter, the long-term private key for the identifier ID _C will be referred to as ssk _C.

The long-term private key receiving unit 202 receives the long-term private key ssk _C from the key generating device 10 .

The temporary key generating unit 203 uses its own long-term private key ssk _C to generate a temporary private key esk _C and a temporary public key X _C.

The temporary key sending unit 204 sends the temporary public key _XC and its own identifier _IDC to the second communications device 30 .

The temporary key receiving unit 205 receives the temporary public key X _S of the second communication device 30 from the second communication device 30 .

The session key generating unit 206 generates key elements using its own long-term secret key ssk _C , the temporary public key X _S received from the second communication device 30, and the like, and then generates a session key from these key elements. Note that this session key is a shared key shared with the second communication device 30.

The storage unit 207 stores various information (for example, public parameters, its own long-term private key ssk _C, etc.).

<<Second communication device 30>>
An example of the functional configuration of the second communication device 30 according to this embodiment is shown in Fig. 7. As shown in Fig. 7, the second communication device 30 according to this embodiment has a long-term key generation unit 301, a certificate issuance request unit 302, a temporary key reception unit 303, a temporary key generation unit 304, a temporary key transmission unit 305, and a session key generation unit 306. Each of these units is realized, for example, by a process in which one or more programs installed in the second communication device 30 are executed by the processor 38. The second communication device 30 according to this embodiment also has a storage unit 307. The storage unit 307 is realized, for example, by the auxiliary storage device 37.

The long-term key generation unit 301 generates a long-term private key and a long-term public key. Hereinafter, the long-term private key of the second communication device 30 is designated as ssk _S , and the long-term public key is designated as spk _S.

The certificate issuance request unit 302 requests an external certificate authority to issue a certificate cert _S for its own identifier ID _S and long-term public key spk _S.

The temporary key receiving unit 303 receives the temporary public key _XC and the identifier ID _C from the first communications device 20 .

The temporary key generator 304 uses its own long-term private key ssk _S to generate a temporary private key esk _S and a temporary public key X _S.

The temporary key transmission unit 305 transmits the temporary public key X _S , its own long-term public key spk _S , its own identifier ID _S , the certificate cert _S, and the like to the first communications device 20 .

The session key generating unit 306 generates key elements using the master public key, the temporary public key _XC received from the first communication device 20, and the like, and then generates a session key from these key elements.

The storage unit 307 stores various information (for example, public parameters, its own long-term private key ssk _S, etc.).

[Example 1]
Hereinafter, a first example of the present embodiment will be described. In this example, it is assumed that each entity holds the following hash functions H ₁ , H ₂ , and H as parameters common to the system.

_H1 : A hash function that takes an identifier as input and outputs an element of _{G2 . H2} : A hash function that takes a κ-bit bit string and an element of _G2 as input and outputs an element of _Zp . H: A hash function that takes a variable-length character string as input and outputs a κ-bit bit string. <Setup process>
The setup process in the first embodiment will be described with reference to FIG.

The setup processing unit 101 of the key generation device 10 generates a bilinear group G=(p, _G1 , _G2 , _GT , _g1 , _g2 , e) (step S101).

Next, the setup processing unit 101 of the key generation device 10 generates a master private key wεZ _p uniformly at random (step S102).

Next, the setup processing unit 101 of the key generation device 10 generates a master public key W=g ₁ ^w (step S103).

Then, the setup processing unit 101 of the key generating device 10 stores the bilinear group G, the master private key w, and the master public key W in the memory unit 103 (step S104). Here, the public parameters are (G, W), and these public parameters (G, W) are made public to the first communication device 20 and the second communication device 30. In the following, it is assumed that the first communication device 20 and the second communication device 30 hold the public parameters (G, W).

<Long-term private key generation process of the first communication device 20>
The long-term private key generation process of the first communication device 20 in the first embodiment will be described with reference to FIG.

The long-term private key request unit 201 of the first communication device 20 requests the key generating device 10 to generate a long-term private key for its own identifier ID _C (step S201). Note that at least the identifier ID _C is specified in this request.

When the long-term private key generation unit 102 of the key generation device 10 receives the request to generate a long-term private key, it generates a long-term private key ssk _C =H ₁ (ID _C ) ^w ∈G ₂ (step S202).

Next, the long-term private key generation unit 102 of the key generation device 10 transmits the long-term private key ssk _C to the first communication device 20 (step S203).

Then, the long-term private key receiving unit 202 of the first communication device 20 receives the long-term private key ssk _C and stores this long-term private key ssk _C in the storage unit 207 (step S204). Note that the long-term private key ssk _C is assumed to be transmitted from the key generating device 10 to the first communication device 20 via a secure communication path.

<Long-term key generation process of the second communication device 30>
The long-term key generation process of the second communication device 30 in the first embodiment will be described with reference to FIG.

The long-term key generation unit 301 of the second communication device 30 generates a long-term private key ssk _S εZ _p uniformly at random (step S301).

Next, the long-term key generation unit 301 of the second communication device 30 generates a long _- term public key spk _S =g ₁ ^ssk_S (step S302).

Next, the certificate issuance request unit 302 of the second communication device 30 requests an external certificate authority to issue a certificate cert _S for its own identifier ID _S and long-term public key spk _S (step S303). As a result, the certificate cert _S is returned from the certificate authority.

Then, the long-term key generation unit 301 of the second communication device 30 stores the long-term private key ssk _S , the long-term public key spk _S, and the certificate cert _S in the storage unit 307 (step S304).

<Authentication key exchange process>
The authentication key exchange process in the first embodiment will be described with reference to Fig. 11. In the following, it is assumed that the first communication device 20 issues a start request to the second communication device 30. That is, it is assumed that the first communication device 20 is the initiator and the second communication device 30 is the responder. It is also assumed that the first communication device 20 has already acquired communication destination information (e.g., IP address, MAC address, etc.) of the second communication device 30.

The temporary key generating unit 203 of the first communication device 20 uniformly randomly generates a temporary secret key esk _C ε{0,1} ^κ , and then calculates x _C = H ₂ (esk _C , ssk _C ) to generate a temporary public key X _C = g ₁ ^x_C (step S401). The temporary secret key esk _C is stored in the storage unit 207. Note that "x_C" represents x _C.

Next, the temporary key transmitting unit 204 of the first communication device 20 transmits the temporary public key _XC and its own identifier _IDC to the second communication device 30 (step S402).

When the temporary key receiving unit 303 receives the temporary public key _XC and the identifier ID _C , the temporary key generating unit 304 of the second communication device 30 uniformly randomly generates a temporary secret key esk _S ∈{0,1} ^κ , and calculates x _S =H ₂ (esk _S , ssk _S ) to generate a temporary public key X _S =g ₁ ^x_S (step S403). The temporary secret key esk _S is stored in the storage unit 307. Note that "x_S" represents x _S.

Next, the temporary key transmission unit 305 of the second communication device 30 transmits the temporary public key X _S , its own long-term public key spk _S , the certificate cert _S and its own identifier ID _S to the first communication device 20 (step S404).

When the temporary key receiving unit 205 receives the temporary public key X _S, the long-term public key spk _S , the certificate cert _S, and the identifier ID _S , the session key generating unit 206 of the first communication device 20 verifies whether the long-term public key spk _S and the identifier ID _S are as described in the certificate cert _S , and verifies that the certificate cert _S has been correctly issued by a predetermined certification authority using the public key of the certification authority (step S405). If any of the verifications fails, the first communication device 20 ends the authentication key exchange process. On the other hand, if all of the verifications are successful, the first communication device 20 executes the next step S406.

The session key generating unit 206 of the first communication device 20 generates key elements _σ1 =e ⁽ _Xs , _sskC ), _σ2 = _{spkSx_C} , _σ3 = _{Xsx_C} , and then generates a session key SK=H( _σ1 , _σ2 , _σ3 , ^IDc , _IDs , _Xc , _Xs , _spkS , _certS ) (step S406). Note that _xC is calculated from the long-term private key _sskC and the temporary private key _eskC stored in the storage unit 207 by _{xC = H2} ( _eskC , _sskC ).

The session key generating unit 306 of the second communication device 30 generates key elements _σ1 =e( ^Wx_S , _H1 ( _IDC )), _σ2 = _{XCssk_S} , _σ3 = ^XCx_S , and then generates ^a session key _SK =H( _σ1 , _σ2 , _σ3 , _IDC , IDs, XC, _Xs , _spkS , _{certS )} (step S407). Note that _xS is calculated from the long-term private key _sskS and the temporary private key _eskS stored in the storage unit 307 by _{xS = H2} ( _eskS , _sskS ). This step may be executed immediately after the above step S404 is completed.

<Summary>
As described above, in this embodiment, the first communication device 20 and the second communication device 30 can share the session key SK. As a result, the first communication device 20 and the second communication device 30 can perform encrypted communication using the session key SK thereafter.

In this embodiment, the first communication device 20 and the second communication device 30 each need to perform the pairing calculation only once. Therefore, the number of pairing calculations is reduced compared to the protocol described in Non-Patent Document 1, for example, and efficient authentication key exchange can be realized.

In addition, in this embodiment, it is sufficient to calculate scalar multiplication on _G1 only three times in each of the first communication device 20 and the second communication device _30. In contrast, for example, in the protocol described in Non-Patent Document 1, it is necessary to calculate scalar multiplication on _G1 four (or five) times and scalar multiplication on G2 two times. Therefore, the number of scalar multiplications is reduced compared to the protocol described in Non-Patent Document 1, and efficient authentication key exchange can be realized.

In this embodiment, the first communication device 20 is authenticated by the key element σ ₁ , and the second communication device 30 is authenticated by the key element σ _2. Furthermore, the key element σ ₃ guarantees the essential security (forward secrecy) in the authentication key exchange.

[Example 2]
Hereinafter, a second embodiment of the present invention will be described. In this embodiment, each entity holds the following hash function _H3 as a parameter common to the system, in addition to the above hash functions _H1 , _H2 , and H.

_H3 : A hash function that takes a κ-bit string and a private key for a digital signature as input, and outputs an element of _Zp . Note that in this embodiment, differences from the first embodiment will be described, and descriptions of components similar to those in the first embodiment will be omitted.

<Setup process>
Since this is the same as the first embodiment, the description thereof will be omitted.

<Long-term private key generation process of the first communication device 20>
Since this is the same as the first embodiment, the description thereof will be omitted.

<Long-term key generation process of the second communication device 30>
The long-term key generation process of the second communication device 30 in the second embodiment will be described with reference to FIG.

The long-term key generation unit 301 of the second communication device 30 generates a key pair (spk _S , ssk _S )←KeyGen(1 ^κ ) of a long-term public key spk _S and a long-term private key ssk _S (step S501). Note that the long-term public key spk _S is a public key for digital signature, and the long-term private key ssk _S is a private key for digital signature.

Next, the certificate issuance request unit 302 of the second communication device 30 requests an external certificate authority to issue a certificate cert _S for its own identifier ID _S and long-term public key spk _S (step S502). As a result, the certificate cert _S is returned from the certificate authority.

Then, the long-term key generation unit 301 of the second communication device 30 stores the long-term private key ssk _S , the long-term public key spk _S, and the certificate cert _S in the storage unit 307 (step S503).

<Authentication key exchange process>
The authentication key exchange process in the second embodiment will be described with reference to Fig. 13. In the following, it is assumed that the first communication device 20 issues a start request to the second communication device 30. That is, it is assumed that the first communication device 20 is the initiator and the second communication device 30 is the responder. It is also assumed that the first communication device 20 has already acquired communication destination information (e.g., IP address, MAC address, etc.) of the second communication device 30.

The temporary key generating unit 203 of the first communication device 20 generates a temporary secret key esk _C ε{0,1} ^κ uniformly at random, and then calculates x _C = H ₂ (esk _C , ssk _C ) to generate a temporary public key X _C = g ₁ ^x_C (step S601). The temporary secret key esk _C is stored in the storage unit 207.

Next, the temporary key transmitting unit 204 of the first communication device 20 transmits the temporary public key _XC and its own identifier _IDC to the second communication device 30 (step S602).

When the temporary key receiving unit 303 receives the temporary public key _XC and the identifier ID _C , the temporary key generating unit 304 of the second communication device 30 uniformly randomly generates a temporary secret key esk _S ∈{0,1} ^κ , and calculates x _S = H ₃ (esk _S , ssk _S ) to generate a temporary public key X _S = g ₁ ^x_S (step S603). The temporary secret key esk _S is stored in the storage unit 307.

Next, the temporary key generating unit 304 of the second communication device 30 generates a signature sign _S <- Sign(ssk _S , m) for a message m including the temporary public key X _S , the identifier ID _C , and the identifier ID _S (step S604).

Next, the temporary key transmission unit 305 of the second communication device 30 transmits the temporary public key X _S , the signature sign _S , its own long-term public key spk _S , the certificate cert _S and its own identifier ID _S to the first communication device 20 (step S605).

When the temporary key receiving unit 205 receives the temporary public key X _S , the signature sign _S , its own long-term public key spk _S , the certificate cert _S, and its own identifier ID _S , the session key generating unit 206 of the first communication device 20 verifies whether the long-term public key spk _S and the identifier ID _S are as described in the certificate cert _S , and verifies that the certificate cert _S has been correctly generated by a predetermined certification authority using the public key of the certification authority, and further verifies whether 1 = Ver (spk _S , m, sign _S ) holds (step S606). If any of the verifications fails, the first communication device 20 ends the authentication key exchange process. On the other hand, if all of the verifications are successful, the first communication device 20 executes the next step S607.

The session key generating unit 206 of the first communication device 20 generates key elements _σ1 = ^e ( _Xs , _sskC ) and _σ2 = _{Xsx_C} , and then generates a session key SK=H( _σ1 , _σ2 , _IDc , _IDs , _Xc , _Xs , _signS , _spkS , _certS ) (step S607). Note that _xC is calculated from the long-term private key _sskC and the temporary private key _eskC stored in the storage unit 207 by _xC = _H2 ( _eskC , _sskC ).

The session key generating unit 306 of the second communication device 30 generates key elements _σ1 =e ^{(Wx_S, H1(IDC)) and σ2=XCx_S ,} _{and then generates a} session key SK=H( _σ1 , _σ2 , _IDC , _IDs , _XC , _Xs , signS, _{spkS , certS} ) (step S608). Note that _xS is calculated from the long-term private key _sskS and the temporary private key _eskS stored in the storage unit 307 by _xS = _H3 ( _eskS , _sskS ). This step may be executed immediately after the above step S605 is completed.

<Summary>
As described above, in this embodiment, the first communication device 20 and the second communication device 30 can share the session key SK. As a result, the first communication device 20 and the second communication device 30 can perform encrypted communication using the session key SK thereafter.

At this time, in this embodiment, similar to the first embodiment, it is sufficient to calculate the pairing calculation only once in each of the first communication device 20 and the second communication device 30. Therefore, the number of pairing calculations is reduced compared to the protocol described in Non-Patent Document 1, for example, and therefore efficient authentication key exchange can be realized.

In addition, in this embodiment, by authenticating the second communication device 30 by a digital signature, a key element for authenticating the second communication device 30 is not required, and it is necessary to calculate scalar multiplication on _G1 only twice in each of the first communication device 20 and the second communication device 30. Therefore, it is possible to realize a more efficient authentication key exchange compared to the first embodiment.

In this embodiment, the first communication device 20 is authenticated by the key element σ ₁ , and the second communication device 30 is authenticated by the digital signature. In addition, the key element σ ₂ guarantees the essential security (forward secrecy) in the authentication key exchange.

The present invention is not limited to the specifically disclosed embodiments above, and various modifications, changes, and combinations with known technologies are possible without departing from the scope of the claims.

[References]
Reference 1: Vercauteren, F.: Optimal pairings. IEEE Trans. Inf. Theory 56, 455-461 (2010)

REFERENCE SIGNS LIST 1 Authentication key exchange system 10 Key generation device 11 Input device 12 Display device 13 External I/F
13a Recording medium 14 Communication I/F
15 RAM
16 ROM
17 Auxiliary storage device 18 Processor 19 Bus 20 First communication device 21 External I/F
21a Recording medium 22 Communication I/F
23 Memory device 24 Processor 25 Bus 30 Second communication device 31 Input device 32 Display device 33 External I/F
33a Recording medium 34 Communication I/F
35 RAM
36 ROM
37 Auxiliary storage device 38 Processor 39 Bus 101 Setup processing unit 102 Long-term private key generation unit 103 Storage unit 201 Long-term private key request unit 202 Long-term private key reception unit 203 Temporary key generation unit 204 Temporary key transmission unit 205 Temporary key reception unit 206 Session key generation unit 207 Storage unit 301 Long-term key generation unit 302 Certificate issuance request unit 303 Temporary key reception unit 304 Temporary key generation unit 305 Temporary key transmission unit 306 Session key generation unit 307 Storage unit

Claims (5)

An authentication key exchange system including a server that functions as a KGC for ID-based encryption, a first device that performs authentication based on the ID-based encryption, and a second device that performs authentication based on a digital signature, and performing authentication key exchange between the first device and the second device,
The server,
a set-up unit configured to generate a bilinear group used in the identity-based encryption, a master private key for the identity-based encryption, and a master public key corresponding to the master private key;
a long-term private key generation unit configured to generate a first long-term private key for a first identifier indicating an identifier of the first device,
The first device includes:
a first temporary key generator configured to generate a first temporary private key and to generate a first temporary public key from the first temporary private key and the first long-term private key;
a first temporary key sending unit configured to send the first temporary public key and the first identifier to the second device;
a first session key generation unit configured to generate a session key from the first temporary public key, the second temporary public key, the long-term public key of the second device, the first temporary private key, the first long-term private key, the first identifier, and the second identifier when receiving at least a second temporary public key, a long-term public key of the second device, and a second identifier indicating an identifier of the second device from the second device,
The second device includes:
a long-term key generator configured to generate a second long-term private key and the long-term public key corresponding to the second long-term private key;
a second temporary key generator configured to generate a second temporary private key and to generate the second temporary public key from the second temporary private key and the second long-term private key;
a second temporary key sender configured to send at least the second temporary public key, the long-term public key, and the second identifier to the first device;
a second session key generator configured to generate the session key from the first temporary public key, the second temporary public key, the second temporary private key, the master public key, the first identifier, and the second identifier ;
The first temporary key generation unit
a generator of a cyclic group that is a domain of a first argument side of a pairing operation in the bilinear group is used as a base, and a first value that is an output value of a hash function H2 having the first temporary private key and the first long-term private key as input _is used as an exponent, and
The first session key generation unit
Further receiving a certificate for the long-term public key, and verifying whether the certificate was issued by a predetermined certification authority;
If the verification is successful, a pairing operation is performed using the second temporary public key as a first argument and the first long-term private key as a second argument, and the result is used as a first key element;
Calculate a second key element by raising the long-term public key to a power of the first value;
Calculating a third key element by raising the second temporary public key to a power of the first value;
is configured to generate, as the session key, an output value of a hash function H having as input the first key element, the second key element, the third key element, the first temporary public key, the second temporary public key, the first identifier, the second identifier, the long-term public key, and the certificate;
The second temporary key transmission unit
further configured to transmit the certificate to the first device;
The second temporary key generation unit
a generator of a cyclic group that is a domain of a first argument side of a pairing operation in the bilinear group is used as a base, and a second value that is an output value of the hash function H2 having the second temporary private key and the second long-term private key as input is used as _an exponent, and
The second session key generation unit
calculating , as the first key element, a result of a pairing operation using the master public key as a base, a power of the second value as a first argument, and an output value of a hash function H1 having the first identifier as an input _as a second argument;
Calculating the second key element to a power of the first temporary public key as a base and the second long-term private key as an exponent;
Calculating the third key element by raising the first temporary public key to a power of the second value;
and generating, as the session key, an output value of the hash function H using the first key element, the second key element, the third key element, the first temporary public key, the second temporary public key, the first identifier, the second identifier, the long-term public key, and the certificate as inputs.
Authenticated Key Exchange System. An authentication key exchange system including a server that functions as a KGC for ID-based encryption, a first device that performs authentication based on the ID-based encryption, and a second device that performs authentication based on a digital signature, and performing authentication key exchange between the first device and the second device,
The server,
a set-up unit configured to generate a bilinear group used in the identity-based encryption, a master private key for the identity-based encryption, and a master public key corresponding to the master private key;
a long-term private key generation unit configured to generate a first long-term private key for a first identifier indicating an identifier of the first device,
The first device includes:
a first temporary key generator configured to generate a first temporary private key and to generate a first temporary public key from the first temporary private key and the first long-term private key;
a first temporary key sending unit configured to send the first temporary public key and the first identifier to the second device;
a first session key generation unit configured to generate a session key from the first temporary public key, the second temporary public key, the long-term public key of the second device, the first temporary private key, the first long-term private key, the first identifier, and the second identifier when receiving at least a second temporary public key, a long-term public key of the second device, and a second identifier indicating an identifier of the second device from the second device,
The second device includes:
a long-term key generator configured to generate a second long-term private key and the long-term public key corresponding to the second long-term private key;
a second temporary key generator configured to generate a second temporary private key and to generate the second temporary public key from the second temporary private key and the second long-term private key;
a second temporary key sender configured to send at least the second temporary public key, the long-term public key, and the second identifier to the first device;
a second session key generator configured to generate the session key from the first temporary public key, the second temporary public key, the second temporary private key, the master public key, the first identifier, and the second identifier;
The first temporary key generation unit
a generator of a cyclic group that is a domain of a first argument side of a pairing operation in the bilinear group is used as a base, and a first value that is an output value of a hash function _H2 having the first temporary private key and the first long-term private key as input is used as an exponent, and
The first session key generation unit
Further receiving a certificate for the long-term public key and a signature of the second device, and performing a first verification indicating whether or not the certificate has been issued by a predetermined certificate authority and a second verification indicating verification of the signature;
If the first verification and the second verification are successful, a pairing operation is performed with the second temporary public key as a first argument and the first long-term private key as a second argument, and a result of the pairing operation is calculated as a first key element;
Calculating a second key element by raising the second temporary public key to a power of the first value;
is configured to generate, as the session key, an output value of a hash function H having as input the first key element, the second key element, the first temporary public key, the second temporary public key, the first identifier, the second identifier, the long-term public key, the certificate, and the signature;
The second temporary key transmission unit
further configured to transmit the certificate and the signature to the first device;
The second temporary key generation unit
a generator of a cyclic group that is a domain of a first argument side of a pairing operation in the bilinear group is used as a base, and a second value that is an output value of a hash function _H3 having the second temporary private key and the second long-term private key as input is used as an exponent, and
The second session key generation unit
calculating, as the first key element, a result of a pairing operation using the master public key as a base, a power of the second value as a first argument, and an output value of a hash function _H1 having the first identifier as an input as a second argument;
Calculating the second key element to a power of the first temporary public key and the second value as an exponent;
and configured to generate, as the session key, an output value of the hash function H using the first key element, the second key element, the first temporary public key, the second temporary public key, the first identifier, the second identifier, the long-term public key, the certificate, and the signature as inputs.
Authenticated Key Exchange System. A method for use in an authentication key exchange system including a server functioning as a KGC for ID-based encryption, a first device that performs authentication based on the ID-based encryption, and a second device that performs authentication based on a digital signature, the system performing authentication key exchange between the first device and the second device, comprising:
The server,
a setup procedure for generating a bilinear group for use in the identity-based encryption, a master private key for the identity-based encryption, and a master public key corresponding to the master private key;
a long-term private key generation step for generating a first long-term private key for a first identifier indicating an identifier of the first device;
The first device comprises:
a first temporary key generation step of generating a first temporary private key and generating a first temporary public key from the first temporary private key and the first long-term private key;
a first temporary key transmission step of transmitting the first temporary public key and the first identifier to the second device;
receiving at least a second temporary public key, a long-term public key of the second device, and a second identifier indicating an identifier of the second device from the second device, executing a first session key generation procedure for generating a session key from the first temporary public key, the second temporary public key, the long-term public key of the second device, the first temporary private key, the first long-term private key, the first identifier, and the second identifier;
The second device comprises:
a long-term key generation step of generating a second long-term private key and the long-term public key corresponding to the second long-term private key;
a second temporary key generation step of generating a second temporary private key and generating the second temporary public key from the second temporary private key and the second long-term private key;
a second temporary key transmission procedure for transmitting at least the second temporary public key, the long-term public key, and the second identifier to the first device;
a second session key generation procedure for generating the session key from the first temporary public key, the second temporary public key, the second temporary private key, the master public key, the first identifier , and the second identifier ;
The first temporary key generation procedure includes:
generate, as the first temporary public key, a power of a first value that is an output value of a hash function H2 that has a base that is a generator of a cyclic group that is a domain of a first argument side of a pairing operation in the bilinear group and an input that is the first temporary private key and the first long-term private _key ;
The first session key generation procedure includes:
Further receiving a certificate for the long-term public key, and verifying whether the certificate was issued by a predetermined certification authority;
If the verification is successful, a pairing operation is performed using the second temporary public key as a first argument and the first long-term private key as a second argument, and the result is used as a first key element;
Calculate a second key element by raising the long-term public key to a power of the first value;
Calculating a third key element by raising the second temporary public key to a power of the first value;
generating, as the session key, an output value of a hash function H having as input the first key element, the second key element, the third key element, the first temporary public key, the second temporary public key, the first identifier, the second identifier, the long-term public key, and the certificate;
The second temporary key transmission procedure includes:
further transmitting the certificate to the first device;
The second temporary key generation procedure includes:
generate, as the second temporary public key, a power of a second value that is an output value of the hash function H2 having as input the second temporary private key and the second long-term private key and a generator of a cyclic group that is _a domain of a first argument side of a pairing operation in the bilinear group as a base and an exponent;
The second session key generation procedure includes:
calculating , as the first key element, a result of a pairing operation using the master public key as a base, a power of the second value as a first argument, and an output value of a hash function H1 having the first identifier as an input _as a second argument;
Calculating the second key element to a power of the first temporary public key as a base and the second long-term private key as an exponent;
Calculating the third key element by raising the first temporary public key to a power of the second value;
generating, as the session key, an output value of the hash function H using as input the first key element, the second key element, the third key element, the first temporary public key, the second temporary public key, the first identifier, the second identifier, the long-term public key, and the certificate;
method. A method for use in an authentication key exchange system including a server functioning as a KGC for ID-based encryption, a first device that performs authentication based on the ID-based encryption, and a second device that performs authentication based on a digital signature, the system performing authentication key exchange between the first device and the second device, comprising:
The server,
a setup procedure for generating a bilinear group for use in the identity-based encryption, a master private key for the identity-based encryption, and a master public key corresponding to the master private key;
a long-term private key generation step for generating a first long-term private key for a first identifier indicating an identifier of the first device;
The first device comprises:
a first temporary key generation step of generating a first temporary private key and generating a first temporary public key from the first temporary private key and the first long-term private key;
a first temporary key transmission step of transmitting the first temporary public key and the first identifier to the second device;
receiving at least a second temporary public key, a long-term public key of the second device, and a second identifier indicating an identifier of the second device from the second device, executing a first session key generation procedure for generating a session key from the first temporary public key, the second temporary public key, the long-term public key of the second device, the first temporary private key, the first long-term private key, the first identifier, and the second identifier;
The second device comprises:
a long-term key generation step of generating a second long-term private key and the long-term public key corresponding to the second long-term private key;
a second temporary key generation step of generating a second temporary private key and generating the second temporary public key from the second temporary private key and the second long-term private key;
a second temporary key transmission procedure for transmitting at least the second temporary public key, the long-term public key, and the second identifier to the first device;
a second session key generation procedure for generating the session key from the first temporary public key, the second temporary public key, the second temporary private key, the master public key, the first identifier, and the second identifier;
The first temporary key generation procedure includes:
A hash function H, which has a base that is a generator of a cyclic group that is a domain of the first argument side of the pairing operation in the bilinear group, and has inputs of the first temporary private key and the first long-term private key. ₂ Generate a power of the first value, which is an output value of
The first session key generation procedure includes:
Further receiving a certificate for the long-term public key and a signature of the second device, and performing a first verification indicating whether or not the certificate has been issued by a predetermined certificate authority and a second verification indicating verification of the signature;
If the first verification and the second verification are successful, a pairing operation is performed with the second temporary public key as a first argument and the first long-term private key as a second argument, and a result of the pairing operation is calculated as a first key element;
Calculating a second key element by raising the second temporary public key to a power of the first value;
generating, as the session key, an output value of a hash function H having as input the first key element, the second key element, the first temporary public key, the second temporary public key, the first identifier, the second identifier, the long-term public key, the certificate, and the signature;
The second temporary key transmission procedure includes:
further transmitting the certificate and the signature to the first device;
The second temporary key generation procedure includes:
A hash function H, which has a base that is a generator of a cyclic group that is a domain of the first argument side of the pairing operation in the bilinear group, and inputs the second temporary private key and the second long-term private key. ₃ Generate a second temporary public key by exponentiating the second value, which is the output value of
The second session key generation procedure includes:
A hash function H with the master public key as a base, the second value as a power as a first argument, and the first identifier as an input. ₁ A pairing operation result having the output value of the second argument is calculated as the first key element,
Calculating the second key element to a power of the first temporary public key and the second value as an exponent;
generating, as the session key, an output value of the hash function H using as input the first key element, the second key element, the first temporary public key, the second temporary public key, the first identifier, the second identifier, the long-term public key, the certificate, and the signature;
method. A program for causing a computer to function as a server, a first device, or a second device included in the authentication key exchange system according to claim 1 or 2 .

Images