JP2013110628A - Key exchange system, key exchange device, key generation apparatus, key exchange method and key exchange program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a secure key exchange technique not assuming random oracle.SOLUTION: A key exchange system includes at least key exchange devices α and β and exchanges session keys. In the key exchange system, a user exchanging keys prepares a dummy attribute set W in addition to his or her own attribute set S to be used for basic authentication, and assigns the W to a verification key of a generated use-and-discard signature. In this event, the user adds, as an authentication condition, an access structure satisfied by a dummy attribute set W corresponding to a specific verification key, in addition to an access structure A desired satisfied by a partner, and performs key exchange. Further, when the last session key is derived, a strong random extractor and a pseudo-random function, instead of the random oracle, are used.

Description

  The present invention relates to information security, and more particularly to a key exchange system, a key exchange device, a key generation device, a key exchange method, and a key exchange program for sharing a session key between two parties.

  Non-Patent Document 1 discloses a key exchange system that can specify an access policy at the time of key exchange and can handle arbitrary attributes even after generating a master secret key and a master public key.

Kazuki Yoneyama, “Strongly Secure Two-Pass Attribute-Based Authenti-cated Key Exchange”, Pairing 2010, LNCS 6487, pp147-166, 2010.

  The contents corresponding to Non-Patent Document 1 are described in Japanese Patent Application No. 2010-290553 that has not been published at the time of filing this application, and are as follows.

[Constitution]
FIG. 1 shows a configuration example of a key exchange system of Japanese Patent Application No. 2010-259053. The key exchange system includes key exchange devices 100 ₁ ,..., 100 _Q connected via the network 1000 (where Q is an integer of 2 or more, q is an integer of 1 to Q, and A and B are 1 to Q) The key generation device 300 is configured. FIG. 2 shows a functional configuration example of the key exchange apparatus, and FIG. 3 shows a functional configuration example of the key generation apparatus. The key exchange device 100 _q includes an access structure determination unit 110 _q , a short-term secret key generation unit 120 _q , an exchange information generation unit 130 _q , a transmission unit 140 _q , a reception unit 145 _q , an attribute confirmation unit 150 _q , and a secret information acquisition unit 160. _q , a session key calculation unit 170 _q , an intermediate information deletion unit 180 _q , and a recording unit 190 _q . The key generation device 300 includes a master key generation unit 310, a long-term secret key generation unit 320, and a recording unit 390. In the following description, the key exchange apparatus 100 _A (corresponding to the key exchange apparatus α) functions as an initiator, and the key exchange apparatus 100 _B (corresponding to the key exchange apparatus β) functions as a responder to share a session key. explain.

Incidentally, kappa are integers, p is a kappa-bit prime number, G and _{G T} is of order p group, g is the original creation of the group G, _{g T} is generator of the group _{G T,} e is G × G → _{G T} H ₁ is a hash function that converts an integer of an arbitrary length to an element of the group G, H ₂ is a hash function that converts an integer of an arbitrary length to an integer of 0 to p−1, and H 2 ₃ is a set of hash functions, P _n is an attribute element indicating an attribute, the attribute set S _a of attribute elements P _n indicating the attribute of the key exchange device 100 _a combination of converting an integer arbitrary length to an integer κ bits, attributes The set S _B is a set of combinations of attribute elements P _n indicating the attributes of the key exchange apparatus 100 _B , N _MAX is a predetermined integer, j and n are integers of 1 to N _MAX , and k _A is the attribute set S _A element, _{k B} the set of attributes _{S B} elements, _{{T a}} is _{T a [1], ...,} T a [N M Set of _{X], {T B}} is _T B [1], _..., a set of T _{B [N MAX],} the set of _{{S A}} is _{S A [1], ...,} S A [N MAX], { S _B } is a set of S _B [1],..., S _B [N _MAX ], {U} is a set of U _{i, j} , and {V} is a set of V _{i, j} .

[Key generation, key extraction]
FIG. 4 shows an example of a processing flow for generating a master secret key, a master public key, and a long-term secret key. The long-term secret key generation process corresponds to key extraction. The master key generation unit 310 of the key generation device 300 randomly selects r and z from integers between 0 and p−1. Then, the master public key _{(g, g ^ r, g} T ^ z) , to record the master secret key in the recording unit 390 as g ^ z, master public key _{(g, g ^ r, g} T ^ z) a Release (S310). Key exchange device 100 _A and the key exchange device 100 _B, respectively a master public key receives _{(g, g ^ r, g} T ^ z), is recorded in the recording unit 190 _B and the recording unit 190 _A.

The long-term secret key generation unit 320 randomly selects t _A [1],..., T _A [N _MAX ] from an integer of 0 or more and p−1 or less, and S ′ _A = g ^ z · g ^ (rt _A [ 1]), T _A [j] = g ^ t _A [1] is calculated for j of 1 to N _{MAX and} the element k _A of the attribute set S _A is calculated.

And (S ′ _A , {T _A }, {S _A }) are transmitted to the key exchange apparatus 100 _A as the long-term secret key (S320 _A ). The key exchange apparatus 100 _A receives the long-term secret key (S ′ _A , {T _A }, {S _A }) and records it in the recording unit 190 _A (S 192 _A ).

Further, the long-term secret key generation unit 320 randomly selects t _B [1],..., T _B [N _MAX ] from an integer of 0 or more and p−1 or less, and S ′ _B = g ^ z · g ^ (rt _B [1]), T _B [j] = g ^ t _B [1] is calculated for j that is greater than or equal to 1 and less than or equal to N _MAX , and the element k _B of the attribute set S _B

And (S ′ _B , {T _B }, {S _B }) as the long-term secret key is transmitted to the key exchange apparatus 100 _B (S 320 _B ). The key exchange apparatus 100 _B receives the long-term secret key (S ′ _B , {T _B }, {S _B }) and records it in the recording unit 190 _B (S 192 _B ).

Incidentally, the master public key to the recording unit 190 _A of advance key exchange device _{100 A (g, g ^ r} , g T ^ z) and long-term secret key _{(S 'A, {T A} }, {S A}) and is recorded, the master public key to the recording unit 190 _B of the key exchange device _{100 B (g, g ^ r} , g T ^ z) and long-term secret key _{(S 'B, {T B} }, {S B}) and if by being recorded, it can be constructed minimum key exchange system only connected key exchange device 100 _a and the key exchange device 100 _B via a network 1000.

[Key exchange]
FIG. 5 shows an example of a flow of key exchange processing for sharing a session key. In this example, the key exchange device 100 _A (corresponding to the key exchange device α) functions as an initiator, and the key exchange device 100 _B (corresponding to the key exchange device β) functions as a responder.

Key exchange unit 100 _A, the access structure determination unit 110 _A, the short-term private key generating unit 120 _A, exchanging information generating unit 130 _A, the transmission unit 140 _A, the reception unit 145 _A, the attribute confirmation section 0.99 _A, secret information acquisition unit 160 _A , a session key calculation unit 170 _A , and an intermediate information deletion unit 180 _A. The key exchange apparatus 100 _B includes an access structure determination unit 110 _B , a short-term secret key generation unit 120 _B , an exchange information generation unit 130 _B , a transmission unit 140 _B , a reception unit 145 _B , an attribute confirmation unit 150 _B , and a secret information acquisition unit 160. _B , a session key calculation unit 170 _B , and an intermediate information deletion unit 180 _B.

