JP5871826B2 - Authenticator generation device, verification device, and program - Google Patents

Description

  The present invention relates to information security technology, and more particularly to message authenticator technology.

  A message authenticator with provable security has been proposed under the security of the common key cryptography primitive. There are also known some techniques for converting an encryption system having normal security into a system having security against related key attacks (for example, see Non-Patent Documents 1 to 3).

Mihir Bellare and David Cash, “Pseudorandom functions and permutations provably secure against related-key attacks,” in Tal Rabin, editor, CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 666-684, Springer, Heidelberg, 2010. Yevgeniy Dodis, Eike Kiltz, Krzysztof Pietrzak, and Daniel Wichs, “Message authentication, revisited,” in David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 355-374, Springer, Heidelberg, 2012. Mihir Bellare, Kenneth G. Paterson, and Susan Thomson, “RKA security beyond the linear barrier: IBE, encryption and signatures,” Cryptology ePrint Archive, Report 2012/514, 2012, to appear ASIACRYPT 2012.

  However, a conventional method with security against a related key attack cannot maintain security unless it breaks itself when a related key attack is detected.

  The present invention provides a message authenticator technique that can improve security against related key attacks without self-destruction.

  When generating a message authenticator, label information corresponding to information including the corresponding key and the message is obtained, and a message authenticator including an image corresponding to the random number corresponding value, the secret key corresponding value, the label information, and the random number corresponding value is obtained. . However, the secret key and the corresponding key are a key pair, the random number corresponding value corresponds to information including a random number, and the secret key corresponding value corresponds to information including the secret key. At the time of verification, verification label information corresponding to information including the corresponding key and the message is obtained, and the message is verified using the message authenticator, the secret key corresponding value, and the verification label information.

  In the present invention, the label information corresponds to the corresponding key of the secret key and the message. Therefore, it is possible to improve security against related key attacks without performing self-destruction.

FIG. 1 is a diagram illustrating an authentication system according to the first embodiment. FIG. 2A is a flowchart for explaining the authenticator generation process of the first embodiment, and FIG. 2B is a flowchart for explaining the verification process of the first embodiment. FIG. 3 is a diagram illustrating an authentication system according to the second embodiment. FIG. 4A is a flowchart for explaining the authenticator generation process of the second embodiment, and FIG. 4B is a flowchart for explaining the verification process of the second embodiment.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.
<Definition>
Symbols and terms used in each embodiment are defined.
[Adaptive trapdoor genus based on label]
The genus of adaptive trapdoor relations (ATR) based on labels includes the following genus F _{f, L} and algorithms Setup (1 ^κ ), TrapGen (pp), Samp (pp, f, L), G ( s).
Setup (1 ^κ ) is a setup algorithm, which receives the security parameter 1 ^κ and obtains and outputs a common parameter pp. 1 ^κ represents a column of κ 1's. κ is a predetermined integer of 1 or more.
TrapGen (pp) is a key generation algorithm, and receives pp as an input, and obtains and outputs a key pair (f, t) of a secret key t and a corresponding key (for example, public key) f corresponding thereto. The key pair (f, t) satisfies the relationship f = μ (t) with respect to the map μ (first map). That is, when the set representing the key space of t is TS and the set representing the key space of f is FS, the mapping μ is a mapping μ: TS → FS that maps the key space TS to the key space FS. The map μ in this embodiment is a homomorphic map. Examples of mapping are functions and algorithms.
Samp (pp, f, L) is a public sampling algorithm, which receives pp, f, and label information L, and obtains and outputs a random number s and y = F _{f, L} (s). F _{f, L} is a genus of a bijective labeled map corresponding to a set of f and L. In other words, F _{f, L} is a set whose elements are injective maps corresponding to pairs of f and L. That is, y = F _{f, L} (s) is obtained by obtaining y by applying pp, f, L, s as input, and applying a bijective mapping corresponding to a pair of f and L to s. Represents. F _{f, L} (s) in this embodiment has homomorphism. Inv (pp, t, L, y) is an inverse element search algorithm, and inputs pp, t, L, y, and outputs an inverse element s = F _{f, L} ⁻¹ (y).
G (s) is an extraction algorithm, and outputs a common key (session key) G (s) εG _K with s as an input. G _K represents an additive commutative group (Abelian group).

[Hash proof system]
Hash proof system based on the label (HPS: hash proof system), the following algorithm ^{Setup (1 κ), SampR (} r), Pub (pp, μ (t), L, r), Priv (pp, t, L , Υ).
Setup (1 ^κ ) is a setup algorithm, which receives the security parameter 1 ^κ and obtains and outputs a common parameter pp. pp is a finite set Υ, ν, FS, TS, a set of mappings D _{f, L} , and a mapping μ. ν⊂Υ, D _{f, L} is a set whose elements are mappings corresponding to pairs of fεFS and LεLS, and LS is a set representing the space of the label information L.
SampR (r) is a sampling algorithm, receives a random number r, obtains ν∈ν⊂Υ and outputs it.
Pub (pp, μ (t), L, r) is an algorithm that receives pp, μ (t), L, r and obtains and outputs j = D _{f, L} (υ). That is, Pub (pp, μ (t), L, r) is a value j obtained by using pp, μ (t), L, r and applying a mapping corresponding to a pair of f and L to υ. Is calculated and output.
Priv (pp, t, L, υ) is an algorithm that receives pp, t, L, υ and obtains and outputs j = D _{f, L} (υ). That is, Priv (pp, t, L, υ) operates the mapping D _{f, L} corresponding to the set of _{f and L} on υ to obtain and output the value j. The map D _{f, L in} this embodiment has homomorphism.

[Bilinear map]
Bilinear mapping _{e: G K × G K →} G T is bilinearity a map whose non-degenerate and efficiency calculations possible. _{However, G K,} G _T is an abelian that place the number is a prime number q.
Due to the bilinearity, e (h ₁ ^α , h ₂ ^β ) = e (h ₁ , h ₂ ) ^αβ for any h ₁ , h ₂ εG _K and any α, βεZ _q . The non-degenerative, of order in the _{G T} of _{e (h 1,} h 1) is q. Due to the efficient computability, e can be calculated efficiently. Z _q represents a remainder group by q. An example of a bilinear map is pairing.

