JP6225097B2 - Signature / Verification System, Signature Device, Verification Device, Signature / Verification Method, Program - Google Patents

Description

  The present invention relates to a signature / verification system, a signature apparatus, a verification apparatus, a signature / verification method, and a program using a group structure maintenance signature scheme.

  A normal signing key contains an integer element. As a non-dialogue proof indicating that a signature key including an integer element is known, the technique of Non-Patent Document 1 is known. However, this method is very inefficient because the signature key is decomposed and verified for each bit. Therefore, the subject of the present invention is a group structure maintenance signature scheme.

  The group structure maintenance signature method is a digital signature method in which a verification key, a message to be signed, and a signature are composed only of group elements, and a verification function is composed only of group operations and pairing product operations. . Groth-Sahai non-dialogue proof system is a technology that can prove that group elements satisfy a functional expression represented by a pairing product while keeping the group elements secret. If it is a group structure maintenance signature method, by using the Groth-Sahai non-dialogue proof system, the constituent elements consisting of the group elements, that is, the verification key, the message, and the arbitrary elements of the signature are kept secret while keeping them secret We can easily prove that satisfies the verification formula consisting of the pairing product.

  A signature scheme shown in Non-Patent Document 2 is known as a digital signature scheme in which a verification key, a signature, and signature keys that are elements other than a message are group elements. Based on this scheme, a signature scheme shown in Non-Patent Document 3 is known as a digital signature scheme in which a message is also made a group element and all of a verification key, a message, a signature, and a signature key are group elements.

Sarah Meiklejohn, “An Extension of the Groth-Sahai Proof System”, [October 22, 2014 search], Internet <http://cseweb.ucsd.edu/~smeiklejohn/files/mastersthesis.pdf>. Dennis Hofheinz, Tibor Jager, and Edward Knapp, “Waters Signatures with Optimal Security Reduction”, [October 22, 2014 search], Internet <http://eprint.iacr.org/2011/703.pdf>. Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, Miyako Ohkubo, “Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions”, ASIACRYPT 2012: 4-24.

  With the digital signature scheme of Non-Patent Document 3, it can be proved by Groth-Sahai non-dialogue proof that the verification formula holds while all of the verification key, message, signature, and signature key are kept secret. In other words, a signing key that was difficult for non-dialogue proof by the normal group structure maintenance signature method can be efficiently shown by non-dialogue proof. However, the signature scheme shown in Non-Patent Document 3 cannot be potentially forged only against a so-called extended random message attack, and has not achieved forgery against a more desirable adaptive selection message attack. No (not secure against selective message attacks).

  Therefore, an object of the present invention is to provide a group structure maintenance signature method in which a verification key, a message, a signature, and a signature key are all group elements and have security against a selective message attack.

The signature / verification system of the present invention includes a signature device and a verification device. _{First, G 1, G 2, G} T the order p group, e and _{G 1} × _{G 2} → _G pairing _T, then any generator of the group _{G 1} and _{g 1,} the _{g 2} groups _{G 2} Arbitrary generators, K is a predetermined integer greater than or equal to 1, k is an integer greater than or equal to 1 and less than or equal to K, m ₁ ,..., M _K is an element of group G ₁ and message M is M = (m ₁ ,. _K ), ^ is a sign indicating a power, u, f ₀₂ ,..., F _K2 , f ₀₃ ,..., F _K3 is an integer that is randomly selected from 1 to p−1, U ₁ = g ₁ ^ u, U ₂ = g ₂ ^ u, (F ₁₀₂ ,..., F _1K2 ) = (g ₁ ^ f ₀₂ ,..., G ₁ ^ f _K2 ), (F ₁₀₃ ,..., F _1K3 ) = (g ₁ ^ f ₀₃ , _{..., g 1 ^ f K3)} , (F 202, ..., F 2K2) = (g 2 ^ f 02, ..., g 2 ^ f K2), (F 203, ..., F 2K3) = (g _{2 ^ f 03, ..., g} 2 ^ f K3), ~ that logarithmic values of the original _{g 2} logarithm values and a group _{G 2} to the base original _{g 1} of the group _{G 1} and the bottom is equal to Is a symbol indicating.

The signature device includes a key generation unit, a one-time key generation unit, a message signature generation unit, and a one-time signature generation unit, and outputs a verification key vk, a one-time verification key opk, and signatures S ₁ and S ₂ . The verification device includes a message signature verification unit and a one-time signature verification unit, acquires a verification key vk, a one-time verification key opk, signatures S ₁ and S ₂ and a message M and verifies the signatures S ₁ and S ₂ .

