JP2019125956A - Key exchange method, key exchange system, key exchange server device, communication device, and program - Google Patents

Abstract

To provide a key exchange technique which cannot acquire an encryption key even when a long-term secret key leaks.SOLUTION: A key exchange method includes: an authentication key generation step in which a key exchange server device generates an authentication key of a communication device; an authentication key reception step in which the communication device acquires the authentication key; a first key generation step in which the communication device generates R; a session ID generation step in which the key exchange server device transmits (sid, R, R) to the communication device; a second key generation step in which the communication device generates a second key from sid, R, R; a first common key generation step in which the key exchange server device generates T'using the second key and generates a first common key; an authentication key update step in which the key exchange server device generates a new authentication key from the authentication key using a key derivation function; a session key generation step in which the communication device generates a second common key and a session key using the first common key; and an authentication key update step in which the communication device generates a new authentication key from the authentication key using the key derivation function.SELECTED DRAWING: Figure 6

Description

  The present invention relates to the application of information security technology, and more particularly to key exchange technology in which a plurality of communication devices forming a group share an encryption key.

  Currently, some chat applications end-to-end encrypt their communication content. End-to-end encryption allows the user to chat with the chat application server without knowing the communication content.

  In a group chat in which a large number of users participate, there are cases where a participating communication device changes dynamically, such as a communication device newly joining the group or an existing communication device leaving the group. Even in such a case, the Dynamic Multi-Cast Key Distribution (DMKD) protocol is used as a protocol that can efficiently exchange keys used for end-to-end encryption (hereinafter referred to as encryption keys). ) Exists. As a representative DMKD protocol, there is one called Y16 protocol (Non-Patent Document 1).

The DMKD protocol has the following features.
(1) The network configuration is a star type centering on the key exchange server device.
(2) The key exchange system comprises a key exchange server device and a communication device. The key exchange server device and the communication device respectively hold a secret key (hereinafter referred to as long-term secret key) used for long-term key exchange and a secret key (hereinafter referred to as short-term secret key) used only for one key exchange. . As a result of key exchange, the communication device can acquire the encryption key, but the key exchange server can not acquire the encryption key.
(3) The DMKD protocol has three basic phases {Dist, Join, Leave}. Performing these phases is called a session. In the Dist (key distribution) phase, a new group is generated, and exchange of encryption keys is performed between communication devices participating in the group. In the Join phase, a new communication device is added to the existing group, and key exchange is performed in the group. In the Leave phase, the communication devices that have joined from the existing group leave, and key exchange is performed in the group.
(4) In the DMKD protocol, a predetermined period called a time frame (TF) is defined, and when the predetermined period elapses and it changes to the next time frame TF, key exchange is performed again in the group. The phase for updating this encryption key is called the update phase.

K. Yoneyama, R. Yoshida, Y. Kawahara, T. Kobayashi, H. Fuji, and T. Yamamoto, “Multi-cast Key Distribution: Scalable, Dynamic and Reliable Secure Construction”, Proc. Of ProvSec 2016, Nanjing, China , pp. 207-226, Nov. 2016.

  There is still a risk that the secret key may be leaked, such as information leakage due to unauthorized access to the key exchange server device, and information leakage due to malware infection of the communication device. In the DMKD protocol, the key exchange server device and the communication device need to securely hold the long-term secret key, but since the holding period is long, the long-term secret key may be leaked due to the above-mentioned risk.

  For the leak of the secret key, it is possible to take measures to invalidate the key and reissue a new key. However, in the case of unauthorized access or malware infection, the server administrator or the user may not be aware that the secret key is leaked, and the secret key may be leaked for a long time. Therefore, even if the private key is leaked, it is important that the security of communication between the communication devices be ensured.

  In the DMKD protocol, the key exchange server apparatus and the communication apparatus share a key (hereinafter referred to as an authentication key) necessary for user authentication and server authentication at the time of key exchange, using the long-term secret key held by itself. When the attacker obtains this authentication key, the attacker can impersonate a valid user and participate in key exchange. Therefore, when the long-term secret key is obtained by the attacker, the attacker can obtain the authentication key, and can participate in key exchange using the authentication key and can obtain the encryption key. Once the encryption key is obtained, for example, the encrypted chat contents in the chat application are known to the attacker.

  Hereinafter, an attack by the Y16 protocol will be described as a specific example. In the Y16 protocol, whenever the time frame TF changes, the key exchange server device is a kind of public key encryption, and the user's attribute secret key (key generated from the long-term secret key of the key exchange server device) in the attribute-based encryption algorithm The MAC key in the message authentication coder algorithm is generated, and the attribute secret key and the MAC key are encrypted and transmitted to the communication device using the public key in the public key encryption algorithm of the communication device. In the Y16 protocol, the attribute private key of the user and the MAC key correspond to the authentication key.

  The communication device having received the encrypted attribute secret key and the MAC key acquires the attribute secret key and the MAC key using the secret key in the public key encryption algorithm (a key corresponding to the long-term secret key of the communication device), Information required to generate an encryption key is acquired, or an authentication tag is added to information to be transmitted to the key exchange server apparatus.

  The key exchange server device authenticates the communication device by the authentication tag. Therefore, if the attacker can obtain the MAC key if the long-term secret key of the communication device is acquired, the attacker can spoof the legitimate user and participate in the key exchange. As a result, the attacker can obtain the encryption key and can view the encrypted chat contents.

  On the other hand, the communication device authenticates the key exchange server device based on whether or not the correct attribute private key can be generated. Therefore, if the long-term secret key of the key exchange server device is acquired by the attacker, the attribute private key of the user can be created, so that the attacker can impersonate the key exchange server device. Although the key exchange server can not directly know the encryption key to be exchanged, the key exchange server can determine the communication device to join the group, so the communication device used by the attacker joins the group be able to. As a result, the attacker can know the encryption key and can view the encrypted chat contents.

  Therefore, an object of the present invention is to provide a key exchange technology which can not acquire an encryption key even if a long-term secret key is leaked.

  In one aspect of the present invention, n is an integer of 2 or more, and α and β are values defined by the following formula,