[Disposable signature]
The disposable signature is a triplet algorithm ots. gen (1 κ), ^ots. sign (osk, M), ots. It consists of vrfy (ovk, σ).
ots. gen (1 ^κ ) is a key generation algorithm, which receives the security parameter 1 ^κ and obtains and outputs a key pair (ovk, osk) of the signature verification key ovk and the corresponding signature generation key osk.
ots. sign (osk, m) is a signature generation algorithm, and receives and outputs a signature σ with the input of osk and message m.
ots. vrfy (ovk, [sigma], m) is a signature verification algorithm, performs signature verification with ovk, [sigma], m as input, and outputs accept acc or reject reg.

[Mapping with collision difficulty (collision resistance)]
Map H has collision difficulty when an enemy operating in polynomial time receives information defining map H belonging to it from the genus of the map and security parameter 1 ^κ , γ ≠ δ and H (γ) = It represents that the set (γ, δ) of H (δ) can be output only with a negligible probability. An example of the mapping H having collision difficulty is a cryptographic hash function such as SHA-1. Usually, maps with collision difficulty also have unidirectionality.

<Principle>
The principle common to each embodiment will be described.
The authenticator generating device obtains label information corresponding to information including a corresponding key and a message, obtains a message authenticator including an image corresponding to a random number corresponding value, a secret key corresponding value, and label information, and a random number corresponding value. And a message authenticator. However, the secret key and the corresponding key are a key pair, the random number corresponding value corresponds to information including a random number, and the secret key corresponding value corresponds to information including the secret key. An example of label information is a value obtained by applying a map having difficulty in collision to information including a corresponding key and a message.

  The message and the message authenticator are input to the verification device. The verification device obtains verification label information corresponding to information including the corresponding key and the message, verifies the message using the message authenticator, the secret key corresponding value, and the verification label information, and outputs a verification result. An example of verification label information is a value obtained by applying a mapping having difficulty in collision to information including a corresponding key and a message.

  In the above configuration, since the label information corresponds to the corresponding key and message of the secret key, the security against the related key attack can be improved without performing self-destruction (details will be described later).

<First Embodiment>
A first embodiment will be described. In the first embodiment, the above principle is applied to the genus of the adaptive trapdoor relation based on the label.
[Constitution]
As illustrated in FIG. 1, the authentication system 1 of this embodiment includes a setting device 110, a key generation device 120, an authenticator generation device 130, and a verification device 140. The setting device 110, the key generation device 120, the authenticator generation device 130, and the verification device 140 each have a predetermined program on a general-purpose or dedicated computer including a CPU (central processing unit), a RAM (random-access memory), and the like. A special device that is read and configured. The setting device 110, the key generation device 120, the authenticator generation device 130, and the verification device 140 are configured to exchange information via a network, a portable recording medium, or the like.

  The authenticator generation device 130 includes an input unit 131, a storage unit 132, a corresponding key generation unit 133, a label information generation unit 134, a message authenticator generation unit 135, and an output unit 136. The message authenticator generation unit 135 includes a sampling unit 135a, an encryption unit 135b, a signature key generation unit 135c, and a signature generation unit 135d. The authenticator generation device 130 executes each process under the control of a control unit (not shown). Data obtained by each unit is stored in the storage unit 132 and is read by each unit as necessary.

  The verification device 140 includes an input unit 141, a storage unit 142, a corresponding key generation unit 143, a verification label information generation unit 144, a verification unit 145, and an output unit 146. The verification unit 145 includes a signature verification unit 145a, an inverse element search unit 145b, and a determination unit 145c. The verification device 140 executes each process under the control of a control unit (not shown). Data obtained by each unit is stored in the storage unit 142 and is read by each unit as necessary.

[Setup process]
In the setup process of this embodiment, the setting device 110 receives the security parameter 1 ^κ , executes the key generation algorithm Setup (1 ^κ ), obtains and outputs a common parameter pp belonging to the adaptive trapdoor-related genus based on the label. . Further, the setting device 110 obtains and outputs a map H: {0, 1} ^* → G _K having collision difficulty. For example, the setting device 110 outputs a cryptographic hash function as the mapping H. pp is sent to and stored in the key generation device 120, and pp and H are sent to the authenticator generation device 130 and the verification device 140, and are stored in the storage units 132 and 142, respectively.

[Key generation process]
In the key generation process of this embodiment, the key generation device 120 receives the common parameter pp and executes the key generation algorithm TrapGen (pp) to obtain the key pair (f, t). Furthermore, the key generation device 120 obtains a secret key kεG _K randomly from the group G _K. The key generation device 120 outputs a secret key (t, k) composed of the first secret key t and the second secret key k. The secret key (t, k) is sent to the authenticator generation device 130 and the verification device 140 and stored in the storage units 132 and 142, respectively.

[Authentication generation process]
An arbitrary-length message Mε {0,1} ^* is input to the input unit 131 of the authenticator generation device 130, stored in the storage unit 132, and the following authenticator generation process (FIG. 2A) is executed.

The corresponding key generation unit 133 receives the first secret key t, applies the mapping μ to the first secret key t, and obtains and outputs the corresponding key f = μ (t) (step S131). The signature key generation unit 135c receives the security parameter 1 ^κ and inputs the key generation algorithm ots. gen (1 ^κ ) is executed to obtain and output a key pair (ovk, osk) of the signature verification key ovk of the disposable signature and the signature generation key osk (step S132).

The label information generation unit 134 receives the corresponding key f and the message M, and applies the mapping H to the information including the corresponding key f and the message M to obtain the label information d = H (f, M) εG _K. Output. Examples of information including the corresponding key f and the message M include a bit combination value between the bit string expression value of the corresponding key f and the message M, a bit combination value between the bit string expression value of the corresponding key f, the message M, and the additional bit string, and the like. It is. Examples of the additional bit string are a part of common parameters and header information. When the mapping H is a hash function, the label information d is a digest value of information including the corresponding key f and the message M (step S133).

The sampling unit 135a receives the common parameter pp, the corresponding key f, and the signature verification key ovk, executes the public sampling algorithm Samp (pp, f, ovk), and sets the pair (s, y) is obtained and output. The random number corresponding value y is a value y = F _{f, ovk} (s) obtained by _applying the second mapping F _{f, ovk} corresponding to the corresponding key f and the signature verification key ovk to the random number s (step S134). ).

