JP5931795B2 - KEY EXCHANGE SYSTEM, KEY GENERATION DEVICE, COMMUNICATION DEVICE, KEY EXCHANGE METHOD, AND PROGRAM - Google Patents

Description

  The present invention relates to information security technology, and more particularly to a key exchange technology for sharing a common session key between two parties.

  Conventional key exchange techniques include a hierarchical ID authentication key exchange system that applies a hierarchical ID-based encryption system. Non-Patent Document 1 describes the FSY method, which is a hierarchical ID authentication key exchange method that is strong against secret key leakage.

  Hereinafter, the FSY method will be described.

[Public parameters]
The PID is a protocol ID and a unique ID corresponding to the protocol specification. Let к be the security parameter. Let p be a k-bit prime number, and G and G _T be a group capable of efficiently calculating the bilinear pairing function e: G × G → G _T. Let g and g _{T be} the generators of groups G and G _T , respectively. _Let Z _p be a remainder ring modulo p. H ₁ : {0,1} ^* → G, H ₂ : {0,1} ^* → Z _p and H: {0,1} ^* → {0,1} ^к are hash functions.

[Key generation process]
The FSY key generation algorithm selects a master secret key s ₀ εZ _p uniformly and sets S ₀ = 1 _G (εG). However, 1 _G is a unit _element of the group G. The key generation algorithm calculates and discloses the master public key P ₀ = g (∈G) and Q ₀ = P ₀ ^ s ₀ (∈G). Here, ^ represents a power.

[Key extraction process]
Each user of the key exchange method is assumed to correspond to identification information (ID ₁ ,..., ID _t-1 ). Each user selects s _t-1 εZ _p uniformly and randomly as initialization processing, and holds it as secret state information. The user set with the identification information ID = (ID ₁ , ..., ID _t-1 ) uses his / her long-term secret key (S _t-1 , Q ₁ , ..., Q _t-1 ) as a key extractor, A long-term secret key (S _t , Q ₁ ,..., Q _t ) is generated as follows for a lower-level user in which the identification information ID ′ = (ID ₁ ,..., ID _t ) is set. First, the key extractor calculates P _t = H ₁ (ID ₁ ,…, ID _t ) (∈G), S _t = S _t-1 P _t ^ s _t-1 , Q _t = P ₀ ^ s _t To do. Subsequently, the key extractor outputs (S _t , Q ₁ ,..., Q _t ) as the long-term secret key of the lower user.

[Key exchange process]
Here, user U _A is the initiator of the key exchange session, and user U _B is the responder. The user U _A belongs to the α-th layer, and the long-term secret key (S _{A, α} , Q _{A, 1} , ..., Q _A, corresponding to the identification information ID _A = (ID _{A, 1} , ..., ID _{A, α} ) _α ). The user U _B belongs to the β hierarchy and the long-term secret key (S _{B, β} , Q _{B, 1} , ..., Q _B, corresponding to the identification information ID _B = (ID _{B, 1} , ..., ID _{B, β} ) _β ).

First, the user U _A randomly selects an ad hoc secret key ~ x∈Z _p . At this time, the user U _A calculates x = H ₂ (S _{A, α} , ˜x), and the ad hoc public key epk _IDB = (X ₀ = P ₀ ^x , X _{B, 2} = P _{B, 2} ^x ,... , X _{B, β} = P _{B, β} ^x ). However, P _{B, i} = H ₁ (ID _{B, 1} ,..., ID _{B, i} ) (1 ≦ i <β). User U _A sends an ad hoc public key epk _IDB to user U _B.

On the other hand, the user U _B selects an ad hoc secret key ~ y∈Z _p uniformly at random. At this time, the user U _B calculates y = H ₂ (S _{B, β} , ˜y), and the ad hoc public key epk _IDA = (Y ₀ = P ₀ ^y , Y _{A, 2} = P _{A, 2} ^y ,... , Y _{A, α} = P _{A, α} ^y ). However, P _{A, i} = H ₁ (ID _{A, 1} ,..., ID _{A, i} ) (1 ≦ i <α). User U _B sends ad hoc public key epk _IDA to user U _A.

Subsequently, the user U _B calculates the shared secret information σ _{B, 1} , σ _{B, 2} , σ _{B, 3} as follows.

Further, the user U _B obtains a session key K = H (σ _{B, 1} , σ _{B, 2} , σ _{B, 3} , PID, ID _A , ID _B , epk _IDB , epk _IDA ). User U _B outputs session key K and ends the process.

On the other hand, the user U _A calculates the shared secret information σ _{A, 1} , σ _{A, 2} , σ _{A, 3} as follows.

Further, the user U _A obtains a session key K = H (σ _{A, 1} , σ _{A, 2} , σ _{A, 3} , PID, ID _A , ID _B , epk _IDB , epk _IDA ). User U _A outputs session key K and ends the process.

Shared secret sigma _{A, 1} the user U _A is _{calculated, σ A, 2, σ A} , 3 and the user U shared secret sigma _{B, 1 of B} is _{calculated, σ B, 2, σ B} , 3 are equal to each other Therefore, the user U _A and the user U _B can obtain the same session key K.

The following shows that the shared secret information σ _{A, 1} is equal to the shared secret information σ _{B, 1} .

The shared secret information σ _{A, 2} and the shared secret information σ _{B, 2} are equal to each other as follows.

It is shown below that the shared secret information σ _{A, 3} is equal to the shared secret information σ _{B, 3} .

Atsushi Fujioka, Koutarou Suzuki, Kazuki Yoneyama, “Hierarchical ID-Based Authenticated Key Exchange Resilient to Ephemeral Key Leakage.”, IEICE Transactions 94-A (6), pp. 1306-1317, 2011.

  In the prior art described in Non-Patent Document 1, there is a problem that the hash function must be an ideally safe random oracle in order to guarantee safety. However, it is known that a random oracle cannot be realized using an actual hash function. Therefore, it is desirable that the security proof be attached without assuming a random oracle.

  In the prior art described in Non-Patent Document 1, each user needs to send and receive a number of elements depending on the depth of the hierarchy (α and β in the above description), and the number of users participating in the key exchange system. The traffic volume will increase explosively when the network becomes large. In addition, heavy pairing calculations are performed when obtaining shared secret information, but the number of calculations is also proportional to the depth of the hierarchy, so if the number of users participating in the key exchange system becomes large The computational complexity also increases explosively. Therefore, a highly scalable method in which the traffic and the number of pairing calculations do not depend on the hierarchy depth is desirable.

  SUMMARY OF THE INVENTION An object of the present invention is to provide a key exchange technique that guarantees safety without assuming a random oracle, and has high expandability without regard to the amount of calculation or communication depending on the depth of the hierarchy.

