JP4856599B2 - Pairing arithmetic device, program - Google Patents

Description

  The present invention relates to information security technology, and in particular, to a pairing arithmetic device, a program, and the like for realizing pairing arithmetic.

An algorithm for calculating pairing in polynomial time was proposed by Miller, and until around 2000, it was mainly used for attacks of elliptic curve cryptography. Pairing around 2000 is great interest in faster pairing becomes to be used in a cryptographic protocol, through improvement by Duursma like, the following eta _T pairing algorithm given by such Barreto.

  Note that the pairing is a so-called bilinear function that is a two-input one-output function and has linearity for each input. Further, calculating and calculating pairing means obtaining an output when a predetermined value is input to the pairing function.

[Η _T pairing algorithm]
[Preparation] E (F _{3 ^ m} ): Elliptic curve g ₁ (ρ) = ρ ³ −ρ−1 defined on the finite field F _{3 ^ m}
g ₂ (σ) = σ ² +1
The element of F _{3 ^ (6m)} is expressed as an element of F _{3 ^ m} [ρ, σ] / (g ₁ (ρ), g ₂ (σ)).
[Input] P = (x _p , y _p ), Q = (x _q , y _q ) ∈E (F _{3 ^ m} )
[Output] η _T (P, Q) ∈F ^* _{3 ^ (6m)}
〔Method of calculation〕
Step 1: y _p ← −y _p (∈F _{3 ^ m} )
Step 2: f ← −y _p (x _p + x _q +1) + y _q σ + y _p ρ (∈F _{3 ^ (6m)} )
Step 3: Repeat Step 3-1 to Step 3-5 from i = 0 to (m−1) / 2.

Step 3-1: u ← x _p + x _q +1 (∈F _{3 ^ m} )
_{^{Step3-2: g ← -u 2 + y}} p y q σ-uρ-ρ 2 (∈F 3 ^ (6m))
Step 3-3: f ← fg (∈F _{3 ^ (6m)} )
Step 3-4: x _p <-x _p ^(1/3) , y _p <-y _p ^(1/3)
Step 3-5: x _q ← x _q ³ , y _q ← y _q ³
Step 4: f ^{((3 ^ 3m) -1) ((3 ^ m) +1) ((3 ^ m)-(3 ^ ((m + 1) / 2)) + 1)} is output.

Non-Patent Document 1 discloses a method for implementing on a computer multiplication of a finite field F _{3 ^ m} that needs to be calculated in the above-described η _T pairing calculation algorithm. Here, the multiplication of the finite field F _{3 ^ m,} refers to determining the two original product belonging to a finite field F _{3 ^ m.} For example, y _p (x _p + x _q +1) in Step ² and u ² and y _p y _{q in} Step 3-2 are multiplications of a finite field F _{3 ^ m} .

In the technique described in Non-Patent Document 1, each time that the multiplication of the finite field F _{3 ^ m} to generate a pre-operation table, performing multiplication finite F _{3 ^ m} with the pre-calculation table (For example, refer nonpatent literature 1.).

Here, in the η _T pairing calculation algorithm, it is necessary to perform 18 finite field F _{3 ^ m} multiplications in Step 3-2 and Step 3-3, as will be described later. For this reason, when the invention described in Non-Patent Document 1 is applied to the η _T pairing calculation algorithm, the pre-calculation table is generated 18 times in Step 3-2 and Step 3-3.
Yuto Kawahara, 3 others, “High-speed software implementation of ηT pairing”, SCIS2007, 2E3-2, 2007,

In the technique described in Non-Patent Document 1, a pre-operation table is generated every time multiplication of a finite field is performed, and there is a problem that pairing operation cannot be sufficiently speeded up.
An object of this invention is to provide the technique for speeding up the calculation of pairing.