A key exchange method performed by a key exchange system including a key exchange server apparatus S and n communication apparatuses U _i (i = 1,..., N), wherein U ₁ is the communication apparatus U _{1 ,.} The representative unit selected from among the above, where time _o is the current time, ID is a predicate variable representing the communication device, TF _m is a predicate variable representing a time frame, and the recording unit of the key exchange server apparatus S A secret key SSK _s = (msk, st _S , st ' _S ) (where, msk is a master secret key of attribute-based encryption, st _S and st' _S are secret strings respectively), and the communication device U _i is recorded (i = 1, ..., n ) to the recording portion of the long-term secret key _{SSK i = (sk i, st} i, st 'i) ( provided that, sk _i is the private key of the public key encryption of the communication device U _i , St _i , st ′ _i are each a secret string), and the key exchange server apparatus S has an attribute as _{i i} = (U _i , time _o ) for i = 1,. Key Derivation Algorithm of Base Cipher Accordingly, the public parameter Params attribute-based encryption using the master secret key msk, generates attribute secret key usk _i of the communication device U _i, by the key generation algorithm of the message authentication codes, said communication device U _i MAC generates key mk _i ⁰ as the authentication key, the encryption algorithm of the public key encryption, the long-term public key SPK _i = pk _i of the communication device U _i (however, pk _i is the public key encryption of the communication device U _i public key) by using the attribute secret key usk _i and the authentication key mk _i ⁰ encrypting to generate a ciphertext CT _i, the ciphertext CT _i said communication device U _i (i∈ {1, ... , an authentication key generating step of transmitting to the n}), the communication device _{U i (i = 1, ...} , n) is the decoding algorithm of the public key encryption using the secret key sk _i, the ciphertext CT decoding the _i, and authentication key receiving step of acquiring the authentication key mk _i ⁰ and the attribute secret key usk _i, the communication device U _{i (i = 1, ...,} n) is the a twisted pseudo-random function secret string st _i, using a st _'i generates _{r i, k i, s i} , = g r_i and first key R _i c _i = generates g ^k_i h ^s_i, by the tag generation algorithm message authentication codes, by using the authentication key mk _i ^0, wherein R _i, to generate an authentication tag t _i ¹ from c _i, (R _i, a first key generation step of transmitting c _i , t _i ¹ ) to the key exchange server apparatus S, and the key exchange server apparatus S, for i = 1,. A first key receiving step of verifying the authentication tag t _i ¹ using the authentication key mk _i ⁰ and the R _i and c _i ; and the key exchange server apparatus S performs the c ₁ , ..., c _n is used to generate a session ID sid, and for i = 1,..., N, the tag generation algorithm of the message authenticator uses the authentication key mk _i ⁰ to execute the s The authentication tag t _i ² is generated from id, R _α , R _β , and (sid, R _α , R _β , t _i ² ) is transmitted to the communication device U _i (iε {1,..., n}) In the session ID generation step, the communication device U _i (iε {2,..., N}) uses the authentication key mk _i ⁰ and the sid, R _α , R _{β according} to a message authentication code verification algorithm. The authentication tag t _i ² is verified, and when the authentication tag t _i ² is valid, a pseudo random function generates K _i ^l using the sid, R _α ^r_i , and the pseudo random function sid, It generates a K _i ^r with R _beta ^r_i, wherein generating the K _i ^l and the K _i second key T _i by exclusive OR of ^r, the representative communication device U ₁ is a message authentication code the verification algorithm, the said authentication key mk ₁ ⁰ sid, R _n, with R _2, wherein to verify the authentication tag t ₁ ^2, if the authentication tag t ₁ ² is valid, the by a pseudo random function sid, a R _n ^r_1 using Generates K ₁ ^l, wherein the pseudo-random function sid, with R ₂ ^r_1 generates K ₁ ^r, generating a second key T ₁ by exclusive OR of the said K ₁ ^l K ₁ ^r And a second key generation step of generating T ′ by exclusive OR of K ₁ ^l and k ₁ || s ₁ and the communication device U _i (iε {2,..., N}), According to the tag generation algorithm of the message authenticator, using the authentication key mk _i ⁰ , the authentication tag t _i from the R _i , c _i , R _α , R _β , k _i , s _i , T _i , U _i , sid ³ and transmit (k _i , s _i , T _i , t _i ³ ) to the key exchange server apparatus S, and the representative communication apparatus U ₁ uses the message authentication code generation algorithm to generate the authentication key An authentication tag t ₁ ³ is generated from the R ₁ , c ₁ , R _n , R ₂ , T ₁ , T ₁ , U ₁ , sid using mk ₁ ⁰ (T ₁ , T ′, t ₁ ³ ), And the key exchange server device S transmits the key to the key exchange server device S, i = 2,. There, by verification algorithm of the message authentication code, wherein said authentication key ^{_{mk i 0 R i, c i}} , R α, R β, k i, s i, T i, U i, using sid, the authentication tag verifies t _i ^3, for i = 1, the verification algorithm of the message authentication codes, the said authentication key ^{_{mk 1 0 R 1, c 1}} , R n, R 2, T 1, T ', U 1, sid using a second key reception step of verifying the authentication tag t ₁ ^3, wherein the key exchange server device S is, by twisting the pseudo random function, the secret string st _S, st 'with _S, k _S, A first common key K ₁ is generated, and k ′ is generated by the exclusive OR of the k ₂ ,..., K _n , k _s , and T ₁ ,. the exclusive OR of _i-1, to generate a _{T 'i, i = 1,} ..., for n, the condition _{P i = (ID = U i} ) ∧ (time o ∈TF m), attribute-based encryption According to the encryption algorithm, using the public parameter Params, Encrypts the common key K _1, and the first common key generation step of generating a ciphertext CT _'i, said key exchange server device S is, i = 2, ..., for n, by the tag generation algorithm message authentication code Using the authentication key mk _i ⁰ , the R _i , c _i , R _α , R _β , k _i , s _i , T _i , U _i , sid, c ₁ , k ′, T ′ _i , T ′ , CT ′ _i generates an authentication tag t _i ⁴ and transmits (c ₁ , k ′, T ′ _i , T ′, CT ′ _i , t _i ⁴ ) to the communication device U _i , for i = 1 , by the tag generation algorithm message authentication codes, by using the authentication key mk ₁ ^0, wherein _{R 1, c 1, R n} , R 2, T 1, T ', U 1, sid, k', CT '1 generates an authentication tag t ₁ ⁴ _{from, (k ', CT' 1} , t 1 4) and the first common key transmitting step of transmitting to the representative communication device U _1, the authentication key update information mu _i (i = 1 , N) are assumed to be information already shared between the key exchange server apparatus S and the communication apparatus U _i , and the key exchange server apparatus S has i = 1,. an authentication key updating step of generating a new authentication key mk _i ¹ from the authentication key mk _i ⁰ and the authentication key update information μ _i or the authentication key mk _i ⁰ by a key derivation function for n U _i (iε {2,..., N}) uses the verification algorithm of the message authenticator to determine the authentication key mk _i ⁰ and the authentication keys mk _i ⁰ , R _i , c _i , R _α , R _β , k _i , s _i , T _{If the} authentication tag t _i ⁴ is verified using _i , U _i , sid, c ₁ , k ′, T ′ _i , T ′, CT ′ _i and the authentication tag t _i ⁴ is valid, 'generates K ₁ ^l by exclusive OR of the K _i ^l a _i, wherein T' T generates k ₁ || s ₁ by exclusive OR of the K ₁ ^l and, attribute-based encryption the decoding algorithm, using the attribute secret key usk _i, decrypts the first common key K ₁ from the ciphertext CT _'i, the representative communication device U ₁ is the verification algorithm of message authentication codes, the authentication the key ^{_{mk 1 0 R 1, c 1}} , R n, R ₂ , T ₁ , T ′, U ₁ , sid, k ′, CT ′ ₁ are used to verify the authentication tag t ₁ ⁴ , and when the authentication tag t _i ⁴ is valid, decryption of the attribute-based encryption algorithm, by using the attribute secret key usk _i, a first common key receiving step of decoding the first common key K ₁ from the ciphertext CT _'1, the communication device _{U i (i∈ {1, ...} , n}) generates a second common key K ₂ from a value generated using the session ID sid and the exclusive OR of the k ′ and the k ₁ by the pseudo random function, and the pseudo random function generates the second common key K ₂ a session key generating step of generating a session key SK by an exclusive OR of a value generated using sid, K ₁ and a value generated using sid, K _{2 according} to a pseudo random function, and the communication device U _i (I ∈ {1,..., N}) is the key derivation function, the authentication key mk _i ⁰ and the authentication key update information μ _i , or the authentication key mk _i ⁰ And an authentication key updating step of generating a new authentication key mk _i ¹ from.

  In one aspect of the present invention, n is an integer of 2 or more, and α and β are values defined by the following formula,

A key exchange method performed by a key exchange system including a key exchange server apparatus S and n communication apparatuses U _i (i = 1,..., N), wherein U ₁ is the communication apparatus U _{1 ,.} The representative unit selected from among the above, where time _o is the current time, ID is a predicate variable representing the communication device, TF _m is a predicate variable representing a time frame, and the recording unit of the key exchange server apparatus S A secret key SSK _s = (msk, st _S , st ' _S ) (where, msk is a master secret key of attribute-based encryption, st _S and st' _S are secret strings respectively), and the communication device U _i is recorded (i = 1, ..., n ) to the recording portion of the long-term secret key _{SSK i = (sk i, st} i, st 'i) ( provided that, sk _i is the private key of the public key encryption of the communication device U _i , St _i , st ′ _i are each a secret string), and the key exchange server apparatus S has an attribute as _{i i} = (U _i , time _o ) for i = 1,. Key Derivation Algorithm of Base Cipher Accordingly, the public parameter Params attribute-based encryption using the master secret key msk, generates attribute secret key usk _i of the communication device U _i, by the key generation algorithm of the message authentication codes, said communication device U _i MAC generates key mk _i ⁰ as the authentication key, the encryption algorithm of the public key encryption, the long-term public key SPK _i = pk _i of the communication device U _i (however, pk _i is the public key encryption of the communication device U _i public key) by using the attribute secret key usk _i and the authentication key mk _i ⁰ encrypting to generate a ciphertext CT _i, the ciphertext CT _i said communication device U _i (i∈ {1, ... , an authentication key generating step of transmitting to the n}), the communication device _{U i (i = 1, ...} , n) is the decoding algorithm of the public key encryption using the secret key sk _i, the ciphertext CT decoding the _i, and authentication key receiving step of acquiring the authentication key mk _i ⁰ and the attribute secret key usk _i, the communication device U _{i (i = 1, ...,} n) is the a twisted pseudo-random function secret string st _i, using a st _'i generates _{r i, k i, s i} , = g r_i and first key R _i a first key generation step of generating c _i = g ^{k _i} h ^s_i and transmitting (R _i , c _i ) to the key exchange server device S; A session ID generation step of generating a session ID sid using c ₁ , ..., c _n and transmitting (sid, R _α , R _β ) to the communication device U _i (iε {1, ..., n}) And the communication device U _i (iε {2,..., N}) generates K _i ^l using the sid, R _α ^r_i by the pseudo random function, and generates the sid, R _β ^r_i by the pseudo random function. It generates a K _i ^r with the K _i by exclusive OR of ^l and the K _i ^r to generate a second key T _i, the representative communication device U ₁ is the by pseudo-random function sid, Generate K ₁ ^l using R _n ^r_1 and generate a pseudo-lander K ₁ ^r is generated using the sid and R ₂ ^{r_1 according} to a random function, and a second key T ₁ is generated by exclusive OR of the K ₁ ^l and the K ₁ ^r , the K ₁ ^l and k _A second key generation step of generating T ′ by XOR with ₁ || s ₁ and the communication device U _i (iε {2,..., N}) generate (K _i , s _i , T a second key transmitting step of transmitting _i ) to the key exchange server apparatus S and the representative communication apparatus U ₁ transmits (T ₁ , T ′) to the key exchange server apparatus S; and the key exchange server apparatus S generates k _S , the first common key K ₁ using the secret string st _S , st ' _{S according} to a twisted pseudorandom function, and the exclusive logic of k ₂ , ..., k _n , k _s The sum generates k ′, and for i = 2,..., N, the exclusive OR of T ₁ ,..., T _i−1 generates T ′ _i , for i = 1,. as a condition _{P i = (ID = U i} ) ∧ (time o ∈TF m), the encryption algorithm of attribute-based encryption, the With open parameters Params, it encrypts the first common key K _1, and the first common key generation step of generating a ciphertext CT _'i, said key exchange server device S is, i = 2, ..., n , (C ₁ , k ′, T ′ _i , T ′, CT ′ _i ) to the communication device U _i , and for i = 1, (k ′, CT ′ ₁ ) as the representative communication device U ₁ A first common key transmission step of transmitting to the first key, and authentication key update information μ _i (i = 1,..., N), which is information already shared between the key exchange server apparatus S and the communication apparatus U _i The key exchange server apparatus S performs authentication based on the authentication key mk _i ⁰ and the authentication key update information μ _i or the authentication key mk _i ^{0 using} a key derivation function for i = 1,. An authentication key updating step of generating a key mk _i ¹ ; and the communication device U _i (iε {2,..., N}) performs an exclusive OR operation on the T ′ _i and the K _i ^l to obtain K ₁ ^l And X ₁ by exclusive OR of the T ′ and the K ₁ ^l. generates || s _1, the decoding algorithm of the attribute-based encryption, using the attribute secret key usk _i, decrypts the first common key K ₁ from the ciphertext CT _'i, the representative communication device U ₁ is , the decoding algorithm of attribute-based encryption, the attributes using a secret key usk _i, a first common key receiving step of decoding the first common key K ₁ from the ciphertext CT _'1, the communication device U _i (i ∈ {1,..., N}) generates a second common key K ₂ from a value generated using the session ID sid and the exclusive OR of the k ′ and the k ₁ by a pseudo random function A session key generating step of generating a session key SK by XORing the value generated using the sid, K ₁ with the pseudorandom function and the value generated using the sid, K ₂ with the pseudorandom function; , The communication device U _i (iε {1,..., N}) uses the key derivation function to execute the authentication key mk An authentication key update step of generating a new authentication key mk _i ¹ from _i ⁰ and the authentication key update information μ _i or the authentication key mk _i ⁰ is included.

  According to the present invention, it is possible to realize key exchange which can not acquire an encryption key even if a long-term secret key is leaked.

FIG. 1 is a block diagram showing an example of the configuration of a key exchange system 10; FIG. 2 is a block diagram showing an example of the configuration of a key exchange server apparatus 100. FIG. 2 is a block diagram showing an example of the configuration of a communication apparatus 200. FIG. 6 is a diagram showing an example of setup processing in the key exchange server apparatus 100. FIG. 7 is a diagram showing an example of setup processing in the communication device 200. The figure which shows an example of a key delivery process. The figure which shows the detail of step S115.

  Hereinafter, embodiments of the present invention will be described in detail. Note that components having the same function will be assigned the same reference numerals and redundant description will be omitted.

<Notation / Terminology>
Before describing the embodiments, notations and terms in this specification will be described.

^ (Caret) represents a superscript. For example, x ^{^ z} indicates that ^yz is a superscript for x, and x _{^ z} indicates that ^yz is a subscript for x. Also, _ (underscore) represents a subscript. For example, ^xy_z represents that _yz is a superscript for x, and _{xy_z} represents that _yz is a subscript for x.

Deriving the element x uniformly and randomly from the set S is written as x∈ _R S.

  Let p be a prime number and G be a cyclic group of order p. Also, let g and h be generators of group G.

The Z an integer set, the coset rings Z _p for a prime p.

Let κ (∈ Z) be a security parameter. Kspace and ^_κ = {0, 1} _κ a kappa-bit key space. Also, let {0, 1} ^{* be} a set of bit strings of arbitrary length.

  Is the bit length of the value.

[Time Frame]
Let t be a certain time interval, and let TF _m : = {time _{(m-1) t + 1} ,..., Time _mt } be a time frame TF _m (m = 1, 2,...) (Where t is 1 or more) Integer). Further, the current time time _o, when the time _o ∈TF _m, referred to as a predicate variable representing a time frame TF _m.

[Public key encryption]
Let public key encryption PKE be PKE = (Gen, Enc, Dec). The key generation algorithm Gen takes 1 ^κ as input, and outputs a pair of public key pk and secret key sk. In other words, it is (pk, sk) ← Gen ( 1 κ). At this time, it is assumed that the plaintext space M _pk is determined, and the plaintext space M _pk includes pk. In particular, when the plaintext space M _pk is not specified, M _pk : = {0, 1} ^κ . The encryption algorithm Enc receives the public key pk and the plaintext m∈M _pk as an input, and outputs a ciphertext CT. That is, CT ← Enc _pk (m). The decryption algorithm Dec receives the secret key sk and the ciphertext CT, and outputs the plaintext m. That is, m ← Dec _sk (CT). If the decryption fails, 、, which is a symbol representing the decryption failure, is output instead of the plaintext m. As a specific configuration example, there is RSA-OAEP (Optimal Asymmetric Encryption Padding).

[Pseudo random function]
_RF κ: = |: the family of {f f {0, 1} κ × Kspace κ → {0,1} κ} a random function, the function _{f∈ R} RF κ a random function. The pseudo-random function, the following conditions are satisfied, seed s∈ {0, 1} function family indexed by ^kappa {F _s} belonging to _s function _{F s: {0, 1}} κ × Kspace κ → {0 , 1} ^κ .
(Condition 1) Given input x, F _s (x) can be calculated in polynomial time.
(Condition 2) Even if the output of the random function f or the output of the pseudorandom function F _s is given to an arbitrary probability polynomial time algorithm D, the value output from either function by the algorithm D The probability of identifying one is negligible.

As a specific configuration example, there is a Goldreich-Goldwasser-Micali pseudorandom function configured as a pseudorandom function using a Blum-Micali pseudorandom number generator (Reference Non-Patent Document 1).
(Reference Non-Patent Document 1: O. Goldreich, S. Goldwasser, and S. Micali, “How to Construct Random Functions”, Journal of the ACM, vol. 33, Issue 4, pp. 792-807, 1986.)

[Twist pseudorandom function]
Twisted pseudo-random function ^{tPRF: {0, 1} κ} × Kspace κ × Kspace κ × {0, 1} κ → Rng κ ( However, Rng _kappa is the range of the function), the exclusive OR between the pseudo-random function F _s It is constructed as follows using

However, a, b'∈ {0, 1 } κ, a ', a b∈Kspace _κ.

The torsional pseudo random function tPRF satisfies the following conditions.
(Conditions) Even if the output of the random function f or the output of the twisted pseudorandom function tPRF is given to an arbitrary probability polynomial time algorithm D, the values are output from either function by the algorithm D. The probability of identifying one is negligible.

Hard collision hash function
Collision hard hash function TCR: {0, 1} ^* → {0, 1} ^κ is a hash function satisfying the following conditions.
(Condition) Even if x randomly selected from {0, 1} ^* is given to an arbitrary polynomial time algorithm A, the algorithm A is x ≠ x 'and TCR (x) = TCR (x') It is difficult to find x '.

  As a specific configuration example, there is SHA256.

Attribute-based encryption
Attribute-based encryption ABE is ABE = (Setup, Der, AEnc, ADec). The setup algorithm Setup takes 1 ^κ and information att defining the attribute as input, and outputs the public parameter Params and the master secret key msk. That is, (Params, msk) Setup Setup (1 ^,, att). The key derivation algorithm Der is set to enter the public parameter Params and the master secret key msk and attributes A _i, and outputs the attribute secret key usk _i of the user U _i. That is, usk _i D Der (Params, msk, A _i ). The encryption algorithm AEnc receives the public parameter Params, the condition P and the plaintext m as an input, and outputs a ciphertext CT. That is, CT ← AEnc (Params, P, m). Decryption algorithm ADec as an input attribute secret key usk _i ciphertext CT for public parameter Params user U _i, in the case of A _i ∈P outputs the plaintext m. In other words, it is _{m ← ADec (Params, usk i} , CT). If A _i ∈P, the symbol ⊥ is output. As a specific configuration example, there is intelligent encryption (Reference Non-Patent Document 2).
(Reference non-patent document 2: "Intelligent encryption", [online], [search on December 20, 2017], Internet <URL: http://www.seclab.ecl.ntt.co.jp/project/data -security / intelligent-crypto.html>)

[Message authenticator]
Let the message authentication code MAC be MAC = (MGen, Tag, Ver). The MAC key generation algorithm MGen receives 1 ^κ as an input, and outputs a MAC key mk (provided that | mk | ≧)). In other words, it is mk ← MGen (1 ^κ). The tag generation algorithm Tag receives the MAC key mk and the plaintext mε {0, 1} ^* as an input, and outputs an authentication tag t. That is, t ← Tag _mk (m). The verification algorithm Ver receives the MAC key mk, the plaintext mε {0, 1} ^* and the authentication tag t as input, and outputs 1 if the authentication tag t is correct or 0 if the authentication tag t is correct. That is, 1 ← Ver _mk (m, t) (if the authentication tag t is correct) or 0 ← Ver _mk (m, t) (if the authentication tag t is not correct). As a specific configuration, there is HMAC (Reference Non-Patent Document 4).
(Reference Non-Patent Document 4: F. Song and A. Yun, “Quantum Security of NMAC and Related Constructions PRF Domain Extension Against Quantum Attacks”, CRYPTO 2017, LNCS 10402, pp. 283-309, 2017.)

[Key Derivation Function]
For the key set K _k , K _d , the function KDF: K _k × K _d → K _k is defined as a key derivation function. Here, the key derivation function KDF satisfies the following conditions.
(Condition) For any polynomial time algorithm D, the probability that the algorithm D can distinguish between the output of KDF and a key randomly selected from the key set K _k is as small as negligible.

  As a specific configuration example, there is one configured using a hash function.

First Embodiment

[System configuration]
The key exchange system 10 includes a key exchange server apparatus 100 and N (≧ 2) communication apparatuses 200 ₁ ,..., 200 _N, as illustrated in FIG. In this embodiment, the key exchange server device 100 and the communication devices 200 ₁ ,..., 200 _N are connected to the communication network 900, respectively. The communication network 900 is a circuit switching or packet switching communication network configured such that the key exchange server device 100 can communicate with each of the communication devices 200 ₁ ,..., 200 _N. In this embodiment, the communication devices 200 ₁ ,..., 200 _N may not be able to communicate with each other. The communication network 900 does not have to be a secure communication channel, and can be, for example, the Internet.

  As illustrated in FIG. 2, the key exchange server apparatus 100 sets up the setup unit 101, the secret string generation unit 102, the long-term key generation unit 103, the authentication key generation unit 111, the first key reception unit 112, the session ID generation unit 113, It includes a second key reception unit 114, a first common key generation unit 115, a first common key transmission unit 116, an authentication key update unit 117, and a recording unit 190. The recording unit 190 is a component that appropriately records information necessary for the processing of the key exchange server apparatus 100.

  As illustrated in FIG. 3, the communication device 200 includes a public key generation unit 201, a secret string generation unit 202, a long-term key generation unit 203, an authentication key reception unit 211, a first key generation unit 212, a session ID reception unit 213, A second key generation unit 214, a second key transmission unit 215, a first common key reception unit 216, a session key generation unit 217, a secret information management unit 218, an authentication key update unit 219, and a recording unit 290 are included. The recording unit 290 is a component that appropriately records information necessary for the process of the communication device 200.

The key exchange method of the embodiment is realized by the key exchange server device 100 and the communication devices 200 ₁ ,..., 200 _N performing processing of each step illustrated in FIG. 4, FIG. 5, FIG. 6, and FIG. .

The key exchange server device 100 and the communication devices 200 ₁ ,..., 200 _N may be, for example, known or dedicated computers having a central processing unit (CPU), a main storage device (RAM: random access memory), etc. It is a special device configured by reading a special program. Each device executes each process, for example, under the control of a central processing unit. The data input to each device and the data obtained by each process are stored in, for example, the main storage device, and the data stored in the main storage device is read out to the central processing unit as the need arises. Used for processing. At least a part of each processing unit included in each device may be configured by hardware such as an integrated circuit.

The recording unit 190 included in the key exchange server device 100 and the recording unit 290 included in the communication devices 200 ₁ ,..., 200 _N are, for example, a main storage device such as a random access memory (RAM), a hard disk, an optical disk, or a flash memory Or the like, or middleware such as a relational database or a key-value store. Each storage unit is preferably a tamper-resistant storage device (for example, a SIM card) in order to store secret information.

[Setup process]
The setup procedure in the key exchange method of the embodiment will be described with reference to FIGS. 4 and 5.

In the following description, symbols are defined as follows. S represents a key exchange server apparatus _{100, U i (i∈ {1} , ..., N}) is a communication device 200 ₁ of N units, ..., denote the 200 _N. Let G be a cyclic group of prime order p. Let g and h be generators of group G respectively. ^{F: {0, 1} κ} × G → Z p 2, F ': {0, 1} κ × Z p → Kspace κ, F'': {0, 1} κ × Kspace κ → {0, 1} ^{κ, F ''': {} 0, 1} the _^κ × Kspace ^κ → Z _p to a pseudo random function. ^{tPRF: {0, 1} κ} × Kspace κ × Kspace κ × {0, 1} κ → Z p, tPRF ': {0, 1} κ × Kspace κ × Kspace κ × {0, 1} κ → Kspace κ Is a twisted pseudorandom function. TCR: {0, 1} ^* → {0, 1} Let ^κ be a collision hard hash function. ^{KDF: {0, 1} *} × {0, 1} κ → {0, 1} * is referred to as a key derivation function.

  First, the setup process of the key exchange server apparatus S will be described (see FIG. 4).

