JP4585372B2 - Pairing calculation device, pairing calculation method, and pairing calculation program - Google Patents

Description

  The present invention relates to an apparatus, a method, and a program using an operation on an elliptic curve, in particular, an operation for realizing a security technique.

A method of realizing ID-base encryption using elliptic curve pairing or a short signature digital signature has been proposed (Patent Document 1).
An outline of encryption and signature by Tate pairing is shown in FIG. Let the ellipse defined on the finite field GF (p) be E / GF (p). Let GF (p) rational point on the ellipse E / GF (p) be P (x, y), and GF (p ^k ) rational point on the ellipse E / GF (p) be Q (x _Q , y _Q ). . In Tate pairing, P and Q are input, an element f on a finite field GF (p ^k ) is output by the Miller algorithm, and f is raised to the power of (p ^k −1) / m by a power operation. Map to element e on GF (p ^k ) and output. Here, p is a prime number or a power of a prime number, m is a prime number and the order of P, Q, and e, k is the smallest integer that satisfies m | (p ^k −1), and m is a factor of (p−1). It is not a number, and the greatest common divisor of p and m is 1.

FIG. 2 shows a functional configuration example of a pairing arithmetic device 1000 using Tate pairing. In order to perform the processing shown in FIG. 1, a Miller arithmetic unit 30 that converts and outputs inputs P and Q to elements f on a finite field GF (p ^k ) using the Miller algorithm and a finite input f by a power operation. The power calculation unit 20 is to be mapped to the element e on the field GF (p ^k ) and output.
FIG. 3 shows an example of the internal configuration of the Miller arithmetic unit 30 occupying a calculation amount of 90% in Tate pairing, and FIG. 4 shows an example of the processing flow. The Miller arithmetic device 30 includes a control unit 100, an assignment unit 200, an elliptical point generation unit 400, an ellipse addition unit 500, an input / output unit 600, a GF (p ^k ) multiplication unit 700, a GF (p ^k ) inverse element unit 850, And a recording unit 190. The control unit 100 controls other components in order to execute processing according to the processing flow shown below. The recording unit 190 may be a non-volatile memory such as a hard disk or a volatile memory that temporarily records only during a series of calculations. Moreover, you may combine.

When m, P, and Q are input to the input / output unit 600, m, P, and Q are recorded in the recording unit 190 (S700). Next, the assigning unit 200 substitutes P for T and 1 for F, and records the result in the recording unit 190 (S710). The point on the ellipse 400 generates a point S (∈E / GF (p ^k )) on the ellipse defined on the finite field GF (p ^k ) that satisfies the conditions S ≠ P and S ≠ Q. The data is recorded in the recording unit 190 (S720). S may be determined in advance or may be randomly generated as long as it satisfies the conditions. The ellipse addition unit 500 reads Q and S from the recording unit 190, calculates Q ′ (= Q + S), and records it in the recording unit 190 (S730). In the assigning unit 200, an integer obtained by rounding up the decimal point of log (m) -1 is substituted into n and recorded in the recording unit 190 (S740). The control unit 100 reads n from the recording unit 190 and confirms whether or not n <0. If Yes, the process proceeds to step S910, and if No, the process proceeds to step S760 (S750). In the case of Yes, the input / output unit 600 reads and outputs F from the recording unit 190 (S910), and the calculation by the Miller algorithm ends. In the case of No, the ellipse addition unit 500 reads T from the recording unit 190, calculates 2T, and records it in the recording unit 190 (S760). The GF (p ^k ) multiplication unit 700 reads Q ′, S, T, and 2T from the recording unit 190, and l ₁ (x, y) = 0 is a straight line connecting T and 2T, l ₂ (x, y) Assuming = 0 as a straight line connecting 2T and O, l ₁ (Q ′), l ₂ (Q ′), l ₁ (S), and l ₂ (S) are calculated and recorded in the recording unit 190 (S770). . However, l ₁ (Q ′) is a value obtained by substituting the x and y coordinates of Q ′ into l ₁ (x, y). If S is selected from elements of a finite field GF (p) (in this case, the elements of the remaining k−1 finite fields GF (p) are 0), l ₁ (S), l ₂ ( The calculation of S) can be omitted, and l ₁ (S) and l ₂ (S) can be omitted in the subsequent steps. Next, the assigning unit 200 reads 2T from the recording unit 190, assigns a value of 2T to T, and records T in the recording unit 190 (S780). The GF (p ^k ) inverse element 850 reads l ₂ (Q ′) and l ₁ (S) from the recording unit 190 and calculates l ₂ (Q ′) ⁻¹ and l ₁ (S) ⁻¹ . Recording is performed in the recording unit 190 (S790). The GF (p ^k ) multiplication unit 700 reads F, l ₁ (Q ′), l ₂ (S), l ₂ (Q ′) ⁻¹ , l ₁ (S) ⁻¹ from the recording unit 190,