In the pairing calculation device for calculating pairing, the pre-calculation means uses the first number expressed by a polynomial as an element of an extension field based on a certain finite field, and the element of the finite field as a coefficient. A plurality of polynomials having the number of terms Ws (Ws is a predetermined natural number) are respectively multiplied. The pre-calculation table storage means stores, as a pre-calculation table for the first number, a correspondence between each pair of polynomials having the number of terms Ws and the calculation result. The dividing means divides the second number that is an element of the extension field and is expressed by a polynomial into a polynomial having the number of terms w. The reference means refers to the pre-calculation table read from the pre-calculation table storage unit, and obtains the product of the first number and each divided polynomial. The adding means adds the products obtained by the reference means to obtain the product of the first number and the second number. Further, during the pairing operation, when multiplying the first number by a plurality of multiplicands which are elements of the extension field and expressed by polynomials, each multiplicand is set as the second number, and the dividing means and the reference means Then, by performing the processing by the adding means, the product of the first number and the multiplicand is obtained with reference to the same pre-calculated table already read from the pre-calculating table storage means.
The system further comprises first reduction means for reducing the product obtained by the addition means, further comprising second reduction means for reducing the product calculated by the pre-calculation means, and the pre-calculation table includes each set of polynomials having the number of terms Ws. And a calculation result reduced by the second reduction means are stored as a pre-calculation table for the first number, and the pre-calculation table for the first number is stored in the pre-calculation table. If it is determined whether or not the pre-calculation table storage means stores the pre-calculation table for the first number, it is determined whether the pre-calculation means stores the first number. There may be further provided first control means for generating the pre-calculation table.
Alternatively, the image processing apparatus further includes a first reduction unit that reduces the product obtained by the addition unit, further includes a second reduction unit that reduces the product calculated by the pre-calculation unit, and the pre-calculation table includes a polynomial having a number of terms Ws. A means for storing each set in association with the calculation result reduced by the second reduction means as a pre-calculation table for the first number. If it is determined whether the multiplication with the multiplier is performed again and it is determined that the multiplication with the first number as the multiplier is performed again, the preliminary calculation for the first number is stored in the pre-calculation table storage unit. When the table is stored and it is determined that the multiplication using the first number as a multiplier is not performed again, the first number is stored in the pre-calculation table storage means. Second control means for controlling so as not to store the precomputed table you are, it may be further provided.

  In the pairing operation, when performing multiplication of a finite field for a certain multiplier, if a pre-calculation table for the multiplier has already been generated, polynomial multiplication is performed using the generated pre-calculation table. . Thereby, it is not necessary to generate a pre-calculation table every time multiplication of a finite field is performed, and pairing calculation can be performed at high speed.

[theory]
In the above η _T pairing algorithm, f is generally a polynomial of ρ and σ,
f = (c ₀ + c ₁ ρ + c ₂ ρ ² ) + (c ₃ + c ₄ ρ + c ₅ ρ ² ) σ
Can be written. Here, c ₀ , c ₁ , c ₂ , c ₃ , c ₄ , c ₅ ∈ F _{3 ^ m} . Further, when d = y _p y _q , g in the above η _T pairing algorithm is expressed as a polynomial of ρ and σ,
g =-(u ² + uρ + ρ ² ) + dσ
Can be written. Then, the calculation of fg in Step 3-3 is
fg = {(c ₀ + c ₁ ρ + c ₂ ρ ² ) + (c ₃ + c ₄ ρ + c ₅ ρ ² ) σ} × {-(u ² + uρ + ρ ² ) + dσ}
Thus, according to the law of distribution, the calculation of fg can be divided into the following four parts.

(c ₀ + c ₁ ρ + c ₂ ρ ² ) × d (1)
(c ₃ + c ₄ ρ + c ₅ ρ ² ) × d (2)
(c ₀ + c ₁ ρ + c ₂ ρ ² ) × (u ² + uρ + ρ ² ) (3)
(c ₃ + c ₄ ρ + c ₅ ρ ² ) × (u ² + uρ + ρ ² ) (4)
In the above formulas (1) and (2), 6 times F _{3 ^ m as} c ₀ d, c ₁ d, c ₂ d, c ₃ d, c ₄ d, c ₅ d, where d is a multiplier. Is multiplied. Here, the pre-calculation table in the present invention is created for a predetermined multiplier (details of the pre-calculation table will be described later). Therefore, in the calculations of the above formulas (1) and (2), once a pre-calculation table with d as a multiplier is created, the pre-calculation table is multiplied by F _{3 ^ m} with another d as a multiplier. Can also be used. Specifically, when calculating a pre-computation table having d as a multiplier when computing c ₀ d, the pre-computation table is c ₁ d, c ₂ d, c ₃ d, c ₄ d, c _5. It can also be used to calculate d.

In the above formulas (3) and (4), for example, c ₂ u, (c ₂ u + c ₁ ) u, c ₀ u, (c ₀ u) u, c ₅ u, ( c ₅ u + c ₄ ) u, c ₃ u, and (c ₃ u) u are multiplied 8 times by F _{3 ^ m} , and 2 times c ₁ u ² and c ₄ u ² with u ² as a multiplier. Can be considered to be multiplied by F _{3 ^ m} . Here, u ² is calculated in Step 3-2 prior to Step 3-3 in which the operations of the above expressions (3) and (4) are performed. In this u ² calculation, u is a multiplier. A calculation table has already been created. Therefore, the already created pre-calculation table with u as a multiplier can be used for the above-described eight multiplications of F _{3 ^ m} with u as a multiplier. Therefore, in this case, if the pre-calculation table having u ² as a multiplier is created once, the calculations of the above expressions (3) and (4) can be performed.