Access structure determination unit 110 _A determines the access structure _{A A,} generates the access structure _A share information generation matrix corresponding to _{A M A} and injective labeling function [rho _A (S110 _A). Short-term private key generation unit 120 _A, for 1 ≦ j ≦ _{N ^A,} selected randomly ^u _{~ j} from 0 or p-1 an integer (S120 _A). Exchanging information generating unit 130 _A is
For 1 ≦ j ≦ N _A , u _j = H ₂ (S ′ _A , {T _A }, {S _A }, u ^to _j ),
X = g ^ u ₁ ,
For 1 ≦ i ≦ _{L A} and 1 ≦ j ≦ _{N A,}
U _{i, j} = g ^ (r (M _A ) _{i, j} u _j ) · H ₁ (j, ρ _A (i)) ^ (− u ₁ ),
For 1 ≦ i ≦ _{L A} and _{N A + 1 ≦ j ≦ N} MAX,
U _{i, j} = H ₁ (j, ρ _A (i)) ^ (− u ₁ )
Is calculated (130 _A ). The transmission unit 140 _A transmits X, {U}, M _A , and ρ _A to the key exchange apparatus 100 _B (S140 _A ). The intermediate information erasure unit 180 _A erases u _j (1 ≦ j ≦ N _A ) (S180 _A ).

The receiving unit 145 _B receives X, {U}, M _A , and ρ _A from the key exchange apparatus 100 _A (S145 _B ). The attribute confirmation unit 150 _B confirms whether the attribute set S _B satisfies the share information generation matrix M _A and the injection labeling function ρ _A, and whether X and {U} are elements of the group G (S 150 _B ).

Access structure determination unit 110 _B determines the access structure _{A B,} and generates the access structure shares information generation matrix corresponding to _{A B M B} and injective labeling function ρ _B (S110 _B). The short-term secret key generation unit 120 _B randomly selects v ^to _j from 0 to p−1 in an integer for 1 ≦ j ≦ N _B (S120 _B ). The exchange information generation unit 130 _B
For _{1 ≦ j ≦ N B, v} j = H 2 (S 'B, {T B}, {S B}, v ~ j),
Y = g ^ v ₁ ,
For 1 ≦ i ≦ _{L B} and 1 ≦ j ≦ _{N B,}
V _{i, j} = g ^ (r (M _B ) _{i, j} v _j ) · H ₁ (j, ρ _B (i)) ^ (− v ₁ ),
For 1 ≦ i ≦ L _B and N _B + 1 ≦ j ≦ N _MAX ,
V _{i, j} = H ₁ (j, ρ _B (i)) ^ (− v ₁ )
The calculate (S130 _B). The transmission unit 140 _B transmits Y, {V}, M _B , and ρ _B to the key exchange apparatus 100 _A (S140 _B ).

The secret information acquisition unit 160 _B obtains a set I _B that satisfies I _B = {k: ρ _A (k) εS _B }, and a legitimate share information set for the secret information u ₁ generated by the key exchange apparatus 100 _A { About (M _A ) _{i, j} u _j }

An integer w _B [k] (where k is an element of the set I _B ) of 0 or more and p−1 or less that holds is obtained (S160 _B ). Session key calculation unit 170 _B

σ ₂ = (g _T ^ z) ^ v ₁
σ ₃ = X ^ v ₁
And the session key K
K = H ₃ (σ ₁ , σ ₂ , σ ₃ , (X, {U}, M _A , ρ _A ), (Y, {V}, M _B , ρ _B ))
Calculated as (S170 _B). The intermediate information erasure unit 180 _B erases v _j (1 ≦ j ≦ N _B ) (S180 _B ).

The receiving unit 145 _A receives Y, {V}, M _B , and ρ _B from the key exchange apparatus 100 _B (S145 _A ). Attribute confirmation section 0.99 _A, the attribute set _{S A} is meet or share information generator matrix _{M B} and injective labeling function [rho _B, Y and {V} to confirm whether the elements of the group G (S150 _A). The secret information acquisition unit 160 _A obtains a set I _{A such} that I _A = {k: ρ _B (k) ∈S _A }, and a valid share information set { ₁ for the secret information v ₁ generated by the key exchange apparatus 100 _B { (M _B ) _{i, j} v _j }

An integer w _A [k] (where k is an element of the set I _A ) is obtained (S160 _A ). Session key calculation unit 170 _A

_{σ 1 = (g T ^ z} ) ^ H 2 (S 'A, {T A}, {S A}, u ~ 1)
_{σ 3 = Y ^ H 2 (} S 'A, {T A}, {S A}, u ~ 1)
And the session key K
K = H ₃ (σ ₁ , σ ₂ , σ ₃ , (X, {U}, M _A , ρ _A ), (Y, {V}, M _B , ρ _B ))
Seek like.

  This key exchange system can specify an access policy at the time of key exchange by the process as described above, and can handle arbitrary attributes even after generating a master secret key and a master public key. However, in order to guarantee safety, there is a problem that the hash function must be ideally secure (random oracle). It is known that a random oracle cannot be realized using an actual hash function. Therefore, it is desirable to have a system that provides security proof without assuming a random oracle.

  The present invention ensures that an access policy can be specified at the time of key exchange as in the key exchange technique of Non-Patent Document 1, and that any attribute can be handled even after generating a master secret key and a master public key. An object of the present invention is to provide a secure key exchange technique that does not assume a random oracle.

The key exchange system of the present invention includes at least a key exchange device α and a key exchange device β. Here, kappa is an integer, p is a kappa-bit prime number, G and G _T is of order p group, g is the original creation of the group G, g _T is generator of the group G _T, e is G × G → G A bilinear mapping that maps like _T , F_σ is a pseudo-random function that converts an integer of arbitrary length into an integer of κ bits according to the value σ of the specified key space Kspace, Ext is an element of the group G in the key space Kspace Strong random extractor that converts to a value, D is an integer, d is an integer between 1 and D, gen is a key generation algorithm for a disposable signature in which the bit length of the verification key is D, sig is the bit length of the verification key Is a signature generation algorithm for a disposable signature in which D is D, ver is an algorithm for verification of a disposable signature in which the bit length of the verification key is D, att ′ is an integer indicating the total number of elements of the attribute, and W _d _R is 1-bit information indicating the dth dummy attribute Symbol indicating that it is a more bit string R, P _n is an attribute element indicating attributes, the set of attribute set S _A is the attribute element P _n indicating the attribute of the key exchange apparatus alpha, access structure A _A key exchange apparatus alpha is _A set of combinations of attribute elements P _n to be obtained from the key exchange device β, the injection labeling function ρ _A is a function indicating the access structure A _A , and the attribute set ρ _A (i) is an i-th corresponding to the access structure A _A The set, share information generation matrix M _A is a matrix of L _A rows N _A columns in which the i-th row corresponds to the attribute set ρ _A (i), and (M _A ) _i is the i-th row of the share information generation matrix M _A corresponding set of vectors, attribute set S _B is the set of attributes element P _n indicating the attribute of the key exchange apparatus beta, access structure a _B is the attribute element P _n key exchange apparatus beta seek key exchange apparatus α combined, single morphism labeling function [rho _B is the access structure A The function shown, attribute set [rho _{B (i)} is the access structure A i-th set corresponding to _B, share information generator matrix M _B is the i-th row corresponds to a set of attributes ρ _{B (i)} L _B rows N A matrix of _B columns, (M _B ) _i is a vector corresponding to the i-th row of the share information generation matrix M _B , L _A , N _A , L _B and N _B are integers, and n _A is the key exchange device α _A predetermined integer 1 to N _A shared by the key exchange device β, n _B is a predetermined integer 1 to N _B shared by the key exchange device α and the key exchange device β, k _A is an element of the attribute set S _A , k _B is an element of the attribute set S _B , r and z are integers from 0 to p−1, h [1],..., H [att ′] are elements of the group G, _{(g, g ^ r, g} T ^ z, h [1], ..., h [att ']) is a master public key, g ^ z is a master secret key, _{t a} Is an integer between 0 and p−1, t _B is an integer between 0 and p−1, S ′ _A = g ^ z · g ^ (rt _A ), S ′ _B = g ^ z · g ^ (rt _B ), T _A = g ^ t _A , T _B = g ^ t _B , S _A [k _A ] = h [k _A ] ^ t _A , S _B [k _B ] = h [k _B ] ^ t _B , {S _A } is a set of S _A [k _A ], {S _B } is a set of S _B [k _B ], {U _i } is a set of U _i , {X _i } is a set of X _i , {V _i } is a set of V _i , {Y _i } is a set of Y _i , ^ is a symbol indicating a power, and (+) is a symbol indicating an exclusive OR for each bit.

The key exchange device α includes a first recording unit, a first access structure determination unit, a first short-term secret key generation unit, a first exchange information generation unit, a first transmission unit, a first reception unit, a first reception unit, A secret information acquisition unit, a first attribute confirmation unit, a first session key calculation unit, and a first intermediate information deletion unit. The key exchange device β includes a second recording unit, a second access structure determination unit, a second short-term secret key generation unit, a second exchange information generation unit, a second transmission unit, a second reception unit, A second secret information acquisition unit, a second attribute confirmation unit, a second session key calculation unit, and a second intermediate information deletion unit. The first recording unit records S ′ _A , T _A , {S _A } as the long-term secret key. The second recording unit records S ′ _B , T _B , {S _B } as the long-term secret key.

The first access structure determination unit determines the access structure A _A , generates the disposable public key vk _A and the disposable secret key sk _A according to the disposable signature key generation algorithm gen, and sets the dummy attribute set W _A = {W _{1 _vk A1, ..., W d} _vk Ad, ..., W D _vk AD} ( however, _{vk Ad} is d-th bit of the disposable public key vk _a) to set the. Then, a share information generation matrix M _A and a linear labeling function ρ _A of the linear secret sharing method corresponding to a condition satisfying the access structure A _A or all the dummy attributes W ₁ —vk A ₁ ,..., W _D —vk _AD are generated. .

The first short-term private key generation unit, 1 ≦ j ≦ _N u = the u_j from 0 or p-1 following integer selected randomly for _{A (u_1, ..., u_N A} ) and the x 0 or p selected -1 from the integer randomly selected randomly x _i from 0 or p-1 an integer for 1 ≦ i ≦ L _a.

The first exchange information generation unit calculates the inner product of the vector u and the vector (M _A ) _i for 1 ≦ i ≦ L _A to obtain a share λ _Ai . Then, the U = g ^ u_n _A and X = g ^ x, the _{1 ≦ i ≦ L A U i} = g ^ (rλ Ai) h [ρ A (i)] ^ (- x i) and _X i = g ^ x _i is calculated, and a disposable signature s _A is generated with sk _A as a key and (U, {U _i }, X, {X _i }) as a message in accordance with the signature generation algorithm sig of the disposable signature.

The first transmitting unit transmits EPK _A = (U, {U _i }, X, {X _i }, M _A , ρ _A , vk _A , s _A ) to the key exchange device β. The first receiving unit receives EPK _B = (V, {V _i }, Y, {Y _i }, M _B , ρ _B , vk _B , s _B ) from the key exchange device β.

The first secret information acquisition _unit, I A =: the _{{i ρ B (i) ∈S} A} the set _{I A} and _{I 'A = {i: ρ} B (i) ∈W B} to become set I 'seek _a, the correctness share the set {lambda _Bi} of secret information v_n _B corresponding to share information generator matrix _{M B,}

An integer w _Ai and an integer w ′ _Ai of 0 or more and p−1 or less that _satisfy is obtained.

First attribute confirmation section are that the attribute set _{S A} to confirm meets share information generator matrix _{M B} and injective labeling function _{ρ B, V, {V i} }, Y, all _{{Y i}} Is true for group G, and vk _B is the key and (V, {V _i }, Y, {Y _i }, s _B ) is the message according to the disposable signature verification algorithm. about,

Confirm that
The first session key calculation unit

σ ₁ = (g _T ^ z) ^ u_n _A
σ ₃ = e (g ^ r, Y) ^ x
Σ ′ ₁ ← Ext (σ ₁ ), σ ′ ₂ ← Ext (σ ₂ ), σ ′ ₃ ← Ext (σ ₃ ) are calculated, and the session identifier sid is set to (EPK _A , EPK _B ) Session key K
K = F_σ ′ ₁ (sid) (+) F_σ ′ ₂ (sid) (+) F_σ ′ ₃ (sid)
Seek like.

The first intermediate information erasure unit includes at least u_j (1 ≦ j ≦ N _A ), x, x _i (1 ≦ i ≦ L _A ), EPK _A , EPK _B , σ ₁ , σ ₂ , σ ₃ , σ ′. ₁ , σ ′ ₂ , σ ′ ₃ , sid, sk _A are deleted.

The second access structure determination unit determines the access structure A _B , generates the disposable public key vk _B and the disposable secret key sk _B according to the key generation algorithm gen of the disposable signature, and sets the dummy attribute set W _B = {W _{1 _vk B1, ..., W d} _vk Bd, ..., W D _vk BD} ( however, _{vk Bd} disposable public key vk d th bit of _B) setting a. Then, a share information generation matrix M _B and a linear labeling function ρ _B of the linear secret sharing method corresponding to the conditions satisfying the access structure A _B or all the dummy attributes W ₁ —vk _{B 1} ,..., W _D —vk _BD are generated. .

The second short-term secret key generating _{unit, 1 ≦ j ≦ N B v} = (v_1, ..., v_N B) a v_j from 0 or p-1 following integer selected randomly for a, a y 0 or p selected -1 from the integer randomly selected randomly y _i from 0 or p-1 an integer for 1 ≦ i ≦ L _B.

The second exchange information generation unit calculates the inner product of the vector v and the vector (M _B ) _i for 1 ≦ i ≦ L _{B and} sets it as the share λ _Bi . Then, a V = g ^ v_n _B and Y = g ^ y, for _{1 ≦ i ≦ L B V i} = g ^ (rλ Bi) h [ρ B (i)] ^ (- y i) and _Y i = g ^ y _i is calculated, and a disposable signature s _B having sk _B as a key and (V, {V _i }, Y, {Y _i }) as a message is generated according to the signature generation algorithm sig of the disposable signature.

The second transmitting unit transmits EPK _B = (V, {V _i }, Y, {Y _i }, M _B , ρ _B , vk _B , s _B ) to the key exchange device α. The second receiving unit receives EPK _A = (U, {U _i }, X, {X _i }, M _A , ρ _A , vk _A , s _A ) from the key exchange device α.

The second secret information acquiring _{unit, I B = {i: ρ} A (i) ∈S B} to become set _{I B} and _{I 'B = {i: ρ} A (i) ∈W A} to become set I ' _B is obtained, and a valid share set {λ _Ai } of the secret information u_n _A corresponding to the share information generation matrix M _A is obtained.

An integer w _Bi and an integer w ′ _Bi that satisfy 0 or more and p−1 or less are obtained.

The second attribute confirmation unit confirms whether the attribute set S _B satisfies the share information generation matrix M _A and the injection labeling function ρ _A , and all of U, {U _i }, X, and {X _i } Is true for group G, and vk _A is the key and (U, {U _i }, X, {X _i }, s _A ) is the message according to the algorithm for verifying the disposable signature. about,

Confirm that
The second session key calculator is

σ ₂ = (g _T ^ z) ^ v_n _B
σ ₃ = e (g ^ r, X) ^ y
Σ ′ ₁ ← Ext (σ ₁ ), σ ′ ₂ ← Ext (σ ₂ ), σ ′ ₃ ← Ext (σ ₃ ) are calculated, and the session identifier sid is set to (EPK _A , EPK _B ) Session key K
K = F_σ ′ ₁ (sid) (+) F_σ ′ ₂ (sid) (+) F_σ ′ ₃ (sid)
Seek like.

The second intermediate information erasure unit includes at least v_j (1 ≦ j ≦ N _B ), y, y _i (1 ≦ i ≦ L _B ), EPK _A , EPK _B , σ ₁ , σ ₂ , σ ₃ , σ ′. ₁ , σ ′ ₂ , σ ′ ₃ , sid, sk _B are deleted.

The key exchange system of the present invention may further include a key generation device having a master key generation unit and a long-term secret key generation unit. In this case, the master key generation unit, r, z, h [1 ], ..., h the [att '] selected at random, master public key _{(g, g ^ r, g} T ^ z, h [1 ],..., H [att ']) and the master secret key g ^ z. If the long-term secret key generation unit randomly selects t _A and t _B , and calculates S ′ _A and S ′ _B , T _A and T _B , S _A [k _A ] and S _B [k _B ]. Good.

According to the key exchange system of the present invention, when performing key extraction (generation of a long-term secret key) by using the linear secret sharing method, the key generation device performs attribute sets S _A and S of the key exchange devices α and β. Based on _B , long-term secret keys (S ′ _A , T _A , {S _A }) and (S ′ _B , T _B , {S _B }) are issued as share information of the linear secret sharing scheme. Further, by assigning linear secret sharing access structures A _A and A _B as access policies at the time of key exchange, it is possible to designate the other party's access policy at the time of key exchange. In addition, the master secret key g ^ z and the master public key of the present invention _{(g, g ^ r, g} T ^ z, h [1], ..., h [att ']) is, because it is independent of the attribute set, attribute There is no need to predetermine the entire set. That is, a long-term secret key can be issued based on an arbitrary attribute at the time of key extraction. Therefore, an effect equivalent to that of Non-Patent Document 1 can be obtained.

  Furthermore, by using a disposable signature, a strong random extractor, and a pseudo-random function, safety can be ensured without assuming a random oracle as follows. A user who performs key exchange prepares a dummy attribute set W in addition to his / her own attribute set S used for authentication, and assigns W to the value of the verification key of the generated disposable signature. At this time, in addition to the access structure A that the other party desires to satisfy, the user adds an access structure that satisfies the dummy attribute set W corresponding to the specific verification key as an authentication condition, and performs key exchange. The dummy attribute set W is not used in a key exchange session between actual users. However, the secret key corresponding to the attribute set satisfying the access structure A can be obtained by using the authentication condition of the dummy attribute set W when determining whether the message sent in the security certificate is correct. Can be judged without knowledge. Also, when deriving the last session key, a strong random extractor and a pseudo-random function are used instead of a random oracle. Specifically, the output of the shared information is leveled by a strong random extractor, and the output is used as a session key by using the value as a key of a pseudo-random function. Thus, in the present invention, safety can be maintained without assuming a random oracle.

The figure which shows the structural example of the key exchange system of Japanese Patent Application No. 2010-259053. The figure which shows the function structural example of the key exchange apparatus of Japanese Patent Application No. 2010-259053. The figure which shows the function structural example of the key generation apparatus of Japanese Patent Application No. 2010-259053. The figure which shows the example of the processing flow of the production | generation of the master private key of Japanese Patent Application No. 2010-290553, a master public key, and a long-term private key. The figure which shows the example of the flow of the process of the key exchange which shares the session key of Japanese Patent Application No. 2010-259053. The figure which shows the structural example of the key exchange system of this invention. The figure which shows the function structural example of the key exchange apparatus of this invention. The figure which shows the function structural example of the key generation apparatus of this invention. The figure which shows the example of the processing flow of the production | generation of the master private key of this invention, a master public key, and a long-term private key. The figure which shows the example of the flow of the process of the key exchange which shares the session key of this invention.

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

[Preparation]
Before describing the key exchange system of the present invention, the theory necessary for understanding the present invention will be described. In the present invention, the access policy is expressed as the following access structure.

_{First, {P 1, P 2,} ..., P n, ..., P N} and a set of attributes. However, N is an integer, n is an integer from 1 to N. P _n indicates an attribute of the user (user) of the key generation device such as “gender is male” or “employee of XX company”. In the following description, “the attribute of the user of the key generation device” is simply expressed as “the attribute of the key generation device”. The access structure is represented as a power set A of a non-empty subset of {P ₁ , P ₂ ,..., P _N }. That is,
A⊆2 ^ {P ₁ , P ₂ ,..., P _N } \ {φ}
However, “^” is a symbol indicating a power, “φ” is a symbol indicating an empty set, “\ {φ}” is a set belonging to the symbol indicating that an empty set is excluded, and a set not belonging is a disallowed set Called. In the present invention, in order to perform access control based on the above access structure, a linear secret sharing method is used as follows.

Share information corresponding to each attribute set is expressed as a vector on the set Z _P of 0 or more p-1 an integer. As a matrix for generating share information, a share information generation matrix M having L rows and N columns is prepared as follows. For i = 1,..., L, the i-th row of the share information generation matrix M is made to correspond to the attribute ρ (i) using the attribute labeling function ρ. The attribute labeling function ρ is a function that determines the attribute ρ (i) when i is specified. Further, “corresponding to the attribute ρ (i)” means, for example, 1, 1, 1, 0, 0,..., 0 if the attribute ρ (1) is P ₁ ∧P ₂ ∧P _3. Is set to the first row of the share information generation matrix M, and if the attribute ρ (2) is P ₁ ∧P _N , 2 of the share information generation matrix M such as 1, 0, 0,. In order to set the line, the i-th line is determined in association with the attribute ρ (i). In the above example, the element corresponding to the attribute P _n included in the AND condition is set to “1” and the element corresponding to the attribute P _n not included is set to “0”. However, the present invention is not limited to this. Since it is only necessary that the lines corresponding to the different conditions are associated with each other so as not to be the same line, the attribute labeling function ρ may be another correspondence within the range having the injectivity.

Next, r ₁ ,..., R _N are randomly selected from integers between 0 and p−1 to generate a vector v = (r ₁ ,..., R _N ) ^T. Here, T is a symbol indicating transposition. In addition, the n-th element r _n, which had been predetermined and secret information. In the case of devices that want to exchange keys, any information can be used as long as the information shared as secret information is the same, so it is sufficient to determine in advance what number of randomly selected integers should be used as secret information. . In this case, M is the vector of the L share information of secret information r _n. Share information (Mv) _i is assigned to the attribute set ρ (i). However, (Mv) _i indicates the i-th component of the vector Mv.

As described above, when the share information generation matrix M and the column vector v including the secret information are used, the linear recoverability of the linear secret sharing method can be used. Here, the linear recoverability will be described. Considering an access structure A, an attribute set S is an arbitrary permitted set of S∈A, and I⊂ {1, 2,..., L} is defined as I = {i: ρ (i) ∈S}. In this case, when {lambda _i} is the set of correct share information _{r n,}

There exists a set {w _i } of integers between 0 and p−1 such that Such a set {w _i } is known to be found in polynomial time of size M. On the other hand, if {λ _i } is not a set of correct share information of r _n , all elements of the set {w _i } cannot be obtained. In the present invention, as described above, by using the share information generation matrix M and the column vector v including the secret information, the session keys are exchanged using the linear recoverability of the linear secret sharing method.

[Constitution]
FIG. 6 shows a configuration example of the key exchange system of the present invention. The key exchange system according to the present invention includes key exchange devices 500 ₁ ,..., 500 _Q connected via a network 1000 (where Q is an integer of 2 or more, q is an integer of 1 to Q, and A and B are 1). The key generation device 600 is configured with different integers of Q or less. FIG. 7 shows a functional configuration example of the key exchange apparatus of the present invention, and FIG. 8 shows a functional configuration example of the key generation apparatus of the present invention. The key exchange device 500 _q includes an access structure determination unit 510 _q , a short-term secret key generation unit 520 _q , an exchange information generation unit 530 _q , a transmission unit 540 _q , a reception unit 545 _q , an attribute confirmation unit 550 _q , and a secret information acquisition unit 560. _q , a session key calculation unit 570 _q , an intermediate information deletion unit 580 _q , and a recording unit 590 _q . The key generation device 600 includes a master key generation unit 610, a long-term secret key generation unit 620, and a recording unit 690. In the following description, a case where the key exchange device 500 _A (corresponding to the key exchange device α) functions as an initiator, and the key exchange device 500 _B (corresponding to the key exchange device β) functions as a responder to share a session key. explain.

In the following description, kappa are integers, p is a kappa-bit prime number, G and G _T is the group of order p, g is generator of the group G, g _T is generator of the group G _T, e is G XG → GT A bilinear mapping that maps as _T , F_σ is a pseudo-random function that converts an integer of an arbitrary length into an integer of κ bits according to the value σ of the specified key space Kspace, Ext is an element of the group G A strong random extractor that converts the value of the key space Kspace, D is an integer (number of elements of dummy attributes), d is an integer between 1 and D, and gen is a disposable signature key whose verification key bit length is D Generation algorithm, sig is a signature generation algorithm for a disposable signature whose verification key bit length is D, ver is a disposable signature verification algorithm whose verification key bit length is D, and att 'is an attribute An integer indicating the total number of elements (actual attributes and The total number of elements combined both Me attribute), the W d _{_R} symbols (herein indicating that information indicating the d-th dummy attribute is a bit string R of one or more bits, and the bit string in the case of 1 bit referred to that), _{P n} is an attribute element indicating an attribute, attribute set _{S a} is the set of attributes element _{P n} indicating the attribute of the key exchange device 500 _a, the access structure _{a a} key exchange device 500 _a key exchange device 500 _B is a set of combinations of attribute elements P _n to be obtained, the injection labeling function ρ _A is a function indicating the access structure A _A , the attribute set ρ _A (i) is the i-th set corresponding to the access structure A _A , share information The generation matrix M _A is a matrix of L _A rows N _A columns in which the i-th row corresponds to the attribute set ρ _A (i), (M _A ) _i is a vector corresponding to the i-th row of the share information generation matrix M _A , attribute set _{S B} is the key exchange apparatus 5 0 set of attributes element _{P n} indicating the attribute of _B, the access structure _{A B} is the set of combinations of attributes element _{P n} key exchange device 500 _B is determined in the key exchange device 500 _A, injective labeling function [rho _B access structure A function indicating the _B, attribute set [rho _B (i) is the set of i-th corresponding to the access structure _{a B,} share information generator matrix _{M B} is the i-th row corresponds to a set of attributes ρ _B (i) _{L B} rows N matrix _{B column, (M B) i} vector corresponding to the i-th row share information generator matrix _{M B is} the _{L a, n a, L B} , n B is an integer, _{n a} key exchange device 500 _{a A} predetermined integer that is shared by the key exchange device 500 _B and not more than 1 N _A , n _B is a predetermined integer that is shared by the key exchange device 500 _A and the key exchange device 500 _B and is not more than 1 N _B , k _a is a set of attributes _{S a} element, _{k B} is the genus Element of the set _{S B,} r and z are 0 or p-1 an integer, _{t B} is 0 or p-1 an integer, h [1], ..., h [att '] is a group G based on, { S _A } is a set of S _A [k _A ], {S _B } is a set of S _B [k _B ], {U _i } is a set of U _i , {X _i } is a set of X _i , {V _i } Is a set of V _i , {Y _i } is a set of Y _i , ^ is a symbol indicating a power, and (+) is a symbol indicating an exclusive OR for each bit.

[Key generation, key extraction]
FIG. 9 shows an example of a processing flow for generating a master secret key, a master public key, and a long-term secret key. The long-term secret key generation process corresponds to key extraction. The master key generation unit 610 of the key generation device 600 randomly selects r and z from integers not less than 0 and not more than p−1, and randomly selects h [1],..., H [att ′] from the group G. Select. Then, the master public key _{(g, g ^ r, g} T ^ z, h [1], ..., h [att ']), the master secret key recorded in the recording unit 390 as g ^ z, master public key _{(g, g ^ r, g} T ^ z, h [1], ..., h [att ']) to publish a (S610). Key exchange unit 500 _A and the key exchange device 500 _B includes a master public respectively key _{(g, g ^ r, g} T ^ z, h [1], ..., h [att ']) receives, recording unit 590 _A and recorded in the recording section 590 _B (S591, S592).

The long-term secret key generation unit 620 randomly selects t _A from an integer of 0 or more and p−1 or less, and S ′ _A = g ^ z · g ^ (rt _A ), T _A = g ^ t _A , attribute set S _A [k _A ] = h [k _A ] ^ t _A is calculated for the element k _A of S _A , and (S ′ _A , T _A , {S _A }) is used as the long-term secret key for the key exchange apparatus 500 _A. to send (S620 _A). The key exchange device 500 _A receives the long-term secret key (S ′ _A , T _A , {S _A }) and records it in the recording unit 590 _A (S 592 _A ).

Further, the long-term secret key generation unit 620 randomly selects t _B from integers of 0 or more and p−1 or less, and S ′ _B = g ^ z · g ^ (rt _B ), T _B = g ^ t _B , S _B [k _B ] = h [k _B ] ^ t _B is calculated for the element k _B of the attribute set S _B and (S ′ _B , T _B , {S _B }) is used as the long-term secret key 500. to send to _B (S620 _B). The key exchange device 500 _B receives the long-term secret key (S ′ _B , T _B , {S _B }) and records it in the recording unit 590 _B (S 592 _B ).

In addition, the master public key in the recording section 590 _A of the pre-key exchange apparatus _{500 A (g, g ^ r} , g T ^ z, h [1], ..., h [att ']) and the long-term secret key (S' _{A , T a, {S a}} ) with is recorded, the master public key _(g in the recording unit 590 _B key exchange device _{500 B, g ^ r, g} T ^ z, h [1], ..., h [att ')) And the long-term secret key (S' _B , T _B , {S _B }) are recorded, the key exchange device 500 _A and the key exchange device 500 _B connected via the network 1000 are the minimum. A limited key exchange system can be configured.

[Key exchange]
FIG. 10 shows an example of a flow of key exchange processing for sharing a session key. In this example, the key exchange device 500 _A (corresponding to the key exchange device α) functions as an initiator, and the key exchange device 500 _B (corresponding to the key exchange device β) functions as a responder.

Key exchange unit 500 _A, the access structure determination unit 510 _A (first access structure determination unit), the short-term private key generation unit 520 _A (first short-term private key generation unit), exchanging information generating unit 530 _A (first Exchange information generation unit), transmission unit 540 _A (first transmission unit), reception unit 545 _A (first reception unit), attribute confirmation unit 550 _A (first attribute confirmation unit), secret information acquisition unit 560 _A (first secret information acquisition unit), session key calculation unit 570 _A (first session key calculation unit), intermediate information deletion unit 580 _A (first intermediate information deletion unit), recording unit 590 _A (first Recording section). The key exchange device 500 _B includes an access structure determination unit 510 _B (second access structure determination unit), a short-term secret key generation unit 520 _B (second short-term secret key generation unit), and an exchange information generation unit 530 _B (second Exchange information generation unit), transmission unit 540 _B (second transmission unit), reception unit 545 _B (second reception unit), attribute confirmation unit 550 _B (second attribute confirmation unit), secret information acquisition unit 560 _B (second secret information acquisition unit), session key calculation unit 570 _B (second session key calculation unit), intermediate information deletion unit 580 _B (second intermediate information deletion unit), recording unit 590 _B (second Recording section).

In key exchange device 500 _A, a recording unit 590 _A is recording S _'A long-term private key, _T A, the _{{S A}.} The access structure determination unit 510 _A determines the access structure A _A , generates the disposable public key vk _A and the disposable secret key sk _A according to the disposable signature key generation algorithm gen, and sets the dummy attribute set W _A = {W _{1 _vk A1, ..., W d _vk} Ad, ..., W D _vk AD} ( however, _{vk Ad} is d-th bit of the disposable public key vk _a) to set the. Then, the share information generation matrix M _A and the injection labeling function ρ _A of the linear secret sharing method corresponding to the conditions satisfying the access structure A _A or all the dummy attributes W ₁ —vk A ₁ ,..., W _D —vk _AD are generated ( S510 _A ).

Short-term private key generation unit 520 _A is, 1 ≦ j ≦ _N a u_j for _A be selected at random from 0 or p-1 an integer u = (u_1, ..., u_N A) and then, the x 0 or p- selected randomly from 1 an integer, 1 ≦ i ≦ _{L a} selected randomly _{x i} from 0 or p-1 an integer for (S520 _a).

Exchanging information generating unit 530 _A is a 1 ≦ i ≦ _{L A} for vectors u and vector _{(M A)} by calculating the inner product of the _i share lambda _Ai. And
U = g ^ u_n _A
X = g ^ x
_{U i = g ^ (rλ Ai} ) h [ρ A (i)] ^ (- x i) , however, 1 ≦ i ≦ _{L A}
X _i = g ^ _{x i,} however, 1 ≦ i ≦ _{L A}
And a disposable signature s _A having sk _A as a key and (U, {U _i }, X, {X _i }) as a message is generated in accordance with the signature generation algorithm sig of the disposable signature (S530 _A ).

The first transmission unit 540 _A transmits EPK _A = (U, {U _i }, X, {X _i }, M _A , ρ _A , vk _A , s _A ) to the key exchange apparatus 500 _B (S540). _A ).

On the other hand, in key exchange apparatus 500 _B , recording unit 590 _B records S ′ _B , T _B , {S _B } as long-term secret keys. Then, the access structure determination unit 510 _B determines the access structure A _B , generates the disposable public key vk _B and the disposable secret key sk _B according to the key generation algorithm gen of the disposable signature, and sets the dummy attribute set W _B = { _{W 1 _vk B1, ..., W} d _vk Bd, ..., W D _vk BD} ( however, _{vk Bd} disposable public key vk d th bit of _B) setting a. Then, a share information generation matrix M _B and a linear labeling function ρ _B of the linear secret sharing method corresponding to the conditions satisfying the access structure A _B or all the dummy attributes W ₁ —vk _{B 1} ,..., W _D —vk _BD are generated ( S510 _B ).

Short-term private key generation unit 520 _B is, 1 ≦ j ≦ about _{N B} a v_j be selected at random from 0 or p-1 an integer v = (v_1, ..., v_N B) and then, the y 0 or p- selected randomly from 1 an integer, selected randomly _{y i} from 0 or p-1 an integer for _{1 ≦ i ≦ L B (S520} B).

Exchanging information generating unit 530 _B is a share lambda _Bi calculates the inner product between the vector v and the vector _{(M B) i} for 1 ≦ i ≦ _{L B.} And
V = g ^ v_n _B
Y = g ^ y
V _i = g ^ (rλ _Bi ) h [ρ _B (i)] ^ (− y _i ) where 1 ≦ i ≦ L _B
Y _i = g ^ y _i where 1 ≦ i ≦ L _B
, And generates a disposable signature s _B with sk _B as a key and (V, {V _i }, Y, {Y _i }) as a message according to the signature generation algorithm sig (S530 _B ).

The transmission unit 540 _B transmits EPK _B = (V, {V _i }, Y, {Y _i }, M _B , ρ _B , vk _B , s _B ) to the key exchange device 500 _A (S 540 _B ).

The receiving unit 545 _B receives EPK _A = (U, {U _i }, X, {X _i }, M _A , ρ _A , vk _A , s _A ) from the key exchange device 500 _A (S 545 _B ). .

The attribute confirmation unit 550 _B confirms whether the attribute set S _B satisfies the share information generation matrix M _A and the injection labeling function ρ _A. And when it is judged that it does not satisfy | fill, a process is stopped. If it is determined that satisfied, the process proceeds to step S560 _B (S551 _B).

The secret information acquisition unit 560 _{B is,} I B =: the _{{i ρ A (i) ∈S} B} set _{I B} and _{I 'B = {i: ρ} A (i) ∈W A} to become set I' _{Find B.} Then, for a valid share set {λ _Ai } of the secret information u_n _A corresponding to the share information generation matrix M _A ,

Determining zero or more p-1 an integer _{w Bi} and integer w _'Bi which holds (S560 _B). As described above, n _A may be an integer between 1 and N _A that is predetermined and shared by the key exchange device 500 _A and the key exchange device 500 _B. For example, n _A = 1 may be set.

The attribute confirmation unit 550 _B determines that all of U, {U _i }, X, and {X _i } are elements of the group G, uses vk _A as a key according to the algorithm for verifying the disposable signature, and (U, {U _i }, X, {X _i }, s _A ) as a message, the result of verification is true,

Confirm that If any of the conditions is not satisfied, the process is stopped. If that satisfies all of the conditions, the process proceeds to step S370 _B (S352 _B).
Session key calculation unit 570 _B

σ ₂ = (g _T ^ z) ^ v_n _B
σ ₃ = e (g ^ r, X) ^ y
Calculate Then, σ ′ ₁ ← Ext (σ ₁ ), σ ′ ₂ ← Ext (σ ₂ ), σ ′ ₃ ← Ext (σ ₃ ) are calculated, and the session identifier sid is set to (EPK _A , EPK _B ). Furthermore, the session key K is
K = F_σ ′ ₁ (sid) (+) F_σ ′ ₂ (sid) (+) F_σ ′ ₃ (sid)
(S570 _B ).

The intermediate information erasing unit 580 _B has at least v_j (1 ≦ j ≦ N _B ), y, y _i (1 ≦ i ≦ L _B ), EPK _A , EPK _B , σ ₁ , σ ₂ , σ ₃ , σ ′ ₁ , Σ ′ ₂ , σ ′ ₃ , sid, sk _B are erased (S580 _B ). In general, all values used during the calculation other than the session key K may be deleted.

It returns to the processing of the key exchange unit 500 _A. The receiving unit 545 _A receives EPK _B = (V, {V _i }, Y, {Y _i }, M _B , ρ _B , vk _B , s _B ) from the key exchange apparatus 500 _B (S 545 _A ). .

The attribute confirmation unit 550 _A confirms whether the attribute set S _A satisfies the share information generation matrix M _B and the injection labeling function ρ _B. And when it is judged that it does not satisfy | fill, a process is stopped. If it is determined that satisfied, the process proceeds to step S560 _A (S551 _A).

The secret information acquisition unit 560 _{A may, I A = {i: ρ} B (i) ∈S A} to become set _{I A} and _{I 'A = {i: ρ} B (i) ∈W B} to become set I' _{Find A.} Then, the correctness share a set of secret information v_n _B corresponding to share information generator matrix _{M B {λ Bi},}

Determining zero or more p-1 an integer _{w Ai} and integer w _'Ai which holds (S560 _A). As described above, _{n B} may be any predetermined one or more _{N B} an integer that is shared by a key exchange device 500 _A and the key exchange device 500 _B. For example, n _B = 1 may be set.

The attribute confirmation unit 550 _A determines that all of V, {V _i }, Y, and {Y _i } are elements of the group G, and uses vk _B as a key according to the algorithm for verifying the disposable signature (V, {V _i }, Y, {Y _i }, s _B ) as a message, the result of verification is true,

Confirm that If any of the conditions is not satisfied, the process is stopped. If that satisfies all of the conditions, the process proceeds to step S570 _A (S552 _A).
The session key calculating unit 570 _A is,

σ ₁ = (g _T ^ z) ^ u_n _A
σ ₃ = e (g ^ r, Y) ^ x
Calculate Then, σ ′ ₁ ← Ext (σ ₁ ), σ ′ ₂ ← Ext (σ ₂ ), σ ′ ₃ ← Ext (σ ₃ ) are calculated, and the session identifier sid is set to (EPK _A , EPK _B ). Furthermore, the session key K is
K = F_σ ′ ₁ (sid) (+) F_σ ′ ₂ (sid) (+) F_σ ′ ₃ (sid)
(S570 _A ).

Intermediate information erasing unit 580 _A is at least _{u_j (1 ≦ j ≦ N A} ), x, x i (1 ≦ i ≦ L A), EPK A, EPK B, σ 1, σ 2, σ 3, σ '1 , Σ ′ ₂ , σ ′ ₃ , sid, sk _A are deleted (S580 _A ). In general, all values used during the calculation other than the session key K may be deleted.

[Confirmation]
Finally key exchange device 100 _A and the key exchange device 100 _B is a session key K acquired will be described equal.

σ ₃ = e (g ^ r, X) ^ y
= G _T ^ (rxy) = e (g ^ r, Y) ^ x
Therefore, the session key can be correctly shared.

According to the key exchange system of the present invention, when performing key extraction (generation of a long-term secret key) by using the linear secret sharing method, the key generation device performs the attribute set S _{A of the} key exchange devices 500 _A and 500 _B. , S _B , long-term secret keys (S ′ _A , T _A , {S _A }), (S ′ _B , T _B , {S _B }) are issued as share information of the linear secret sharing scheme. Further, by assigning linear secret sharing access structures A _A and A _B as access policies at the time of key exchange, it is possible to designate the other party's access policy at the time of key exchange. In addition, the master secret key g ^ z and the master public key of the present invention _{(g, g ^ r, g} T ^ z, h [1], ..., h [att ']) is, because it is independent of the attribute set, attribute There is no need to predetermine the entire set. That is, a long-term secret key can be issued based on an arbitrary attribute at the time of key extraction. Therefore, an effect equivalent to that of Non-Patent Document 1 can be obtained.

  Furthermore, by using a disposable signature, a strong random extractor, and a pseudo-random function, safety can be ensured without assuming a random oracle as follows. A user who performs key exchange prepares a dummy attribute set W in addition to his / her own attribute set S used for authentication, and assigns W to the value of the verification key of the generated disposable signature. At this time, in addition to the access structure A that the other party desires to satisfy, the user adds an access structure that satisfies the dummy attribute set W corresponding to the specific verification key as an authentication condition, and performs key exchange. The dummy attribute set W is not used in a key exchange session between actual users. However, when determining whether or not the message sent in the security certificate is correct, the authentication condition of the dummy attribute set W is used to determine the secret key corresponding to the attribute set satisfying the access structure A. Can be judged without knowledge. Also, when deriving the last session key, a strong random extractor and a pseudo-random function are used instead of a random oracle. Specifically, the output of the shared information is leveled by a strong random extractor, and the output is used as a session key by using the value as a key of a pseudo-random function. Thus, in the present invention, safety can be maintained without assuming a random oracle.

[Program, recording medium]
The various processes described above are not only executed in time series according to the description, but may also be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes. Needless to say, other modifications are possible without departing from the spirit of the present invention.

  Further, when the above-described configuration is realized by a computer, processing contents of functions that each device should have are described by a program. The processing functions are realized on the computer by executing the program on the computer.

  The program describing the processing contents can be recorded on a computer-readable recording medium. As the computer-readable recording medium, 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.

  The present invention can be used for encrypted communication in which a session key is shared between two parties.

100 _q , 500 _q Key exchange device 110 _q , 510 _q Access structure determination unit 120 _q , 520 _q Short-term secret key generation unit 130 _q , 530 _q Exchange information generation unit 140 _q , 540 _q transmission unit 145 _q , 545 _q reception unit 150 _q , 550 _q attribute confirmation unit 160 _q , 560 _q secret information acquisition unit 170 _q , 570 _q session key calculation unit 180 _q , 580 _q intermediate information deletion unit 190 _q , 390, 590 _q , 690 recording unit 300, 600 key Generation devices 310 and 610 Master key generation units 320 and 620 Long-term secret key generation unit 1000 Network

Claims (8)

A key exchange system comprising at least a key exchange device α and a key exchange device β, and exchanging session keys,
κ is an integer, p is κ-bit prime, G and _{G T} is the group of order p, g is generator of the group G, _{g T} is generator of the group _{G T,} e is as G × G → _{G T} F_σ is a pseudo-random function that converts an integer of arbitrary length into an integer of κ bits according to the specified key space Kspace value σ, and Ext converts an element of the group G into a value of the key space Kspace Strong random extractor, D is an integer, d is an integer between 1 and D, gen is a key generation algorithm for a disposable signature such that the bit length of the verification key is D, sig is the bit length of the verification key is D An algorithm for generating a signature for a disposable signature, ver is an algorithm for verifying a disposable signature in which the bit length of the verification key is D, att ′ is an integer indicating the total number of elements of the attribute, and W _d _R is the d th The information indicating the dummy attribute is a bit of 1 bit Symbol indicating the Tsu preparative column R, P _n is an attribute element indicating attributes, the set of attribute set S _A is the attribute element P _n indicating the attribute of the key exchange apparatus alpha, access structure A _A key exchange apparatus alpha is _A set of combinations of attribute elements P _n to be obtained from the key exchange device β, the injection labeling function ρ _A is a function indicating the access structure A _A , and the attribute set ρ _A (i) is an i-th corresponding to the access structure A _A The set, share information generation matrix M _A is a matrix of L _A rows N _A columns in which the i-th row corresponds to the attribute set ρ _A (i), and (M _A ) _i is the i-th row of the share information generation matrix M _A corresponding set of vectors, attribute set S _B is the set of attributes element P _n indicating the attribute of the key exchange apparatus beta, access structure a _B is the attribute element P _n key exchange apparatus beta seek key exchange apparatus α combined, single morphism labeling function [rho _B indicates the access structure a _B The number, the attribute set [rho _B (i) is _{L B} rows _{N B} columns corresponding to the access i-th set corresponding to the structure _{A B,} share information generator matrix _{M B} is the i-th row is the attribute set [rho _B (i) (M _B ) _i is a vector corresponding to the i-th row of the share information generation matrix M _B , L _A , N _A , L _B and N _B are integers, n _A is the key exchange device α and the key _A predetermined integer 1 to N _A shared by the exchange device β, n _B is a predetermined integer 1 to N _B shared by the key exchange device α and the key exchange device β, and k _A is Elements of the attribute set S _A , k _B are elements of the attribute set S _B , r and z are integers from 0 to p−1, h [1],..., H [att ′] are elements of the group G, _{, g ^ r, g T ^} z, h [1], ..., h [att ']) is a master public key, g ^ z is a master secret key, _{t a} is greater than or equal to 0 p-1 or less, t _B is an integer of 0 or more and p-1 or less, S ′ _A = g ^ z · g ^ (rt _A ), S ′ _B = g ^ z · g ^ (rt _B ), T _{A = g ^ t A, T} B = g ^ t B, S A [k A] = h [k A] ^ t A, S B [k B] = h [k B] ^ t B, {S A } Is a set of S _A [k _A ], {S _B } is a set of S _B [k _B ], {U _i } is a set of U _i , {X _i } is a set of X _i , {V _i } is A set of V _i , {Y _i } is a set of Y _i , ^ is a symbol indicating a power, (+) is a symbol indicating a bitwise exclusive OR,
The key exchange device α
_A first recording unit for recording S ′ _A , T _A , {S _A } as a long-term secret key;
An access structure A _A is determined, a disposable public key vk _A and a disposable secret key sk _A are generated according to a key generation algorithm gen for a disposable signature, and a dummy attribute set W _A = {W ₁ —vk A ₁ ,..., W _d —vk _{Ad, ..., W D _vk AD} } ( however, _{vk Ad} is d-th bit of the disposable public key vk _a) is set and the access structure _{a a} or all of the dummy attributes _{W 1 _vk A1, ..., W} D _vk _A first access structure determination unit that generates a share information generation matrix M _A and a bijective labeling function ρ _A of a linear secret sharing method corresponding to a condition satisfying _AD ;
_{1 ≦ j ≦ N A u =} (u_1, ..., u_N A) a u_j from 0 or p-1 following integer selected randomly for a, selected at random x from 0 or p-1 an integer _A first short-term secret key generation unit that randomly selects x _i from 0 to p−1 for 1 ≦ i ≦ LA;
1 ≦ i ≦ _{L A} computes the inner product of the vectors u and vector _{(M A) i} and share lambda _Ai for, U = g ^ and U_n _A and X = g ^ x, U for 1 ≦ i ≦ _{L A i} = g ^ (rλ _Ai ) h [ρ _A (i)] ^ (− x _i ) and X _i = g ^ x _i are calculated, and sk _A is keyed according to the algorithm sig for signature generation of the disposable signature, ( U, {U _i }, X, {X _i }) as a message, a first exchange information generation unit that generates a disposable signature s _A ;
_A first transmitter that transmits EPK _A = (U, {U _i }, X, {X _i }, M _A , ρ _A , vk _A , s _A ) to the key exchange device β;
A first receiving unit for receiving EPK _B = (V, {V _i }, Y, {Y _i }, M _B , ρ _B , vk _B , s _B ) from the key exchange device β;
I _A =: the _{{i ρ B (i) ∈S} A} the set _{I A} and _{I 'A = {i: ρ} B (i) ∈W B} to become set I' obtains the _A, share information generator matrix For a valid share set {λ _Bi } of secret information v_n _B corresponding to M _B ,

A first secret information acquisition unit for obtaining an integer w _Ai and an integer w ′ _Ai of 0 or more and p−1 or less for which
Check whether the attribute set S _A satisfies the share information generation matrix M _B and the injection labeling function ρ _B , and that all of V, {V _i }, Y, {Y _i } are elements of the group G The result of verifying vk _B as a key and (V, {V _i }, Y, {Y _i }, s _B ) as a message according to the algorithm for verifying the disposable signature is true,

A first attribute confirmation unit for confirming that

σ ₁ = (g _T ^ z) ^ u_n _A
σ ₃ = e (g ^ r, Y) ^ x
Σ ′ ₁ ← Ext (σ ₁ ), σ ′ ₂ ← Ext (σ ₂ ), σ ′ ₃ ← Ext (σ ₃ ) are calculated, and the session identifier sid is set to (EPK _A , EPK _B ) Session key K
K = F_σ ′ ₁ (sid) (+) F_σ ′ ₂ (sid) (+) F_σ ′ ₃ (sid)
A first session key calculation unit to be obtained as follows:
At least u_j (1 ≦ j ≦ N _A ), x, x _i (1 ≦ i ≦ L _A ), EPK _A , EPK _B , σ ₁ , σ ₂ , σ ₃ , σ ′ ₁ , σ ′ ₂ , σ ′ ₃ , Sid, sk _A , a first intermediate information erasing unit,
With
The key exchange device β
A second recording unit for recording S ′ _B , T _B , {S _B } as a long-term secret key;
An access structure A _B is determined, a disposable public key vk _B and a disposable secret key sk _B are generated according to a key generation algorithm gen for a disposable signature, and a dummy attribute set W _B = {W ₁ —vk _{B 1} ,..., W _d —vk _Bd ,..., W _{D —} vk _BD } (where vk _Bd is the d-th bit of the disposable public key vk _B ), and the access structure A _B or all dummy attributes W _{1 —} vk _B1 ,…, W _{D —} vk and a second access structure determination unit for generating a linear share information generator matrix secret sharing scheme M _B and injective labeling function [rho _B corresponding to the condition satisfying the _{BD,
1 ≦ j ≦ N B v =} (v_1, ..., v_N B) a v_j from 0 or p-1 following integer selected randomly for a, selected at random y from 0 or p-1 an integer a second short-term private key generation unit to select randomly y _i from 0 or p-1 an integer for 1 ≦ i ≦ L _B,
1 ≦ i ≦ _{L B} calculates the inner product between the vector v and the vector _{(M B) i} for a share _{λ Bi, V = g ^ v_n} B and Y = g ^ y and, V for 1 ≦ i ≦ _{L B i = g ^ (rλ Bi)} h [ρ B (i)] ^ (- y i) and _Y i = g ^ a _{y i} is calculated, the key to sk _B according to the algorithm sig of disposable signature signature generation, ( V, {V _i }, Y, {Y _i }) as a message, a second exchange information generating unit that generates a disposable signature s _B ;
A second transmitter that transmits EPK _B = (V, {V _i }, Y, {Y _i }, M _B , ρ _B , vk _B , s _B ) to the key exchange device α;
_A second receiving unit that receives EPK _A = (U, {U _i }, X, {X _i }, M _A , ρ _A , vk _A , s _A ) from the key exchange device α;
I _B =: the _{{i ρ A (i) ∈S} B} set _{I B} and I: seeking _{'B = {i ρ A (} i) ∈W A} to become set I' _B, share information generator matrix For a valid share set {λ _Ai } of secret information u_n _A corresponding to M _A ,

A second secret information acquisition unit that obtains an integer w _Bi and an integer w ′ _Bi that are equal to or greater than 0 and equal to or less than p−1.
Confirm that the attribute set S _B satisfies the share information generation matrix M _A and the injection labeling function ρ _A , and that all of U, {U _i }, X, {X _i } are elements of the group G The result of verifying vk _A as a key and (U, {U _i }, X, {X _i }, s _A ) as a message according to the algorithm for verifying the disposable signature is true,

A second attribute confirmation unit for confirming that

σ ₂ = (g _T ^ z) ^ v_n _B
σ ₃ = e (g ^ r, X) ^ y
Σ ′ ₁ ← Ext (σ ₁ ), σ ′ ₂ ← Ext (σ ₂ ), σ ′ ₃ ← Ext (σ ₃ ) are calculated, and the session identifier sid is set to (EPK _A , EPK _B ) Session key K
K = F_σ ′ ₁ (sid) (+) F_σ ′ ₂ (sid) (+) F_σ ′ ₃ (sid)
A second session key calculation unit to be obtained as follows:
At least v_j (1 ≦ j ≦ N _B ), y, y _i (1 ≦ i ≦ L _B ), EPK _A , EPK _B , σ ₁ , σ ₂ , σ ₃ , σ ′ ₁ , σ ′ ₂ , σ ′ ₃ , Sid, sk _B , a second intermediate information erasing unit,
A key exchange system. The key exchange system according to claim 1,
And a key generation device having a master key generation unit and a long-term secret key generation unit,
The r, z, h [1] , ..., h [att '] , the are those of the master key generation unit has been selected at random, master public key _{(g, g ^ r, g} T ^ z, h [ 1], ..., h [att ']) and the master secret key g ^ z are generated by the master key generation unit,
The t _A and t _B are randomly selected by the long-term secret key generation unit, and S ′ _A and S ′ _B , T _A and T _B , S _A [k _A ] and S _B [k _B ] are The long-term secret key generation unit is calculated,
The long-term secret key (S ′ _A , T _A , {S _A }) recorded by the key exchange device α is obtained from the key generation device, and is recorded by the key exchange device β. The long-term secret key (S ′ _B , T _B , {S _B }) is obtained from the key generation device. A key exchange device for exchanging session keys,
κ is an integer, p is κ-bit prime, G and _{G T} is the group of order p, g is generator of the group G, _{g T} is generator of the group _{G T,} e is as G × G → _{G T} F_σ is a pseudo-random function that converts an integer of arbitrary length into an integer of κ bits according to the specified key space Kspace value σ, and Ext converts an element of the group G into a value of the key space Kspace Strong random extractor, D is an integer, d is an integer between 1 and D, gen is a key generation algorithm for a disposable signature such that the bit length of the verification key is D, sig is the bit length of the verification key is D An algorithm for generating a signature for a disposable signature, ver is an algorithm for verifying a disposable signature in which the bit length of the verification key is D, att ′ is an integer indicating the total number of elements of the attribute, and W _d _R is the d th The information indicating the dummy attribute is a bit of 1 bit Symbol indicating the Tsu preparative column R, P _n is an attribute element indicating attributes, the set of attribute set S _A is the attribute element P _n indicating the attribute of the key exchange apparatus, the access structure A _A has the key exchange device _A set of combinations of attribute elements P _n required for a key exchange device to be exchanged with key, a bijective labeling function ρ _A corresponds to a function indicating the access structure A _A, and an attribute set ρ _A (i) corresponds to the access structure A _A I-th set, share information generation matrix M _A is a matrix of L _A rows and N _A columns in which i-th row corresponds to attribute set ρ _A (i), and (M _A ) _i is _i of share information generation matrix M _A The vector corresponding to the second row, the attribute set S _B is a set of attribute elements P _n indicating the attributes of the key exchange device to be exchanged, and the access structure A _B is the attribute element P required by the key exchange device to be exchanged. _n set of combination of, injection labeling Number [rho _B function indicating the access structure A _B, i th set attribute set [rho _{B (i)} is that corresponding to the access structure A _B, share information generator matrix M _B is the i-th row is the attribute set [rho _B ( i) a matrix of L _B rows and N _B columns corresponding to i), (M _B ) _i is a vector corresponding to the i th row of the share information generation matrix M _B , L _A , N _A , L _B and N _B are integers, shared n _a is predetermined by one or more, n _a less integer shared by the target key exchange device for the key exchange device and key exchange, n _B is subject to key exchange device for the key exchange device and key exchange A predetermined integer of 1 to N _B , k _A is an element of the attribute set S _A , k _B is an element of the attribute set S _B , r and z are integers of 0 to p−1, h [1], ..., h [att '] is the group G based _{on, (g, g ^ r,} g T ^ z, h [1], ..., h [att' ]) Is a master public key, g ^ z is a master secret key, _{t A} is greater than or equal to 0 p-1 an integer, _{t B} is greater than or equal to 0 p-1 an _{integer, S 'A = g ^ z} · g ^ ( rt _A ), S ′ _B = g ＾ z · g ^ (rt _B ), T _A = g ^ t _A , T _B = g ^ t _B , S _A [k _A ] = h [k _A ] ^ t _A , S _B [k _B ] = h [k _B ] ^ t _B , {S _A } is a set of S _A [k _A ], {S _B } is a set of S _B [k _B ], and {U _i } is A set of U _i , {X _i } is a set of X _i , {V _i } is a set of V _i , {Y _i } is a set of Y _i , ^ is a symbol indicating a power, and (+) is a bitwise exclusion Is a symbol indicating a logical OR,
An access structure determination unit determines the access structure A _A, generates the access structure A share information generation matrix corresponding to _A M _A and injective labeling function [rho _A,
A recording unit for recording S ′ _A , T _A , {S _A } as a long-term secret key;
An access structure A _A is determined, a disposable public key vk _A and a disposable private key sk _A are generated according to a key generation algorithm gen for a disposable signature, and a dummy attribute set W _A = {W ₁ —vk A ₁ ,..., W _d —vk _{Ad, ..., W D _vk AD} } ( however, _{vk Ad} is d-th bit of the disposable public key vk _a) is set and the access structure _{a a} or all of the dummy attributes _{W 1 _vk A1, ..., W} D _vk an access structure determination unit for generating a share information generator matrix M _a and injective labeling function [rho _a corresponding linear secret sharing scheme in conditions satisfying the _{AD,
1 ≦ j ≦ N A u =} (u_1, ..., u_N A) a u_j from 0 or p-1 following integer selected randomly for a, selected at random x from 0 or p-1 an integer _A short-term secret key generation unit that randomly selects x _i from an integer of 0 to p−1 for 1 ≦ i ≦ LA;
1 ≦ i ≦ _{L A} computes the inner product of the vectors u and vector _{(M A) i} and share lambda _Ai for, U = g ^ and U_n _A and X = g ^ x, U for 1 ≦ i ≦ _{L A i} = g ^ (rλ _Ai ) h [ρ _A (i)] ^ (− x _i ) and X _i = g ^ x _i are calculated, and sk _A is keyed according to the algorithm sig for signature generation of the disposable signature, ( U, {U _i }, X, {X _i }) as an exchange information generating unit that generates a disposable signature s _A having a message;
_A transmitter that transmits EPK _A = (U, {U _i }, X, {X _i }, M _A , ρ _A , vk _A , s _A ) to a target device for key exchange;
A receiving unit that receives EPK _B = (V, {V _i }, Y, {Y _i }, M _B , ρ _B , vk _B , s _B ) from a device to be subjected to key exchange;
I _A =: the _{{i ρ B (i) ∈S} A} the set _{I A} and _{I 'A = {i: ρ} B (i) ∈W B} to become set I' obtains the _A, share information generator matrix For a valid share set {λ _Bi } of secret information v_n _B corresponding to M _B ,

A secret information acquisition unit for obtaining an integer w _Ai and an integer w ′ _Ai of 0 to p−1 that holds
Check whether the attribute set S _A satisfies the share information generation matrix M _B and the injection labeling function ρ _B , and that all of V, {V _i }, Y, {Y _i } are elements of the group G The result of verifying vk _B as a key and (V, {V _i }, Y, {Y _i }, s _B ) as a message according to the algorithm for verifying the disposable signature is true,

An attribute confirmation unit for confirming that

σ ₁ = (g _T ^ z) ^ u_n _A
σ ₃ = e (g ^ r, Y) ^ x
Σ ′ ₁ ← Ext (σ ₁ ), σ ′ ₂ ← Ext (σ ₂ ), σ ′ ₃ ← Ext (σ ₃ ) are calculated, and the session identifier sid is set to (EPK _A , EPK _B ) Session key K
K = F_σ ′ ₁ (sid) (+) F_σ ′ ₂ (sid) (+) F_σ ′ ₃ (sid)
A session key calculation unit to be obtained as follows,
At least u_j (1 ≦ j ≦ N _A ), x, x _i (1 ≦ i ≦ L _A ), EPK _A , EPK _B , σ ₁ , σ ₂ , σ ₃ , σ ′ ₁ , σ ′ ₂ , σ ′ ₃ , Sid, sk _A , an intermediate information erasing unit,
A key exchange device comprising: A key exchange device for exchanging session keys,
κ is an integer, p is κ-bit prime, G and _{G T} is the group of order p, g is generator of the group G, _{g T} is generator of the group _{G T,} e is as G × G → _{G T} F_σ is a pseudo-random function that converts an integer of arbitrary length into an integer of κ bits according to the specified key space Kspace value σ, and Ext converts an element of the group G into a value of the key space Kspace Strong random extractor, D is an integer, d is an integer between 1 and D, gen is a key generation algorithm for a disposable signature such that the bit length of the verification key is D, sig is the bit length of the verification key is D An algorithm for generating a signature for a disposable signature, ver is an algorithm for verifying a disposable signature in which the bit length of the verification key is D, att ′ is an integer indicating the total number of elements of the attribute, and W _d _R is the d th The information indicating the dummy attribute is a bit of 1 bit P _n is an attribute element indicating an attribute, P _n is an attribute element indicating an attribute, S _A is a set of attribute elements P _n indicating an attribute of a key exchange device to be exchanged, and an access structure A _A is a key _A set of combinations of attribute elements P _n required for the key exchange apparatus to be exchanged, the injection labeling function ρ _A corresponds to the function indicating the access structure A _A , and the attribute set ρ _A (i) corresponds to the access structure A _A The i-th set, the share information generation matrix M _A is a matrix of L _A rows and N _A columns where the i-th row corresponds to the attribute set ρ _A (i), and (M _A ) _i is the i-th of the share information generation matrix M _A vector corresponding to a row, attribute set S _B is the set of attributes element P _n indicating the attribute of the key exchange apparatus, the access structure a _B attributes element P to determine the key exchange device for which the key exchange device is a key exchange _n set of combination of, injection labeling Number [rho _B function indicating the access structure A _B, i th set attribute set [rho _{B (i)} is that corresponding to the access structure A _B, share information generator matrix M _B is the i-th row is the attribute set [rho _B ( i) a matrix of L _B rows and N _B columns corresponding to i), (M _B ) _i is a vector corresponding to the i th row of the share information generation matrix M _B , L _A , N _A , L _B and N _B are integers, shared n _a is predetermined by one or more, n _a less integer shared by the target key exchange device for the key exchange device and key exchange, n _B is subject to key exchange device for the key exchange device and key exchange A predetermined integer of 1 to N _B , k _A is an element of the attribute set S _A , k _B is an element of the attribute set S _B , r and z are integers of 0 to p−1, h [1], ..., h [att '] is the group G based _{on, (g, g ^ r,} g T ^ z, h [1], ..., h [att' ]) Is a master public key, g ^ z is a master secret key, _{t A} is greater than or equal to 0 p-1 an integer, _{t B} is greater than or equal to 0 p-1 an _{integer, S 'A = g ^ z} · g ^ ( rt _A ), S ′ _B = g ＾ z · g ^ (rt _B ), T _A = g ^ t _A , T _B = g ^ t _B , S _A [k _A ] = h [k _A ] ^ t _A , S _B [k _B ] = h [k _B ] ^ t _B , {S _A } is a set of S _A [k _A ], {S _B } is a set of S _B [k _B ], and {U _i } is A set of U _i , {X _i } is a set of X _i , {V _i } is a set of V _i , {Y _i } is a set of Y _i , ^ is a symbol indicating a power, and (+) is a bitwise exclusion Is a symbol indicating a logical OR,
A recording unit for recording S ′ _B , T _B , {S _B } as a long-term secret key;
An access structure A _B is determined, a disposable public key vk _B and a disposable secret key sk _B are generated according to a key generation algorithm gen for a disposable signature, and a dummy attribute set W _B = {W ₁ —vk _{B 1} ,..., W _d —vk _Bd ,..., W _{D —} vk _BD } (where vk _Bd is the d-th bit of the disposable public key vk _B ), and the access structure A _B or all dummy attributes W _{1 —} vk _B1 ,…, W _{D —} vk an access structure determination unit for generating a linear share information generator matrix secret sharing scheme M _B and injective labeling function [rho _B corresponding to the condition satisfying the _{BD,
1 ≦ j ≦ N B v =} (v_1, ..., v_N B) a v_j from 0 or p-1 following integer selected randomly for a, selected at random y from 0 or p-1 an integer , short-term private key generating section to select at random the y _i from 0 or p-1 an integer for 1 ≦ i ≦ L _B,
1 ≦ i ≦ _{L B} calculates the inner product between the vector v and the vector _{(M B) i} for a share _{λ Bi, V = g ^ v_n} B and Y = g ^ y and, V for 1 ≦ i ≦ _{L B i = g ^ (rλ Bi)} h [ρ B (i)] ^ (- y i) and _Y i = g ^ a _{y i} is calculated, the key to sk _B according to the algorithm sig of disposable signature signature generation, ( V, {V _i }, Y, {Y _i }) as a message and an exchange information generation unit that generates a disposable signature s _B.
EPK _B = (V, {V _i }, Y, {Y _i }, M _B , ρ _B , vk _B , s _B )
_A receiving unit that receives EPK _A = (U, {U _i }, X, {X _i }, M _A , ρ _A , vk _A , s _A ) from the key exchange device to be exchanged;
I _B =: the _{{i ρ A (i) ∈S} B} set _{I B} and I: seeking _{'B = {i ρ A (} i) ∈W A} to become set I' _B, share information generator matrix For a valid share set {λ _Ai } of secret information u_n _A corresponding to M _A ,

A secret information acquisition unit that obtains an integer w _Bi and an integer w ′ _Bi that are equal to or larger than 0 and equal to or smaller than p−1.
Confirm that the attribute set S _B satisfies the share information generation matrix M _A and the injection labeling function ρ _A , and that all of U, {U _i }, X, {X _i } are elements of the group G The result of verifying vk _A as a key and (U, {U _i }, X, {X _i }, s _A ) as a message according to the algorithm for verifying the disposable signature is true,

An attribute confirmation unit for confirming that

σ ₂ = (g _T ^ z) ^ v_n _B
σ ₃ = e (g ^ r, X) ^ y
Σ ′ ₁ ← Ext (σ ₁ ), σ ′ ₂ ← Ext (σ ₂ ), σ ′ ₃ ← Ext (σ ₃ ) are calculated, and the session identifier sid is set to (EPK _A , EPK _B ) Session key K
K = F_σ ′ ₁ (sid) (+) F_σ ′ ₂ (sid) (+) F_σ ′ ₃ (sid)
A session key calculation unit to be obtained as follows,
At least v_j (1 ≦ j ≦ N _B ), y, y _i (1 ≦ i ≦ L _B ), EPK _A , EPK _B , σ ₁ , σ ₂ , σ ₃ , σ ′ ₁ , σ ′ ₂ , σ ′ ₃ , Sid, sk _B , an intermediate information erasing unit,
A key exchange device comprising: A key generation device that generates a master secret key, a master public key, and a long-term secret key for a key exchange device,
κ represents an integer, p is a κ-bit prime number, G and G _T is the group of order p, g is generator of the group G, g _T is generator of the group G _T, att 'is the total number of elements of attributes An integer, {S _A } is a set of S _A [k _A ], ^ is a symbol indicating a power,
R and z are selected at random from integers between 0 and p−1, h [1],..., H [att ′] are selected at random from the group G, and the master public key is (g, g ^ r, g _T ^ z, h [1],..., h [att ′]), a master key generation unit having a master secret key g ^ z;
T _A is randomly selected from an integer of 0 or more and p−1 or less, and S ′ _A = g ^ z · g ^ (rt _A ), T _A = g ^ t _A , S for element k _A of attribute set S _{A A} long-term secret key generation unit that calculates _A [k _A ] = h [k _A ] ^ t _A and outputs (S ′ _A , T _A , {S _A }) as a long-term secret key;
A key generation device comprising: A key exchange method for exchanging session keys using a key exchange system including at least a key exchange device α and a key exchange device β,
κ is an integer, p is κ-bit prime, G and _{G T} is the group of order p, g is generator of the group G, _{g T} is generator of the group _{G T,} e is as G × G → _{G T} F_σ is a pseudo-random function that converts an integer of arbitrary length into an integer of κ bits according to the specified key space Kspace value σ, and Ext converts an element of the group G into a value of the key space Kspace Strong random extractor, D is an integer, d is an integer between 1 and D, gen is a key generation algorithm for a disposable signature such that the bit length of the verification key is D, sig is the bit length of the verification key is D An algorithm for generating a signature for a disposable signature, ver is an algorithm for verifying a disposable signature in which the bit length of the verification key is D, att ′ is an integer indicating the total number of elements of the attribute, and W _d _R is the d th The information indicating the dummy attribute is a bit of 1 bit Symbol indicating the Tsu preparative column R, P _n is an attribute element indicating attributes, the set of attribute set S _A is the attribute element P _n indicating the attribute of the key exchange apparatus alpha, access structure A _A key exchange apparatus alpha is _A set of combinations of attribute elements P _n to be obtained from the key exchange device β, the injection labeling function ρ _A is a function indicating the access structure A _A , and the attribute set ρ _A (i) is an i-th corresponding to the access structure A _A The set, share information generation matrix M _A is a matrix of L _A rows N _A columns in which the i-th row corresponds to the attribute set ρ _A (i), and (M _A ) _i is the i-th row of the share information generation matrix M _A corresponding set of vectors, attribute set S _B is the set of attributes element P _n indicating the attribute of the key exchange apparatus beta, access structure a _B is the attribute element P _n key exchange apparatus beta seek key exchange apparatus α combined, single morphism labeling function [rho _B indicates the access structure a _B The number, the attribute set [rho _B (i) is _{L B} rows _{N B} columns corresponding to the access i-th set corresponding to the structure _{A B,} share information generator matrix _{M B} is the i-th row is the attribute set [rho _B (i) (M _B ) _i is a vector corresponding to the i-th row of the share information generation matrix M _B , L _A , N _A , L _B and N _B are integers, n _A is the key exchange device α and the key _A predetermined integer 1 to N _A shared by the exchange device β, n _B is a predetermined integer 1 to N _B shared by the key exchange device α and the key exchange device β, and k _A is Elements of the attribute set S _A , k _B are elements of the attribute set S _B , r and z are integers from 0 to p−1, h [1],..., H [att ′] are elements of the group G, _{, g ^ r, g T ^} z, h [1], ..., h [att ']) is a master public key, g ^ z is a master secret key, _{t a} is greater than or equal to 0 p-1 or less, t _B is an integer of 0 or more and p-1 or less, S ′ _A = g ^ z · g ^ (rt _A ), S ′ _B = g ^ z · g ^ (rt _B ), T _{A = g ^ t A, T} B = g ^ t B, S A [k A] = h [k A] ^ t A, S B [k B] = h [k B] ^ t B, {S A } Is a set of S _A [k _A ], {S _B } is a set of S _B [k _B ], {U _i } is a set of U _i , {X _i } is a set of X _i , {V _i } is A set of V _i , {Y _i } is a set of Y _i , ^ is a symbol indicating a power, (+) is a symbol indicating a bitwise exclusive OR,
The key exchange device α records S ′ _A , T _A , {S _A } as long-term secret keys,
The key exchange device β records S ′ _B , T _B , {S _B } as long-term secret keys,
The key exchange device α determines an access structure A _A , generates a disposable public key vk _A and a disposable secret key sk _A according to a key generation algorithm gen for a disposable signature, and sets a dummy attribute set W _A = {W ₁ _vk. _{A1, ..., W d _vk Ad} , ..., W D _vk AD} ( however, _{vk Ad} is d-th bit of the disposable public key vk _a) is set and the access structure _{a a} or all of the dummy attributes _W 1 _{_vk A1,} ..., a first access structure determination step of generating a W _D _vk linear secret sharing scheme share information generation matrix corresponding to the condition satisfying the _AD M _a and injective labeling function [rho _a,
The key exchange apparatus α is, 1 ≦ j ≦ _N a u_j from 0 or p-1 an integer for _A be selected randomly u = (u_1, ..., u_N A) and the x 0 or p-1 or less _A first short-term secret key generation step that randomly selects x _i from 0 to p−1 for 1 ≦ i ≦ LA,
The key exchange device α calculates the inner product of the vector u and the vector (M _A ) _i for 1 ≦ i ≦ L _A to obtain a share λ _Ai , U = g ^ u_n _A , X = g ^ x, 1 ≦ i ≦ L _A U _i = g ^ (rλ _Ai ) h [ρ _A (i)] ^ (− x _i ) and X _i = g ^ x _i are calculated, and the signature generation algorithm sig of the disposable signature is calculated. Accordingly, a first exchange information generating step for generating a disposable signature s _A having sk _A as a key and (U, {U _i }, X, {X _i }) as a message;
First transmission in which the key exchange device α transmits EPK _A = (U, {U _i }, X, {X _i }, M _A , ρ _A , vk _A , s _A ) to the key exchange device β. Steps,
The key exchange device β is to determine an access structure _{A B,} generates a disposable public key vk _B and disposable secret key sk _B according to the algorithm gen key generation disposable signature, dummy attribute set _W B _{= {W} 1 _{_vk B1, ..., W d _vk Bd} , ..., W D _vk BD} ( however, _{vk Bd} disposable public key vk d th bit of _B) is set and the access structure _{a B} or all of the dummy attributes _W 1 _{_vk B1,} ..., and the second access structure determination step of generating a W _D linear secret sharing scheme share information generation matrix corresponding to the condition satisfying the _vk _BD M _B and injective labeling function [rho _B,
The key exchange device β is, 1 ≦ j ≦ _{N B} are selected randomly v_j from 0 or p-1 an integer for v = (v_1, ..., v_N B) and the y 0 or p-1 or less selected randomly from integers, a second short-term private key generation step of selecting from 1 ≦ i ≦ L integer of 0 to p-1 below y _i for _B randomly,
The key exchange device β calculates an inner product of a vector v and a vector (M _B ) _i for 1 ≦ i ≦ L _B to obtain a share λ _Bi, and V = g ^ v_n _B , Y = g ^ y, 1 ≦ i ≦ _{L B} for _{V i = g ^ (rλ Bi} ) h [ρ B (i)] ^ (- y i) and calculates the _{Y i} = g ^ _y i, the algorithm sig signature generation disposable signature Therefore, a second exchange information generation step for generating a disposable signature s _B with sk _B as a key and (V, {V _i }, Y, {Y _i }) as a message;
Second transmission in which the key exchange device β transmits EPK _B = (V, {V _i }, Y, {Y _i }, M _B , ρ _B , vk _B , s _B ) to the key exchange device α. Steps,
The key exchange device β receives the second EPK _A = (U, {U _i }, X, {X _i }, M _A , ρ _A , vk _A , s _A ) from the key exchange device α. Receiving step;
_A second simple attribute confirmation step in which the key exchange device β confirms whether the attribute set S _B satisfies the share information generation matrix M _A and the injection labeling function ρ _A ;
The key exchange device β _is, I B =: the _{{i ρ A (i) ∈S} B} set _{I B} and _{I 'B = {i: ρ} A (i) ∈W A} to become set I' _B For a valid share set {λ _Ai } of the secret information u_n _A corresponding to the share information generation matrix M _A ,

A second secret information acquisition step for obtaining an integer w _Bi and an integer w ′ _Bi that are equal to or larger than 0 and equal to or smaller than p−1, and
The key exchange device β is configured such that U, {U _i }, X, {X _i } are all elements of the group G, vk _A is keyed according to a disposable signature verification algorithm, and (U, {U _i }, X, {X _i }, s _A ) as a message, the result of verification is true,

A second attribute confirmation step for confirming that
The key exchange device β

σ ₂ = (g _T ^ z) ^ v_n _B
σ ₃ = e (g ^ r, X) ^ y
Σ ′ ₁ ← Ext (σ ₁ ), σ ′ ₂ ← Ext (σ ₂ ), σ ′ ₃ ← Ext (σ ₃ ) are calculated, and the session identifier sid is set to (EPK _A , EPK _B ) Session key K
K = F_σ ′ ₁ (sid) (+) F_σ ′ ₂ (sid) (+) F_σ ′ ₃ (sid)
A second session key calculation step determined as follows:
The key exchange device β has at least v_j (1 ≦ j ≦ N _B ), y, y _i (1 ≦ i ≦ L _B ), EPK _A , EPK _B , σ ₁ , σ ₂ , σ ₃ , σ ′ ₁ , a second intermediate information erasing step for erasing σ ′ ₂ , σ ′ ₃ , sid, sk _B ;
The key exchange device α receives first EPK _B = (V, {V _i }, Y, {Y _i }, M _B , ρ _B , vk _B , s _B ) from the key exchange device β. Receiving step;
_A first simple attribute confirmation step in which the key exchange device α confirms whether the attribute set S _A satisfies the share information generation matrix M _B and the injection labeling function ρ _B ;
The key exchange apparatus α _is, I A =: the _{{i ρ B (i) ∈S} A} the set _{I A} and I _'A =: the _{{i ρ B (i) ∈W} B} the set I' _A For a valid share set {λ _Bi } of the secret information v_n _B corresponding to the share information generation matrix M _B ,

A first secret information acquisition step for obtaining an integer w _Ai and an integer w ′ _Ai of 0 to p−1 _satisfying
The key exchange device α is configured such that V, {V _i }, Y, {Y _i } are all elements of the group G, vk _B is keyed according to the algorithm for verifying the disposable signature, and (V, {V _i }, Y, {Y _i }, s _B ) as a message, the result of verification is true,

A first attribute confirmation step for confirming that
The key exchange device α is

σ ₁ = (g _T ^ z) ^ u_n _A
σ ₃ = e (g ^ r, Y) ^ x
Σ ′ ₁ ← Ext (σ ₁ ), σ ′ ₂ ← Ext (σ ₂ ), σ ′ ₃ ← Ext (σ ₃ ) are calculated, and the session identifier sid is set to (EPK _A , EPK _B ) Session key K
K = F_σ ′ ₁ (sid) (+) F_σ ′ ₂ (sid) (+) F_σ ′ ₃ (sid)
A first session key calculation step obtained as follows:
The key exchange device α has at least u_j (1 ≦ j ≦ N _A ), x, x _i (1 ≦ i ≦ L _A ), EPK _A , EPK _B , σ ₁ , σ ₂ , σ ₃ , σ ′ ₁ , a first intermediate information erasing step for erasing σ ′ ₂ , σ ′ ₃ , sid, sk _A ;
A key exchange method. The key exchange method according to claim 6, wherein
The key exchange system further includes a master key generation unit and a long-term secret key generation unit,
The master key generating means, the r, z, h [1] , ..., h the [att '] selected at random, master public key _{(g, g ^ r, g} T ^ z, h [1], ..., h [att ']) and a master key generating step for generating a master secret key g ^ z;
The long-term secret key generation means randomly selects t _A and t _B , and calculates S ′ _A and S ′ _B , T _A and T _B , S _A [k _A ] and S _B [k _B ]. A long-term secret key generation step;
_A first long-term secret key obtaining step in which the key exchange device α obtains S ′ _A , T _A , {S _A } as a long-term secret key;
The key exchange method, characterized in that the key exchange device β also has a second long-term secret key acquisition step of acquiring S ′ _B , T _B , {S _B } as a long-term secret key.   A key exchange program for causing a computer to function as the key exchange device according to claim 3 or 4, or the key generation device according to claim 5.

Images