を計算し、Ｆの値として記録部１９０に記録する（Ｓ８１０）。制御部１００は、記録部１９０からｍとｎを読み取り、ｍのｎ番目のビットが１かを確認し、Ｙｅｓの場合にはステップＳ８３０へ進み、Ｎｏの場合にはステップＳ９００へ進む（Ｓ８２０）。Ｙｅｓの場合、楕円加算部５００で、記録部１９０からＴ、Ｐを読み取り、Ｔ＋Ｐを計算し、記録部１９０に記録する（Ｓ８３０）。ＧＦ（ｐ^ｋ）乗算部７００は、Ｑ’、Ｓ、Ｔ、Ｐ，Ｔ＋Ｐを記録部１９０から読み取り、ｌ_１（ｘ，ｙ）＝０をＴとＰとを結ぶ直線、ｌ_２（ｘ，ｙ）＝０をＴ＋ＰとＯとを結ぶ直線とし、ｌ_１（Ｑ’）、ｌ_２（Ｑ’）、ｌ_１（Ｓ）、ｌ_２（Ｓ）を計算して、記録部１９０に記録する（Ｓ８４０）。代入部２００は、記録部１９０からＴ＋Ｐを読み取り、ＴにＴ＋Ｐを代入し、Ｔを記録部１９０に記録する（Ｓ８５０）。ＧＦ（ｐ^ｋ）逆元部８５０は、記録部１９０からｌ_２（Ｑ’）、ｌ_１（Ｓ）を読み取り、ｌ_２（Ｑ’）^−１、ｌ_１（Ｓ）^−１を計算し、記録部１９０に記録する（Ｓ８６０）。ＧＦ（ｐ^ｋ）乗算部７００は、記録部１９０からＦ、ｌ_１（Ｑ’）、ｌ_２（Ｓ）、ｌ_２（Ｑ’）^−１、ｌ_１（Ｓ）^−１を読み取り、

Is recorded in the recording unit 190 as a value of F (S810). The control unit 100 reads m and n from the recording unit 190 and checks whether the nth bit of m is 1. If Yes, the process proceeds to step S830, and if No, the process proceeds to step S900 (S820). . In the case of Yes, the ellipse addition unit 500 reads T and P from the recording unit 190, calculates T + P, and records it in the recording unit 190 (S830). The GF (p ^k ) multiplication unit 700 reads Q ′, S, T, P, T + P from the recording unit 190, and l ₁ (x, y) = 0 is a straight line connecting T and P, l ₂ (x, y) = 0 is a straight line connecting T + P and O, and l ₁ (Q ′), l ₂ (Q ′), l ₁ (S), and l ₂ (S) are calculated and recorded in the recording unit 190. (S840). The assigning unit 200 reads T + P from the recording unit 190, substitutes T + P for T, and records T in the recording unit 190 (S850). The GF (p ^k ) inverse element unit 850 reads l ₂ (Q ′) and l ₁ (S) from the recording unit 190 and calculates l ₂ (Q ′) ⁻¹ and l ₁ (S) ⁻¹ . Recording is performed in the recording unit 190 (S860). The GF (p ^k ) multiplication unit 700 reads F, l ₁ (Q ′), l ₂ (S), l ₂ (Q ′) ⁻¹ , l ₁ (S) ⁻¹ from the recording unit 190,

を計算し、Ｆの値として記録部１９０に記録する（Ｓ８９０）。ステップＳ８２０でＮｏと判断した場合とステップＳ８９０が終了した場合、代入部２００は、記録部１９０からｎを読み取り、ｎ−１をｎに代入し、ｎを記録部１９０に記録する（Ｓ９００）。次にステップＳ７５０に戻り、ステップＳ７５０の判断がＹｅｓとなるまで処理が繰り返される。
特開2004-177673号公報

Is recorded in the recording unit 190 as the value of F (S890). When it is determined No in step S820 and when step S890 is completed, the assignment unit 200 reads n from the recording unit 190, substitutes n−1 for n, and records n in the recording unit 190 (S900). Next, the process returns to step S750, and the process is repeated until the determination in step S750 becomes Yes.
JP 2004-177673 A

Since the amount of calculation required for the pairing calculation is very large compared to the normal elliptic calculation, the problem is that the calculation speed is slow. When realizing Tate pairing, most of the processing time is Miller's algorithm as described above, and Patent Document 1 also discusses speeding up Miller's algorithm. Many of these speeding-up methods are speeding up focusing on the properties of elliptic curves, such as a high-speed calculation method in the case of a special curve called a super singular curve.
The problem to be solved by the present invention is also to increase the calculation speed of pairing.

In the present invention, speeding up is performed using the properties of a finite field. FIG. 5 shows the principle of high-speed operation according to the present invention. Tate The pairing, while mapping the original f on the finite field GF ^{(p k)} based on e on the finite field GF by exponentiation ^{(p k),} the finite field GF ^{(p k)} above satisfies the following condition: Is also mapped to the element e on the finite field GF (p ^k ) by a power operation.
f ′ = rf where r is an element on the finite field GF ( ^{pk / 2} ) (1)
Therefore, in the present invention, when k is an even number, the property of this finite field is used, and an element f ′ is obtained by an algorithm having a smaller calculation amount than the Miller algorithm (hereinafter referred to as “pseudo Miller algorithm”). The element e is obtained by calculating the power of f ′.