Thus, in Step 3-2, the multiplication of u ² and y _p y _q is performed twice, and in Step 3-3, 16 times (= 6 times of the above formulas (1) and (2) + (3), (4 It is necessary to perform a total of 18 multiplications of F _{3 ^ m} including the multiplication of 10) in the formula. However, given as described above, Step 3-2, in Step 3-3, as a pre-operation, u, either the _{y p} and _{y q,} d, a total of four pre-calculation table to multiplier a ^{u 2,} respectively You can see that it is enough if you create it.

Further, in the above formulas (3) and (4), the calculation using u ² as a multiplier is not performed, and c ₂ u, (c ₂ u) u, c ₁ u, (c ₁ u) with u as a multiplier. ) U, c ₀ u, (c ₀ u) u, c ₅ u, (c ₅ u) u, c ₄ u, (c ₄ u) u, c ₃ u, (c ₃ u) u, 12 times It can be considered that the following calculation is performed. In this case, it is not necessary to create a pre-calculation table with u ² as a multiplier. Therefore, in this case, Step 3-2, in Step 3-3, as a pre-operation, u, either the _{y p} and _{y q,} may be creating a total of three pre-calculation table to the d respectively multiplier. That is, it can be seen that the number of pre-calculation tables that need to be created can be further reduced.

  In this way, pairing calculation can be performed at high speed by reusing the pre-calculation table for a certain multiplier for other calculations of the finite field for that multiplier. Further, it is possible to further increase the speed of the pairing operation by increasing the speed of the polynomial multiplication portion by adding a cost to the portion for creating the pre-operation table.

[Pre-calculation table]
A pre-operation table and polynomial multiplication using the pre-operation table will be described. For convenience of explanation, polynomial multiplication for a finite field F _{3 ^ m} that is an m-th order extension field of a fundamental field F ₃ = {0, 1, 2} of characteristic 3 C (x) = A (x) · B (X)
Take as an example. A finite field that is an m-th order extension field of a base field of another characteristic can be similarly subjected to polynomial multiplication by configuring a pre-calculation table. The polynomial multiplication, the input A (x), from _{B (x) ∈F 3 ^ m} , refers to determining the output _{C (x) ∈F 3 ^ m} . Here, A (x), B (x), and C (x) are expressed as follows.

A (x) = a ₀ + a ₁ x + a ₂ x ² +... + A _m−1 x ^m−1
B (x) = b ₀ + b ₁ x + b ₂ x ² +... + B _m−1 x ^m−1
C (x) = c ₀ + b ₁ x + b ₂ x ² +... + B _2m−2 x ^2m−2
This polynomial multiplication can be processed at high speed by the so-called Windows method. Windows method performs pre-computed for A (x), is that the algorithm for adding check plurality of coefficients _{b i} at the same time scanning the B (x). Here, the number of coefficients (b _{i + w−1} , b _{i + w−2} ,..., B _i ) to be confirmed at a time is defined as the window size Ws. The pre-computation table is a result of pre-computation for this A (x).

Specifically, the pre-computation for A (x) is a Ws-1 order polynomial with the number of terms Ws W (x) = w ₀ + w ₁ x + w ₂ x ² +... + W _Ws−1 x ^Ws−1 (w _i ∈ {0, 1, 2})
Is obtained for all combinations of A (x) × W (x). In other words, the A (x) represented by the original a is polynomial in m-th extension field F _{3 ^ m} for the finite field F ₃ and base body, the number of terms Ws to its original coefficients of a finite field F ₃ Each polynomial W (x) is calculated. The calculation result of A (x) × W (x) for a set {w ₀ , w ₁ , w ₂ ,..., W _Ws−1 } of a certain coefficient w _i ε { ₀ , ₁ , ₂ } is expressed as A ′ [w _Assuming that ₀ , w ₁ , w ₂ ,..., W _Ws−1 ] ∈F _{3 ^ m} , for example, a pre-operation table as illustrated in FIG. Thus, the pre-calculation table is a table in which each set of Ws coefficients is associated with the calculation result. In other words, the pre-operation table associates each polynomial of the number of terms Ws with the operation result.

  Next, polynomial multiplication using a pre-calculation table will be described. B (x), which is an m-order polynomial, is divided into polynomials having a number of terms Ws. More specifically, after being divided into polynomials having the number of terms Ws, each of the divided polynomials having the number of terms Ws is bundled with a common power of x.

B (x) = (b ₀ + b ₁ x + b ₂ x ² +… + b _Ws-1 x ^Ws-1 )
+ (b _Ws + b + _{Ws + 1} x + b _{Ws + 2} x ² +… + b _2Ws-1 x ^Ws-1 ) x ^Ws
...
+ (b _m-Ws + b _{m-Ws + 1} x + b _{m-Ws + 2} x ² +… + b _m-1 x ^m-1 ) x ^m-Ws
In this case, A (x) · B (x) can be written as follows.