The encryption unit 135b receives the random number s and the second secret key k, executes an extraction algorithm G (s) to obtain a common key G (s) corresponding to the random number s, and conforms to a predetermined common key cryptosystem. The secret key corresponding value c is obtained by encrypting the second secret key k with the common key G (s) and output. For example, the encryption unit 135b obtains and outputs c = G (s) · k (step S135). However, “·” represents an operation defined by a group. For example, when G (s), kε {0, 1} ^κ , G (s) · k is an exclusive OR of G (s) and k.

  The signature generation unit 135d receives the signature generation key osk, the random number correspondence value y, the secret key correspondence value c, and the label information d, and inputs the signature generation algorithm ots. sign (osk, (d, y, c)) is executed, and a signature σ (random number correspondence value, secret key correspondence value and label information) for information including the random number correspondence value y, the secret key correspondence value c, and the label information d Image) is output. Examples of information including the random number correspondence value y, the secret key correspondence value c, and the label information d include bit combination values of y, c, d bit string expression values, bit combination values of y, c, d and additional bit strings, etc. (Step S136).

  The output unit 136 obtains a message authenticator τ = (ovk, y, c, σ) including the signature verification key ovk, the random number corresponding value y, the secret key corresponding value c, and the signature σ (step S137), and message authentication. The child τ and the message M are output (step S138). The message authenticator τ and the message M are sent to the verification device 140.

[Verification processing]
The message authenticator τ = (ovk, y, c, σ) and the message M are input to the input unit 141 of the verification device 140, stored in the storage unit 142, and the following verification process (FIG. 2B) is executed.

  The corresponding key generation unit 143 receives the first secret key t, applies the mapping μ to the first secret key t, and obtains and outputs the corresponding key f = μ (t) (step S141).

The verification label information generation unit 144 receives the corresponding key f and the message M, and applies the mapping H to information including the corresponding key f and the message M to verify the verification label information d ′ = H (f, M) ∈G. _{Get K} and output. The structure of “mapping H” and “information including the corresponding key f and message M” in the verification label information generation unit 144 is the same as that of the “mapping H” and “corresponding key f and message M in the label information generation unit 134. It is the same as "information including" (step S142).

  The signature verification unit 145a receives the signature verification key ovk, the signature σ, and the verification label information d 'as inputs, and the signature verification algorithm ots. vrfy (ovk, σ, (d ′, y, c)) is executed for information including the random number corresponding value y, the secret key corresponding value c, and the verification label information d ′ using the signature verification key ovk. Whether or not the signature σ is acceptable is verified, and an acceptance (pass) acc or a rejection (fail) reg is output (step S143). The structure of “information including random number corresponding value y, private key corresponding value c, and verification label information d ′” is the same as “random number corresponding value y, private key corresponding value c, label information d” in signature generation unit 135d. It is the same as the structure of “information including”. When the signature verification unit 145a outputs the rejection reg, the output unit 146 outputs the rejection reg (step S147), and the process ends.

On the other hand, when the signature verification unit 145a outputs an acceptance acc, the inverse element search unit 145b receives the common parameter pp, the secret key t, the signature verification key ovk, and the random number corresponding value y as input, and the inverse element search algorithm Inv (pp , T, ovk, y), and the inverse search map F _{f, L} ⁻¹ corresponding to the corresponding key f and the signature verification key ovk is applied to the random number corresponding value y to restore the random number restored value s ′ = F _{f , L} ⁻¹ (y) is obtained and output (step S144).

The determination unit 145c receives the random number restoration value s ′, the secret key corresponding value c, and the second secret key k, and executes the extraction algorithm G (s ′) to execute the common key G (corresponding to the random number restoration value s ′. s ′), and whether the second secret key k matches the decrypted value obtained by decrypting the second secret key k with the common key G (s ′) in accordance with the common key cryptosystem described above. judge. For example, the determination unit 145c determines whether or not k = c · G (s ′) ^{− 1} is satisfied (step S145). However, G (s ′) ⁻¹ represents the inverse element of G (s ′).

  Here, when it is determined that the decrypted value and the second secret key k do not match, the output unit 146 outputs a rejection reg (step S147) and ends the process. On the other hand, when it is determined that the decrypted value matches the second secret key k, the output unit 146 outputs an acceptance acc (step S146), and the process ends.

<Example 1 of the first embodiment>
As Example 1 of the first embodiment, “Reference 1: Hoeteck Wee,“ Public key encryption against related key attacks, ”in Marc Fischlin, Johannes Buchmann, and Mark Manulis, editors, PKC 2012, volume 7293 of Lecture Notes in Computer Science, pages 262-279, Springer, Heidelberg, 2012. "and Reference 2: Dennis Hofheinz and Eike Kiltz,“ Practical chosen ciphertext secure encryption from factoring, ”in Antoine Joux, editor, EUROCRYPT 2009, volume 5479 of Lecture An example in which the present invention is applied to an adaptive trapdoor relationship based on the prime factorization assumption disclosed in "Notes in Computer Science, pages 313-332, Springer, Heidelberg, 2009." is shown. In this embodiment, Λ, Ω, κ and ω are constants, g is a generator of a group of order N, r is a random number, f = g ^ΛΩt , s = g ^Ωr , y = (u, w), u = g ^ΩΛr , w = (f · g ^ovk ) ^r , the common key is (lsb _N (s), lsb _N (s ² ),..., lsb _N (s ^{v (κ−1)} )), v (i) = 2 ⁱ , lsb _N (α) is information corresponding to a value in which α is represented by an integer of − (N−1) / 2 or more and (N−1) / 2 or less, and the random number restoration value is 2 ^c = a * ovk + bΛΩ it is s' ⁼ relative integer a, b, c satisfying ^{(w a · u b-at} ) v (ovk-c). However, “α * β” represents multiplication of α and β, and when there is no particular confusion, multiplication of α and β is expressed as “αβ”.

Setup of the embodiment ^{(1 κ), TrapGen (pp} ), Samp (pp, f, ovk), shown Inv (pp, t, ovk, y), the details of the G (s). For simplicity, let κ and ω be positive integers, Ω = 2 ^ω , Λ = 2 ^κ . In this case, [0, Ω−1] is a space for label information d and verification label information d ′. However, [ι ₁ , ι ₂ ] represents a section from ι _{1 to} ι ₂ .

Setup (1 ^κ ) receives the security parameter 1 ^κ , randomly selects κ-bit strong prime numbers P and Q≡3 (mod 4) according to a uniform distribution (P = 2p + 1, Q = 2ε + 1), and N = P * Q. Further, Setup (1 ^κ ) defines a signed quotient group QR _N ⁺ where QR _N ⁺ = J _N ⁺ , sets g as a generator of QR _N ⁺ , and outputs a common parameter pp = (N, g). QR _N ⁺ and J _N ⁺ are defined as follows.
QR _N ⁺ = {| x || x∈QR _N ⁺ }
J _N ⁺ = {| x || x∈J _N } (ie, J _N ⁺ = J _N / (± 1))
However, Z _N ^* is a group formed by the whole of N remainders having an inverse element, J _N is a subgroup of Z _N ^* formed by Jacobian 1 and QR _N is a square remainder. | X | ∈Z _N is the absolute value of x when x∈ [− (N−1) / 2, (N−1) / 2].