In the pseudo Miller algorithm, the process of obtaining an inverse element using the Miller algorithm is replaced with a process of obtaining an element that is r times the inverse element obtained with a small amount of calculation (hereinafter referred to as “pseudo inverse element”). Specifically, when k is an even number and L is an element on a finite field GF (p ^k ),

を擬似逆元として使用する。
ここで、正規基底表現の場合には、Ｌのｐ^ｋ／２乗は、Ｌを２つの有限体ＧＦ（ｐ^ｋ／２）上の元Ｌ_０とＬ_１に分割し、Ｌ_０とＬ_１とを入れ替えることで実現できる。また、多項式基底表現の場合には、Ｌ（∈ＧＦ（ｐ^ｋ））のｐ^ｋ／２乗は、Ｌを２つの有限体ＧＦ（ｐ^ｋ／２）上の元Ｌ_０とＬ_１に分割し、Ｌ_０−ｕ_１Ｌ_１と−Ｌ_１とを合成することで実現できる。ここで、ｕ_１（∈ＧＦ（ｐ^ｋ／２））は最小多項式の係数として定まる定数であり、通常０や±１などの小さい数を用いることが多い。

Is used as a pseudo inverse element.
Here, in the case of a regular basis expression, L p ^{k / 2} means that L is divided into elements L ₀ and L ₁ on ^two finite fields GF (p ^{k / 2} ), and L ₀ and L ₁ This can be achieved by replacing Also, in the case of polynomial basis representation, p ( ^{k / 2} ) of L (εGF (p ^k )) divides L into elements L ₀ and L ₁ on ^two finite fields GF (p ^{k / 2} ). and _{it can} be realized by combining the _L 0 _{-u 1} L 1 and -L _1. Here, u ₁ (∈GF (p ^{k / 2} )) is a constant determined as a coefficient of the minimum polynomial, and usually a small number such as 0 or ± 1 is often used.

l ₂ (x, y) (∈GF (p ^k )) is expressed by arranging elements on k finite fields GF (p) side by side, and is multiplied by l ₂ (x, y) by Miller algorithm. Instead, by multiplying elements on a finite field GF (p ^k ) that is r times l ₂ (x, y) including elements that are 0 among the elements on ^k finite fields GF (p), Since it is clear that the original multiplication on the finite field GF (p) with a value of 0 is 0, it can be omitted. Therefore, by the method shown in FIG. 6, an element that is r times l ₂ (x, y) including elements on a finite field GF (p) having a value of 0 is obtained. l ₂ (x, y) is
L = aX + b (4)
Can be expressed as For example, if X is an element on a finite field GF (p ⁶ ), the element X is divided into elements X ₁ and X ₀ on two finite fields GF (p ³ ) as shown in FIG. Both sides are multiplied by an element c (= X ₁ ⁻¹ ) on the finite field GF (p ³ ). When L ′ = cL, L ′ is an element including two elements on a finite field GF (p) having a value of 0 as shown in FIG. 6 and satisfies the expression (1). Therefore, if cl ₂ (x, y) is multiplied instead of l ₂ (x, y) (hereinafter referred to as “pseudo multiplication”), the mapping by the power operation is the same point, but the amount of calculation Can be reduced.

Next, a case where a pseudo inverse element of L ′ is obtained will be described. When obtaining a pseudo inverse element, L ′ is divided into elements L ₀ ′ and L ₁ ′ on ^two finite fields GF (p ^{k / 2} ) as described above. also, _'if the value in the include finite GF (p) on the original 0, L _1' L 1 is finite GF (p) on the original value to the pseudo-inverse is 0 neat Will be included. Therefore, even when L is divided, the amount of calculation can be reduced by obtaining L ′, obtaining the pseudo inverse element of L ′, and multiplying.

According to the present invention, in a Tate pairing operation on an elliptic curve, when k is an even number, a high-speed mapping from E / GF (p ^k ) to GF (p ^k ) is performed using the property of a finite field. Can be made. Further, the present invention can increase the speed without using special elliptic curve properties. Furthermore, it can be applied to an elliptic curve of an arbitrary characteristic and has a wide application range.

Below, in order to avoid duplication of description, the same number is given to the structural part which has the same function, and the process step which performs the same process, and description is abbreviate | omitted.
[First Embodiment]
FIG. 7 shows a functional configuration example of the pairing arithmetic device of the present invention. The difference from FIG. 2 is that a pseudo Miller arithmetic device 10 is provided instead of the Miller arithmetic device 30. The pseudo Miller arithmetic device 10 is a device that realizes a pseudo Miller algorithm by performing pseudo multiplication with the above pseudo inverse element. An internal configuration example of the pseudo Miller arithmetic device 10 is shown in FIG. 8, and a processing flow of the pseudo Miller arithmetic device 10 is shown in FIG. 8 is different from FIG. 3 in that the type of data recorded in the recording unit 150 in FIG. 8 is different from the type of data recorded in the recording unit 190 in FIG. The GF (p ^k ) inverse element 850 is replaced with a pseudo GF (p ^k ) inverse element 800, and a c generator 300 and a pseudo GF (p ^k ) multiplier 900 are added for pseudo multiplication. That is. First, “recording to the recording unit 190” or “reading from the recording unit 190” in the description of FIG. 4 is replaced with “recording to the recording unit 150” or “reading from the recording unit 150” in FIG. . The other differences between the processing flow of FIG. 9 and the processing flow of FIG. 4 are as follows.