A (x) ・ B (x) = A (x) ・ (b ₀ + b ₁ x + b ₂ x ² +… + b _Ws-1 x ^Ws-1 )
+ A (x) ・ (b _Ws + b + _{Ws + 1} x + b _{Ws + 2} x ² +… + b _2Ws-1 x ^Ws-1 ) x ^Ws
...
+ A (x) ・ (b _m-Ws + b _{m-Ws + 1} x + b _{m-Ws + 2} x ² +… + b _m-1 x ^Ws-1 ) x ^m-Ws
In the precomputation table, the product of A (x) and an arbitrary polynomial W (x) of the number of terms Ws has been calculated. The product of Ws and each polynomial can be easily obtained. That is, the calculation result corresponding to the set of Ws coefficients of the divided polynomial of the number of terms Ws is referred to. Then, if the divided polynomial of the number of terms Ws is enclosed by a power of x, each of the number of terms Ws divided by A (x) is obtained by multiplying the operation result by the power of x. A product with a polynomial can be obtained.

A (x) ・ B (x) = A [b ₀ , b ₁ , b ₂ ,…, b _Ws-1 ]
+ A [b _Ws , b _{Ws + 1} , b _{Ws + 2} ,…, b _2Ws-1 ] x ^Ws
...
+ A [b _m-Ws , b _{m-Ws + 1} , b _{m-Ws + 2} ,…, b _m-1 ] x ^m-Ws
C (x) = A (x) · B (x) is calculated by adding the product of A (x) obtained in this way and each polynomial of the divided number of terms Ws.

[Device configuration]
The pairing calculation unit 3 illustrated in FIG. 1 calculates pairing η _T (P, Q) for predetermined inputs P and Q. When it is necessary to perform multiplication of a finite field during the pairing calculation, the control unit 2 of the pairing calculation unit 3 controls so that the multiplication calculation unit 1 of the pairing calculation unit 3 performs the calculation. .

  Hereinafter, as an example, a multiplier A which is an element of an extension field based on a certain finite field and is expressed by a polynomial is multiplied by a multiplicand B which is an element of the same extension field and is expressed by a polynomial. Explain. The multiplier A corresponds to A (x) described in the above item [Preliminary table], and the multiplicand B corresponds to B (x).

FIG. 2 shows a functional configuration of the multiplication operation unit 1. When a multiplier A that is an element of an extension field based on a finite field and is expressed by a polynomial is input, the pre-operation unit 10 of the multiplication operation unit 1 reads the window size Ws from the memory 15, and the multiplier A _A pre-calculation table t _A for is generated. Specifically, as described above, a multiplier A that is an element of an extension field based on a certain finite field and is expressed by a polynomial, and a term number Ws (Ws is a predetermined number) whose coefficient is the element of the finite field. _A pre-calculation table t _A is generated by multiplying each of a plurality of (natural number) polynomials.

The generated pre-calculation table t _A is stored in the pre-calculation table storage unit 11. In this example, the pre-calculation table storage unit 11, only the pre-calculation table t _A is stored, may store other pre calculation table.

  When the multiplicand B is input to the product operation unit 12, the dividing unit 121 of the product operation unit 12 reads the window size Ws from the memory 15, and divides the multiplicand B into polynomials having a term number Ws. The divided polynomial of the number of terms Ws is sent to the reference unit 122. When the number of terms of the multiplicand B is not a multiple of the window size Ws, the multiplicand B is divided into a polynomial of the number of terms Ws and a polynomial of the number of terms below Ws. That is, in general, the multiplicand B is divided into polynomials having a term number Ws or less.

The reference unit 122 refers to the precomputation table t _{A in} the precomputation table storage unit 11 to obtain the product of the multiplier A and each polynomial of the divided number of terms Ws. The product obtained for each polynomial is sent to the adder 123. For the polynomial of the number of terms below Ws that occurs when the number of terms of the multiplicand B is not a multiple of the window size Ws, the pre-computation table may be referred to assuming that the corresponding coefficient is 0.

Addition unit 123, by referring unit 122 adds the products obtained, the product of the multiplier factor A and the multiplicand B, in other words, product _M of the multiplier A and the multiplicand B about precomputed table _{t A (t} A, B) Is calculated and output.

  The pairing calculation unit 3 continues the pairing calculation using the output result.

When it is necessary to perform multiplication with A as a multiplier again, the multiplier A and the multiplicand are generated using the pre-calculation table t _A that has already been generated and stored in the pre-calculation table storage unit 11. The product of is calculated.

When it is necessary to perform multiplication using a number D other than A as a multiplier, the pre-calculation unit 10 generates a pre-calculation table t _D for the multiplier D and stores it in the pre-calculation table storage unit 11 in the same manner as described above. and, product unit 12 by referring to the pre-calculation table t _D, for multiplying finite.

  In order to perform this processing automatically, it is determined whether or not a pre-calculation table for a certain multiplier is stored in the pre-calculation table storage unit 11, and a pre-calculation table for the multiplier is stored in the pre-calculation table storage unit 11. If it is determined that it is not stored, the first control unit 13 may be provided that causes the pre-calculation unit 10 to generate a pre-calculation table for the multiplier.

  In addition, when it is determined whether multiplication for a certain multiplier is performed again and it is determined that multiplication for the multiplier is performed again, a pre-calculation table for the multiplier is stored in the pre-calculation table storage unit 11. A second control unit 14 is provided that controls the multiplier so that the pre-calculation table storage unit 11 does not store the pre-calculation table for the multiplier when it is determined that the multiplication for the multiplier is not performed again. May be.