TrapGen (pp) receives pp as input, randomly selects t from the interval [1, (N−1) / 4] according to a uniform distribution, calculates f = μ (t) = g ^ΛΩt, and ^generates a key pair ( f, t) is output.

Samp (pp, f, ovk) takes pp, f, ovk as input, calculates (s, u) = ( ^gΩr , ^gΩΛr ) for the second random number r, and w = (f · g ^ovk ) ^r And s and y = (u, w) are output.

Inv (pp, t, ovk, y) checks whether or not u, w ∈ QR _N ⁺ for y = (u, w), and if u, w ^∈ QR _N ⁺ , w ^ΩΛ = u ^{ovk + ΛΩt} If w ^ΩΛ = u ^{ovk + ΛΩt} , then s ′ = (w ^a · u ^b-at ) ^{v (ovk-c} ) for integers a, b, c∈Z such that 2 ^c = a * ovk + bΛΩ ^{) And} outputs s ′.

G (s) takes sεQR _N ⁺ as an input and sets (lsb _N (s), lsb _N (s ² ),..., Lsb _N (s ^{v (κ−1)} )) ε {0, 1} ^κ Output. lsb _N (α) represents the least significant bit when α is represented by [− (N−1) / 2, (N−1) / 2] and further represented by a bit string.

[Commutability of G (s)]
The common key obtained by G (s) in this embodiment is an element of {0, 1} ^κ . {0,1} ^κ can be regarded as a κ-order extension GF (2) ^κ of a finite field GF (2) of order 2. Therefore, it can be said that the common key obtained by G (s) of this embodiment is an element of an additive commutative group.

[Homomorphism of map μ]
For any Δ∈Z and t∈ [1, (N−1) / 4], the following holds: However, Z represents an integer set.
μ (t + Δ) = g ^{ΛΩ (t + Δ)} = g ^ΛΩt · g ^ΛΩΔ = μ (t) + μ (Δ)
Therefore, the map μ has homomorphism.

[Map F _{μ (t),} homomorphism of _ovk ]
For t∈ [1, (N−1) / 4] and any ovk, s = g ^Ωr , F _{μ (t), ovk} (s) = (u, w) = (g ^ΩΛr , (g ^ΛΩt G ^ovk ) ^r ). At this time, the following holds for an arbitrary Δ∈Z.
F _{μ (t + Δ), ovk} (s) = (g ^ΩΛr , (g ^{ΛΩ (t + Δ)} · g ^ovk ) ^r )
= ( ^GΩΛr , ( ^gΛΩt · g ^ovk ) ^r · g ^ΛΩrΔ )
= (U, w · u ^Δ )
Therefore, F _{μ (t + Δ), ovk} (s) can be calculated from F _{μ (t), ovk} (s) and Δ, and the map F _{μ (t), ovk} has homomorphism.

<Example 2 of the first embodiment>
As Example 2 of the first embodiment, an example in which the present embodiment is applied to an adaptive trapdoor relationship based on the DBDH assumption disclosed in Non-Patent Document 3 will be described. In this embodiment, v and h are group elements, g is a group generator, r is a random number, e is a bilinear mapping, the first secret key is t, the second secret key is k, and f = g ^t , S = v ^r , y = (u, w), u = g ^r , w = (f · v ^ovk ) ^r , the common key is e (s, h), and the random number restoration value is s ′ = (w U− ^t ) ^{(1 / ovk)} . Details of Setup (1 ^κ ), TrapGen (pp), Samp (pp, f, ovk), Inv (pp, t, ovk, y), and G (s) of the present example will be described below.

Setup (1 ^κ ) receives the security parameter 1 ^κ and generates a group for bilinear mapping (G _K , G _T , q, e, g). Furthermore Setup (1 ^kappa) is, v from the group _{G K,} select H∈G _K randomly common parameter _{pp = (G K, G T} , q, e, g, v, h) the obtained output.

TrapGen (pp) randomly selects T∈Z _q a pp as input, calculates the f = ^{g t,} outputs a key pair (f, t).

Samp (pp, f, ovk) receives pp, f, ovk and calculates (s, u) = (v ^r , g ^r ) for random number r. Further, Samp (pp, f, ovk) calculates w = (f · v ^ovk ) ^r and outputs s and y = (u, w).

Inv (pp, t, ovk, y) takes pp, t, ovk, y as inputs, checks whether u, wεG _K for y = (u, w), and u, wεG _K S ′ = (w · u ^−t ) ^{(1 / ovk)} is calculated. Further, Inv (pp, t, ovk, y) checks whether e (g, s ′) = e (v, u), and if e (g, s ′) = e (v, u) Output s'.

G (s) inputs the pp and S∈G _K, and outputs the _{e (s, h) ∈G T} .

[Commutability of G (s)]
Common key obtained in the G (s) of this embodiment is the original abelian G _T.

[Homomorphism of map μ]
The following holds for any Δ∈Z _q and t∈Z _q .
μ (t + Δ) = g ^{(t + Δ)} = g ^t · g ^Δ = μ (t) + μ (Δ)
Therefore, the map μ has homomorphism.

[Map F _{μ (t),} homomorphism of _ovk ]
When s = v ^r for tεZ _q and an arbitrary ovk, F _{μ (t), ovk} (s) = (u, w) = (g ^r , (g ^t · v ^ovk ) ^r ). At this time, for any Δ∈Z _q , the following holds.
F _{μ (t + Δ), ovk} (s) = (g ^r , ( ^{gt + Δ} · v ^ovk ) ^r )
^{= (G r, (g t} · v ovk) r · g Δr)
= (U, w · u ^Δ )
Therefore, F _{μ (t + Δ), ovk} (s) can be calculated from F _{μ (t), ovk} (s) and Δ, and the map F _{μ (t), ovk} has homomorphism.
[Collision difficulty of map μ]
The difficulty of collision of the map μ can be proved by the discrete logarithm assumption of g.