In order to solve the above problem, a key exchange system according to an aspect of the present invention includes a key generation device and a plurality of communication devices layered in an L hierarchy. In the following, ^ represents power, • represents multiplication, Z _p is a remainder ring modulo prime p, G and G _T are bilinear pairing functions e: G × G → G _T efficiently It is a computable group, g is a generator of group G, F _ke , F _gen , F _sig and F _kdf are pseudo-random functions, FS is a pseudo-random function key space, Gen is any single-use signature scheme , Sign is a signature generation algorithm of any single use signature scheme, and Ver is a signature verification algorithm of any single use signature scheme. The key generator selects a value z from the ring Z _p , calculates a value g ₁ = g ^z, and generates a parameter that selects values g ₂ , g ₃ , g ₄ , h ₁ ,..., H _L from the group G A master secret key generation unit that calculates a master secret key MSK = g ₂ ^z , a long-term secret key SSK _i of a communication device belonging to the i-th layer, a value r selected from the ring Z _p , a value w ₁ , Select w ₂ , w ₃ , w ₄ , w ₅ , w ₆ from the key space FS, u ₀ = MSK · (h ₁ ^ ID ₁ … h _i ^ ID _i · g ₃ ) ^r , u ₁ = g ^r , U ₂ = g ₄ ^r , and SSK _i = (u ₀ , u ₁ , u ₂ , h _{i + 1} ^r ,…, h _L ^r , w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ ) and a long-term secret key generation unit.