[First η _T pairing algorithm]
The following is a first eta _T pairing computation algorithm when the present invention is applied to eta _T pairing. This first η _T pairing calculation algorithm is the following formulas (3) and (4): c ₂ u, (c ₂ u + c ₁ ) u, c ₀ u, (c ₀ u) with u as a multiplier u 8, c ₅ u, (c ₅ u + c ₄ ) u, c ₃ u, (c ₃ u) u, 8 times F _{3 ^ m} multiplication, and u ² is a multiplier c ₁ u ² , c _This is an algorithm in the case of performing 2 F _{3 ^ m} multiplications of ₄ u ² . That is, in Step3, as a pre-operation, u, either the _{y p} and _{y q,} d, to create a total of four pre-calculation table to multiplier a ^{u 2,} respectively, of which u, d, multiplier and ^{u 2} The pre-calculation table is an algorithm for reusing.

In the following algorithm, T (A) is a function that outputs a pre-calculation table t _A for the multiplier AεF _{3 ^ m} . M (t, B) is a function that outputs a product of a multiplier and B relating to the pre-operation table t. For example, M (T (A), B) = A · B. Calculations for the function T (A) and the function M (t, B) are performed in the multiplication calculation unit 1. Specifically, the calculation for the function T (A) is performed in the pre-calculation unit 10, and the calculation for the function M (t, B) is performed in the product calculation unit 12. Other processing is performed by the pairing calculation unit 3. The same applies to the second η _T pairing algorithm described later.

  The following Step 3-3-4 is a step corresponding to the calculation of the above formula (3), and the following Step 3-3-5 is a step corresponding to the calculation of the above formula (4), and the following Step 3-3-6 is performed. Is the reduction step.

[Preparation] E (F _{3 ^ m} ): Elliptic curve g ₁ (ρ) = ρ ³ −ρ−1 defined on the finite field F _{3 ^ m}
g ₂ (σ) = σ ² +1
The element of F _{3 ^ (6m)} is expressed as an element of F _{3 ^ (m)} [ρ, σ] / (g ₁ (ρ), g ₂ (σ)).
[Input] P = (x _p , y _p ), Q = (x _q , y _q ) ∈E (F _{3 ^ m} )
[Output] η _T (P, Q) ∈F ^* _{3 ^ (6m)}
〔Method of calculation〕
Step 1: y _p ← −y _p (∈F _{3 ^ m} )
Step 2: f ← −y _p (x _p + x _q +1) + y _q σ + y _p ρ (∈F _{3 ^ (6m)} )
Step 3: Repeat Step 3-1 to Step 3-5 from i = 0 to (m−1) / 2.

Step 3-1: u ← x _p + x _q +1 (∈F _{3 ^ m} )
Step 3-2:
Step 3-2-1: t _u ← T (u)
Step 3-2-2: u ₂ <-M (t _u , u)
Step3-2-3: d ← _y p _{y q
Step3-3: f = (c 0 +} c 1 ρ + c 2 ρ 2) + (c 3 + c 4 ρ + c 5 ρ 2) and sigma.

Step 3-3-1: t _d ← T (d)
Step 3-3-2:
d ₀ ← M (t _d , c ₀ )
d ₁ ← M (t _d , c ₁ )
d ₂ ← M (t _d , c ₂ )
d ₃ ← M (t _d , c ₃ )
d ₄ ← M (t _d , c ₄ )
d ₅ ← M (t _d , c ₅ )
Step 3-3-3: t _{u ^ 2} <-T (u ₂ )
Step 3-3-4:
e ₁ ← M (t _u , c ₀ )
e ₀ ← M (t _u , e ₁ )
e ₁ <-M ( _{tu 2} , c ₁ ) + e ₁
e ₃ <-M (t _u , c ₂ ) + c ₁
e ₂ <-M (t _u , e ₃ ) + c ₀
e ₄ ← c ₂
e ₀ ← e ₀ + e ₃
e ₁ ← e ₁ + e ₃ + e ₄
e ₂ ← e ₂ + e ₄
Step 3-3-5:
f ₁ ← M (t _u , c ₃ )
f ₀ ← M (t _u , f ₁ )
f ₁ <-M ( _{tu 2} , c ₄ ) + f ₁
f ₃ ← M (t _u , c ₅ ) + c ₄
f ₂ ← M (t _u , f ₃ ) + c ₃
f ₄ ← c ₅
f ₀ ← f ₀ + f ₃
f ₁ ← f ₁ + f ₃ + f ₄
f ₂ ← f ₂ + f ₄
Step 3-3-6:
c ₀ ← −d ₀ −e ₀
c ₁ ← −d ₁ −e ₁
c ₂ ← −d ₂ −e ₂
c ₃ ← d ₃ -f ₀
c ₄ ← d ₄ -f ₁
c ₅ ← d ₅ -f ₂
Step 3-3-7: f ← (c ₀ + c ₁ ρ + c ₂ ρ ² ) + (c ₃ + c ₄ ρ + c ₅ ρ ² ) σ
Step 3-4: x _p <-x _p ^(1/3) , y _p <-y _p ^(1/3)
Step 3-5: x _q ← x _q ³ , y _q ← y _q ³
Step 4: f ^{((3 ^ 3m) -1) ((3 ^ m) +1) ((3 ^ m)-(3 ^ ((m + 1) / 2)) + 1)} is output.