Ｐｒ｜Θ｜は｜Θ｜の確率を表す。ＫＳ（ｐｐ）は、共通パラメータｐｐを入力として秘密鍵ｋｅｙ（第１実施形態ではｋｅｙ＝（ｔ，ｋ））を出力する鍵生成アルゴリズムである。Ｒ−Ｔａｇ_κは関連鍵攻撃の秘密鍵間の写像φとメッセージＭとを入力とし、ｐｐ，ｋｅｙ，Ｍに対する署名ＴＡＧ（ｐｐ，φ（ｋｅｙ），Ｍ）を返す神託機械である。Ｌ_Ｔは神託機械Ｒ−Ｔａｇ_κへの問合せ内容の順序付きリスト（（φ_１，Ｍ_１），...，（φ_η，Ｍ_η））である。任意の多項式時間の敵Ａに対して、式（１）の利得が無視できるとき、メッセージ認証子はＵＦ−ＲＫ−ＣＭＶＡ安全であるという。 <Security against related key attacks>
Next, the security against the related key attack of the system of this embodiment will be described.
[Indicator of security against related key attacks]
As an index of security against related key attacks, the gain of enemy A is defined as follows.

Pr | Θ | represents the probability of | Θ |. KS (pp) is a key generation algorithm that outputs the secret key key (in the first embodiment, key = (t, k)) with the common parameter pp as an input. R-Tag _κ is a oracle machine that receives a mapping φ between a secret key of a related key attack and a message M, and returns a signature TAG (pp, φ (key), M) for pp, key, M. L _T is an ordered list of the inquiry to the oracle machine _{R-Tag κ ((φ 1} , M 1), ..., (φ η, M η)) is. For any polynomial time enemy A, the message authenticator is said to be UF-RK-CMVA secure when the gain of equation (1) is negligible.

The system of this embodiment can reduce the gain of the formula (1) compared to the conventional configuration, and can improve the security against related key attacks. In particular, the method of this embodiment is strong against additive related key attacks. Further, when the mapping μ and F _{μ (t), ovk} have homomorphism, it can be proved that the gain of the expression (1) can be ignored (detailed proof is omitted). In the following, an additive related key attack for the message authenticator method based on Non-Patent Document 3 is assumed, and it is shown that the related key attack is not successful with the configuration of this embodiment.

[Message authenticator based on Non-Patent Document 3]
A message authenticator method based on Non-Patent Document 3 will be exemplified below.
Key generation: The key generation algorithm randomly selects a secret key (t, k) = ((t1, t2, t3, t4), k) εZ _q ⁴ × G _K. g ₁ and g ₂ are generators of the group G _K , and implicitly g ₂ = g ₁ ^t1 .
Authentication code generation: The authentication code generation algorithm uses r as a random number for message Mε {0,1} ^* , c ₁ = g ₁ ^r , c ₂ = c ₁ ^t1 (= g ₂ ^r ), label information L = Let H (c ₁ , c ₂ , M). Further, the authenticator generation algorithm sets ν = c ₁ ^{t2 * L + t3} , c = k · c ₁ ^t4, and outputs a message authenticator τ = (c ₁ , c ₂ , ν, c).
Verification: The verification algorithm takes τ and M as inputs, obtains L ′ = H (c ₁ , c ₂ , M), and whether ν = c ₁ ^{t2 * L ′ + t3} and k = c · c ₁ ^−t4 If ν = c ₁ ^{t2 * L ′ + t3} and k = c · c ₁ ^−t4 , acc is output, otherwise rej is output.

[Additive key attack]
The following additive key attack succeeds against the message authenticator method based on Non-Patent Document 3 described above.
1. The enemy sets the counterfeit message to M∈ {0,1} ^* .
2. The enemy appropriately selects δ, η∈Z _q other than 0, and sets Δ = (0, ξ2, ξ3, 0, 1 _G ) ∈Z _q ⁴ × G _K. However, 1 _G is a unit _element of the group G _K.
3. The enemy has the secret key (t, k) = ((t1, t2, t3, t4), k) and the related key φ (t, k) = (t + ξ, k) = ((t1, t2 + ξ2, t3 + ξ3, t4), k) Inquires of the oracle machine R-Tag _κ with the map φ and the message M to be mapped.
4). The enemy receives the following as a reply from the oracle machine R-Tag _κ .
τ ′ = (c ₁ , c ₂ , ν ′, c) = (c ₁ , c ₂ , c ₁ ^{(t2 + ξ2) * L + (t3 + ξ3)} , k · c ₁ ^t4 )
Here, L = H (c ₁ , c ₂ , M), c ₁ = g ₁ ^r , c ₂ = g ₂ ^r (= c ₁ ^t1 ).
5. The enemy uses the above response to calculate L = H (c ₁ , c ₂ , M), and further calculates ν = ν ′ · (c ₁ ^{ξ 2 * L} · c ₁ ^{ξ 3} ) ⁻¹ .
6). The enemy outputs a forged message authenticator τ = (c ₁ , c ₂ , ν, c).
This message authenticator τ is the same as that obtained for the forged message M using the secret key (t, k) = ((t1, t2, t3, t4), k), and the verification algorithm is acc. Output. Therefore, the gain of Expression (1) is 1.

  This attack is based on the fact that the label information L does not change between the secret key (t, k) and the related key φ (t, k). On the other hand, the label information of this embodiment is d = H (f, M) corresponding to information including the corresponding key f = μ (t) and the message M. That is, in this embodiment, label information H (μ (t), M) corresponding to the secret key (t, k) and label information H (μ corresponding to the related key φ (t, k) = (t + ξ, k). (T + ξ), M). Therefore, this attack does not lead to this form, and the gain of Expression (1) is smaller than that of the conventional method. Note that due to the collision difficulty of the map H, the probability that μ (t) ≠ μ (t + ξ) and H (μ (t), M) = H (μ (t + ξ), M) is negligibly small. Further, due to the collision difficulty of the map μ, the probability that the enemy selects ξ that satisfies t ≠ t + ξ and μ (t) = μ (t + ξ) is so small that it can be ignored.

Second Embodiment
A second embodiment will be described. In the first embodiment, the above-described principle is applied to a hash certification system based on labels. Hereinafter, differences from the first embodiment will be described, and descriptions of matters common to the first embodiment will be simplified.
[Constitution]
As illustrated in FIG. 2, the authentication system 2 of this embodiment includes a setting device 210, a key generation device 220, an authenticator generation device 230, and a verification device 240. The setting device 210, the key generation device 220, the authenticator generation device 230, and the verification device 240 are special devices configured by reading a predetermined program into a general-purpose or dedicated computer. The setting device 210, the key generation device 220, the authenticator generation device 230, and the verification device 240 are configured to be able to exchange information via a network, a portable recording medium, or the like.

  The authenticator generation device 230 includes an input unit 131, a storage unit 132, a corresponding key generation unit 133, a label information generation unit 234, a message authenticator generation unit 235, and an output unit 236. The message authenticator generation unit 235 includes a sampling unit 235a and a mapping unit 235b. The authenticator generation device 230 executes each process under the control of a control unit (not shown). Data obtained by each unit is stored in the storage unit 132 and is read by each unit as necessary.

  The verification device 240 includes an input unit 141, a storage unit 142, a corresponding key generation unit 143, a verification label information generation unit 244, a verification unit 245, and an output unit 246. The verification unit 245 includes a mapping unit 245a and a determination unit 234b. The verification device 240 executes each process under the control of a control unit (not shown). Data obtained by each unit is stored in the storage unit 142 and is read by each unit as necessary.