Key generating _{unit, V 1 ~V 2, V 1} '~V 2', based on _V 1, _{V 1} of the group _{G 1} as H 1 to H ₂ is true ', _{H 1} and original _{V 2} groups _{G 2} , V ₂ ′, H ₂ , a, b, α are randomly selected from integers between 0 and p−1, ρ is randomly selected from integers between 1 and p−1, and R ₂ = V ₂ (V ₂ ') ^a
vk ₁ = g ₂ ^b , vk ₂ = g ₂ ^a , vk ₃ = g ₂ ^ba , vk ₄ = R ₂ , vk ₅ = R ₂ ^b , vk ₆ = H ₂ , vk ₇ = g ₁ ^ρ , vk ₈ = g ₂ ^{αb / ρ} is obtained,
A verification key vk including vk ₁ , vk ₂ , vk ₃ , vk ₄ , vk ₅ , vk ₆ , vk ₇ , vk ₈ and a signature key including vk, g ₁ ^α , g ₁ ^b , V ₁ , V ₁ ′ sk is generated.

The one-time key generation unit randomly selects v, a ₁ ,..., A _K from integers of 0 or more and p−1 or less,
(N ₂₀₁ , N ₂₀₂ , N ₂₀₀ ) = (F ₂₀₂ ^ v, F ₂₀₃ ^ v, U ₂ ^ v) and i = 1,..., K (N _2i1 , N _2i2 , N _2i0 ) = (F _{2i2 ^ a i, F 2i3 ^ a} i, U 2 ^ a i)
Calculate
_{(N 201, N 202, N} 200), ..., generates the _{(N 2K1, N 2K2, N} 2K0) and the one-time verification key opk _{including, v,} a 1, ..., one-time signature key osk comprising _{a K} To do.

Message signature generation unit obtains the message M, by using a one-time signature key osk, a signature for the message M according to a predetermined signature scheme with security against selection message attacks, the group G ₁ origional or A signature S ₁ including only elements of group G ₂ is generated.

The one-time signature generation unit randomly selects r ₁ , r ₂ , and z from integers between 0 and p−1,
r = r ₁ + r ₂ (mod p)
Seeking