[Second η _T pairing algorithm]
Below, the 2nd (eta) _T pairing calculation algorithm at the time of applying this invention to (eta) _T pairing is shown. In this second η _T pairing algorithm, c ₂ u, (c ₂ u) is calculated by not using u ² as a multiplier, but using u as a multiplier in the above equations (3) and (4). u, c ₁ u, (c ₁ u) u, c ₀ u, (c ₀ u) u, c ₅ u, (c ₅ u) u, c ₄ u, (c ₄ u) u, c ₃ u, This is an algorithm in the case of performing 12 operations (c ₃ u) u. That, Step 3-2, in Step 3-3, as a pre-operation, u, whereas either of _{y p} and _{y q,} creating a total of three pre-calculation table to the d each multiplier, of which u, multipliers and d The pre-calculation table is an algorithm for reusing.

  The following Step 3-3-3 is a step corresponding to the calculation of the above formula (3), and the following Step 3-3-4 is a step corresponding to the calculation of the above formula (4), and the following Step 3-3-5 is performed. Is the reduction step.

[Preparation] E (F _{3 ^ m} ): Elliptic curve g ₁ (ρ) = ρ ³ −ρ−1 defined on the finite field F _{3 ^ m}
g ₂ (σ) = σ ² +1
The element of F _{3 ^ (6m)} is expressed as an element of F _{3 ^ (m)} [ρ, σ] / (g ₁ (ρ), g ₂ (σ)).
[Input] P = (x _p , y _p ), Q = (x _q , y _q ) ∈E (F _{3 ^ m} )
[Output] η _T (P, Q) ∈F ^* _{3 ^ (6m)}
〔Method of calculation〕
Step 1: y _p ← −y _p (∈F _{3 ^ m} )
Step 2: f ← −y _p (x _p + x _q +1) + y _q σ + y _p ρ (∈F _{3 ^ (6m)} )
Step 3: Repeat Step 3-1 to Step 3-5 from i = 0 to (m−1) / 2.

Step 3-1: u ← x _p + x _q +1 (∈F _{3 ^ m} )
Step 3-2:
Step 3-2-1: t _u ← T (u)
Step3-2-2: d ← _y p _{y q
Step3-3: f = (c 0 +} c 1 ρ + c 2 ρ 2) + (c 3 + c 4 ρ + c 5 ρ 2) and sigma.

Step 3-3-1: t _d ← T (d)
Step 3-3-2:
d ₀ ← M (t _d , c ₀ )
d ₁ ← M (t _d , c ₁ )
d ₂ ← M (t _d , c ₂ )
d ₃ ← M (t _d , c ₃ )
d ₄ ← M (t _d , c ₄ )
d ₅ ← M (t _d , c ₅ )
Step 3-3-3:
e ₄ ← c ₂
e ₃ ← M (t _u , e ₄ )
e ₂ ← M (t _u , e ₃ )
e ₃ ← e ₃ + c ₁
e ₁ ← M (t _u , c ₁ )
e ₂ ← e ₂ + e ₁
e ₁ ← M (t _u , e ₁ )
e ₂ ← e ₂ + c ₀
e ₀ ← M (t _u , c ₀ )
e ₁ ← e ₁ + e ₀
e ₀ ← M (t _u , e ₀ )
e ₀ ← e ₀ + e ₃
e ₁ ← e ₁ + e ₃ + e ₄
e ₂ ← e ₂ + e ₄
Step 3-3-4:
f ₄ ← c ₅
f ₃ ← M (t _u , f ₄ )
f ₂ ← M (t _u , f ₃ )
f ₃ ← f ₃ + c ₄
f ₁ ← M (t _u , c ₄ )
f ₂ ← f ₂ + f ₁
f ₁ ← M (t _u , f ₁ )
f ₂ ← f ₂ + c ₃
f ₀ ← M (t _u , c ₃ )
f ₁ ← f ₁ + f ₀
f ₀ ← M (t _u , f ₀ )
f ₀ ← f ₀ + f ₃
f ₁ ← f ₁ + f ₃ + f ₄
f ₂ ← f ₂ + f ₄
Step 3-3-5:
c ₀ ← −d ₀ −e ₀
c ₁ ← −d ₁ −e ₁
c ₂ ← −d ₂ −e ₂
c ₃ ← d ₃ -f ₀
c ₄ ← d ₄ -f ₁
c ₅ ← d ₅ -f ₂
Step 3-3-6: f ← (c ₀ + c ₁ ρ + c ₂ ρ ² ) + (c ₃ + c ₄ ρ + c ₅ ρ ² ) σ
Step 3-4: x _p <-x _p ^(1/3) , y _p <-y _p ^(1/3)
Step 3-5: x _q ← x _q ³ , y _q ← y _q ³
Step 4: f ^{((3 ^ 3m) -1) ((3 ^ m) +1) ((3 ^ m)-(3 ^ ((m + 1) / 2)) + 1)} is output.