Steps S110 and S120 are added between step S730 and step S740. In step S110, c generator 300, _{'X Q} is x-coordinate of the' Q a ^{(∈GF (p} k)) is divided into two _{X 1} and _{X 0,} calculates the ^{X 1 -1,} the values of c Is recorded in the recording unit 150. In step S120, assuming that the coordinates of Q ′ are (X _Q ′, Y _Q ′), the GF (p ^k ) multiplier 700 calculates (cX _Q ′, cY _Q ′), and records it as Q ″. To record.
Step S770 is replaced with step S130. In step S130, the GF (p ^k ) multiplication unit 700 reads Q ″, S, T, and 2T from the recording unit 150, and l ₁ (x, y) = 0 is a straight line connecting T and 2T, l ₂ ( l ₁ (Q ″), l ₂ (Q ″), l ₁ (S), l ₂ (S) are calculated as x, y) = 0 as a straight line connecting 2T and O, and recorded in the recording unit 150 To do.

Steps S790 and S810 are replaced with steps S140 to S160. In step S140, the pseudo GF ^{(p k)} inverse element unit 800, the recording unit _{150 l 2 (Q "),} l read 1 _{(S), l 2 (Q} " pseudo inverse and _l 1 of) (S ) Is calculated and recorded in the recording unit 150. In step S150, the pseudo GF (p ^k ) multiplication unit 900 reads pseudo inverse elements of l ₁ (Q ″) and l ₂ (Q ″) from the recording unit 150,

を計算し、Ｆの値として記録部１５０に記録する。
ステップＳ８４０は、ステップＳ１７０に置き換えられる。ステップＳ１７０では、
ＧＦ（ｐ^ｋ）乗算部７００が、Ｑ”、Ｓ、Ｔ、Ｐ，Ｔ＋Ｐを記録部１５０から読み取り、ｌ_１（ｘ，ｙ）＝０をＴとＰとを結ぶ直線、ｌ_２（ｘ，ｙ）＝０をＴ＋ＰとＯとを結ぶ直線とし、ｌ_１（Ｑ”）、ｌ_２（Ｑ”）、ｌ_１（Ｓ）、ｌ_２（Ｓ）を計算して、記録部１５０に記録する。

Is recorded in the recording unit 150 as the value of F.
Step S840 is replaced with step S170. In step S170,
The GF (p ^k ) multiplication unit 700 reads Q ″, S, T, P, T + P from the recording unit 150, and l ₁ (x, y) = 0 is a straight line connecting T and P, l ₂ (x, y) = 0 is a straight line connecting T + P and O, and l ₁ (Q ″), l ₂ (Q ″), l ₁ (S), l ₂ (S) are calculated and recorded in the recording unit 150. .

Steps S860 and S880 are replaced with steps S180 to S200. In step S180, the pseudo GF ^{(p k)} inverse element unit 800, the recording unit _{150 l 2 (Q "),} l read 1 _{(S), l 2 (Q} " pseudo inverse and _l 1 of) (S ) Is calculated and recorded in the recording unit 150. In step S190, the pseudo GF (p ^k ) multiplication unit 900 reads pseudo inverse elements of l ₁ (Q ″) and l ₂ (Q ″) from the recording unit 150,

を計算し、Ｆの値として記録部１５０に記録する。
なお、本発明でもＳを有限体ＧＦ（ｐ）の元から選定すると（この場合、残りのｋ−１個の有限体ＧＦ（ｐ）の元は０である。）、ｌ_１（Ｓ）、ｌ_２（Ｓ）の計算や演算を省略できる。
このように変更した処理フローによって、Millerアルゴリズムよりも計算量を少なくし、有限体ＧＦ（ｐ^ｋ）上の元ｆ’を求めることができる。
［第２実施形態］
本実施形態では、第１実施形態の図８中に示した擬似ＧＦ（ｐ^ｋ）逆元部８００の内部構成について示す。入力Ｓ（∈ＧＦ（ｐ^ｋ））の擬似逆元の計算では、ｋを偶数としたことを利用して、逆元Ｓ^−１を求めるのではなく、逆元Ｓ^−１のｒ（∈ＧＦ（ｐ^ｋ／２））倍であるＳのｐ^ｋ／２乗を求めている。正規基底の場合には、入力Ｓのｐ^ｋ／２乗は、Ｓを２つの有限体ＧＦ（ｐ^ｋ／２）上の元Ｓ_０とＳ_１に分割し、Ｓ_０とＳ_１とを入れ替えることで実現できる。

Is recorded in the recording unit 150 as the value of F.
In the present invention, when S is selected from elements of a finite field GF (p) (in this case, the elements of the remaining k−1 finite fields GF (p) are 0), l ₁ (S), Calculation and calculation of l ₂ (S) can be omitted.
With the processing flow thus changed, the calculation amount can be reduced as compared with the Miller algorithm, and the element f ′ on the finite field GF (p ^k ) can be obtained.
[Second Embodiment]
In the present embodiment, an internal configuration of the pseudo GF (p ^k ) inverse element unit 800 shown in FIG. 8 of the first embodiment is shown. In the calculation of the pseudo inverse element of the input S (∈GF (p ^k )), the inverse element S ⁻¹ is not obtained using the fact that k is an even number, but r (∈GF) of the inverse element S ^−1. ( ^{Pk / 2} )) times S to the ^{pk / 2} power. In the case of a normal basis, p ^{k / 2} of the input S divides S into elements S ₀ and S ₁ on ^two finite fields GF (p ^{k / 2} ) and swaps S ₀ and S _1. This can be achieved.

FIG. 10 shows a functional configuration example of the pseudo GF (p ^k ) inverse element 800 in the case of a normal basis, and FIG. 11 shows a processing flow. The pseudo GF (p ^k ) inverse element unit 800 includes a dividing unit 810 and a replacement combining unit 820. When the element S on the finite field GF (p ^k ) is input, the dividing unit 810 divides S into two elements S ₀ and S ₁ of the finite field GF (p ^{k / 2} ) (S810). The replacement combining unit 820 generates a pseudo inverse element of S by exchanging the divided elements S ₀ and S ₁ and combining them (S 820), and outputs a pseudo inverse element of S (S 830).
Since the pseudo inverse element can be obtained simply by replacing the elements in this way, a significant reduction in the amount of calculation can be expected as compared with division.
[Modification]
In the second embodiment, the pseudo GF (p ^k ) inverse element portion 800 in the case of a normal basis has been shown. However, in this modification, the case of a polynomial basis is shown. In the case of a polynomial basis, the p ^{k / 2} power of the input S (∈GF (p ^k )) splits S into elements S ₀ and S ₁ on ^two finite fields GF (p ^{k / 2} ), S ₀ -u _{1 This} can be realized by combining S ₁ and -S ₁ . Here, u ₁ (∈GF (p ^{k / 2} )) is a first-order coefficient of the minimum polynomial f (x) = x ² + u ₁ x + u _{0 in} the polynomial basis, and uses a small value such as 0 or ± 1. There are many cases.

FIG. 12 shows the pseudo GF (p ^k ) inverse element 800 ′ in the case of a polynomial basis, and FIG. 13 shows the processing flow. The pseudo GF (p ^k ) inverse element unit 800 ′ includes a dividing unit 810, a recording unit 860, a multiplying unit 870, a subtracting unit 880, and a combining unit 890. In the recording unit 860, u ₁ (εGF (p ^{k / 2} )) is recorded in advance. When the element S on the finite field GF (p ^k ) is input, the dividing unit 810 divides S into two elements S ₀ and S ₁ of the finite field GF (p ^{k / 2} ) (S810). The multiplying unit 870 multiplies u ₁ recorded in the recording unit 860 and S ₁ that is the output of the dividing unit 810 to obtain u ₁ S ₁ (S 840). The subtraction unit 880 subtracts u ₁ S ₁ output from the multiplication unit 870 from S ₀ output from the division unit 810 to obtain S ₀ -u ₁ S ₁ (S850). The synthesis unit 890, the _{S 1} which is the output of the _S 0 _-u 1 _{S 1} and the split portion 810 which is the output from the subtraction unit _880, the S by synthesizing the S 0 _-u 1 _{S 1} and -S ₁ A pseudo inverse element is obtained (S860), and a pseudo inverse element of S is output (S830).

In this way, since the pseudo inverse element can be obtained by dividing the element and performing multiplication, subtraction, and synthesis once, it can be expected to greatly reduce the amount of calculation compared to division.
[Third Embodiment]
In the present embodiment, an internal configuration of the pseudo GF (p ^k ) multiplication unit 900 shown in FIG. 8 of the first embodiment is shown. Since Q ″ is obtained in steps S110 and S120 so as to include elements on the finite field GF (p) whose value is 0, l ₂ (Q ″) is the element on the finite field GF (p) whose value is 0. The number is k / 2-1. Therefore, in the multiplication of l ₂ (Q ″) or l ₂ (Q ″) pseudo inverse element, it is only necessary to repeat the original multiplication on k / 2 + 1 finite fields GF (p).

An example of the internal configuration of the pseudo GF (p ^k ) multiplier 900 is shown in FIG. In the multiplication unit 910 that has changed the multiplication range, the calculation range j = 1 to k of the pseudo inverse element of l ₂ (Q ″) or l ₂ (Q ″) is changed to j = 1 to 1 + k / 2 as described above. , Perform multiplication. FIG. 15 shows a processing flow. However, α ^{i + j} shown in the processing flow indicates a digit (which element is added to a plurality of finite fields GF (p) expressing the result of multiplication)
Evaluation of Computation Amount when k = 6 Assume that the computation amount of the original multiplication on the finite field GF (p ^k ) is M _k and the computation amount of the original multiplication on the finite field GF (p) is M. Since the amount of addition and constant multiplication are sufficiently smaller than the amount of multiplication, for the sake of simplicity, they are ignored in this evaluation, and the textbook method and the Karatsuba method, which are generally known as multiplication methods, are k. = 6 is evaluated.

Generally, in the textbook method, M ₆ = 4M ₃ , M ₃ = 9M, and M ₆ = 36M, and in the Karatsuba method, M ₆ = 3M ₃ , M ₃ = 6M, and M ₆ = 18M. By successive expansion of the polynomial basis, an element on the normal finite field GF (p ⁶ ) is represented by an element on the six finite fields GF (p), but l2 (Q ″) of the pseudo multiplication is six finite fields. Two of the elements on the field GF (p) are 0, and are used to perform multiplication with a smaller amount of calculation than normal multiplication.
The amount of computation M ₆ ′ in the pseudo multiplication of l2 (Q ″) and an element on the finite field GF (p ⁶ ) is M ₆ ′ = 24 M in the textbook method. Next, the case of the Karatsuba method is examined. An element on the finite field GF (p ³ ) can be expressed by three elements on the finite field GF (p), but one of them becomes 0 by three multiplications, Multiply “binary polynomial x ternary polynomial” is 6 unary multiplications in the textbook method, but using the Toom-Cook method is possible with 4 unary multiplications. (M.Gonda, K.Matsuo, K.Aoki, J.Chao, and S.Tsujii, “Improvements of addition algorithm on genus 3 hyperelliptic curves and their implementations”, Vol.II, 3A3-1, pp.995- 1000, January 2004.). Therefore, when the Karatsuba method and the Toom-Cook method are combined, M ₆ ′ = 3M ₃ ′, M ₃ ′ = 4 M, and M ₆ ′ = 12 M. As described above, by using pseudo multiplication in both the textbook method and the Karatsuba method, the amount of calculation becomes 2/3 of the normal multiplication.

In all the embodiments of the present invention, all or a part of the above-described processing procedure can be executed by a computer and a program for operating the computer. Further, the program can be recorded on a computer-readable recording medium, and can be read and executed by a computer as necessary.
[Evaluation of computational complexity]
Desk evaluation
When the calculation amounts of the ellipse addition part and the ellipse double part in Miller's algorithm are TADD and TDBL, respectively, the calculation quantities are as follows. The calculation amount TMmiller of Miller's algorithm is as follows: n is an integer obtained by rounding up the decimal point of log (m) +1.
TMiller = (n / 2) TADD + nTDBL
It becomes. The original multiplication complexity on the finite field GF (p ^k ) is M _k , the square calculation quantity is S _k , the original multiplication complexity on the finite field GF (p) is M, and the square calculation quantity is S Then, in the conventional method (Patent Document 1),
_{TADD = 2M k + (3k +} 10) M + 3S
_{TDBL = 2M k + 2S k +} (3k + 7) M + 6S
It becomes. However, this is the case where the denominator and numerator of the element f on the finite field GF (p ^k ) are obtained separately.

The ellipse addition part TADD ′ using the pseudo inverse element and the calculation amount TDBL ′ of the ellipse double part are:
TADD ′ = 2M _k + (3k + 10) M + 3S
TDBL ′ = 2M _k + S _k + (3k + 7) M + 6S
It becomes. In addition, since the calculation amount of the inverse element is almost 0, it is not necessary to separately obtain the denominator and the numerator of the element f on the finite field GF (p ^k ). Thereby, an extra calculation can be reduced.
Since the ellipse addition part TADD ″ using the pseudo multiplication and the calculation amount TDBL ″ of the ellipse double part can replace one of M _k with the calculation amount M _k ′ in the case of the pseudo multiplication,
TADD "= _Mk + _Mk '+ (3k + 10) M + 3S
_{TDBL "= M k + M k} '+ S k + (3k + 7) M + 6S
It becomes.

Therefore, it can be seen that a reduction in calculation amount can be expected.
Experiments In order to confirm the effect of the present invention, the program of the present invention and the program of the conventional method were run on a computer and compared. Language is gcc version 3.3.3, OS is FreeBSD 5.2.1, Multiple-length library is GNU MP ver.4.1.4, CPU is AMD Opteron (TM) Processor 248 (2.2Ghz), Parameters are M. Scott and P. Barreto , “Generating more MNT elliptic curves”, Cryptology ePrint Archive 2004/058, available form http://eprint.iacr.org/2004/058. p = 625852803282871856053922297323874661378036491717 (16 bits), k = 6, m = 208617601094290618684641029477488665211553761021, a = -3, b = 423976005090848776334332509669574781621802740510.

  As a result, the execution time for one Miller algorithm in the conventional method is 11.22 ms, while the execution time for one pseudo Miller algorithm of the present invention is 9.03 ms, which is 24% faster.

The figure which shows the outline | summary of Tate pairing calculation. The figure which shows the function structural example of the pairing calculating device using Tate pairing. The figure which shows the internal structural example of a Miller arithmetic unit. The figure which shows the processing flow of a Miller algorithm. The figure which shows the principle of the speeding-up of a calculation using the pseudo Miller algorithm. The figure which shows the outline | summary of the pre-processing for reducing the frequency | count of multiplication by pseudo multiplication. The figure which shows the function structural example of the pairing arithmetic unit using a pseudo Miller algorithm. The figure which shows the function structural example of a pseudo Miller arithmetic unit. The figure which shows the processing flow of a pseudo Miller algorithm. The figure which shows the function structural example of the pseudo inverse element calculating part in a normal basis. The figure which shows the processing flow of the pseudo inverse element operation part in a normal basis. The figure which shows the function structural example of the pseudo | simulation inverse element calculating part in a polynomial basis. The figure which shows the processing flow of the pseudo | simulation inverse element operation part in a polynomial basis. The figure which shows the function structural example of a pseudo multiplication part. The figure which shows the processing flow of a pseudo multiplication part.

Claims (13)

p is a prime number or a power of a prime number, k is an even number, and a point P on an elliptic curve on a finite field GF (p) and a point Q on an elliptic curve on a finite field GF (p ^k ) are input. A pairing operation for obtaining an element on a finite field GF (p ^k ) from the obtained points, mapping the obtained element on the finite field to an element e (P, Q) on the finite field GF (p ^k ), and outputting the result In the device
Instead of the inverse element of the element L on the finite field GF (p ^k ) used in the Miller algorithm, the Miller algorithm for obtaining the element f on the finite field from P and Q is used.

A pseudo Miller operation unit for obtaining an element f ′ on a finite field GF (p ^k ) from P and Q,
A power calculator that maps the element f ′ obtained by the pseudo Miller calculator to the element e (P, Q) on the finite field GF (p ^k ) by a power calculation;
A pairing arithmetic device comprising: p is a prime number or a power of a prime number, k is an even number, and a point P on an elliptic curve on a finite field GF (p) and a point Q on an elliptic curve on a finite field GF (p ^k ) are input. A pairing operation for obtaining an element on a finite field GF (p ^k ) from the obtained points, mapping the obtained element on the finite field to an element e (P, Q) on the finite field GF (p ^k ), and outputting the result In the device
When r is an element on a finite field GF ( ^{pk / 2} ),
Instead of accumulating the element L on the finite field GF (p ^k ) used in the Miller algorithm for the Miller algorithm for obtaining the element f on the finite field from P and Q,
If the element L ′ of the finite field GF (p ^k ) is at least one value of 0 on the k finite fields GF (p) representing L ′ and L ′ = rL
A pseudo Miller computing unit that selects an element satisfying the following, changes to an algorithm that integrates L ′, and obtains an element f ′ on a finite field GF (p ^k ) from P and Q;
A power calculator that maps the element f ′ obtained by the pseudo Miller calculator to the element e (P, Q) on the finite field GF (p ^k ) by a power calculation;
A pairing arithmetic device comprising: p is a prime number or a power of a prime number, k is an even number, and a point P on an elliptic curve on a finite field GF (p) and a point Q on an elliptic curve on a finite field GF (p ^k ) are input. A pairing operation for obtaining an element on a finite field GF (p ^k ) from the obtained points, mapping the obtained element on the finite field to an element e (P, Q) on the finite field GF (p ^k ), and outputting the result In the device
When r is an element on a finite field GF ( ^{pk / 2} ),
A Miller algorithm for obtaining an element f on a finite field GF (p ^k ) from P and Q is used instead of the inverse element of the element L on the finite field GF (p ^k ) used in the Miller algorithm.

Using
Instead of accumulating the elements L on the finite field GF (p ^k ) used in the Miller algorithm,
If the element L ′ of the finite field GF (p ^k ) is at least one value of 0 on the k finite fields GF (p) representing L ′ and L ′ = rL
A pseudo Miller operation unit characterized in that an element f ′ on a finite field GF (p ^k ) is ^obtained by selecting an element satisfying the above and changing to an algorithm for accumulating L ′;
A power calculator that maps the element f ′ obtained by the pseudo Miller calculator to the element e (P, Q) on the finite field GF (p ^k ) by a power calculation;
A pairing arithmetic device comprising: In the pairing arithmetic device according to claim 2 or 3,
a and b are integers, based on X are represented by using the two elements _{X 0} and _{X 1} of the finite field GF (p ^{k / 2)} of the finite field GF ^{(p k),} finite GF ^{(p k} ) When the above element L can be expressed as L = aX + b,
A pairing operation device including a pseudo Miller operation unit that sets L ′ = X ₁ ⁻¹ L. In the pairing arithmetic device according to any one of claims 1, 3 and 4,
When the original S of the finite field GF ^{(p k)} is represented by the two elements _{S 0} and _{S 1} of the finite field GF using normal basis (p ^{k / 2),}
Pairing computation device comprising a pseudo Miller calculation unit for obtaining the pseudo-inverse element by replacing the S ₀ and S _1. In the pairing arithmetic device according to any one of claims 1, 3 and 4,
Original S of a finite field GF ^{(p k)} are finite GF (p ^{k / 2)} of the two elements _S 0, _{S 1,} and the minimum polynomial _{^{f (x) = x 2 +}} u 1 x + u 0 by using a polynomial basis Is represented by
A pairing arithmetic device comprising a pseudo Miller arithmetic unit for obtaining a pseudo inverse element by combining S ₀ -u ₁ S ₁ and -S ₁ . p is a prime number or a power of a prime number, k is an even number, and a point P on an elliptic curve on a finite field GF (p) and a point Q on an elliptic curve on a finite field GF (p ^k ) are input. A pairing operation for obtaining an element on a finite field GF (p ^k ) from the obtained points, mapping the obtained element on the finite field to an element e (P, Q) on the finite field GF (p ^k ), and outputting the result In the method
In the pseudo Miller arithmetic unit, a Miller algorithm for obtaining an element f on a finite field from P and Q is used instead of the inverse element of the element L on the finite field GF (p ^k ) used in the Miller algorithm.

Is changed to an algorithm using, and an element f ′ on a finite field GF (p ^k ) is ^obtained from P and Q,
A pairing calculation method characterized in that the power calculation unit maps the element f ′ obtained by the pseudo Miller calculation unit to the element e (P, Q) on the finite field GF (p ^k ) by a power calculation. p is a prime number or a power of a prime number, k is an even number, and a point P on an elliptic curve on a finite field GF (p) and a point Q on an elliptic curve on a finite field GF (p ^k ) are input. A pairing operation for obtaining an element on a finite field GF (p ^k ) from the obtained points, mapping the obtained element on the finite field to an element e (P, Q) on the finite field GF (p ^k ), and outputting the result In the method
When r is an element on a finite field GF ( ^{pk / 2} ),
Instead of accumulating the element L on the finite field GF (p ^k ) used in the Miller algorithm for the Miller algorithm for obtaining the element f on the finite field from P and Q in the pseudo Miller arithmetic unit,
If the element L ′ of the finite field GF (p ^k ) is at least one value of 0 on the k finite fields GF (p) representing L ′ and L ′ = rL
Is selected from elements satisfying the above, and the algorithm is changed to an algorithm for accumulating L ′, and an element f ′ on the finite field GF (p ^k ) is ^obtained from P and Q,
A pairing calculation method characterized in that the power calculation unit maps the element f ′ obtained by the pseudo Miller calculation unit to the element e (P, Q) on the finite field GF (p ^k ) by a power calculation. p is a prime number or a power of a prime number, k is an even number, and a point P on an elliptic curve on a finite field GF (p) and a point Q on an elliptic curve on a finite field GF (p ^k ) are input. A pairing operation for obtaining an element on a finite field GF (p ^k ) from the obtained points, mapping the obtained element on the finite field to an element e (P, Q) on the finite field GF (p ^k ), and outputting the result In the method
When r is an element on a finite field GF ( ^{pk / 2} ),
A Miller algorithm for obtaining an element f on a finite field GF (p ^k ) from P and Q by a pseudo Miller arithmetic unit is used instead of the inverse element of the element L on the finite field GF (p ^k ) used in the Miller algorithm.

The process of using
Instead of accumulating the elements L on the finite field GF (p ^k ) used in the Miller algorithm,
If the element L ′ of the finite field GF (p ^k ) is at least one value of 0 on the k finite fields GF (p) representing L ′ and L ′ = rL
And a process for obtaining an element f ′ on a finite field GF (p ^k ) by changing to an algorithm that integrates L ′,
And a process of mapping the element f ′ obtained by the pseudo Miller operation unit to the element e (P, Q) on the finite field GF (p ^k ) by a power operation. Calculation method. In the pairing calculation method according to claim 8 or 9,
2 a and b are integers, the finite field GF of ^{(p k)} of the original X a representing the k finite field GF (p) finite based can be divided into two on the GF (p ^{k / 2)} If one _element is X ₀ and X ₁ and the element L on the finite field GF (p ^k ) can be expressed as L = aX + b,
In the pseudo Miller calculation unit, L ′ = X ₁ ⁻¹ L The pairing calculation method according to claim 7, 9 or 10,
Two elements of a finite field GF (p ^{k / 2} ) obtained by dividing an element on k finite fields GF (p) expressing the element S of the finite field GF (p ^k ) into two are ^denoted by S ₀ . If S ₁
A pairing calculation method characterized in that a pseudo inverse element is obtained by replacing S ₀ and S ₁ in a pseudo Miller calculation unit. The pairing calculation method according to claim 7, 9 or 10,
An element S of a finite field GF (p ^k ) is a polynomial basis, and two elements of a finite field GF (p ^{k / 2} ) formed by dividing an element on ^k finite fields GF (p) into two S ₀ and S ₁ , where u ₁ is an element on a finite field GF (p ^{k / 2} ) determined for each polynomial basis,
A pairing calculation method, wherein a pseudo inverse element is obtained by combining S ₀ -u ₁ S ₁ and -S ₁ in a pseudo Miller calculation unit.   A pairing calculation program for realizing the pairing calculation device according to claim 1 by a computer.

Images