σ ₁ = g ₁ ^α V ₁ ^{r
_{σ 2 = (V 1 ')}} r g 1 -z
σ ₃ = (g ₁ ^b ) ^z
σ ₄ = (g ₁ ^b ) ^ r ₂
σ ₅ = g ₁ ^ r ₁
And a signature S ₂ including σ ₀ , σ ₁ , σ ₂ , σ ₃ , σ ₄ , σ ₅ is generated.

Message signature verification unit acquires the one-time verification key opk the signature S ₁ and the message M, by using a one-time verification key opk acquired, verifies the signature S ₁ obtained in accordance with a predetermined signature scheme.

One-time signature verification unit acquires the verification key vk signature S ₂ and the one-time verification key opk,

e (σ ₁ , vk ₁ ) e (σ ₂ , vk ₃ ) e (σ ₃ , vk ₂ ) = e (σ ₄ , vk ₄ ) e (σ ₅ , vk ₅ ) e (vk ₇ , vk ₈ )
e (F _1i2 , N _2i0 ) = e (U ₁ , N _2i1 ) (where i = 0,..., K)
e (F _1i3 , N _2i0 ) = e (U ₁ , N _2i2 ) (where i = 0,..., K)
To verify the signature S ₂ acquired by confirming that all is true of.

According to the signature-verification system of the present invention, the signature S ₁ with respect to the message M, it is generated by utilizing the group structure maintained signature scheme with security against selection message attacks as a one-time signature scheme. The signature of the device one-time signature for verification key S _2, which itself can be randomly generated, the verification key, message, signature, but all of the signature key is a group element have only to safety for a random message attack signature scheme It is generated with. By combining the two signature schemes in this way, it is possible to provide a group structure maintaining signature scheme that has security against selective message attacks, with all of the verification key, message, signature, and signature key being group elements.

The figure which shows the structural example of the signature and verification system of this invention. The figure which shows the processing flow of the signature apparatus of this invention. The figure which shows the processing flow of the verification apparatus 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.

FIG. 1 shows a configuration example of the signature / verification system of the present invention, FIG. 2 shows a processing flow of the signature apparatus of the present invention, and FIG. 3 shows a processing flow of the verification apparatus of the present invention. The signature / verification system includes a signature device 100 and a verification device 200 connected via a network 800. The signature device 100 includes a key generation unit 110, a one-time key generation unit 120, a message signature generation unit 130, a one-time signature generation unit 140, and a signature recording unit 190, and includes a verification key vk, a one-time verification key opk, and a signature S _1. , S ₂ is output. The verification device 200 includes a message signature verification unit 230, a one-time signature verification unit 240, and a verification recording unit 290. The verification device 200 acquires the verification key vk, the one-time verification key opk, the signatures S ₁ and S ₂ and the message M and acquires the signature S. _1, to verify the _{S 2.}

_{First, G 1, G 2, G} T the order p group, e and _{G 1} × _{G 2} → _G pairing _T, then any generator of the group _{G 1} and _{g 1,} the _{g 2} groups _{G 2} Arbitrary generators, K is a predetermined integer greater than or equal to 1, k is an integer greater than or equal to 1 and less than or equal to K, m ₁ ,..., M _K is an element of group G ₁ and message M is M = (m ₁ ,. _K ), ^ is a sign indicating a power, u, f ₀₂ ,..., F _K2 , f ₀₃ ,..., F _K3 is an integer that is randomly selected from 1 to p−1, U ₁ = g ₁ ^ u, U ₂ = g ₂ ^ u, (F ₁₀₂ ,..., F _1K2 ) = (g ₁ ^ f ₀₂ ,..., G ₁ ^ f _K2 ), (F ₁₀₃ ,..., F _1K3 ) = (g ₁ ^ f ₀₃ , _{..., g 1 ^ f K3)} , (F 202, ..., F 2K2) = (g 2 ^ f 02, ..., g 2 ^ f K2), (F 203, ..., F 2K3) = (g ₂ ^ _f 03, _..., and g 2 _{^ f K3).} In addition, ˜ is a symbol indicating that the logarithm value of the original g ₁ of the group G ₁ and the logarithm value of the original g ₂ of the group G ₂ are equal. That is, V _{1 to} V ₂ are

Shows the relationship. The pairing e is a mapping having the property that e (g ₁ ^a , g ₂ ^b ) = e (g ₁ , g ₂ ) ^ab , e (g ₁ , g ₂ ) ≠ 1. _{Further, p, G 1, G 2} , G T, e, (F 102, ..., F 1K2), (F 103, ..., F 1K3), (F 202, ..., F 2K2), (F 203, ... , F _2K3 ), U ₁ , U ₂ are predetermined common parameters (global keys including bilinear mapping group expressions), and are recorded in the signature recording unit 190 and the verification recording unit 290 in advance. To do.

The key generation unit _{110, V 1 ~V 2, V 1} '~V 2', based on _V 1, _{V 1} of the group _{G 1} as H 1 to H ₂ is true ', the original V of an _{H 1} and the group _{G 2 2} , V ₂ ′, and H ₂ are determined, a, b, and α are randomly selected from integers of 0 or more and p−1 or less, and ρ is randomly selected from integers of 1 or more and p−1 or less. Then, the key generation unit 110
vk ₁ = g ₂ ^b , vk ₂ = g ₂ ^a , vk ₃ = g ₂ ^ba , vk ₄ = R ₂ , vk ₅ = R ₂ ^b , vk ₆ = H ₂ , vk ₇ = g ₁ ^ρ , vk ₈ = g ₂ ^{αb / ρ} is obtained,
A verification key vk including vk ₁ , vk ₂ , vk ₃ , vk ₄ , vk ₅ , vk ₆ , vk ₇ , vk ₈ and a signature key including vk, g ₁ ^α , g ₁ ^b , V ₁ , V ₁ ′ sk is generated (S110). _{However, R 2 = V 2 (V} 2 ') is ^a.

The one-time key generation unit 120 randomly selects v, a ₁ ,..., A _K from integers between 0 and p−1. Then, the one-time key generation unit 120
(N ₂₀₁ , N ₂₀₂ , N ₂₀₀ ) = (F ₂₀₂ ^ v, F ₂₀₃ ^ v, U ₂ ^ v) and i = 1,..., K (N _2i1 , N _2i2 , N _2i0 ) = (F _{2i2 ^ a i, F 2i3 ^ a} i, U 2 ^ a i)
Calculate
_{(N 201, N 202, N} 200), ..., generates the _{(N 2K1, N 2K2, N} 2K0) and the one-time verification key opk _{including, v,} a 1, ..., one-time signature key osk comprising _{a K} (S120).

The message signature generation unit 130 obtains the message M, and uses the one-time signature key osk to sign the message M according to a predetermined signature scheme that is secure against the selected message attack and is an element of the group G ₁ Alternatively, the signature S ₁ including only the elements of the group G ₂ is generated (S 130). Since the one-time verification key opk, the message M, and the signature S ₁ are all composed only of the elements of the group G ₁ or the elements of the group G ₂ , the signature scheme used by the message signature generation unit 130 is the group structure maintenance signature. It is a method. As a specific example of a signature method having security against a selected message attack, the message signature generation unit 130

As in, there is a method of determining the signature S _1. However, the signature scheme used by the message signature generation unit 130 may be any other signature scheme as long as it is a group structure maintenance signature scheme that is secure against a selected message attack. The message M to be signed of interest of K original group G _1. While regular message is an integer of arbitrary length, in which case, may be converted to a K-number of the original group G _1. The converted message is defined as a message M of the present application. If the message to be signed in the subject is short, it make the message M by padding so that the K of the original group G _1. Values padding may if choose beforehand out of the original group G _1.

The one-time signature generation unit 140 randomly selects r ₁ , r ₂ , and z from integers of 0 or more and p−1 or less,
r = r ₁ + r ₂ (mod p)
Ask for. Then, the one-time signature generation unit 140

σ ₁ = g ₁ ^α V ₁ ^{r
_{σ 2 = (V 1 ')}} r g 1 -z
σ ₃ = (g ₁ ^b ) ^z
σ ₄ = (g ₁ ^b ) ^ r ₂
σ ₅ = g ₁ ^ r ₁
And a signature S ₂ including σ ₀ , σ ₁ , σ ₂ , σ ₃ , σ ₄ , and σ ₅ is generated (S 140). In this process, and it generates a signature S ₂ for a one-time verification key opk using the signature key sk. Through these processes, the signature device 100 outputs the verification key vk, the one-time verification key opk, and the signatures S ₁ and S ₂ .

Message signature verification unit 230 acquires the one-time verification key opk the signature S ₁ and the message M, by using a one-time verification key opk acquired signature S obtained in accordance signature scheme message signature generation unit 130 according ₁ is verified (S230). For example, in the case of the specific example of the signature S ₁ shown in the description of the message signature generation unit 130, the message signature verification unit 230 includes m ₁ ,..., M _K included in the acquired message M and the acquired signature S _1. Is an element of group G ₁ and

If it is correct, it is OK. If it is not correct, NG is determined. If the acquired signature S ₁ is the correct signature

Thus, the left side and the right side are equal, and can be verified by the above calculation.

One-time signature verification unit 240, to obtain the the verification key vk signature _{S 2} and the one-time verification key opk,

e (σ ₁ , vk ₁ ) e (σ ₂ , vk ₃ ) e (σ ₃ , vk ₂ ) = e (σ ₄ , vk ₄ ) e (σ ₅ , vk ₅ ) e (vk ₇ , vk ₈ )
e (F _1i2 , N _2i0 ) = e (U ₁ , N _2i1 ) (where i = 0,..., K)
e (F _1i3 , N _2i0 ) = e (U ₁ , N _2i2 ) (where i = 0,..., K)
To verify the signature S ₂ acquired by confirming that all is true of (S240). That is, if all the expressions are satisfied, it is determined to be OK, and if any expression is not satisfied, it is determined to be NG.

Then, indicating that the first equation holds true if correct the acquired signature S _2. The first equation is

Next, it holds If it is correct acquired signature S _2. The second equation is

It becomes. _{Here, V 1 ~V 2, V 1} '~V 2' V 1 As is _{true, V 2, V 1 ',} V 2' so is determined, if correct signature _{S 2} acquired (left ) = (Right side). The third equation is
( _Left side) = e (F _1i2 , N _2i0 )
= E (g ₁ ^ f _i2 , U ₂ ^ a _i )
= E (g ₁ , g ₂ ^ u) ^ (f _i2 · a _i )
= E (g ₁ , g ₂ ) ^ (u · f _i2 · a _i )
(Right side) = e (U ₁ , N _2i1 )
= E (U ₁ , F _2i2 ^ a _i )
= E (g ₁ ^ u, g ₂ ^ f _i2 ) ^ a _i
= E (g ₁ , g ₂ ) ^ (u · f _i2 · a _i )
It becomes. Therefore, if correct the acquired signature _{S 2} (left side) = (right side) is satisfied. The fourth equation is
( _Left side) = e (F _1i3 , N _2i0 )
= E (g ₁ ^ f _i3 , U ₂ ^ a _i )
= E (g ₁ , g ₂ ^ u) ^ (f _i3 · a _i )
= E (g ₁ , g ₂ ) ^ (u · f _i3 · a _i )
( _Right side) = e (U ₁ , N _2i2 )
= E (U ₁ , F _2i3 ^ a _i )
= E (g ₁ ^ u, g ₂ ^ f _i3 ) ^ a _i
= E (g ₁ , g ₂ ) ^ (u · f _i3 · a _i )
It becomes. Therefore, if correct the acquired signature _{S 2} (left side) = (right side) is satisfied.

Here, the one-time key generation unit 120, the message signature generation unit 130, and the one-time signature generation unit 140 of the signature device 100 are considered as a signature generation unit 150 as a group. The key generation unit 110 is the same as the key generation in Non-Patent Document 3, and the signature generation unit 150 is different from that in Non-Patent Document 3. Specifically, the generation of the signature S ₂ signature device 100 for one-time verification key can be randomly generated internally, the verification key, the message, the signature, all the signature key is a group element security against random message attacks utilizing signature scheme only to the signature S ₁ with respect to the message M is generated by the group structure maintained signature scheme with security against selection message attacks. By combining the two signature schemes in this way, it is possible to provide a group structure maintaining signature scheme that has security against selective message attacks, with all of the verification key, message, signature, and signature key being group elements.

[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, for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.

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

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

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

100 Signature Device 110 Key Generation Unit 120 One-Time Key Generation Unit 130 Message Signature Generation Unit 140 One-Time Signature Generation Unit 150 Signature Generation Unit 190 Signature Recording Unit 200 Verification Device 230 Message Signature Verification Unit 240 One-Time Signature Verification Unit 290 Verification Recording Unit 800 network

Claims (8)

A signature / verification system having a signature device and a verification device,
_{G 1,} G 2, G _T the order p group, e and _{G 1} × pairing _{G 2} → _{G T, g 1} any generator of the group _{G 1, g 2} any of the group _{G 2} Generator, K is a predetermined integer of 1 or more, k is an integer of 1 to K, m ₁ ,..., M _K is an element of group G ₁ , and message M is M = (m ₁ ,..., M _K ) , ^ Is a symbol indicating a power, u, f ₀₂ ,..., F _K2 , f ₀₃ ,..., F _K3 is an integer selected randomly from 1 to p−1, U ₁ = g ₁ ^ u, U ₂ = g ₂ ^ u, (F ₁₀₂ ,..., F _1K2 ) = (g ₁ ^ f ₀₂ ,..., g ₁ ^ f _K2 ), (F ₁₀₃ ,..., F _1K3 ) = (g ₁ ^ f _{03 ,. g 1 ^ f K3), (} F 202, ..., F 2K2) = (g 2 ^ f 02, ..., g 2 ^ f K2), (F 203, ..., F 2K3) = (g 2 ^ _{03, ..., g 2 ^ f} K3), symbol indicates that equal the logarithm of the value and ~ a bottom original _{g 2} logarithm values and a group _{G 2} to the base original _{g 1} of the group _{G 1} age,
The signing device is:
_{V 1 ~V 2, V 1 '} ~V 2', based on _V 1, _{V 1} of the group _{G 1} as H 1 to H ₂ is true ', the original _V 2, _{V 2} of an _{H 1} and the group _{G 2',} H ₂ is determined, a, b, α are randomly selected from integers of 0 or more and p−1 or less, ρ is randomly selected from integers of 1 or more and p−1 or less, and R ₂ = V ₂ (V ₂ ') ^a
vk ₁ = g ₂ ^b , vk ₂ = g ₂ ^a , vk ₃ = g ₂ ^ba , vk ₄ = R ₂ , vk ₅ = R ₂ ^b , vk ₆ = H ₂ , vk ₇ = g ₁ ^ρ , vk ₈ = g ₂ ^{αb / ρ} is obtained,
A verification key vk including vk ₁ , vk ₂ , vk ₃ , vk ₄ , vk ₅ , vk ₆ , vk ₇ , vk ₈ and a signature key including vk, g ₁ ^α , g ₁ ^b , V ₁ , V ₁ ′ a key generation unit for generating sk;
Randomly selecting v, a ₁ ,..., A _K from integers of 0 or more and p−1 or less,
(N ₂₀₁ , N ₂₀₂ , N ₂₀₀ ) = (F ₂₀₂ ^ v, F ₂₀₃ ^ v, U ₂ ^ v) and i = 1,..., K (N _2i1 , N _2i2 , N _2i0 ) = (F _{2i2 ^ a i, F 2i3 ^ a} i, U 2 ^ a i)
Calculate
_{(N 201, N 202, N} 200), ..., generates the _{(N 2K1, N 2K2, N} 2K0) and the one-time verification key opk _{including, v,} a 1, ..., one-time signature key osk comprising _{a K} A one-time key generator to
The message M is acquired, and the signature for the message M, which is the element of the group G ₁ or the element of the group G ₂ , according to a predetermined signature scheme having security against the selected message attack using the one-time signature key osk. A message signature generation unit for generating a signature S ₁ including only
R ₁ , r ₂ , and z are selected at random from integers of 0 or more and p−1 or less,
r = r ₁ + r ₂ (mod p)
Seeking

σ ₁ = g ₁ ^α V ₁ ^{r
_{σ 2 = (V 1 ')}} r g 1 -z
σ ₃ = (g ₁ ^b ) ^z
σ ₄ = (g ₁ ^b ) ^ r ₂
σ ₅ = g ₁ ^ r ₁
And a one-time signature generation unit that generates a signature S ₂ including σ ₀ , σ ₁ , σ ₂ , σ ₃ , σ ₄ , and σ ₅ , and includes a verification key vk, a one-time verification key opk, and a signature S ₁ , and it outputs the S _2,
The verification device includes:
A message signature verification unit that obtains a one-time verification key opk, a signature S ₁ and a message M, and verifies the signature S ₁ according to the predetermined signature scheme using the one-time verification key opk; and a verification key vk Obtain signature S ₂ and one-time verification key opk,

e (σ ₁ , vk ₁ ) e (σ ₂ , vk ₃ ) e (σ ₃ , vk ₂ ) = e (σ ₄ , vk ₄ ) e (σ ₅ , vk ₅ ) e (vk ₇ , vk ₈ )
e (F _1i2 , N _2i0 ) = e (U ₁ , N _2i1 ) (where i = 0,..., K)
e (F _1i3 , N _2i0 ) = e (U ₁ , N _2i2 ) (where i = 0,..., K)
One-time signature verification unit for verifying the signature S ₂ by making sure that all is true of,
A signature / verification system. The signature / verification system according to claim 1,
The message signature generation unit

And ask for signature S ₁
The message signature verification unit
M ₁ ,..., M _K included in the acquired message M and the acquired signature S ₁ are elements of the group G ₁ , and

A signature / verification system characterized by confirming that A signature device that constitutes a signature / verification system together with a verification device,
_{G 1,} G 2, G _T the order p group, e and _{G 1} × pairing _{G 2} → _{G T, g 1} any generator of the group _{G 1, g 2} any of the group _{G 2} Generator, K is a predetermined integer of 1 or more, k is an integer of 1 to K, m ₁ ,..., M _K is an element of group G ₁ , and message M is M = (m ₁ ,..., M _K ) , ^ Is a symbol indicating a power, u, f ₀₂ ,..., F _K2 , f ₀₃ ,..., F _K3 is an integer selected randomly from 1 to p−1, U ₁ = g ₁ ^ u, U ₂ = g ₂ ^ u, (F ₁₀₂ ,..., F _1K2 ) = (g ₁ ^ f ₀₂ ,..., g ₁ ^ f _K2 ), (F ₁₀₃ ,..., F _1K3 ) = (g ₁ ^ f _{03 ,. g 1 ^ f K3), (} F 202, ..., F 2K2) = (g 2 ^ f 02, ..., g 2 ^ f K2), (F 203, ..., F 2K3) = (g 2 ^ _{03, ..., g 2 ^ f} K3), symbol indicates that equal the logarithm of the value and ~ a bottom original _{g 2} logarithm values and a group _{G 2} to the base original _{g 1} of the group _{G 1} age,
The signature device includes a key generation unit, a one-time key generation unit, a message signature generation unit, a one-time signature generation unit,
The key generation unit
_{V 1 ~V 2, V 1 '} ~V 2', based on _V 1, _{V 1} of the group _{G 1} as H 1 to H ₂ is true ', the original _V 2, _{V 2} of an _{H 1} and the group _{G 2',} H ₂ is determined, a, b, α are randomly selected from integers of 0 or more and p−1 or less, ρ is randomly selected from integers of 1 or more and p−1 or less, and R ₂ = V ₂ (V ₂ ') ^a
vk ₁ = g ₂ ^b , vk ₂ = g ₂ ^a , vk ₃ = g ₂ ^ba , vk ₄ = R ₂ , vk ₅ = R ₂ ^b , vk ₆ = H ₂ , vk ₇ = g ₁ ^ρ , vk ₈ = g ₂ ^{αb / ρ} is obtained,
A verification key vk including vk ₁ , vk ₂ , vk ₃ , vk ₄ , vk ₅ , vk ₆ , vk ₇ , vk ₈ and a signature key including vk, g ₁ ^α , g ₁ ^b , V ₁ , V ₁ ′ generate sk,
The one-time key generation unit
Randomly selecting v, a ₁ ,..., A _K from integers of 0 or more and p−1 or less,
(N ₂₀₁ , N ₂₀₂ , N ₂₀₀ ) = (F ₂₀₂ ^ v, F ₂₀₃ ^ v, U ₂ ^ v) and i = 1,..., K (N _2i1 , N _2i2 , N _2i0 ) = (F _{2i2 ^ a i, F 2i3 ^ a} i, U 2 ^ a i)
Calculate
_{(N 201, N 202, N} 200), ..., generates the _{(N 2K1, N 2K2, N} 2K0) and the one-time verification key opk _{including, v,} a 1, ..., one-time signature key osk comprising _{a K} And
The message signature generation unit
The message M is acquired, and the signature for the message M, which is the element of the group G ₁ or the element of the group G ₂ , according to a predetermined signature scheme having security against the selected message attack using the one-time signature key osk. Generates a signature S ₁ containing only
The one-time signature generator
R ₁ , r ₂ , and z are selected at random from integers of 0 or more and p−1 or less,
r = r ₁ + r ₂ (mod p)
Seeking

σ ₁ = g ₁ ^α V ₁ ^{r
_{σ 2 = (V 1 ')}} r g 1 -z
σ ₃ = (g ₁ ^b ) ^z
σ ₄ = (g ₁ ^b ) ^ r ₂
σ ₅ = g ₁ ^ r ₁
And a signature S ₂ including σ ₀ , σ ₁ , σ ₂ , σ ₃ , σ ₄ , and σ ₅ is generated. The signature device according to claim 3,
The message signature generation unit

As the signature device and obtains the signature S _1. A verification device that receives a verification key vk, a one-time verification key opk, signatures S ₁ , S ₂ , and a message M and verifies the signatures S ₁ , S ₂ ,
_{G 1,} G 2, G _T the order p group, e and _{G 1} × pairing _{G 2} → _{G T, g 1} any generator of the group _{G 1, g 2} any of the group _{G 2} Generator, K is a predetermined integer of 1 or more, k is an integer of 1 to K, m ₁ ,..., M _K is an element of group G ₁ , and message M is M = (m ₁ ,..., M _K ) , ^ Is a symbol indicating a power, u, f ₀₂ ,..., F _K2 , f ₀₃ ,..., F _K3 is an integer selected randomly from 1 to p−1, U ₁ = g ₁ ^ u, U ₂ = g ₂ ^ u, (F ₁₀₂ ,..., F _1K2 ) = (g ₁ ^ f ₀₂ ,..., g ₁ ^ f _K2 ), (F ₁₀₃ ,..., F _1K3 ) = (g ₁ ^ f _{03 ,. g 1 ^ f K3), (} F 202, ..., F 2K2) = (g 2 ^ f 02, ..., g 2 ^ f K2), (F 203, ..., F 2K3) = (g 2 ^ _{03, ..., g 2 ^ f} K3), symbol indicates that equal the logarithm of the value and ~ a bottom original _{g 2} logarithm values and a group _{G 2} to the base original _{g 1} of the group _{G 1} age,
Source _V 1, _{V 1} of the group _{G 1} ', _{H 1} and source _V 2, _{V 2} of the group _{G 2', H 2} is _{V 1 ~V 2, V 1 '} ~V 2', is H 1 to H ₂ Thus, a, b, α are integers of 0 or more and p−1 or less, ρ is an integer of 1 or more and p−1 or less, R ₂ = V ₂ (V ₂ ′) ^a , vk ₁ = g ₂ ^b , vk ₂ = g ₂ ^a , vk ₃ = g ₂ ^ba , vk ₄ = R ₂ , vk ₅ = R ₂ ^b , vk ₆ = H ₂ , vk ₇ = g ₁ ^ρ , vk ₈ = g ₂ ^{αb / ρ} ,
v, a ₁ ,..., a _K is an integer from 0 to p−1,
(N ₂₀₁ , N ₂₀₂ , N ₂₀₀ ) = (F ₂₀₂ ^ v, F ₂₀₃ ^ v, U ₂ ^ v),
About i = 1,..., K (N _2i1 , N _2i2 , N _2i0 ) = (F _2i2 ^ a _i , F _2i3 ^ a _i , U ₂ ^ a _i )
And
r ₁ , r ₂ , z is an integer of 0 or more and p−1 or less, r = r ₁ + r ₂ (mod p),

σ ₁ = g ₁ ^α V ₁ ^{r
_{σ 2 = (V 1 ')}} r g 1 -z
σ ₃ = (g ₁ ^b ) ^z
σ ₄ = (g ₁ ^b ) ^ r ₂
σ ₅ = g ₁ ^ r ₁
And
The verification key vk includes vk ₁ , vk ₂ , vk ₃ , vk ₄ , vk ₅ , vk ₆ , vk ₇ , vk ₈ ,
The one-time verification key opk includes (N ₂₀₁ , N ₂₀₂ , N ₂₀₀ ),..., (N _2K1 , N _2K2 , N _2K0 ),
The signature S ₁ is a signature for the message M generated using the one-time signature key osk according to a predetermined signature scheme that is secure against a selected message attack, and is an element of the group G ₁ or the group G _2. Contains only
Signature S ₂ includes σ ₀ , σ ₁ , σ ₂ , σ ₃ , σ ₄ , σ ₅ ,
The verification device includes a message signature verification unit and a one-time signature verification unit,
The message signature verification unit
One-time verification key opk, signature S ₁ and message M are acquired, and using the one-time verification key opk, the signature S ₁ is verified according to the predetermined signature scheme,
The one-time signature verification unit
Get the the verification key vk signature _{S 2} and the one-time verification key opk,

e (σ ₁ , vk ₁ ) e (σ ₂ , vk ₃ ) e (σ ₃ , vk ₂ ) = e (σ ₄ , vk ₄ ) e (σ ₅ , vk ₅ ) e (vk ₇ , vk ₈ )
e (F _1i2 , N _2i0 ) = e (U ₁ , N _2i1 ) (where i = 0,..., K)
e (F _1i3 , N _2i0 ) = e (U ₁ , N _2i2 ) (where i = 0,..., K)
Verification apparatus characterized by verifying the signature S ₂ by checking that all holds the. The verification device according to claim 5,
The signature _{S 1} is

Is what was sought,
The message signature verification unit
M ₁ ,..., M _K included in the acquired message M and the acquired signature S ₁ are elements of the group G ₁ , and

The verification apparatus characterized by confirming that it is. A signature / verification method using a signature device and a verification device,
_{G 1,} G 2, G _T the order p group, e and _{G 1} × pairing _{G 2} → _{G T, g 1} any generator of the group _{G 1, g 2} any of the group _{G 2} Generator, K is a predetermined integer of 1 or more, k is an integer of 1 to K, m ₁ ,..., M _K is an element of group G ₁ , and message M is M = (m ₁ ,..., M _K ) , ^ Is a symbol indicating a power, u, f ₀₂ ,..., F _K2 , f ₀₃ ,..., F _K3 is an integer selected randomly from 1 to p−1, U ₁ = g ₁ ^ u, U ₂ = g ₂ ^ u, (F ₁₀₂ ,..., F _1K2 ) = (g ₁ ^ f ₀₂ ,..., g ₁ ^ f _K2 ), (F ₁₀₃ ,..., F _1K3 ) = (g ₁ ^ f _{03 ,. g 1 ^ f K3), (} F 202, ..., F 2K2) = (g 2 ^ f 02, ..., g 2 ^ f K2), (F 203, ..., F 2K3) = (g 2 ^ _{03, ..., g 2 ^ f} K3), symbol indicates that equal the logarithm of the value and ~ a bottom original _{g 2} logarithm values and a group _{G 2} to the base original _{g 1} of the group _{G 1} age,
The signature device includes a key generation unit, a one-time key generation unit, a message signature generation unit, a one-time signature generation unit,
The verification device includes a message signature verification unit and a one-time signature verification unit,
The key generation unit
_{V 1 ~V 2, V 1 '} ~V 2', based on _V 1, _{V 1} of the group _{G 1} as H 1 to H ₂ is true ', the original _V 2, _{V 2} of an _{H 1} and the group _{G 2',} H ₂ is determined, a, b, α are randomly selected from integers of 0 or more and p−1 or less, ρ is randomly selected from integers of 1 or more and p−1 or less, and R ₂ = V ₂ (V ₂ ') ^a
vk ₁ = g ₂ ^b , vk ₂ = g ₂ ^a , vk ₃ = g ₂ ^ba , vk ₄ = R ₂ , vk ₅ = R ₂ ^b , vk ₆ = H ₂ , vk ₇ = g ₁ ^ρ , vk ₈ = g ₂ ^{αb / ρ} is obtained,
A verification key vk including vk ₁ , vk ₂ , vk ₃ , vk ₄ , vk ₅ , vk ₆ , vk ₇ , vk ₈ and a signature key including vk, g ₁ ^α , g ₁ ^b , V ₁ , V ₁ ′ a key generation step of generating sk;
The one-time key generation unit
Randomly selecting v, a ₁ ,..., A _K from integers of 0 or more and p−1 or less,
(N ₂₀₁ , N ₂₀₂ , N ₂₀₀ ) = (F ₂₀₂ ^ v, F ₂₀₃ ^ v, U ₂ ^ v) and i = 1,..., K (N _2i1 , N _2i2 , N _2i0 ) = (F _{2i2 ^ a i, F 2i3 ^ a} i, U 2 ^ a i)
Calculate
_{(N 201, N 202, N} 200), ..., generates the _{(N 2K1, N 2K2, N} 2K0) and the one-time verification key opk _{including, v,} a 1, ..., one-time signature key osk comprising _{a K} A one-time key generation step,
The message signature generation unit
The message M is acquired, and the signature for the message M, which is the element of the group G ₁ or the element of the group G ₂ , according to a predetermined signature scheme having security against the selected message attack using the one-time signature key osk. A message signature generation step for generating a signature S ₁ containing only
The one-time signature generation unit
R ₁ , r ₂ , and z are selected at random from integers of 0 or more and p−1 or less,
r = r ₁ + r ₂ (mod p)
Seeking

σ ₁ = g ₁ ^α V ₁ ^{r
_{σ 2 = (V 1 ')}} r g 1 -z
σ ₃ = (g ₁ ^b ) ^z
σ ₄ = (g ₁ ^b ) ^ r ₂
σ ₅ = g ₁ ^ r ₁
And a one-time signature generation step for generating a signature S ₂ including σ ₀ , σ ₁ , σ ₂ , σ ₃ , σ ₄ , and σ ₅ , and executing the verification key vk, the one-time verification key opk, and the signature S ₁ and S ₂ are output,
The message signature verification unit
A message signature verification step of acquiring a one-time verification key opk, a signature S ₁ and a message M, and verifying the signature S ₁ according to the predetermined signature scheme using the one-time verification key opk;
The one-time signature verification unit
Get the the verification key vk signature _{S 2} and the one-time verification key opk,

e (σ ₁ , vk ₁ ) e (σ ₂ , vk ₃ ) e (σ ₃ , vk ₂ ) = e (σ ₄ , vk ₄ ) e (σ ₅ , vk ₅ ) e (vk ₇ , vk ₈ )
e (F _1i2 , N _2i0 ) = e (U ₁ , N _2i1 ) (where i = 0,..., K)
e (F _1i3 , N _2i0 ) = e (U ₁ , N _2i2 ) (where i = 0,..., K)
One-time signature verification step of verifying the signature S ₂ by making sure that all is true of,
Execute the signature / verification method.   A program for causing a computer to function as the signature device according to claim 3 or 4, or the verification device according to claim 5 or 6.

Images