[Modifications, etc.]
Although η _T pairing has been described as an example, the present invention can also be applied to pairing operations other than η _T pairing.

  The pre-computation unit 10 may be provided with a reduction unit 101, and the computation result computed by the pre-computation unit 10 may be reduced using a predetermined irreducible polynomial. As a result, a pre-calculation table in which each set of polynomials having the number of terms Ws and each calculation result reduced by the reduction unit 101 is associated is stored in the pre-calculation table storage unit 11. The data amount of the pre-calculation table can be reduced by the reduction.

  Further, a reduction unit 1231 may be provided in the addition unit 123, and the addition result added by the addition unit 123 may be reduced using a predetermined irreducible polynomial.

  Further, in order to determine an appropriate window size Ws, a first measurement unit 17 and a window size determination unit 16 may be provided. The first measuring unit 17 measures the time taken for the pairing calculation for each of the plurality of Ws when the predetermined pairing calculation is performed based on the plurality of Ws. The time taken for the pairing calculation, measured for each window size Ws, is sent to the window size determination unit 16. The window size determination unit 16 selects Ws that minimizes the time taken for the measured pairing calculation. Then, the minimum Ws is set in the memory 15. This makes it possible to cause the pre-calculation means to perform the multiplication based on Ws that minimizes the time taken for the pairing calculation.

In general, there are a plurality of methods for performing the same pairing calculation, such as the first η _T pairing calculation algorithm and the second η _T pairing calculation algorithm described above. In order to determine an appropriate pairing calculation algorithm, as illustrated in FIG. 1, an algorithm storage unit 4, a second measurement unit 5, and an algorithm determination unit 6 may be provided. The algorithm storage unit 4 stores a plurality of pairing calculation algorithms for calculating the same pairing. The second measuring unit 5 takes the pairing calculation when the pairing calculation unit 3 performs the pairing calculation based on the plurality of pairing calculation algorithms read from the algorithm storage unit 4. Time is measured for each pairing algorithm. The time measured for each pairing calculation algorithm is sent to the algorithm determination unit 6. The algorithm determination unit 6 selects a pairing operation algorithm that minimizes the time taken to perform the measured pairing operation. Based on the minimum pairing calculation algorithm, the pairing calculation unit 3 is controlled to perform the pairing calculation. As a result, the time required for the pairing calculation can be minimized, and the pairing calculation can be performed at high speed.

  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. 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. The computer-readable recording medium may be any medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory. Specifically, for example, the magnetic recording device may be a hard disk device or a flexible Discs, magnetic tapes, etc. as optical disks, DVD (Digital Versatile Disc), DVD-RAM (Random Access Memory), CD-ROM (Compact Disc Read Only Memory), CD-R (Recordable) / RW (ReWritable), etc. As the magneto-optical recording medium, MO (Magneto-Optical disc) or the like can be used, and as the semiconductor memory, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory) or the like can 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.

  As an execution form different from the above-described embodiment, the computer may read the program directly from the portable recording medium and execute processing according to the program. Each time is transferred, 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.

  In addition, the various processes described above are not only executed in time series according to the description, but may be executed in parallel or individually according to the processing capability of the apparatus that executes the processes or as necessary. Needless to say, other modifications are possible without departing from the spirit of the present invention.

The figure which illustrates the function structure of the pairing calculating part 3. The figure which illustrates the function structure of the multiplication calculating part 1. The figure which illustrates a prior calculation table.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Multiplication calculating part 2 Control part 3 Pairing calculating part 4 Algorithm memory | storage part 5 Second measuring part 6 Algorithm determination part 10 Pre-arithmetic part 11 Pre-arithmetic table memory | storage part 12 Product calculating part 13 First control part 14 Second control part 15 Memory 16 Window size determination unit 17 First measurement unit 101 Reduction unit 121 Division unit 122 Reference unit 123 Addition unit 1231 Reduction unit