[Setup process]
In the setup process of this embodiment, the setting device 210 receives the security parameter 1 ^κ , executes the key generation algorithm Setup (1 ^κ ), obtains and outputs a common parameter pp of the hash certification system based on the label. Further, the setting device 210 obtains and outputs a map H: {0, 1} ^* → G _K having a collision difficulty. pp is sent to and stored in the key generation device 220, and pp and H are sent to the authenticator generation device 230 and the verification device 240, and are stored in the storage units 132 and 142, respectively.

[Key generation process]
In the key generation processing of this embodiment, the key generation device 220 receives the common parameter pp, selects a secret key t at random, and outputs it. The secret key t is sent to the authenticator generation device 230 and the verification device 240 and stored in the storage units 132 and 142, respectively.

[Authentication generation process]
An arbitrary-length message Mε {0,1} ^* is input to the input unit 131 of the authenticator generation device 230, stored in the storage unit 132, and the following authenticator generation process (FIG. 4A) is executed.

  The corresponding key generation unit 133 receives the first secret key t, applies the mapping μ to the first secret key t, and obtains and outputs the corresponding key f = μ (t) (step S131).

  The sampling unit 235a selects the random number r according to the uniform distribution (step S232), executes the sampling algorithm SampR (r), and obtains and outputs the image SampR (r) of the random number r as the random number corresponding value υ (step S233). ).

  The label information generation unit 234 receives the corresponding key f, the random number corresponding value υ, and the message M, and applies the mapping H to the information including the corresponding key f, the random number corresponding value υ, and the message M, so that the label information d = H (F, υ, M) is obtained and output. Examples of information including the correspondence key f, the random number correspondence value υ, and the message M include the bit string representation value of the correspondence key f, the bit string representation value of the random number correspondence value υ and the message M, and the bit string of the correspondence key f. The bit string expression value υ of the expression value and the random number corresponding value, the bit combination value of the message M and the additional bit string, and the like. When the mapping H is a hash function, the label information d is a digest value of information including the corresponding key f, the random number corresponding value υ, and the message M (step S234).

The mapping unit 235b receives the common parameter pp, the secret key t, the label information d, and the random number corresponding value υ, executes the algorithm Priv (pp, t, d, υ), and the image j = D _{f, d} (υ ) And output. That is, the image j is obtained by applying the second mapping D _{f, d} corresponding to the secret key t (secret key corresponding value) and the label information _d to the random number corresponding value υ (step S235).

The output unit 236 generates a message authenticator τ = (υ, j) including a random number corresponding value υ and an image j (a value obtained by applying the second mapping D _{f, d} (υ) to the random number corresponding value υ). Obtaining (step S237), the message authenticator τ and the message M are output (step S138). The message authenticator τ and the message M are sent to the verification device 240.

[Verification processing]
The message authenticator τ = (υ, j) and the message M are input to the input unit 141 of the verification device 240, stored in the storage unit 142, and the following verification process (FIG. 4B) is executed.

  The corresponding key generation unit 143 receives the first secret key t, applies the mapping μ to the first secret key t, and obtains and outputs the corresponding key f = μ (t) (step S141).

The verification label information generation unit 244 receives the corresponding key f, the random number corresponding value υ, and the message M, and applies the mapping H to the information including the corresponding key f, the random number corresponding value υ, and the message M to verify the label information d. '= H (f, υ, M) εG _K is obtained and output. The structure of “mapping H” and “information including correspondence key f, random number correspondence value υ and message M” in verification label information generation unit 144 is the same as “mapping H” and “correspondence in label information generation unit 134. It is the same as “information including key f, random number corresponding value υ, and message M” (step S242).

The mapping unit 245a receives the common parameter pp, the secret key t, the verification label information d ′, and the random number corresponding value υ, executes the algorithm Priv (pp, t, d ′, υ), and the image j ′ = D _{f , D ′} (υ) are obtained and output. That is, the image j ′ is obtained by applying the second mapping D _{f, d ′} corresponding to the secret key t (secret key corresponding value) and the verification label information _{d ′} to the random number corresponding value υ (step S243).

  The determination unit 245b receives the obtained image j ′ and the image j included in the message authenticator τ = (υ, j) as input, and determines whether they match (step S235). Here, when it is determined that the image j ′ and the image j do not match (j ′ ≠ j), the output unit 246 outputs a rejection ej (step S247), and the process ends. On the other hand, when it is determined that the image j ′ and the image j match (j ′ = j), the output unit 246 outputs an acceptance acc (step S246), and the process is terminated.

<Example of the second embodiment>
As an example of the second embodiment, an example in which the present embodiment is applied to a hash certification system based on the DDH assumption will be described. In this embodiment, g ₁ and g ₂ are generators of the group G _K (commutative group, for example, cyclic group), the label information is d, the verification label information is d ′, and the secret key is t = (x1, x2, y1) , Y2), the corresponding key is (X, Y) = (g ₁ ^x1 g ₂ ^x2 , g ₁ ^y1 g ₂ ^y2 ), the random number corresponding value is υ = (υ ₁ , υ ₂ ) ∈G _K ² , The value obtained by applying the second mapping at the time to the random number corresponding value is j = υ ₁ ^{x1 * d + y1} · υ ₂ ^{x2 * d + y2} , and the value obtained by ^applying the second mapping at the time of verification to the random number corresponding value is j '= Υ ₁ ^{x1 * d' + y1} · υ ₂ ^{x2 * d + y2} .