In step S101, the setup unit 101 of the key exchange server apparatus S generates the public parameter Params and the master secret key msk according to the setup algorithm Setup of the attribute-based encryption ABE ((Params, msk) Setup Setup (1 ^,, att)) .

In step S102, secret string generation unit 102 of the key exchange server S generates a secret string _{(st S, st 'S)} (st S ∈ R Kspace κ, st' S ∈ R {0, 1} κ) .

In step S103, the long-term key generation unit 103 of the key exchange server apparatus S sets the long-term secret key SSK _s = (msk, st _S , st ' _S ), the long-term public key SPK _s = (Params, p, G, g, h) , TCR, tPRF, tPRF ', F, F', F '', F '''). The long-term key generation unit 103 records the long-term secret key SSK _s and the long-term public key SPK _s in the recording unit 190. Moreover, long-term key generation unit 103, long-term public key SPK _s communication device U _1, ..., is transmitted to the U _N.

Next, setup processing of the communication device U _i (iε {1,..., N}) will be described (see FIG. 5).

In step S201, the public key generation unit 201 of the communication device U _i is the key generation algorithm Gen public key cryptography PKE generates a pair of public key pk _i and secret key sk _i of the communication device U _i ((pk _{i, ^{sk i) ← Gen (1 κ}} )).

In step S202, secret string generation unit 202 of the communication device U _i generates a secret string _{(st i, st 'i)} (st i ∈ R Kspace κ, st' i ∈ {0, 1} κ).

In step S203, long key generation unit 203 of the communication device U _i is long secret key _{SSK i = (sk i, st} i, st 'i), to generate a long-term public key SPK _i = pk _i. The long-term key generation unit 203 records the long-term secret key SSK _i and the long-term public key SPK _i in the recording unit 290. Further, the long-term key generation unit 203 transmits the long-term public key SPK _i to the key exchange server apparatus S.

[Key distribution process]
The key distribution procedure in the key exchange method of the embodiment will be described with reference to FIGS. 6 and 7. This process corresponds to the process in the Dist (key distribution) phase in the DMKD protocol.

Below, among n communication devices 200 ₁ ,..., 200 _N , arbitrary n (2 ≦ n ≦ N) communication devices U _i (iε {1,..., N}) share the session key SK Shall be When S and U _i are the input of each algorithm, it shall represent an identifier uniquely identifying each device.

In step S111, when the communication device U _i (iε {1,..., N}) starts a session, the authentication key generation unit 111 of the key exchange server device S starts a session of the time frame of the communication device U _i . when was the first session in TF _m, the current time as the time _o ∈TF _m, attribute _{a i = (U i, time} o) as, attribute-based encryption ABE by the key derivation algorithm Der, the communication device U _i An attribute secret key usk _i <-Der (Params, msk, A _i ) is generated. The authentication key generation unit 111, the key generation algorithm MGEN of message authentication codes MAC, generates MAC key mk _i ⁰ ← MGen communication device U _i a (1 ^kappa) as the authentication key. The authentication key generation unit 111 records the authentication key mk _i ⁰ in the recording unit 190. The authentication key generation unit 111, the encryption algorithm Enc public key cryptography PKE, encrypts the attribute secret key usk _i and authentication keys mk _i ⁰ with long public key SPK _i = pk _i of the communication device U _i , to generate a cipher text _{CT i ← Enc pk_i (usk i} , mk i 0). The authentication key generation unit 111 transmits the ciphertext CT _i to the communication device U _i (iε {1,..., N}).

In step S211, the communication device _{U i (i∈ {1, ...} , n}) authentication key receiving unit 211 of the by decryption algorithm Dec of the public key cryptography PKE, using the private key sk _i of the communication device U _i key exchange decrypts the ciphertext CT _i received from the server device S, attributes private key and authentication key ^{_{(usk i, mk i 0)}} ← Dec acquires _{sk_i} (CT _i). Authentication key receiving section 211 records the attribute secret key usk _i and authentication keys mk _i ⁰ to the recording unit 290.

In step S212, the communication device _{U i (i∈ {1, ...} , n}) first key generation unit 212 _{of, ~ r i ∈ R {0} , 1} κ, ~ r 'i ∈ R Kspace κ, ~ _{k i ∈ R {0, 1} } κ, ~ k 'i ∈ R Kspace κ, ~ s i ∈ R {0, 1} κ, ~ s' to generate a _i ∈ _R Kspace _κ, short secret key ESK _i = A short-term secret key ESK _i is recorded in the recording unit 290 by generating (̃r _i , ̃r ′ _i , ̃k _i , ̃k ′ _i , ̃s _i , ̃s ′ _i ). The first key generation unit 212, the twisted pseudo-random function _{tPRF, r i = tPRF (~} r i, ~ r 'i, st i, st' i), k i = tPRF (~ k i, ~ k 'i , st _i , st ′ _i ), s _i = t PRF (̃s _i , ̃s ′ _i , st _i , st ′ _i ). The first key generation unit 212, first key R _i = g ^r_i, generates a c _i = g ^k_i h ^s_i. The first key generation unit 212, the tag generation algorithm Tag of the message authentication codes MAC, using the authentication key mk _i ⁰ R _i, authentication from c _i tag ^{_{t i 1 = Tag mk_i ^ 0}} (R i, c i) Generate Then, the first key generation unit 212 transmits (R _i , c _i , t _i ¹ ) to the key exchange server apparatus S.

In step S112, the first key receiving unit 112 of the key exchange server device S receives (R _i , c _i , t _i ¹ ) from the communication device U _i . The first key reception unit 112, all communication devices U _1, ..., from _{U n (R 1, c 1} , t 1 1), ..., (R n, c n, t n 1) receive Wait until you do. The first key receiving unit 112 calculates Ver _{mk_i ̃0} (R _i , c _i , t _i ¹ ) using the authentication key mk _i ⁰ of the communication device U _{i according} to the verification algorithm Ver of the message authentication code MAC. , Verify the authentication tag t _i ¹ If the authentication tag t _i ¹ is not valid (t _i ¹ = 1), the first key receiving unit 112 ends the process.

In step S113, the session ID generator 113 of key exchange server device S, by a collision-resistant hash function TCR, communication device U _1, ..., c ₁ received from the U _n, ..., with c _n, sid = TCR Generate (c ₁ ,..., c _n ) as a session ID. In addition, one communication device is selected from the _n communication devices U ₁ ,..., U _n as a representative. The selection method of the representative may be arbitrary, for example, to select a communication device with the highest priority which has been determined in advance. Here, it is assumed that the communication device U ₁ is selected, referred to as a representative communication device U _1. In addition, n−1 communication devices U _i (iε {2,..., N}) other than the representative communication device U ₁ are called general communication devices. The session ID generation unit 113 uses the authentication key mk _i ^{0 according} to the tag generation algorithm Tag of the message authentication code MAC for i = 1,..., N using the authentication key t _i ² = Tag _{mk_i ^ 0} (sid, R _α , R _β ) and transmit (sid, R _α , R _β , t _i ² ) to the communication device U _i (iε {1,..., N}). However, α and β are defined by the following equations.

The key exchange server device S notifies the communication device U ₁ is a representative communication device to the communication device U _1.

In step S213, the session ID reception unit 213 of the communication device U _i (iε {1,..., N}) receives (sid, R _α , R _β , t _i ² ) from the key exchange server device S. The communication device U _i executes the subsequent processing as soon as (sid, R _α , R _β , t _i ² ) is received. If i = 2,..., n, that is, if the communication device U _i is a general communication device U _i , the process proceeds to step S214 _i . For i = 1, i.e. the communication device U _i is equal representative communication device U _1, the process proceeds to step S214 _1.

In step S214 _i , the second key generation unit 214 of the general communication device U _i (iε {2,..., N}) uses the authentication key mk _i ^{0 according} to the verification algorithm Ver of the message authenticator MAC _{Calculate mk_i ̃0} (sid, R _α , R _β , t _i ² ) and verify the authentication tag t _i ² If the authentication tag t _i ² is not valid (t _i ² = 1), the second key generation unit 214 ends the processing. If the authentication tag t _i ² is valid, the second key generation unit 214 generates K _i ^l using (sid, R _α ^r_i ) with the pseudo random function F as in the following equation, and generates the pseudo random function It generates a K _i ^r with _(sid, R β ^r_i) by F, generating a second key T _i by exclusive OR of the K _i ^l and K _i ^r.

In step S215 _i, general communication device _{U i (i∈ {2, ...} , n}) second key transmission unit 215, due tag generation algorithm Tag of the message authentication codes MAC, using the authentication key mk _i ^0, authentication tag ^{_{t i 3 = tag mk_i ^ 0}} (R i, c i, R α, R β, k i, s i, T i, U i, sid) to generate. The second key transmission unit 215 transmits to the _{(k i, s i, T} i, t i 3) the key exchange server device S.

In step S214 _1, second key generation unit 214 of the representative communication device U ₁ is a verification algorithm Ver message authentication codes MAC, using the authentication key ^{_{mk 1 0, Ver mk_1 ~ 0}} (sid, R n, R 2 , t ₁ ² ) and verify the authentication tag t _i ² . Authentication tag t ₁ ² justifiable (t ₁ ² = ₁₎ Otherwise, the second key generating unit 214 ends the process. If the authentication tag t ₁ ² is valid, the second key generation unit 214 generates K ₁ ¹ using (sid, R _n ^r_1 ) with the pseudo random function F as in the following equation, and generates a pseudo random function Generate K ₁ ^r using (sid, R ₂ ^r_1 ) according to F, generate a second key T ₁ by ^XORing K ₁ ^l and K ₁ ^r , generate K ₁ ^l and k ₁ || Generate T ′ by exclusive OR with s ₁ However, || is a concatenation operator.

In step S215 _1, representative second key transmission unit 215 of the communication device U ₁ is a tag generation algorithm Tag of the message authentication codes MAC, using the authentication key mk ₁ ^0, authentication tag ^{_{t 1 3 = Tag mk_1 ^ 0}} ( R ₁ , c ₁ , R _n , R ₂ , T ₁ , T ′, U ₁ , sid) are generated. The second key transmission unit 215 transmits (T ₁ , T ′, t ₁ ³ ) to the key exchange server apparatus S.

In step S114 _i, second key reception unit 114 of the key exchange server device S, i = 2, ..., for n, in general the communication device U _i from _{(k i, s i, T} i, t i 3) receive Then, using the authentication key mk _i ⁰ of the general communication device U _{i according} to the verification algorithm Ver of the message authenticator MAC, Ver _{mk_i ^ 0} (R _i , c _i , R _α , R _β , k _i , s _i , Calculate T _i , U _i , sid, t _i ³ ) and verify the authentication tag t _i ³ . If the authentication tag t _i ³ is not valid (t _i ³ = 1), the second key receiving unit 114 ends the processing.

In step S114 _1, second key reception unit 114 of the key exchange server device S, from the representative communication device _{U 1 (T 1, T '} , t 1 3) receives, by verification algorithm Ver message authentication code MAC, _Calculate Ver _{mk_1 ^ 0} (R ₁ , c ₁ , R _n , R ₂ , T ₁ , T ₁ , U ₁ , sid, t ₁ ³ ) using the authentication key mk ₁ ⁰ of the representative communication device U ₁ , Verify the authentication tag t _i ³ . Authentication tag t ₁ ³ justifiable (t ₁ ³ = ₁₎ Otherwise, the second key reception unit 114 terminates the process.

In step S115a, the first common key generation unit 115 of the key exchange server device _{S, ~ k S ∈ R {0} , 1} κ, ~ k 'S ∈ R Kspace κ, ~ K 1 ∈ R {0, 1} ^kappa, 'to generate a ₁ ∈ _R Kspace _kappa, by twisting pseudo-random function _{tPRF, k S = tPRF (~} k S, ~ k' ~ K S, st S, st 'S), the first common key K ₁ = Generate tPRF (̃K ₁ , ̃K ′ ₁ , st _S , st ′ _S ). Also, the first shared key generation unit 115 generates k ′ by the exclusive OR of k ₂ ,..., K _n , k _s as in the following equation.

In step S115 b, the first common key generation unit 115 of the key exchange server apparatus S obtains the exclusive OR of T ₁ ,..., T _i−1 for i = 2,. to generate a T _'i.

In step S115c, the first common key generation unit 115 of the key exchange server apparatus S sets attribute P _i = (ID = U _i ) ∧ (time _o ∈TF _m ) for i = 1,. The first common key K ₁ is encrypted by the encryption algorithm AEnc of the encryption ABE to generate a ciphertext CT ′ _i AEAEnc (Params, P _i , K ₁ ). Here, ID is a predicate variable representing a communication device.

In step S116 _i, the first common key transmission unit 116 of the key exchange server device S, i = 2, ..., for n, the tag generation algorithm Tag of the message authenticator MAC, authentication key mk _i of the general communication device U _i with ^0, authentication tag ^{_{t i 4 = tag mk_i ^ 0}} (R i, c i, R α, R β, k i, s i, T i, U i, sid, c 1, k ', T' _i , T ', CT' _i ) are generated. The first common key transmission unit 116 transmits (c ₁ , k ′, T ′ _i , T ′, CT ′ _i , t _i ⁴ ) to the general communication device U _i .

In step S116 _1, the first common key transmission unit 116 of the key exchange server device S, by the tag generation algorithm Tag of the message authentication codes MAC, using the authentication key mk ₁ ⁰ representative communication device U _1, the authentication tag t _{1 ^{4 = Tag mk_1 ^ 0 (R}} 1, c 1, R n, R 2, T 1, T ', U 1, sid, k', CT '1) to generate a. The first common key transmission unit 116 transmits (k ′, CT ′ ₁ , t ₁ ⁴ ) to the representative communication device U ₁ .

In step S117, the authentication key updating section 117 of the key exchange server device S, i = 1, ..., for n, by the key derivation function KDF, new authentication key from the authentication key _{^{mk i 0 mk i 1 ← KDF}} (mk i 0 , sid). Further, the authentication key updating unit 117 deletes the authentication key mk _i ⁰ from the recording unit 190 and records the new authentication key mk _i ¹ in the recording unit 190.

In step S216 _i, general communication device _{U i (i∈ {2, ...} , n}) of the first common key receiving unit 216, from the key exchange server device _{S (c 1, k ',} T' i, T ' , CT ′ _i , t _i ⁴ ), and using verification key mk _i ⁰ of general communication device U _{i according} to verification algorithm Ver of message authentication code MAC, Ver _{mk_i ^ 0} (R _i , c _i , R Calculate _α , R _β , k _i , s _i , T _i , U _i , sid, c ₁ , k ′, T ′ _i , T ′, CT ′ _i , t _i ⁴ ), and identify the authentication tag t _i ⁴ Verify. If the authentication tag t _i ⁴ is not valid (t _i ⁴ = 1), the first common key receiving unit 216 ends the process. If the authentication tag t _i ⁴ is valid, the first common key reception unit 216 generates K ₁ ^l by the exclusive OR of T ′ _i and K _i ^l as in the following equation, and T ′ The exclusive OR with K ₁ ^l generates k ₁ || s ₁ .

The first common key receiving unit 216, the decryption algorithm ADec attribute-based cryptographic ABE, using the attribute secret key usk _i communication device U _i, the first common key _{K 1 ← ADec usk_i (CT '} i, P _i ) decrypt.

In step S216 _1, first common key receiving unit 216 of the representative communication device U ₁ from the key exchange server device _{S (k ', CT' 1} , t 1 4) receives the verification algorithm Ver message authenticator MAC by using the authentication key mk ₁ ⁰ representative communication device _{U 1, Ver mk_1 ^ 0 (} R 1, c 1, R n, R 2, T 1, T ', U 1, sid, k', CT ' Calculate ₁ , t ₁ ⁴ ) and verify the authentication tag t ₄ . Authentication tag t ₁ ⁴ justifiable (t _i ⁴ = 1) Otherwise, the first common key receiving unit 216, the process ends. The first common key reception unit 216 uses the attribute secret key usk ₁ of the representative communication device U ₁ according to the decryption algorithm ADec of the attribute-based encryption ABE to use the first common key K ₁ AD _{ADec usk_1} (CT ′ ₁ , P ₁ Decrypt).

In step S217, the session key generation unit 217 of the communication device U _i (iε {1,..., N}) uses the pseudo random function F ′ to set the session IDs sid, k ′ and k ₁ as shown in the following equation. the value generated by using an exclusive OR, to generate a second common key K _2.

Then, the session key generation unit 217 generates a value generated using (sid, K ₁ ) with the pseudo random function F ′ ′ and using (sid, K ₂ ) with the pseudo random function F ′ ′ The session key SK is generated by the exclusive OR of the calculated values.

The first common key K ₁ , the second common key K ₂ , and the session key SK shared by the communication devices U _i (iε {1,..., N}) are also referred to as encryption keys.

In step S218 _i, general communication device _{U i (i∈ {2, ...} , n}) secret information management unit 218 of the generated secret information ^{_{H i l, H i r,}} r according to the following equation, the recording unit 290 Record on

In step S218 _1, the secret information management unit 218 of the representative communication device U ₁ generates secret information ^{_{H i l, H i r,}} r according to the following equation, is recorded in the recording unit 290.

In step S219, the communication device _{U i (i∈ {1, ...} , n}) authentication key updating section 219 of the the key derivation function KDF, authentication key new authentication key from ^{_{mk i 0 mk i 1 ← KDF}} (mk i Generate ⁰ , sid). Further, the authentication key updating unit 219 deletes the authentication key mk _i ⁰ from the recording unit 290 and records the new authentication key mk _i ¹ in the recording unit 290.

  According to the invention of this embodiment, it is possible to realize key exchange which can not acquire an encryption key even if a long-term secret key leaks.

  According to the invention of this embodiment, in order to exchange the encryption key in a certain session, the authentication key updated most recently is required. However, in order to obtain the most recently updated authentication key, the authentication key updated one before is required. Therefore, when the first authentication key is exchanged securely, even if the long-term secret key leaks, the attacker can not obtain the authentication key. As a result, even if the attacker obtains the long-term secret key, the attacker can not obtain the encryption key by spoofing.

  Here, the processing procedure corresponding to the processing in the Dist (key delivery) phase in the DMKD protocol has been described, but the processing procedure corresponding to the processing in the Join (addition) phase, the Leave (leave) phase, and the Update (update) phase The same is true for That is, in order to execute key exchange securely, an authentication key may be newly generated using the key derivation function KDF each time any phase occurs. The details will be described below.

Currently (the k 1 or more integer) mk _i ^k authentication key to join the group by which the communication device and the key exchange server is maintaining a. For example, the authentication key immediately after a group is created and an encryption key is shared for the first time is mk _i ¹ (ie, k = 1). Occur any of the phases, if the encryption key is shared, using a key derivation function KDF, authentication key mk _i ^k and a session ID of the session sid ^{k + 1} authentication key from mk _i ^{k + 1} ← KDF ( Generate mk _i ^k , sid ^{k + 1} ). Each device, remove the authentication key mk _i ^k from the recording unit, a new authentication key mk _i ^{k + 1} is recorded in the recording unit.

<Modification>
A process of assuring integrity using the message authenticator MAC, that is, a process of generating an authentication tag t _i ¹ in S212, a process of verifying the authentication tag t _i ¹ in S112, a process of generating an authentication tag t _i ² in S113 and S213. authentication verification process of the tag t _i ^2, the authentication verification process of the authentication in the tag t _i generation process ³ and S114 tags t _i ^3, the authentication tag t _i ⁴ in the authentication tag t _i generation process and S216 of ⁴ in S116 in S215 The verification process may be omitted.

<Modification 2>
Also, in S217, the communication device U _i generates two keys from the sid using the pseudo random function, that is, the second common key K ₂ and the session key SK, and transmits these two keys between the communication device U _i in it are to be shared, second only generates the common key K _2, may be shared.

<Modification 3>
In the authentication key update process in S117 and S219, a new authentication key is generated using the current authentication key and session ID as the input of the key derivation function, but instead of the session ID, the following data is generated as the input of the key derivation function: Either may be used.
(1) R _i or c _i shared by the processing in S 212 and S 112
In this case, KDF: {0, 1} ^* × G → {0, 1} ^* may be used as the key derivation function. Therefore, the authentication key updating section 117 of the key exchange server device S, i = 1, ..., for n, by the key derivation function KDF, authentication key mk _i ⁰ from the new authentication key ^{_{mk i 1 ← KDF (mk i}} 0, R _i ) (or mk _i ¹ ← KDF (mk _i ⁰ , c _i )) is generated. The communication device _{U i (i∈ {1, ...} , n}) authentication key updating section 219 of the the key derivation function KDF, authentication key new authentication key from ^{_{mk i 0 mk i 1 ← KDF}} (mk i 0, Generate R _i ) (or mk _i ¹ ← KDF (mk _i ⁰ , c _i )).
(2) T _i shared by the processing in S 215 and S 114
In this case, KDF: {0, 1} ^* × Z _p ² → {0, 1} ^* may be used as the key derivation function. Therefore, the authentication key updating section 117 of the key exchange server device S, i = 1, ..., for n, by the key derivation function KDF, new authentication from the authentication key mk _i ⁰ key ^{_{mk i 1 ← KDF (mk i}} 0, T _i ) Generate. The communication device _{U i (i∈ {1, ...} , n}) authentication key updating section 219 of the the key derivation function KDF, authentication key new authentication key from ^{_{mk i 0 mk i 1 ← KDF}} (mk i 0, Generate T _i ).
(3) The first common key K ₁ shared by the processing in S115 and S216
In this case, KDF: {0, 1} ^* × Z _p → {0, 1} ^* may be used as the key derivation function. Therefore, the authentication key updating unit 117 of the key exchange server apparatus S calculates the authentication key mk _i ¹ K KDF (m k _i ⁰ , K) from the authentication key mk _i ^{0 according} to the key derivation function KDF for i = 1,. ₁ ) Generate. The communication device _{U i (i∈ {1, ...} , n}) authentication key updating section 219 of the the key derivation function KDF, authentication key new authentication key from ^{_{mk i 0 mk i 1 ← KDF}} (mk i 0, Generate K ₁ ).

The sid, R _i , c _i , T _i , and K ₁ used to update the authentication key are referred to as authentication key update information μ _i (i = 1,..., N). The information already shared between the key exchange server device S and the communication device U _i such as sid, R _i , c _i , T _i and K ₁ listed here is the authentication key update information μ _i and can do. The information already shared between the key exchange server S and the communication device U _i refers to the key exchange server S and the communication device U _i by the process of S 116 by the key exchange server S and the process of S 216 by the communication device U _i. Information that is shared among

<Modification 4>
The key set K _d used to define the key derivation function may be K _d = φ (where φ is an empty set). That is, KDF: {0, 1} ^* → {0, 1} ^* . In this case, the authentication key update process in S117 and S219 is as follows. The authentication key updating unit 117 of the key exchange server device S generates a new authentication key mk _i ¹ K KDF (mk _i ⁰ ) from the authentication key mk _i ⁰ by the key derivation function KDF for i = 1,. . The communication device _{U i (i∈ {1, ...} , n}) authentication key updating section 219 of the the key derivation function KDF, new authentication from the authentication key mk _i ⁰ key ^{_{mk i 1 ← KDF (mk i}} 0) Generate

<Supplementary Note>
The apparatus according to the present invention is, for example, an input unit to which a keyboard or the like can be connected, an output unit to which a liquid crystal display or the like can be connected as a single hardware entity, or a communication device (for example, communication cable) capable of communicating outside the hardware entity. Communication unit that can be connected, CPU (central processing unit, cache memory, registers, etc. may be provided), RAM or ROM that is memory, external storage device that is hard disk, input unit for these, output unit, communication unit , CPU, RAM, ROM, and a bus connected so as to enable exchange of data between external storage devices. If necessary, the hardware entity may be provided with a device (drive) capable of reading and writing a recording medium such as a CD-ROM. Examples of physical entities provided with such hardware resources include general purpose computers.

  The external storage device of the hardware entity stores a program necessary for realizing the above-mentioned function, data required for processing the program, and the like (not limited to the external storage device, for example, the program is read) It may be stored in the ROM which is a dedicated storage device). In addition, data and the like obtained by the processing of these programs are appropriately stored in a RAM, an external storage device, and the like.

  In the hardware entity, each program stored in the external storage device (or ROM etc.) and data necessary for processing of each program are read into the memory as necessary, and interpreted and processed appropriately by the CPU . As a result, the CPU realizes predetermined functions (each component requirement expressed as the above-mentioned,...

  The present invention is not limited to the above-described embodiment, and various modifications can be made without departing from the spirit of the present invention. Further, the processing described in the above embodiment may be performed not only in chronological order according to the order of description but also may be performed in parallel or individually depending on the processing capability of the device that executes the processing or the necessity. .

  As described above, when the processing function in the hardware entity (the apparatus of the present invention) described in the above embodiment is implemented by a computer, the processing content of the function that the hardware entity should have is described by a program. Then, by executing this program on a computer, the processing function of the hardware entity is realized on the computer.

  The program describing the processing content can be recorded in a computer readable recording medium. As the computer readable recording medium, any medium such as a magnetic recording device, an optical disc, a magneto-optical recording medium, a semiconductor memory, etc. may be used. Specifically, for example, as a magnetic recording device, a hard disk device, a flexible disk, a magnetic tape or the like as an optical disk, a DVD (Digital Versatile Disc), a DVD-RAM (Random Access Memory), a CD-ROM (Compact Disc Read Only) Memory), CD-R (Recordable) / RW (Rewritable), etc. as magneto-optical recording medium, MO (Magneto-Optical disc) etc., as semiconductor memory EEP-ROM (Electronically Erasable and Programmable Only Read Memory) etc. Can be used.

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

  For example, a computer that executes such a program first temporarily stores a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. Then, at the time of execution of the process, the computer reads the program stored in its own recording medium and executes the process according to the read program. Further, as another execution form of this program, the computer may read the program directly from the portable recording medium and execute processing according to the program, and further, the program is transferred from the server computer to this computer Each time, processing according to the received program may be executed sequentially. In addition, a configuration in which the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes processing functions only by executing instructions and acquiring results from the server computer without transferring the program to the computer It may be Note that the program in the present embodiment includes information provided for processing by a computer that conforms to the program (such as data that is not a direct command to the computer but has a property that defines the processing of the computer).

  Further, in this embodiment, the hardware entity is configured by executing a predetermined program on a computer, but at least a part of the processing content may be realized as hardware.

Claims (6)

Let n be an integer of 2 or more, and α and β be values defined by the following formula,

A key exchange method executed by a key exchange system including a key exchange server apparatus S and n communication apparatuses U _i (i = 1,..., N),
The communication device U ₁ to U _1, and ..., U _n 1 single representative communication device selected from, time _o the current time, the predicate variable representing a communication apparatus ID, and the predicate variable representing the time frame TF _m,
In the recording unit of the key exchange server apparatus S, long-term secret key SSK _s = (msk, st _S , st ' _S ) (wherein msk is a master secret key of attribute-based encryption, st _S and st' _S are secret respectively). String) is recorded,
The communication device _{U i (i = 1, ...} , n) to the recording portion of the long-term secret key _{SSK i = (sk i, st} i, st 'i) ( provided that, sk _i public of the communication device U _i The secret key of the key encryption, st _i and st ' _i are each a secret string) is recorded,
The key exchange server apparatus S sets the attribute A _i = (U _i , time _o ) for i = 1,..., N by the key derivation algorithm of the attribute based encryption, the public parameter Params of the attribute based encryption and the master using the secret key msk, generates attribute secret key usk _i of the communication device U _i, by the key generation algorithm of the message authentication code, generates a MAC key mk _i ⁰ of the communication device U _i as the authentication key, public the encryption algorithm key encryption, the long-term public key SPK _i = pk _i of the communication device U _i (however, pk _i is the public key of the public key encryption of the communication device U _i) using the attribute secret key usk _i and the authentication key mk _i ⁰ encrypting to generate a ciphertext CT _i, the ciphertext CT _i said communication device _{U i (i∈ {1, ...} , n}) and the authentication key generating step of transmitting to the ,
The communication device U _i (i = 1,..., N) decrypts the ciphertext CT _i using the secret key sk _{i according} to a decryption algorithm of public key cryptography, and the attribute secret key uski _i An authentication key receiving step of acquiring an authentication key mk _i ⁰ ;
The communication device U _i (i = 1,..., N) generates r _i , k _i , s _i using the secret string st _i , st ′ _{i according} to a twist pseudo random function, and generates a first key R _i = g ^r_i and c _i = g ^k_i h ^s_i are generated, and an authentication tag t _i ¹ is generated from the R _i and c _i using the authentication key mk _i ^{0 according} to a tag generation algorithm of the message authentication ^coder , A first key generation step of transmitting (R _i , c _i , t _i ¹ ) to the key exchange server apparatus S;
The key exchange server apparatus S verifies the authentication tag t _i ¹ using the authentication key mk _i ⁰ and the R _i and c _{i according} to a message authentication code verification algorithm for i = 1,. A first key receiving step
The key exchange server apparatus S generates a session ID sid using the c ₁ ,..., C _{n according} to the collision hard hash function, and for i = 1,. by using the authentication key mk _i ^0, the _sid, R α, generates an authentication tag t _i ² from _{R β, (sid, R α} , R β, t i 2) the communication device U _i (i ∈ A session ID generation step for sending to {1, ..., n}),
The communication device U _i (iε {2,..., N}) uses the authentication key mk _i ⁰ and the sid, R _α , R _{β according} to the verification algorithm of the message authentication code, and the authentication tag t _i ² is verified, and if the authentication tag t _i ² is valid, a pseudo random function is used to generate K _i ^l using the sid, R _α ^r_i , and a pseudo random function is using the sid, R _β ^r_i Generate K _i ^r and generate a second key T _i by exclusive OR of the K _i ^l and the K _i ^r ;
The representative communication device U ₁ is the verification algorithm of message authentication codes, the said authentication key mk ₁ ⁰ sid, R _n, with R _2, wherein to verify the authentication tag t ₁ ^2, wherein the authentication tag t ₁ If ² is valid, the by pseudo-random function sid, with R _n ^r_1 generates K ₁ ^l, wherein sid, with R ₂ ^r_1 generates K ₁ ^r by a pseudo-random function, the K ₁ a second key generation step of generating a second key T ₁ by XOR of ^l and the K ₁ ^r, and T ′ by XOR of the K ₁ ^l and k ₁ || s ₁ When,
The communication device U _i (iε {2,..., N}) uses the authentication key mk _i ^{0 according} to the tag generation algorithm of the message authentication code to use the R _i , c _i , R _α , R _β , An authentication tag t _i ³ is generated from k _i , s _i , T _i , U _i , sid, and (k _i , s _i , T _i , t _i ³ ) is transmitted to the key exchange server apparatus S,
The representative communication device U ₁ is, by the tag generation algorithm message authentication codes, by using the authentication key mk ₁ ^0, wherein _{R 1, c 1, R n} , R 2, T 1, T ', U 1, sid generates an authentication tag t ₁ ³ from the second key transmitting step of transmitting _{(T 1, T ', t} 1 3) to the key exchange server device S,
The key exchange server apparatus S uses the authentication key mk _i ⁰ and the R _i , c _i , R _α , R _β , k _i , s _{i according to the} message authentication code verification algorithm for i = 2,. , T _i, U _i, using sid, verifies the authentication tag t _i ^3, for i = 1, the verification algorithm of the message authentication codes, the said authentication key ^{_{mk 1 0 R 1, c 1}} , R _{n, R 2, T 1,} T ', with U _1, sid, a second key reception step of verifying the authentication tag t ₁ ^3,
The key exchange server device S is, by twisting the pseudo random function, the secret string st _S, st 'with _S, k _S, first generates a common key K _1, the _{k 2, ..., k n,} k The exclusive OR of _s generates k ′, and for i = 2,..., n, the exclusive OR of T ₁ ,..., T _i−1 generates T ′ _i , i = 1 , ..., n, the first common key K ₁ using the public parameter Params according to the encryption algorithm of attribute-based encryption as a condition P _i = (ID = U _i ) ∧ (time _o ∈TF _m ) To generate a ciphertext CT ′ _i by encrypting the first common key generation step;
The key exchange server apparatus S uses the authentication key mk _i ^{0 according} to the tag generation algorithm of the message authentication coder for i = 2,..., N to use the R _i , c _i , R _α , R _β , k _An authentication tag t _i ⁴ is generated from _i , s _i , T _i , U _i , sid, c ₁ , k ′, T ′ _i , T ′, CT ′ _i (c ₁ , k ′, T ′ _i , T ', CT' _i, transmits a t _i ⁴⁾ to the communication device U _i, for i = 1, by the tag generation algorithm message authentication codes, by using the authentication key mk ₁ ^0, wherein R _1, c ₁ , R _n , R ₂ , T ₁ , T ′, U ₁ , sid, k ′, CT ′ ₁ Generate an authentication tag t ₁ ⁴ from the above, (k ′, CT ′ ₁ , t ₁ ⁴ ) A first common key transmission step of transmitting to the communication device U ₁ ;
It is assumed that authentication key update information μ _i (i = 1,..., N) is information already shared between the key exchange server apparatus S and the communication apparatus U _i .
The key exchange server apparatus S obtains the authentication key mk _i ⁰ and the authentication key update information μ _i or the authentication key mk _i ⁰ new from the authentication key mk _i ^{0 using} a key derivation function for i = 1,. an authentication key update step of generating _i ¹ ;
The communication device U _i (iε {2,..., N}) is configured to verify the authentication key mk _i ⁰ and the R _i , c _i , R _α , R _β , k _i , s according to a message authentication code verification algorithm. _The authentication tag t _i ⁴ is verified using _i , T _i , U _i , sid, c ₁ , k ′, T ′ _i , T ′, CT ′ _i and the authentication tag t _i ⁴ is valid In this case, K ₁ ^l is generated by the exclusive OR of the T ′ _i and the K _i ^l, and k ₁ || s ₁ is generated by the exclusive OR of the T ′ and the K ₁ ^l , the decoding algorithm of the attribute-based encryption, using the attribute secret key usk _i, decrypts the first common key K ₁ from the ciphertext CT _'i,
The representative communication device U ₁ is the verification algorithm of message authentication codes, the said authentication key ^{_{mk 1 0 R 1, c 1}} , R n, R 2, T 1, T ', U 1, sid, k', using CT _'1, wherein to verify the authentication tag t ₁ ^4, when the authentication tag t _i ⁴ is valid, the decoding algorithm of the attribute-based encryption, using the attribute secret key usk _i, the ciphertext from CT _'1 and the first common key receiving step of decoding the first common key K _1,
The second communication device U _i (iε {1,..., N}) generates a second by a value generated using the session ID sid and the k ′ and the exclusive OR of the k ₁ by a pseudo random function. generates a common key K _2, the by pseudo-random function sid, wherein the value and the pseudo-random function generated using K ₁ sid, the exclusive OR of the generated value with K _2, the session key SK A session key generation step to generate;
The communication device U _i (iε {1,..., N}) uses the key derivation function to obtain the authentication key mk _i ⁰ and the authentication key update information μ _i or the authentication key new from the authentication key mk _i ⁰ A key exchange method comprising: an authentication key update step of generating mk _i ¹ ; Let n be an integer of 2 or more, and α and β be values defined by the following formula,

A key exchange method executed by a key exchange system including a key exchange server apparatus S and n communication apparatuses U _i (i = 1,..., N),
The communication device U ₁ to U _1, and ..., U _n 1 single representative communication device selected from, time _o the current time, the predicate variable representing a communication apparatus ID, and the predicate variable representing the time frame TF _m,
In the recording unit of the key exchange server apparatus S, long-term secret key SSK _s = (msk, st _S , st ' _S ) (wherein msk is a master secret key of attribute-based encryption, st _S and st' _S are secret respectively). String) is recorded,
The communication device _{U i (i = 1, ...} , n) to the recording portion of the long-term secret key _{SSK i = (sk i, st} i, st 'i) ( provided that, sk _i public of the communication device U _i The secret key of the key encryption, st _i and st ' _i are each a secret string) is recorded,
The key exchange server apparatus S sets the attribute A _i = (U _i , time _o ) for i = 1,..., N by the key derivation algorithm of the attribute based encryption, the public parameter Params of the attribute based encryption and the master using the secret key msk, generates attribute secret key usk _i of the communication device U _i, by the key generation algorithm of the message authentication code, generates a MAC key mk _i ⁰ of the communication device U _i as the authentication key, public the encryption algorithm key encryption, the long-term public key SPK _i = pk _i of the communication device U _i (however, pk _i is the public key of the public key encryption of the communication device U _i) using the attribute secret key usk _i and the authentication key mk _i ⁰ encrypting to generate a ciphertext CT _i, the ciphertext CT _i said communication device _{U i (i∈ {1, ...} , n}) and the authentication key generating step of transmitting to the ,
The communication device U _i (i = 1,..., N) decrypts the ciphertext CT _i using the secret key sk _{i according} to a decryption algorithm of public key cryptography, and the attribute secret key uski _i An authentication key receiving step of acquiring an authentication key mk _i ⁰ ;
The communication device U _i (i = 1,..., N) generates r _i , k _i , s _i using the secret string st _i , st ′ _{i according} to a twist pseudo random function, and generates a first key R _i = generates g ^r_i and c _i = g ^k_i h ^s_i, a first key generating step of transmitting (R _i, c _i) of the said key exchange server device S,
The key exchange server apparatus S generates a session ID sid using the c ₁ ,..., C _{n according} to the collision hard hash function, and (sid, R _α , R _β ) is used as the communication apparatus U _i (i∈ A session ID generation step for sending to {1, ..., n}),
The communication device U _i (iε {2,..., N}) generates K _i ^l using the sid, R _α ^r_i with a pseudorandom function, and uses the sid, R _β ^r_i with a pseudo random function K _i ^r to generate, to generate the K _i ^l and the K _i second key T _i by exclusive OR of the ^r Te,
The representative communication device U ₁ generates K ₁ ^l using the sid and R _n ^r ₁ by a pseudo random function, and generates K ₁ ^r using the sid and R ₂ ^r ₁ by a pseudo random function, the K Second key generation that generates a second key T ₁ by exclusive OR of ₁ ^l and the K ₁ ^r, and generates T ′ by exclusive OR of the K ₁ ^l and k ₁ || s ₁ Step and
The communication device U _i (iε {2,..., N}) transmits (k _i , s _i , T _i ) to the key exchange server apparatus S,
A second key transmission step in which the representative communication device U ₁ transmits (T ₁ , T ′) to the key exchange server device S;
The key exchange server device S is, by twisting the pseudo random function, the secret string st _S, st 'with _S, k _S, first generates a common key K _1, the _{k 2, ..., k n,} k The exclusive OR of _s generates k ′, and for i = 2,..., n, the exclusive OR of T ₁ ,..., T _i−1 generates T ′ _i , i = 1 , ..., n, the first common key K ₁ using the public parameter Params according to the encryption algorithm of attribute-based encryption as a condition P _i = (ID = U _i ) ∧ (time _o ∈TF _m ) To generate a ciphertext CT ′ _i by encrypting the first common key generation step;
The key exchange server apparatus S transmits (c ₁ , k ′, T ′ _i , T ′, CT ′ _i ) for i = 2,..., N to the communication apparatus U _i , and for i = 1 a first common key transmission step of transmitting (k ′, CT ′ ₁ ) to the representative communication device U ₁ ;
It is assumed that authentication key update information μ _i (i = 1,..., N) is information already shared between the key exchange server apparatus S and the communication apparatus U _i .
The key exchange server apparatus S obtains the authentication key mk _i ⁰ and the authentication key update information μ _i or the authentication key mk _i ⁰ new from the authentication key mk _i ^{0 using} a key derivation function for i = 1,. an authentication key update step of generating _i ¹ ;
The communication device _{U i (i∈ {2, ...} , n}) is the T 'generates K ₁ ^l by exclusive OR of _i and the K _i ^l, the T' and said K ₁ ^l k ₁ generates || s ₁ by XOR, the decoding algorithm of attribute-based encryption, using the attribute secret key usk _i, decrypts the first common key K ₁ from the ciphertext CT _'i ,
The representative communication device U ₁ is the decoding algorithm of the attribute-based encryption, using the attribute secret key usk _i, a first common key receiving step of decoding the first common key K ₁ from the ciphertext CT _'1,
The second communication device U _i (iε {1,..., N}) generates a second by a value generated using the session ID sid and the k ′ and the exclusive OR of the k ₁ by a pseudo random function. generates a common key K _2, the by pseudo-random function sid, wherein the value and the pseudo-random function generated using K ₁ sid, the exclusive OR of the generated value with K _2, the session key SK A session key generation step to generate;
The communication device U _i (iε {1,..., N}) uses the key derivation function to obtain the authentication key mk _i ⁰ and the authentication key update information μ _i or the authentication key new from the authentication key mk _i ⁰ A key exchange method comprising: an authentication key update step of generating mk _i ¹ ;   The key exchange system which implements the key exchange method of Claim 1 or 2.   The key exchange server apparatus contained in the key exchange system which implements the key exchange method of Claim 1 or 2.   The communication apparatus contained in the key exchange system which implements the key exchange method of Claim 1 or 2.   A program for causing a computer to function as a key exchange server apparatus or a communication apparatus included in a key exchange system for executing the key exchange method according to claim 1 or 2.

Images