Claims (5)

In the pairing calculation device for calculating pairing,
A first number that is an element of an extension field based on a certain finite field and is represented by a polynomial, and a plurality of polynomials having a number of terms Ws (Ws is a predetermined natural number) having coefficients of the elements of the finite field, respectively. Pre-calculation means for multiplication;
Pre-calculation table storage means for storing each set of polynomials of the number of terms Ws and the calculation result in association with each other as a pre-calculation table for the first number;
A dividing unit that divides the second number that is an element of the extension field and is expressed by a polynomial into a polynomial having a term number w or less;
Reference means for obtaining a product of the first number and each of the divided polynomials with reference to the pre-calculation table read from the pre-calculation table storage unit;
Adding means for obtaining a product of the first number and the second number by adding the products obtained by the reference means;
With
During the pairing operation, when multiplying the first number by a plurality of multiplicands that are elements of the extension field and represented by a polynomial, respectively, each of the multiplicands is set as a second number, and the dividing means, reference means, by performing the processing by the adding means, with reference to the same pre-computation table already generated read from the pre-calculation table storage means, respectively determined Me a product of the first number and the multiplicand ,
Further example Bei the first reduction means for reduction of the product of the upper Symbol adding means obtained,
Further comprising a second reduction means for reduction on articles before product of calculating means is calculated,
The pre-computation table stores, as a pre-computation table for the first number, a correspondence between each pair of polynomials having the number of terms Ws and the computation result reduced by the second reduction means. a means for,
Precomputed table for the first few upper SL is determined whether stored in the pre-calculation table storage device, pre-calculation table for the first number is not stored in the pre-calculation table storage means If it is determined that there is no first control means for causing the pre-calculation means to generate a pre-calculation table for the first number;
The pairing arithmetic device further comprising: In the pairing calculation device for calculating pairing,
A first number that is an element of an extension field based on a certain finite field and is represented by a polynomial, and a plurality of polynomials having a number of terms Ws (Ws is a predetermined natural number) having coefficients of the elements of the finite field, respectively. Pre-calculation means for multiplication;
Pre-calculation table storage means for storing each set of polynomials of the number of terms Ws and the calculation result in association with each other as a pre-calculation table for the first number;
A dividing unit that divides the second number that is an element of the extension field and is expressed by a polynomial into a polynomial having a term number w or less;
Reference means for obtaining a product of the first number and each of the divided polynomials with reference to the pre-calculation table read from the pre-calculation table storage unit;
Adding means for obtaining a product of the first number and the second number by adding the products obtained by the reference means;
With
During the pairing operation, when multiplying the first number by a plurality of multiplicands that are elements of the extension field and represented by a polynomial, respectively, each of the multiplicands is set as a second number, and the dividing means, reference means, by performing the processing by the adding means, with reference to the same pre-computation table already generated read from the pre-calculation table storage means, respectively determined Me a product of the first number and the multiplicand ,
Further example Bei the first reduction means for reduction of the product of the upper Symbol adding means obtained,
Further comprising a second reduction means for reduction on articles before product of calculating means is calculated,
The pre-computation table stores, as a pre-computation table for the first number, a correspondence between each pair of polynomials having the number of terms Ws and the computation result reduced by the second reduction means. a means for,
In pairing computation above reporting, to determine whether the multiplication to multiplier the number of the first is performed again, when the multiplication to multiplier the number of the first is determined to be again performed The pre-calculation table storage means stores the pre-calculation table for the first number, and if it is determined that the multiplication using the first number as a multiplier is not performed again, the pre-calculation table Second control means for controlling the storage means not to store the pre-calculation table for the first number;
The pairing arithmetic device further comprising: In the pairing arithmetic device according to claim 1 or 2 ,
A first measuring means for measuring, for each of the plurality of Ws, the time taken to perform the pairing calculation when a predetermined pairing calculation is performed based on the plurality of Ws;
A window size determining means for selecting Ws that minimizes the time taken for the measured pairing calculation, and causing the pre-calculation means to perform the multiplication based on the Ws to be minimized;
A pairing operation device comprising: In the pairing arithmetic device according to claim 1 or 2 ,
Algorithm storage means for storing a plurality of pairing operation algorithms;
Secondly, when each pairing calculation is performed based on a plurality of pairing calculation algorithms read from the algorithm storage means, the time taken for the pairing calculation is measured for each of the plurality of pairing calculation algorithms Measuring means;
Select a pairing operation algorithm that minimizes the time taken for the measured pairing operation, and cause the pairing operation device to perform the pairing operation based on the minimum pairing operation algorithm An algorithm determination means;
A pairing operation device comprising: A pairing calculation program for causing a computer to function as each means of the pairing calculation device according to any one of claims 1 to 4 .

Images