The communication apparatus belongs to the α-th layer and identification information ID = (ID ₁ ,..., ID _α ) is set, and the communication information belongs to the β-th layer and the identification information ID ′ = (ID ′ ₁ ,..., ID ′ _β ) It is assumed that the session key SK is shared with the set communication device. The communication device includes an ad hoc secret key generation unit that selects values esk _ke , esk ' _ke , esk _gen , esk' _gen , esk _sig , esk ' _sig from the key space FS, and a pseudo-random function F _ke (w ₁ , esk _ke ) And the output of the pseudorandom function F _ke (esk ' _ke , w ₂ ) to generate the pseudorandom number s and output the pseudorandom function F _gen (w ₃ , esk _gen ) a pseudo-random function _{F gen (esk 'gen, w} 4) calculates the exclusive OR of the output of generating a pseudo-random number rand _gen, pseudo-random function _{F sig (w 5, esk sig} ) and the output of the pseudo a pseudo-random number generator for generating a pseudo-random number rand _sig by calculating an exclusive OR of the output of the random function _{F sig (esk 'sig, w} 6), executes the key generation algorithm Gen using the pseudo-random number rand _gen Then, a signing key generation unit that generates the signing key sk and the verification key vk, and generates the ciphertext C ₁ by calculating the value g of the value g, and (h ₁ ^ ID ′ ₁ … h _β ^ ID ′ _β · g ₄ ^vk · g ₃₎ to calculate the ^s to generate a ciphertext C ₂ A ciphertext generating unit, using the pseudo-random number rand _sig and signature key sk as an input ciphertext C ₁ and the ciphertext C ₂ performs signature algorithm Sign, generates a signature sigma, ciphertext C _1, the ciphertext C ₂ , an ad hoc public key generation unit that generates an ad hoc public key EPK including a signature σ and a verification key vk, and a ciphertext C ′ ₁ , a ciphertext C ′ ₂ , and a signature σ ′ from a communication device in which the identification information ID ′ is set And the ad hoc public key EPK ′ including the verification key vk ′, the ciphertext C ′ ₁ , the ciphertext C ′ ₂ and the signature σ ′ are input, and the verification algorithm Ver is executed using the verification key vk ′, and the ad hoc disclosure An ad hoc public key verification unit that verifies the key EPK ′, calculates e (g ₁ , g ₂ ) ^s to generate secret information σ ₁ , and e (C ′ ₁ , u ₀ · u ₂ ^{vk ′} ) / e (C ′ ₂ , u ₁ ) to generate secret information σ ₂ , e (C ′ ₁ , g ₃ ) ^s to generate secret information σ ₃ , and identification information ID , Identification information ID ', ad hoc public Hirakikagi EPK and generates a session identification information ST based on ad hoc public key EPK ', the secret information sigma ₁ and the pseudo-random function F _kdf output and secret sigma ₂ and the session identification information ST to enter the session identification information ST Session key that generates the session key SK by calculating the exclusive OR of the output of the pseudo-random function F _{kdf that receives} and the secret information σ ₃ and the output of the pseudo-random function F _{kdf that receives} the session identification information ST And a generation unit.

  The key exchange technique of the present invention is highly extensible because it has a security proof even without assuming a random oracle, and the amount of calculation and the amount of communication are constant even when the hierarchy of the communication device is deep.

It is a figure which illustrates the function structure of a key exchange system. It is a figure which illustrates the function structure of a key generation apparatus. It is a figure which illustrates the function structure of a communication apparatus. It is a figure which illustrates the processing flow of the key generation method. It is a figure which illustrates the processing flow of the key exchange method. It is a figure which illustrates the processing flow of the key exchange method.

  In the present invention, by using a pseudo-random function and a strong random extractor or key derivation function instead of a random oracle, a safe system is realized without assuming a random oracle. In addition, this method uses a hierarchical ID-based encryption whose ciphertext length and the number of pairing calculations do not depend on the depth of the hierarchy, so that the traffic and the number of pairing calculations depend on the depth of the hierarchy. It is highly scalable.

  In the prior art, a random oracle was used to derive the session key, but in the present invention, the distribution of the shared information is smoothed by a strong random extractor or key derivation function, and the output is obtained by using the value as the key of the pseudo-random function. Use as a session key. Since the process for deriving the session key is changed in this way, a random oracle is not required. This method is described in “Colin Boyd, Yvonne Cliff, Juan Manuel Gonzalez Nieto, Kenneth G. Paterson,“ Efficient One-Round Key Exchange in the Standard Model ”, ACISP 2008, pp. 69-83.

  Also, in the present invention, the amount of communication and the number of pairing calculations are made constant using the Boneh-Boyen-Goh hierarchical ID-based encryption (hereinafter abbreviated as BBG-HIBE). Specifically, the BBG-HIBE ciphertext was exchanged and a session key was generated from the decrypted message. Further, by signing a ciphertext using a single-use signature, it is possible to detect message tampering. The construction method of BBG-HIBE is described in detail in “Dan Boneh, Xavier Boyen, Eu-Jin Goh,“ Hierarchical Identity Based Encryption with Constant Size Ciphertext ”, EUROCRYPT 2005, pp. 440-456”.

[Embodiment]
Hereinafter, embodiments of the present invention will be described in detail. In addition, the same number is attached | subjected to the component which has the same function in drawing, and duplication description is abbreviate | omitted.

〔Constitution〕
An example of a functional configuration of the key exchange system A according to the embodiment will be described with reference to FIG. The key exchange system A includes a key generation device 1 and N (≧ 2) communication devices 2 ₁ ,..., 2 _N. The key generation device 1 and the N communication devices 2 ₁ ,..., 2 _N are connected to the network 9. The network 9 only needs to be configured so that the key generation device 1 and each of the N communication devices 2 ₁ ,..., 2 _N can communicate with each other, for example, the Internet 9, LAN, WAN, or the like. it can. Further, the key generation device 1 and each of the N communication devices 2 ₁ ,..., 2 _N do not necessarily need to be able to communicate online via a network. For example, information output by the key generation device 1 is stored in a portable recording medium such as a USB memory, and is input offline to any one of the communication devices 2 _n (n = 1,..., N) from the portable recording medium. You may comprise as follows. Since the input / output of data between the other devices is the same, a specific description is omitted.

Identification information ID ₁ ,..., ID _N is assigned to each of the _N communication devices 2 ₁ ,. Communication apparatus 2 _1, ..., 2 _N is layered on L hierarchy, the hierarchy identification information ID _1, ..., represented by ID _N. For example, assuming that identification information ID _n = (ID ₁ , ID ₂ ,..., ID _i ) is set in the i-th layer communication device 2 _n (1 ≦ n ≦ N), communication in the i + 1-th layer Identification information ID _m = (ID ₁ , ID ₂ ,..., ID _i , ID _{i + 1} ) is set in the device 2 _m (1 ≦ m ≦ N, m ≠ n). Thus, the hierarchical structure is expressed by including the identification information of any communication apparatus belonging to the higher hierarchy in the identification information of the communication apparatus belonging to the lower hierarchy.

  With reference to FIG. 2, an example of a functional configuration of the key generation device 1 included in the key exchange system A will be described. The key generation device 1 includes a parameter generation unit 10, a master secret key generation unit 12, a long-term secret key generation unit 14, a control unit 101, a memory 102, and a storage unit 103. The key generation device 1 is a special configuration in which a special program is read into a known or dedicated computer having a central processing unit (CPU), a main storage device (Random Access Memory, RAM), and the like. Device. The key generation device 1 executes each process under the control of the control unit 101. The data input to the key generation device 1 and the data obtained in each process are stored in the memory 102, and the data stored in the memory 102 is read out as necessary and used for other processes. The storage unit 103 is, for example, a main storage device such as a RAM (Random Access Memory), an auxiliary storage device including a semiconductor memory element such as a hard disk, an optical disk, or a flash memory, or a relational database or a key-value store. The middleware can be configured.

With reference to FIG. 3, an example of a functional configuration of the communication device 2 _n (n = 1,..., N) included in the key exchange system A will be described. The communication device 2 _n includes an ad hoc secret key generation unit 20 _n , a pseudo random number generation unit 22 _n , a signature key generation unit 24 _n , a ciphertext generation unit 26 _n , an ad hoc public key generation unit 28 _n , and an ad hoc public key verification unit 30 _n. A secret information generation unit 32 _n , a session key generation unit 34 _n , a control unit 201 _n , a memory 202 _n and a storage unit 203 _n . The communication device 2 _n may further include a long-term secret key generation unit 36 _n . The communication device 2 _n is, for example, a special program configured by reading a special program into a known or dedicated computer having a central processing unit (CPU), a main storage device (Random Access Memory, RAM), and the like. Device. The communication device 2 _n executes each process under the control of the control unit 201 _n . Data obtained by the data and the processing input to the communication device 2 _n is stored in the memory 202 _n, the data stored in the memory 202 _n is read out as necessary be used for other processing. The storage unit 203 _n is, for example, a main storage device such as a RAM (Random Access Memory), an auxiliary storage device configured by a semiconductor memory element such as a hard disk, an optical disk, or a flash memory, or a relational database or key value. It can be configured by middleware such as a store.

[Definition]
Hereinafter, symbols used in the embodiment are defined. Let к be a positive integer security parameter. Let p be a prime number of к bits. G, G _T the bilinear pair each ring function e: the G × G → G _T and efficiently computable group. Let g be a generator of group G and let g _T = e (g, g). _Let Z _p be a remainder ring modulo p. Let L be the maximum depth of the hierarchy in the key exchange system.

_Let (Gen, Sign, Ver) be a one-time-use signature algorithm such that the verification key is an element of the ring Zp. Gen is a signature key generation algorithm for generating a signature key and a verification key. Sign is a signature generation algorithm that generates a single-use signature. Ver is a signature verification algorithm that verifies a single-use signature. In the present invention, any single-use signature algorithm can be applied. For example, “Payman Mohassel,“ One-Time Signatures and Chameleon Hash Functions. ”Selected Areas in Cryptography 2010, pp. 302-319” describes an efficient method for constructing a single-use signature.

F _ke : {0,1} ^* × FS → Z _p ^* , F _gen : {0,1} ^* × FS → RS _gen , F _sig : {0,1} ^* × FS → RS _sig , F _kdf : { 0,1} ^* × FS → {0,1} ^к is a pseudo-random function. Here, FS is a pseudo random function key space, RS _gen is a signature key generation algorithm Gen random space, and RS _sig is a signature generation algorithm Sign random space.

[Public parameters]
With reference to FIG. 4, an operation example of the public parameter generation process and the long-term secret key extraction process executed by the key exchange system A will be described in the order of procedures actually performed.

In step S10, the parameter generation unit 10 included in the key generation device 1 selects the value ^z uniformly and randomly from the ring Z _p ^* , calculates the value g ₁ = g ^z, and calculates the values g ₂ , g ₃ , and g _4. , h ₁ ,..., h _L are uniformly selected from group G. Subsequently, the parameter generation unit 10 displays the public parameters Params = (F _ke , F _gen , F _sig , F _kdf , G, G _T , g, g _T , g ₁ , g ₂ , g ₃ , g ₄ , h ₁ , ... h _L ).

In step S12, the master secret key generation unit 12 included in the key generation device 1 calculates the value g _{2 to} the z-th power to generate a master secret key MSK = g ₂ ^z .

[Key extraction process]
In step S14, the long-term secret key generation unit 14 included in the key generation device 1 performs communication with respect to the communication device 2 _i having identification information ID = (ID ₁ ,..., ID _i ) for i = 1,. Issue a long-term secret key. Specifically, the long-term secret key generation unit 14 first selects a value r uniformly and randomly from the ring Z _p and sets the values w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , and w ₆ to a pseudorandom space. Select randomly from FS. Subsequently, the long-term secret key generation unit 14 uses the identification information ID, the values r, w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ , the master secret key MSK, and the public parameter Params to identify the identification information. A long-term secret key SSK _ID corresponding to ID = (ID ₁ ,..., ID _i ) is generated as follows.

The communication device 2 _m belonging to the upper layer (i-1th layer) may be configured to extract the long-term secret key from the communication device 2 _n belonging to the lower layer (ith layer). In this case, each communication device 2 _n (n = 1,..., N) is configured to include the long-term secret key generation unit 36 _n . For example, the host communication device 2 _m has identification information ID ′ = (ID ₁ ,..., ID _i-1 ), and its long-term secret key is SSK _{ID ′} = (u ₀ , u ₁ , u ₂ , v _i , …, V _L , w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ ). First, the long-term public key generation unit 36 _m included in the communication device 2 _m selects a value r ′ from the ring Z _p uniformly and randomly, and values w ′ ₁ , w ′ ₂ , w ′ ₃ , w ′ ₄ , w Choose ' ₅ , w' ₆ from the pseudorandom space FS uniformly and randomly. Subsequently, the long-term secret key generation unit 36 _m includes the identification information ID ′, the values r ′, w ′ ₁ , w ′ ₂ , w ′ ₃ , w ′ ₄ , w ′ ₅ , w ′ ₆ , the long-term secret key SSK _{ID. 'And the} public parameter Params are used to generate a long-term secret key SSK _ID corresponding to the identification information ID = (ID ₁ ,..., ID _i ) as follows.

Even if the long-term secret key SSK _ID is generated by any method, the generated long-term secret key SSK _ID belongs to the i-th layer having identification information ID = (ID ₁ ,..., ID _i ) secretly. It is conveyed to the communication device 2 _n . The long-term secret key SSK _ID may be transported off-line using a portable storage medium such as a USB memory, or on-line using an encrypted communication path established on the network 9. Also good.

In step S203 _n , the communication device 2 _n stores the long-term secret key SSK _ID input offline or online in the storage unit 203 _n .

[Key exchange process]
An example of a processing flow in which two communication devices included in the key exchange system 1 share a session key will be described with reference to FIGS. Symbols A1 and B1 in FIG. 5 indicate that the processing continues to symbols A1 and B1 in FIG. First, the first half of the processing flow will be described with reference to FIG.

In this example, the communication apparatus 2 _A to which the identification information ID _A = (ID _{A, 1} ,..., ID _{A, α} ) belonging to the α-th layer is assigned, and the identification information ID _B = (ID _B belonging to the β-th layer) _{, 1} ,..., ID _{B, β} ) share a common session key SK with the communication device 2 _B assigned. The communication device 2 _A has a long-term secret key SSK _IDA corresponding to the identification information ID _A = (u _{A, 0} , u _{A, 1} , u _{A, 2} , v _{A, α + 1} ,... V _{A, L} , w _{A, 1, w a, 2, w} a, 3, w a, 4, w a, 5, w a, 6) has a long-term private key communication device 2 _B corresponds to the identification information ID _B SSK _IDB = (u _{B, 0} , u _{B, 1} , u _{B, 2} , v _{B, β + 1} , ... v _{B, L} , w _{B, 1} , w _{B, 2} , w _{B, 3} , w _{B, 4} , w _{B, 5} , w _{B, 6} ).

In step S20 _A, the ad hoc private key generating section 20 _A included in the communication device 2 _A, the value from the pseudo-random number space _{FS esk A, ke, esk '} A, ke, esk A, gen, esk' A, gen, esk _{A, sig} , esk ' _{A, sig} are selected at random, and the ad hoc secret key ESK _A = (esk _{A, ke} , esk' _{A, ke} , esk _{A, gen} , esk ' _{A, gen} , esk _{A, sig} , esk ' _{A, sig} ).

In step S22 _A, the pseudo-random number generation unit 22 _A included in the communication device 2 _A uses the public parameters Params ad hoc secret key ESK _A, the following equation, the pseudo-random number s _A, the pseudo-random number rand _{A, gen} and pseudo Random numbers rand _{A, sig} are calculated.

In step S24 _A, the signature key generation unit 24 _A included in the communication device 2 _A is the following equation to perform the signature key generation algorithm Gen pseudorandom number rand _A, the _gen as input signing key of the signature Single Use sk _A And a verification key vk _A is generated.

In step S261 _A, ciphertext generating unit 26 _A included in the communication device 2 _A uses the generator g and the pseudo-random number s _A group G, the following equation, to generate a ciphertext C _{A, 1.}

In step S262 _A, the ciphertext generator 26 _A, the identification information ID = communication device 2 _B is a key exchange partner _{(ID B, 1, ...,} ID B, β), the pseudo-random number s _A, verification key vk _A The ciphertext C _{A, 2} is generated by the following equation using the public parameter Params.

In step S281 _A, the ad hoc public key generation unit 28 _A included in the communication device 2 _A is the following equation, the ciphertext C _{A, 1} and the ciphertext C _{A, 2} pseudorandom number rand _A as _{input, sig} and signature key _A signature generation algorithm Sign is executed using sk _A to generate a signature σ _A for a single-use signature.

In step S282 _A, the ad hoc public key generation unit 28 _A includes the ciphertext C _{A, 1,} ciphertext C _{A, 2,} by using the signature sigma _A and the verification key vk _A, the ad hoc public key EPK _A = (C _{A, 1} , C _{A, 2} , σ _A , vk _A ). Then, the ad hoc public key EPK _A, and transmits to the communication device 2 _B as a set of identification information ID _B of the identification information ID _A and the communication device 2 _B of the communication device 2 _A.

In step S20 _B , the ad hoc secret key generation unit 20 _B included in the communication device 2 _B , like the ad hoc secret key generation unit 20 _A , uses the values esk _{B, ke} , esk ′ _{B, ke} , esk from the pseudorandom space FS. _{B, gen} , esk ' _{B, gen} , esk _{B, sig} , esk' _{B, sig} are chosen randomly and ad hoc secret key ESK _B = (esk _{B, ke} , esk ' _{B, ke} , esk _{B, gen} , esk'B _{, gen} , eskB _{, sig} , esk'B _{, sig} ).

In step S22 _B, pseudo-random number generation unit 22 _B included in the communication device 2 _B, like the pseudo-random number generator 22 _A, using the public parameters Params ad hoc secret key ESK _B, the following equation, the pseudo-random number s _B , pseudorandom numbers rand _{B, gen} and pseudorandom numbers rand _{B, sig} are calculated.

In step S24 _B, the signature key generation unit 24 _B included in the communication device 2 _B, like the signature key generation unit 24 _A, the following equation, executes a signature key generation algorithm Gen pseudorandom number rand _B, the _gen as an input Then, a signature key sk _B and a verification key vk _B for a single use signature are generated.

In step S261 _B , the ciphertext generation unit 26 _B included in the communication device 2 _B uses the generation source g of the group G and the pseudorandom number s _B , as in the ciphertext generation unit 26 _A , to Sentence C _{B, 1} is generated.

In step S262 _B, the ciphertext generating unit 26 _B, as well as the ciphertext generator 26 _A, the identification information ID = communication apparatus 2 _A is a key exchange partner _{(ID A, 1, ...,} ID A, α) Using the pseudo random number s _B , the verification key vk _B, and the public parameter Params, the ciphertext C _{B, 2} is generated by the following equation.

In step S281 _B , the ad hoc public key generation unit 28 _B included in the communication device 2 _B obtains the ciphertext C _{B, 1} and the ciphertext C _{B, 2 according} to the following equation, as with the ad hoc public key generation unit 28 _A. The signature generation algorithm Sign is executed using the pseudo-random numbers rand _{B, sig} and the signature key sk _B as inputs to generate a signature σ _B for a single-use signature.

In step S282 _B , the ad hoc public key generation unit 28 _B uses the ciphertext C _{B, 1} , ciphertext C _{B, 2} , signature σ _B and verification key vk _B in the same manner as the ad hoc public key generation unit 28 _A. , The ad hoc public key EPK _B = (C _{B, 1} , C _{B, 2} , σ _B , vk _B ) is generated. Then, the ad hoc public key EPK _B, and transmits to the communication device 2 _A the identification information ID _A of the identification information ID _B and the communication device 2 _A communication device 2 _B as a set.

  Next, the latter half of the processing flow will be described with reference to FIG.

In step S30 _A, the ad hoc public key EPK _B communication device 2 _A from the communication device 2 _B, when receiving the identification information ID _B and the identification information ID _A, the ad hoc public key verification unit 30 _A included in the communication device 2 _A is The ciphertext C _{B, 1} , ciphertext C _{B, 2} and signature σ _B are input, and the signature verification algorithm Ver is executed using the verification key vk _B to verify whether the following equation holds.

Ad hoc public key verification unit 30 _A, when the Equation does not hold, and stops the session stops processing. If the previous expression is satisfied, the process continues in step S321 _A later.

In step S321 _A, secret information generating unit 32 _A included in the communication device 2 _A uses an ad hoc secret key ESK _A and public parameters Params, by the following equation, to generate a pseudo-random number s _A.

Subsequently, the secret information generation unit 32 _A generates the secret information σ _{A, 1 according} to the following equation using the pseudo random number s _A and the public parameter Params.

In step S322 _A, secret information generation unit 32 _A, using long-term secret key SSK _A, ciphertext C _{B, 1,} the ciphertext C _{B, 2} and the verification key vk _B, the following equation, the secret information sigma _{A, 2} is generated.

In step S323 _A, secret information generating unit 32 _A includes the ciphertext C _{B, 1,} using the pseudo-random number s _A and public parameter Params, by the following equation, to generate the secret information sigma _{A, 3.}

In step S34 _A, the session key generation unit 34 _A included in the communication device 2 _A, first, the identification information ID _A, the identification information ID _B, using an ad hoc public key EPK _A and ad hoc public key EPK _B, session identification information ST = (ID _A , ID _B , EPK _A , EPK _B ) is generated. Subsequently, the session key generation unit 34 _A generates the session key SK by the following equation using the secret information σ _{A, 1} , the secret information σ _{A, 2} , the secret information σ _{A, 3} and the session identification information ST. .

In step S30 _B, the communication device 2 _B ad hoc public key EPK _A from the communication device 2 _A, when receiving the identification information ID _A and the identification information ID _B, the ad hoc public key verification unit 30 _B included in the communication device 2 _B is As with the ad hoc public key verification unit 30 _A , the signature verification algorithm Ver is executed using the verification key vk _A with the ciphertext C _{A, 1} , the ciphertext C _{A, 2} and the signature σ _A as input, and the following equation is established: Verify whether or not.

If the previous equation does not hold, the ad hoc public key verification unit 30 _B interrupts the process and stops the session. If the previous expression is satisfied, the process continues in step S321 and subsequent _B.

In step S321 _B , the secret information generation unit 32 _B included in the communication device 2 _B uses the ad hoc secret key ESK _B and the public parameter Params, similarly to the secret information generation unit 32 _A , to calculate a pseudo random number s Generate _B.

Subsequently, the secret information generation unit 32 _B uses the long-term secret key SSK _B , the ciphertext C _{A, 1} , the ciphertext C _{A, 2} and the verification key vk _A to obtain the secret information σ _{B, 1 according} to the following equation: Generate.

In step S322 _B, the secret information generating unit 32 _B, using the pseudo-random number s _B and public parameter Params, by the following equation, to generate the secret information sigma _{B, 2.}

In step S323 _B, the secret information generating unit 32 _B, as well as the secret information generating unit 32 _A, the ciphertext C _{A, 1,} using the pseudo-random number s _B and public parameter Params, by the following equation, the secret information sigma _{B , 3} is generated.

In step S34 _B, a session key generation unit 34 _B included in the communication device 2 _B, like the session key generation unit 34 _A, the identification information ID _A, the identification information ID _B, the ad hoc public key EPK _A and ad hoc public key EPK with _B, session identification information _{ST = (ID a, ID B} , EPK a, EPK B) to produce a. Subsequently, the session key generation unit 34 _B uses the secret information σ _{B, 1} , the secret information σ _{B, 2} , the secret information σ _{B, 3} and the session identification information ST to generate a session key SK according to the following equation: .

Secret sigma _{A, 1} to calculate the secret information generating unit 32 _{A, σ A, 2,} secret information to calculate the sigma _{A, 3} and secret information generating unit _{32 B σ B, 1, σ} B, 2, σ B, _{Since 3} is equal to each other, the communication device 2A and the communication device 2B can obtain the same session key SK.

The following shows that the secret information σ _{A, 1} is equal to the secret information σ _{B, 1} .

It is shown below that the secret information σ _{A, 2} is equal to the secret information σ _{B, 2} .

It is shown below that the secret information σ _{A, 3} and the secret information σ _{B, 3} are equal.

  In the key exchange system 1 of the embodiment, the session key generation unit 34 generates a session key SK using a pseudo random function and a strong random extractor. As a result, a safe method is realized without assuming a random oracle as in the prior art described in Non-Patent Document 1.

  In the key exchange system 1 of the embodiment, the length of the ad hoc public key EPK does not depend on the depth of the hierarchy. The pairing calculation calculated by the secret information generation unit 32 is fixed to a total of four times regardless of the depth of the hierarchy. Thus, since the communication amount and the number of pairing calculations do not depend on the hierarchy depth as in the prior art described in Non-Patent Document 1, the expandability is high.

[Program, recording medium]
The present invention is not limited to the above-described embodiment, and it goes without saying that modifications can be made as appropriate without departing from the spirit of the present invention. The various processes described in the above-described embodiments are not only executed in time series according to the order described, but may be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes.

  When various processing functions in each device described in the above embodiment are realized by a computer, the processing contents of the functions that each device should have are described by a program. Then, by executing this program on a computer, various processing functions in each of the above devices are realized on the computer.

  The program describing the processing contents can be recorded on a computer-readable recording medium. As the computer-readable recording medium, for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.

  The program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

  A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, the computer reads a program stored in its own recording medium and executes a process according to the read program. As another execution form of the program, the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).

  In this embodiment, the present apparatus is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.

A Key exchange system 1 Key generation device 2 Communication device 9 Network 10 Parameter generation unit 12 Master secret key generation unit 14 Long-term secret key generation unit 20 Ad hoc secret key generation unit 22 Pseudo random number generation unit 24 Signature key generation unit 26 Ciphertext generation unit 28 Ad hoc public key generation unit 30 Ad hoc public key verification unit 32 Secret information generation unit 34 Session key generation unit 36 Long-term secret key generation unit

Claims (6)

A key exchange system including a key generation device and a plurality of communication devices layered in an L hierarchy,
^ Represents power, • represents multiplication, Z _p is a residue ring modulo prime p, and G and G _T can efficiently calculate the bilinear pairing function e: G × G → G _T Group, g is a generator of group G, F _ke , F _gen , F _sig and F _kdf are pseudo-random functions, FS is a pseudo-random function key space, Gen is a signature key of any one-time signature scheme As a generation algorithm, Sign is a signature generation algorithm of the above-mentioned single-use signature method, Ver is a signature verification algorithm of the above-mentioned single-use signature method,
The key generation device
A parameter generator that selects the value z from the ring Z _p , calculates the value g ₁ = g ^z , and selects the values g ₂ , g ₃ , g ₄ , h ₁ ,..., H _L from the group G;
A master secret key generator for calculating the master secret key MSK = g ₂ ^z ;
The long-term secret key SSK _i of the communication device belonging to the i-th layer is selected from the ring Z _p as the value r, and the values w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ are selected from the key space FS. U ₀ = MSK · (h ₁ ^ ID ₁ … h _i ^ ID _i · g ₃ ) ^r , u ₁ = g ^r , u ₂ = g ₄ ^r and SSK _i = (u ₀ , u ₁ , u ₂ , h _{i + 1} ^r , ..., h _L ^r , w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ ),
Including
The communication device is
The identification information ID = (ID ₁ ,..., ID _α ) belonging to the α hierarchy and the identification information ID ′ = (ID ′ ₁ ,..., ID ′ _β ) belonging to the β hierarchy are set above As sharing session key SK with communication device,
An ad hoc secret key generation unit for selecting values esk _ke , esk ' _ke , esk _gen , esk' _gen , esk _sig , esk ' _sig from the key space FS;
The pseudorandom function s is generated by calculating the exclusive OR of the output of the pseudorandom function F _ke (w ₁ , esk _ke ) and the output of the pseudorandom function F _ke (esk ' _ke , w ₂ ), and Calculate the exclusive OR of the output of the pseudo-random function F _gen (w ₃ , esk _gen ) and the output of the pseudo-random function F _gen (esk ' _gen , w ₄ ) to generate the pseudo-random rand _gen Pseudorandom number that generates a pseudorandom number rand _sig by calculating the exclusive OR of the output of the pseudorandom function F _sig (w ₅ , esk _sig ) and the output of the pseudorandom function F _sig (esk ' _sig , w ₆ ) A generator,
Executing the key generation algorithm Gen using the pseudorandom number rand _gen, and generating a signature key sk and a verification key vk;
To generate a cipher text C ₁ to calculate the power of s of the value g, generates a ciphertext C ₂ to calculate the _{(h 1 ^ ID '1 ...} h β ^ ID' β · g 4 vk · g 3) s A ciphertext generator to
The ciphertext C ₁ and the ciphertext C ₂ are input to execute the signature algorithm Sign using the pseudo random number rand _sig and the signature key sk to generate a signature σ, and the ciphertext C ₁ and the ciphertext C ₂ , an ad hoc public key generation unit that generates an ad hoc public key EPK including a signature σ and a verification key vk;
When receiving the ad hoc public key EPK ′ including the ciphertext C ′ ₁ , the ciphertext C ′ ₂ , the signature σ ′ and the verification key vk ′ from the communication device in which the identification information ID ′ is set, the ciphertext C ′ ₁ , An ad hoc public key verification unit that executes the verification algorithm Ver using the verification key vk ′ as an input with the ciphertext C ′ ₂ and the signature σ ′, and verifies the ad hoc public key EPK ′;
e (g ₁ , g ₂ ) ^s is calculated to generate secret information σ ₁ , and e (C ′ ₁ , u ₀・ u ₂ ^{vk ′} ) / e (C ′ ₂ , u ₁ ) is calculated to obtain the secret A secret information generation unit that generates information σ ₂ and calculates e (C ′ ₁ , g ₃ ) ^s to generate secret information σ ₃ ;
Based on the identification information ID, the identification information ID ′, the ad hoc public key EPK and the ad hoc public key EPK ′, the session identification information ST is generated, and the pseudo-random function F having the secret information σ ₁ and the session identification information ST as inputs is input. receiving the output and the secret information sigma ₂ and the session identification information ST of _kdf of the pseudo-random function F _kdf which receives the pseudo-random function F _kdf output and the secret information sigma ₃ and the session identification information ST A session key generation unit that calculates an exclusive OR with the output and generates the session key SK;
Including key exchange system. The key exchange system according to claim 1,
The communication device is
Given the long-term secret key SSK = (u ₀ , u ₁ , u ₂ , v _i , ..., v _L , w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ ), the value r ′ Z _{p is} selected, values w ′ ₁ , w ′ ₂ , w ′ ₃ , w ′ ₄ , w ′ ₅ , w ′ ₆ are selected from the key space FS, and a long-term secret key SSK ′ is generated by the following equation: A long-term secret key generation unit;

Further including a key exchange system. ^ Represents power, • represents multiplication, Z _p is a residue ring modulo prime p, and G and G _T can efficiently calculate the bilinear pairing function e: G × G → G _T A group, g is a generator of group G, FS is a key space of a pseudo-random function,
A parameter generator that selects the value z from the ring Z _p , calculates the value g ₁ = g ^z , and selects the values g ₂ , g ₃ , g ₄ , h ₁ ,..., H _L from the group G;
A master secret key generator for calculating the master secret key MSK = g ₂ ^z ;
The long-term secret key SSK _i of the communication device belonging to the i-th layer is selected from the ring Z _p as the value r, and the values w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ are selected from the key space FS. U ₀ = MSK · (h ₁ ^ ID ₁ … h _i ^ ID _i · g ₃ ) ^r , u ₁ = g ^r , u ₂ = g ₄ ^r and SSK _i = (u ₀ , u ₁ , u ₂ , h _{i + 1} ^r , ..., h _L ^r , w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ ),
Key generation device including In a plurality of communication devices hierarchized in the L layer, the identification information ID = (ID ₁ ,..., ID _α ) belonging to the α layer is set, and the identification information ID ′ = (ID ′) belonging to the β layer ₁ ,..., ID ′ _β ) and a communication device sharing a session key SK with the communication device,
^ Represents power, • represents multiplication, Z _p is a residue ring modulo prime p, and G and G _T can efficiently calculate the bilinear pairing function e: G × G → G _T Group, g is a generator of group G, F _ke , F _gen , F _sig and F _kdf are pseudo-random functions, FS is a pseudo-random function key space, Gen is a signature key of any one-time signature scheme As a generation algorithm, Sign is a signature generation algorithm of the above-mentioned single-use signature method, Ver is a signature verification algorithm of the above-mentioned single-use signature method,
The value z is a random number selected from the ring Z _p , the value g ₁ = g ^z , and the values g ₂ , g ₃ , g ₄ , h ₁ ,…, h _L are the random numbers selected from the group G , The master secret key MSK = g ₂ ^z , the value r is a random number selected from the ring Z _p , and the values w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ are from the key space FS The long-term secret key SSK _i of the communication device belonging to the i-th layer that is the selected random number is u ₀ = MSK · (h ₁ ^ ID ₁ … h _i ^ ID _i · g ₃ ) ^r , u ₁ = g ^r , U ₂ = g ₄ ^r and SSK _i = (u ₀ , u ₁ , u ₂ , h _{i + 1} ^r ,…, h _L ^r , w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ ) And
An ad hoc secret key generation unit for selecting values esk _ke , esk ' _ke , esk _gen , esk' _gen , esk _sig , esk ' _sig from the key space FS;
The pseudorandom function s is generated by calculating the exclusive OR of the output of the pseudorandom function F _ke (w ₁ , esk _ke ) and the output of the pseudorandom function F _ke (esk ' _ke , w ₂ ), and Calculate the exclusive OR of the output of the pseudo-random function F _gen (w ₃ , esk _gen ) and the output of the pseudo-random function F _gen (esk ' _gen , w ₄ ) to generate the pseudo-random rand _gen Pseudorandom number that generates a pseudorandom number rand _sig by calculating the exclusive OR of the output of the pseudorandom function F _sig (w ₅ , esk _sig ) and the output of the pseudorandom function F _sig (esk ' _sig , w ₆ ) A generator,
Executing the key generation algorithm Gen using the pseudorandom number rand _gen, and generating a signature key sk and a verification key vk;
To generate a cipher text C ₁ to calculate the power of s of the value g, generates a ciphertext C ₂ to calculate the _{(h 1 ^ ID '1 ...} h β ^ ID' β · g 4 vk · g 3) s A ciphertext generator to
The ciphertext C ₁ and the ciphertext C ₂ are input to execute the signature algorithm Sign using the pseudo random number rand _sig and the signature key sk to generate a signature σ, and the ciphertext C ₁ and the ciphertext C ₂ , an ad hoc public key generation unit that generates an ad hoc public key EPK including the signature σ and the verification key vk;
When receiving the ad hoc public key EPK ′ including the ciphertext C ′ ₁ , the ciphertext C ′ ₂ , the signature σ ′ and the verification key vk ′ from the communication device in which the identification information ID ′ is set, the ciphertext C ′ ₁ , An ad hoc public key verification unit that executes the verification algorithm Ver using the verification key vk ′ as an input with the ciphertext C ′ ₂ and the signature σ ′, and verifies the ad hoc public key EPK ′;
e (g ₁ , g ₂ ) ^s is calculated to generate secret information σ ₁ , and e (C ′ ₁ , u ₀・ u ₂ ^{vk ′} ) / e (C ′ ₂ , u ₁ ) is calculated to obtain the secret A secret information generation unit that generates information σ ₂ and calculates e (C ′ ₁ , g ₃ ) ^s to generate secret information σ ₃ ;
Based on the identification information ID, the identification information ID ′, the ad hoc public key EPK and the ad hoc public key EPK ′, the session identification information ST is generated, and the pseudo-random function F having the secret information σ ₁ and the session identification information ST as inputs is input. receiving the output and the secret information sigma ₂ and the session identification information ST of _kdf of the pseudo-random function F _kdf which receives the pseudo-random function F _kdf output and the secret information sigma ₃ and the session identification information ST A session key generation unit that calculates an exclusive OR with the output and generates the session key SK;
Including a communication device. In the plurality of communication devices hierarchized in the L layer, the communication device belonging to the α layer and the identification information ID = (ID ₁ ,..., ID _α ) and the identification information ID ′ = A key exchange method in which (ID ′ ₁ ,..., ID ′ _β ) is set and the communication device shares a session key SK,
^ Represents power, • represents multiplication, Z _p is a residue ring modulo prime p, and G and G _T can efficiently calculate the bilinear pairing function e: G × G → G _T Group, g is a generator of group G, F _ke , F _gen , F _sig and F _kdf are pseudo-random functions, FS is a pseudo-random function key space, Gen is a signature key of any one-time signature scheme As a generation algorithm, Sign is a signature generation algorithm of the above-mentioned single-use signature method, Ver is a signature verification algorithm of the above-mentioned single-use signature method,
The parameter generator selects a value z from the ring Z _p , calculates a value g ₁ = g ^z, and generates a parameter for selecting the values g ₂ , g ₃ , g ₄ , h ₁ ,..., H _L from the group G Steps,
A master secret key generation step in which a master secret key generation unit calculates a master secret key MSK = g ₂ ^z ;
The long-term secret key generation unit selects the long-term secret key SSK _i of the communication device belonging to the i-th layer from the ring Z _p as the value r, and the values w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ Is selected from the above key space FS and u ₀ = MSK · (h ₁ ^ ID ₁ … h _i ^ ID _i · g ₃ ) ^r , u ₁ = g ^r , u ₂ = g ₄ ^r is calculated, and SSK _i = (MSK · (h ₁ ^ ID ₁ … h _i ^ ID _i · g ₃ ) ^r , g ^r , g ₄ ^r , h _{i + 1} ^r ,…, h _L ^r , w ₁ , w ₂ , w ₃ , w ₄ , w ₅ , w ₆ ) and a long-term secret key generation step,
An ad hoc secret key generation unit that selects values esk _ke , esk ' _ke , esk _gen , esk' _gen , esk _sig , and esk ' _sig from the key space FS;
The pseudo-random number generator calculates the exclusive OR of the output of the pseudo-random function F _ke (w ₁ , esk _ke ) and the output of the pseudo-random function F _ke (esk ' _ke , w ₂ ). s is generated, and an exclusive OR of the output of the pseudo random function F _gen (w ₃ , esk _gen ) and the output of the pseudo random function F _gen (esk ' _gen , w ₄ ) is calculated, and the pseudo random number rand Generate _gen , calculate the exclusive OR of the output of the pseudorandom function F _sig (w ₅ , esk _sig ) and the output of the pseudorandom function F _sig (esk ' _sig , w ₆ ) a pseudo-random number generation step for generating _sig ;
A signature key generation unit that executes the key generation algorithm Gen using the pseudo-random number rand _gen and generates a signature key sk and a verification key vk;
The ciphertext generation unit calculates ciphertext C ₁ by calculating the value g of the value g and calculates (h ₁ ^ ID ' ₁ … h _β ^ ID' _β · g ₄ ^vk · g ₃ ) ^s a ciphertext generating step of generating a ciphertext C _2,
Ad hoc public key generating unit, by using the pseudo random number rand _sig and the signature key sk to generate the signature σ by performing the signature algorithm Sign the ciphertext C ₁ and the ciphertext C ₂ as an input, the encryption An ad hoc public key generation unit that generates an ad hoc public key EPK including a sentence C ₁ , the cipher text C ₂ , the signature σ, and the verification key vk;
When the ad hoc public key verification unit receives the ad hoc public key EPK ′ including the ciphertext C ′ ₁ , the ciphertext C ′ ₂ , the signature σ ′, and the verification key vk ′ from the communication device in which the identification information ID ′ is set, Ad hoc public key verification for verifying the ad hoc public key EPK ′ by executing the verification algorithm Ver using the verification key vk ′ with the cipher text C ′ ₁ , the cipher text C ′ ₂ and the signature σ ′ as inputs. Steps,
The secret information generation unit calculates e (g ₁ , g ₂ ) ^s to generate secret information σ ₁ , and e (C ′ ₁ , u ₀ · u ₂ ^{vk ′} ) / e (C ′ ₂ , u ₁ ) To generate secret information σ ₂ , and e (C ′ ₁ , g ₃ ) ^s to generate secret information σ ₃ ,
The session key generation unit generates session identification information ST based on the identification information ID, identification information ID ′, ad hoc public key EPK and ad hoc public key EPK ′, and inputs the secret information σ ₁ and the session identification information ST. The output of the pseudo-random function F _kdf to which the secret information σ ₂ and the session identification information ST are input and the output of the pseudo-random function F _kdf , the secret information σ ₃ and the session identification information ST to be input A session key generation step of calculating an exclusive OR with the output of the pseudo-random function F _kdf and generating the session key SK;
Key exchange method including   A program for causing a computer to function as the key generation device according to claim 3 or the communication device according to claim 4.

Images