Details of Setup ( ^1κ ), key generation algorithm, Pub (pp, μ (t), L, r), and Priv (pp, t, L, υ) of this embodiment will be described below.
Setup (1 ^κ ) takes security parameter 1 ^κ as input, g ₁ and g ₂ as generators of group G _K of order q, and g ₂ = g ₁ ^ω is a language for (g ₁ , g ₂ ) Let it be a trapdoor.
The key generation algorithm receives the common parameter pp, selects a secret key t = (x1, x2, y1, y2) εZ _q ⁴ at random according to a uniform distribution, and maps it to (x1, x2, y1, y2) The corresponding key (X, Y) = (g ₁ ^x1 · g ₂ ^x2 , g ₁ ^y1 · g ₂ ^y2 ) is obtained by ^applying μ.
Pub (pp, μ (t), d, r) inputs pp, μ (t) = (X, Y), d, ^r and calculates and outputs j = (X ^d · Y) ^r. .
Priv (pp, t, d, υ) takes pp, t, d, υ = (υ ₁ , υ ₂ ) as input, and calculates and outputs j = υ ₁ ^{x1 * d + y1} · υ ₂ ^{x2 * d + y2.} .

[Homomorphism of map μ]
The following holds for any Δ = (δ1, δ2, η1, η2) εZ _q ⁴ and t = (x1, x2, y1, y2).
μ (t + Δ) = (g ₁ ^{x1 + δ1} · g ₂ ^{x2 + δ2} , g ₁ ^{y1 + η1} · g ₂ ^{y2 + η2} )
= (G1 ^x1 · g2 ^x2 · g1 ^δ1 · g2 ^δ2 ,
g1 ^y1 · g2 ^y2 · g1 ^η1 · g2 ^η2 )
= (G ₁ ^x1 · g ₂ ^x2 , g ₁ ^y1 · g ₂ ^y2 ) ·
(G ₁ ^δ1 · g ₂ ^δ2 , g ₁ ^η1 · g ₂ ^η2 )
= Μ (t) · μ (Δ)
Therefore, the map μ has homomorphism.

[Homomorphism of map D _{f, d} ]
Arbitrary Δ = (δ1, δ2, η1, η2), μ (t + Δ) = (g ₁ ^{x1 + δ1} · g ₂ ^{x2 + δ2} , g ₁ ^{y1 + η1} · g ₂ ^{y2 + η2} ), label information d and υ = (υ ₁ , υ ₂ ) The following holds for ∈ G _K ² .
D _{μ (t + Δ), d} (υ ₁ , υ ₂ ) = υ ₁ ^{(x1 + δ1) d + (y1 + η1)} · υ ₂ ^{(x2 + δ2) d + (y2 + η2)
_{= Υ 1 x1 * d + y1}} · υ 2 x2 * d + y2 · υ 1 δ1 * d + η1 · υ 2 δ2 * d + η2
= D [ _{mu] (t), d} ([nu] ₁ , [nu] ₂ ) .D [ _{mu] ([delta]), d} ([nu] ₁ , [nu] ₂ ).
Therefore, the map D _{f, d} has homomorphism.
[Collision difficulty of map μ]
The collision difficulty of the map μ can be proved by the discrete logarithm assumption of (g ₁ , g ₂ ).

[Message authenticator based on Non-Patent Document 3]
A message authenticator method based on Non-Patent Document 3 will be exemplified below.
Key generation: The key generation algorithm randomly selects the secret key t = (t1, t2, t3, t4) εZ _q ⁴ .
Authentication code generation: The authentication code generation algorithm randomly selects υ = (υ ₁ , υ ₂ ) = (g ₁ ^r , g ₂ ^r ) for the message MεZ _{q and} sets the label information L = M. However, g ₁ and g ₂ are generators of the group G _K. Further, the authenticator generation algorithm calculates j = D _{f, L} (υ) = υ ₁ ^{x1 * L + y1} · υ ₂ ^{x2 * L + y2,} and outputs τ = (υ ₁ , υ ₂ , j) as a message authenticator. .
Verification: The verification algorithm takes τ and M as inputs, sets label information L = M, calculates j ′ = D _{f, L} (υ) = υ ₁ ^{x1 * L + y1} · υ ₂ ^{x2 * L + y2} , and j ′ = j If so, acc is output, and if not, rej is output.

[Additive key attack]
The following additive key attack succeeds against the message authenticator method based on Non-Patent Document 3 described above.
1. The enemy sets the counterfeit message to M∈Z _q .
2. 2. Enemy properly selects Δ = (δ1, δ2, η1, η2) εZ _q ⁴ other than (0, 0, 0, 0) The enemy makes an inquiry to the oracle machine R-Tag _κ with the mapping φ that maps the secret key t = (t1, t2, t3, t4) to the related key φ (t) = (t1 + δ1, t2 + δ2, t3 + η1, t4 + η2) and the message M.
4). The enemy receives the following as a reply from the oracle machine R-Tag _κ .
τ ′ = (υ ₁ , υ ₂ , j ″) = (υ ₁ , υ ₂ , D _{μ (t + ξ), M} (υ ₁ , υ ₂ )) = (υ ₁ , υ ₂ , υ ₁ ^{(x1 + δ1) M + (y1 + η1)} · υ ₂ ^{(x2 + δ2) M + (y2 + η2)} )
Here, c ₁ = g ₁ ^r and c ₂ = g ₂ ^r .
5. The enemy uses the above response to calculate:
j = j ″ · (ν ₁ ^{δ1 * M + η1} · υ ₂ ^{δ2 * M + η2} ) ⁻¹
= Υ ₁ ^{x1 * M + y1} · υ ₂ ^{x2 * M + y2} = D _{μ (t), M} (υ ₁ , υ ₂ )
6). The enemy outputs a forged message authenticator τ = (c ₁ , c ₂ , j).
This message authenticator τ is the same as that obtained for the forged message M using the secret key t = (t1, t2, t3, t4), and the verification algorithm outputs acc. Therefore, the gain of Expression (1) is 1.

  This attack is based on the fact that the label information L = M does not change between the secret key t and its associated key φ (t). On the other hand, the label information of this embodiment is d = H (f, υ, M) corresponding to information including the corresponding key f = μ (t), the random number corresponding value υ, and the message M. That is, in this embodiment, label information H (μ (t), υ, M) corresponding to the secret key t and label information H (μ (φ (t)), M) corresponding to the related key φ (t) are obtained. Different. Therefore, this attack does not lead to this form, and the gain of Expression (1) is smaller than that of the conventional method. Note that due to the collision difficulty of the map H, μ (t) ≠ μ (φ (t)) and H (μ (t), υ, M) = H (μ (φ (t)), υ, M). The probability of becoming so small is negligible. Further, due to the difficulty of collision of the mapping μ, the probability that t ≠ μ (t) and μ (t) = μ (φ (t)) is negligibly small.

<Other variations, etc.>
The present invention is not limited to the above-described embodiment. For example, a plurality of authenticator generation devices and verification devices may exist. 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.

  When the above configuration is realized by a computer, the processing contents of the functions that each device should have are described by a program. By executing this program on a computer, the above processing functions are realized on the computer. The program describing the processing contents can be recorded on a computer-readable recording medium. An example of a computer-readable recording medium is a non-transitory recording medium. Examples of such a recording medium are a magnetic recording device, an optical disk, a magneto-optical recording medium, a semiconductor memory, and the like.

  This program is distributed, for example, 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, this computer reads a program stored in its own recording device and executes a process according to the read program. As another execution form of the program, the computer may read the program directly from the portable recording medium and execute processing according to the program, and each time the program is transferred from the server computer to the computer. The processing according to the received program may be executed sequentially. The above-described processing may be executed by a so-called ASP (Application Service Provider) type service that realizes a processing function only by an execution instruction and result acquisition without transferring a program from the server computer to the computer. Good.

  In the above embodiment, the processing functions of the apparatus are realized by executing a predetermined program on a computer. However, at least a part of these processing functions may be realized by hardware.

1, 2 Authentication system 110, 210 Setting device 120, 220 Key generation device 130, 230 Authentication code generation device 140, 240 Verification device

Claims (15)

A secret key and a corresponding key are a key pair, a random number corresponding value corresponds to information including a random number, a secret key corresponding value corresponds to information including the secret key,
A label information generating unit for obtaining label information corresponding to information including the corresponding key and the message;
A message authenticator generating unit for obtaining a message authenticator including an image of the random number corresponding value, the secret key corresponding value, and the label information, and the random number corresponding value;
An authenticator generation device having The authenticator generation device according to claim 1,
The label information is a value obtained by applying a mapping having difficulty in collision to information including the corresponding key and the message.
An authenticator generation device characterized by the above. The authenticator generating device according to claim 1 or 2,
The secret key includes a first secret key and a second secret key;
The corresponding key is a value obtained by applying a first mapping to the first secret key;
The random number corresponding value is a value obtained by applying a second mapping corresponding to the corresponding key and the signature verification key to the random number;
The secret key corresponding value is a ciphertext obtained by encrypting the second secret key with a common key corresponding to the random number;
An image of the random number corresponding value, the secret key corresponding value, and the label information includes the random number corresponding value, the secret key corresponding value, and the label information using a signature generation key corresponding to the signature verification key. A signature obtained on the information,
The message authenticator includes the signature verification key, the random number corresponding value, the secret key corresponding value, and the signature.
An authenticator generation device characterized by the above. An authenticator generating device according to claim 3, wherein
Λ, Ω and κ are constants, g is a generator of a group of order N, r is a second random number, the first secret key is t, the second secret key is k, and the corresponding key is f = g ^ΛΩt , The random number is s = g ^Ωr , the random number corresponding value is y = (u, w), u = g ^ΩΛr , w = (f · g ^ovk ) ^r , the signature verification key is ovk, and the common key is (lsb _N (S), lsb _N (s ² ),..., Lsb _N (s ^{v (κ−1)} )), v (i) = 2 ⁱ , lsb _N (α) is α − (N−1) / 2 This is information corresponding to a value expressed by an integer of (N-1) / 2 or less.
An authenticator generation device characterized by the above. An authenticator generating device according to claim 3, wherein
v and h are group elements, g is a generator of the group, r is a second random number, e is a bilinear mapping, the first secret key is t, the second secret key is k, and the corresponding key is f = g ^t , the random number is s = v ^r , the random number corresponding value is y = (u, w), u = g ^r , w = (f · v ^ovk ) ^r , the signature verification key is ovk, and the common key is e (s, h),
An authenticator generation device characterized by the above. The authenticator generation device according to any one of claims 3 to 5 ,
The first map and the second map are homomorphic maps;
An authenticator generation device characterized by the above. The private key and the corresponding key are a key pair,
A verification label information generation unit for obtaining verification label information corresponding to information including the corresponding key and the message;
Using a message authenticator, a secret key correspondence value, and the verification label information, and a verification unit that verifies the message,
The message authenticator includes a random number corresponding value, an image for the secret key corresponding value, and label information, and the random number corresponding value;
A verification apparatus characterized by that. The verification device according to claim 7 , comprising:
The verification label information is a value obtained by applying a mapping having difficulty in collision to information including the corresponding key and the message.
A verification apparatus characterized by that. The verification device according to claim 7 or 8 , comprising:
The secret key includes a first secret key;
The corresponding key is a value obtained by applying a first mapping to the first secret key;
The message authenticator includes a signature verification key, the random number corresponding value, the secret key corresponding value, and a signature;
The verification unit includes a signature verification unit that uses the signature verification key to verify whether the signature is valid for information including the random number corresponding value, the secret key corresponding value, and the verification label information;
A verification apparatus characterized by that. The verification device according to claim 9 , comprising:
The secret key further includes a second secret key;
The verification unit
An inverse element search unit that obtains a random number restoration value by operating an inverse element search map corresponding to the corresponding key and the signature verification key on the random number corresponding value;
A determination unit that determines whether the decrypted value obtained by decrypting the secret key corresponding value with the common key corresponding to the random number restoration value matches the second secret key;
A verification apparatus characterized by that. A verification device according to claim 1 0,
Λ, Ω, and κ are constants, g is a generator of group N, the first secret key is t, the second secret key is k, the corresponding key is f = g ^ΛΩt , and the random number restoration value is s , The random number corresponding value is y = (u, w), the signature verification key is ovk, and the common key is (lsb _N (s), lsb _N (s ² ),..., Lsb _N (s ^{v (κ−1) )} )), V (i) = 2 ⁱ , lsb _N (α) is information corresponding to a value in which α is represented by an integer of − (N−1) / 2 or more and (N−1) / 2 or less,
The inverse element search unit obtains (w ^a · u ^b-at ) ^{v (ovk−c)} for integers a, b, c satisfying 2 ^c = a * ovk + bΛΩ as the random number restoration value,
A verification apparatus characterized by that. A verification device according to claim 1 0,
v and h are group elements, g is the group generator, e is a bilinear mapping, the first secret key is t, the second secret key is k, the corresponding key is f = g ^t , and the random number is supported The value is y = (u, w), the signature verification key is ovk, the common key is e (s, h),
The inverse element search unit obtains (w · u ^−t ) ^{(1 / ovk)} as the random number restoration value;
A verification apparatus characterized by that. Be any of the verification device of claims 9 1 2,
The first shooting image is homomorphism mapping,
A verification apparatus characterized by that. Program for causing a computer to function as one of the authentication code generation apparatus of claims 1 6. Program for causing a computer to function as any of the verification device of claims 7 1 3.

Images