JP6777569B2 - Pairing arithmetic unit, pairing arithmetic method, and program - Google Patents

Description

The present invention relates to a cryptographic technique using pairing in the field of information and communication, and more particularly to a technique for efficiently calculating pairing.

In recent years, due to the bilinearity of pairing on an elliptical curve, high ID-based cryptography (see Non-Patent Document 1), attribute-based cryptography (see Non-Patent Document 2), and functional cryptography (see Non-Patent Document 3) A functional encryption method has been proposed. An encryption method using such pairing is also called a pairing encryption. In recent years, development by Open Source Software (OSS) in Apache Milagro (incubating) (see Non-Patent Document 4) and standardization by Internet Engineering Task Force (IETF) (Non-Patent Document 5) , 6), and other activities are being carried out to use pairing cryptography in the real world.

Pairing on an elliptic curve can be calculated using the Miller's Algorithm proposed by Miller (see Miller's Algorithm, Non-Patent Document 7). In the mirror algorithm, it is necessary to construct an L function which is a straight line passing through two points on an elliptic curve or a tangent line passing through one point. As a method of constructing the L function, there is known a method of constructing a double / addition on an elliptic curve using the Affine coordinate system / Jacobian coordinate system using the slope calculated in the middle of the calculation (non-). See Patent Document 8). Since the Affine coordinate system uses the inverse element calculation and the Jacobian coordinate system does not use the inverse element calculation, these coordinate systems are used properly according to the ratio of the calculation time of the computer multiplication and the inverse element calculation. A coordinate system other than the Affine coordinate system / Jacobian coordinate system includes the Compressed Jacobian coordinate system (see Non-Patent Document 9), but a method of constructing an L function using this coordinate system is not known.

D. Boneh and M. Franklin, "Identity-Based Encryption from the Weil Pairing", CRYPTO 2001, LNCS 2139, pp. 213-229, 2001. A. Sahai and B. Waters, "Identity-Based Encryption", EUROCRYPT 2005, LNCS 3494, pp. 457-473, 2005. T. Okamoto and K. Takashima, "Fully secure functional encryption with general relations from the decisional linear assumption", CRYPTO 2010, LNCS 6223, pp. 191-208, 2010. Apache Software Foundation, "MILAGRO", [online], [Searched February 22, 2017], Internet <URL: https://milagro.apache.org/> RFC5091, "Identity-Based Cryptography Standard (IBCS) # 1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems", 2007. RFC6508, "Sakai-Kasahara Key Encryption (SAKKE)", 2012. V. S. Miller, "The Weil Pairing, and Its Efficient Calculation", Journal of Cryptology, vol. 17, pp. 235-261, 2004. S. Chatterjee, P. Sarkar and R. Barua, "Efficient Computation of Tate Pairing in Projective Coordinate over General Characteristic Fields", ICISC 2004, LNCS 3506, pp. 168-181, 2005. F. Hoshino, T. Kobayashi and K. Aoki, "Compressed Jacobian Coordinates for OEF", VIETCRYPT 2006, LNCS 4341, pp. 147-156, 2006.

In order to realize pairing encryption as an actual system, it is important to perform pairing operations efficiently. Depending on the performance of the computer, double / addition on an elliptic curve using the Compressed Jacobian coordinate system may be able to calculate faster than other coordinate systems. However, a method of constructing an L function required for a pairing operation using the Compressed Jacobian coordinate system has not been known.

In view of the above points, an object of the present invention is to realize a technique capable of efficiently calculating pairing by constructing an L function necessary for pairing calculation using the Compressed Jacobian coordinate system. Is.

In order to solve the above problems, in the pairing arithmetic device of the present invention, p and r are prime numbers, k is an embedded order, d is a positive integer, E is an elliptical curve, and F _p is an order p. _Let F _{p ^ (k / d) be} a finite field of order p ^{k / d} , let F _{p ^} ^{k be} a finite field of order p ^k , and let G _{1 be} on the elliptical curve E (F _p ). Let G _{2 be a} subgroup of the order r on the elliptical curve E (F _{p ^ (k / d)} ), and let G _{3 be a} subgroup of the order r on the finite field F _{p ^ k} . As a finite field, e is a pairing of G ₁ × G ₂ → G ₃ , ECDBL is an input point on an elliptical curve, and that point is doubled on the elliptical curve, and two on the elliptical curve. Compute the double on an elliptical curve using the Compressed Jacobian coordinate system, which outputs the values Λ _n ∈ F _{p ^ (k / d)} , λ _d ∈ F _p, which are calculated in the process of calculating the multiplication. As an algorithm, ECADD is input to two points on an elliptical curve, the points obtained by adding the two points on the elliptical curve, and the value calculated in the process of calculating the addition on the elliptical curve Λ _n ∈ F _{p ^ ( k / d),} and outputs λ _d ∈F _p, and the algorithm that calculates the addition on the elliptic curve using Compressed Jacobian coordinates, elliptic curve E (F _p) points on _P = (x P, y _P) and the elliptic curve _{E (F p ^ (k /} d)) point on the _Q = (X Q, a pairing e (P, pairing computation device for calculating the Q) and Y _Q), the value 1 to f, the algorithm as input and the point (X _1, Y _1, Z ₁₎ to the point _{(X Q, Y Q, 1} ) initializing unit that assigns a point (X _1, Y _1, Z ₁₎ ECDBL is calculated and the points (X ₁ , Y ₁ , Z ₁ ) are doubled on the elliptical curve E to obtain the points (X ₃ , Y ₃ , Z ₃ ) and the values Λ _n , λ _d. L ← y _P Z ₁ ² Z ₃ + (-, using the part and the values f, Λ _n , λ _d , Z ₃ , point (x _P , y _P ), (X ₁ , Y ₁ , Z ₁ ) x _P Λ _n Z ₁ ² + (Λ _n X ₁ -Y ₁ λ _d )), f ← f ² · L is calculated, and the point (X ₃ , Y ₃ , Z ₃ ) is the point (X ₁ , Y ₁₎ , Z ₁ ) and the point (X ₁ , Y ₁ , Z ₁ ), (X _Q , Y _Q , 1) The algorithm ECADD is calculated with the input of, and the points (X ₁ , Y ₁ , Z ₁ ) and the points (X _Q , Y _Q , 1) are added on the elliptical curve E to the points (X ₃ , Y ₃ , Z _3). ) And the elliptical addition part to obtain the above values Λ _n , λ _d , and the values f, Λ _n , Z ₃ , points (x _P , y _P ), (X _Q , Y _Q , 1), L ← y _P Z ₃ + (-x _P Λ _n + (Λ _n X _Q -Y _Q Z ₃ )), f ← f · L is calculated, and the point (X ₃ , Y ₃ , Z ₃ ) is the point (X ₁ , It includes an addition part to be assigned to Y ₁ , Z ₁ ) and a final calculation part to calculate f ^{(p ^ k-1) / r} .

According to the present invention, it is possible to construct an L function necessary for a pairing operation using the Compressed Jacobian coordinate system and efficiently perform the pairing operation.

FIG. 1 is a diagram illustrating a functional configuration of a pairing arithmetic unit. FIG. 2 is a diagram illustrating a processing procedure of the pairing calculation method.

Hereinafter, embodiments of the present invention will be described in detail. In the drawings, the components having the same function are given the same number, and duplicate description is omitted.

The symbol "^" used in superscripts or subscripts as used herein indicates that the character immediately following it is the superscript. For example, f ^{(p ^ k-1) / r} means that f is raised to the power of (p ^k -1) / r. In mathematical formulas, these symbols are described in their original notation, that is, superscripts in superscripts. For example, f ^{(p ^ k-1) / r} is described as follows.

[Preparation]
Prior to the description of the embodiments, an outline of the terms used in the present specification will be described.

<Pairing>
Let p and r be prime numbers. Let k be the embedded order. Let d be a positive integer. Let E be an elliptic curve. _Let F _{p be} a finite field of order p. _Let F _{p ^ (k / d) be} a finite field of order p ^{k / d} . _Let F _{p ^ k be} a finite field of order p ^k . _Let G _{1 be a} subgroup of the order r on the elliptic curve E (F _p ). _Let G _{2 be a} subgroup of the order r on the elliptic curve E (F _{p ^ (k / d)} ). _Let G _{3 be a} subgroup of the order r on the finite field F _{p ^ k} . Let f _{r and Q} be rational functions.

For the groups G ₁ , G ₂ , and G ₃ , pairing e is defined as follows.

<Mirror algorithm>
The rational functions f _{r and Q} can be calculated by using the mirror algorithm described in Non-Patent Document 7. The mirror algorithm is shown in Algorithm 1.

In step 3 of the mirror algorithm, the double calculation on the elliptic curve is calculated. In step 7 of the mirror algorithm, the addition on the elliptic curve is calculated. As described above, there are three known coordinate systems that perform operations on the elliptic curve: the Affine coordinate system, the Jacobian coordinate system, and the Compressed Jacobian coordinate system. Hereinafter, each coordinate system will be described. Note that m is a positive integer.

<Affine coordinate system>
The Affine coordinate system is described in detail on pages 79-82 of Reference 1 below. The elliptic curve E _A in the Affine coordinate system defined on the finite field F _{p ^ m} can be expressed by Eq. (1) for a, b ∈ F _{p ^ m} satisfying 4a ³ + 27b ² ≠ 0. ..

A point on the elliptic curve E _A can be expressed as _{(x, y) ∈F p ^} m × F p ^ m. In the Affine coordinate system, this expression is used to double / add on the elliptic curve E _A.

[Reference 1] D. R. Hankerson, A. J. Menezes and S. A. Vanstone, "Guide to Elliptic Curve Cryptography", Springer, 2004.

<Jacobian coordinate system>
The Jacobian coordinate system is described in detail on pages 86-89 of Reference 1 above. Elliptic curve E _J in Jacobian coordinate system defined on a finite field F _{p ^ m is, X∈F p ^ m, Y∈F p} ^ m, relative Z∈F _{p ^ m,} the equation (1) By replacing with (x, y) = (X / Z ² , Y / Z ³ ), it can be expressed as in equation (2).

A point on the elliptic curve E _J, can be expressed as (X, Y, Z) ∈F p ^ m × F p ^ m × F p ^ m. The Jacobian coordinate system uses this representation to perform doubling / addition on the elliptic curve E _J.

<Compressed Jacobian coordinate system>
The Compressed Jacobian coordinate system is described in detail in Non-Patent Document 9 above. Elliptic curve E _ComJ in Compressed Jacobian coordinate system defined on a finite field F _{p ^ m is, X∈F p ^ m, Y∈F p} ^ m, relative z∈F _p, the above equation (1) By replacing (x, y) = (X / z ² , Y / z ³ ), it can be expressed as in Eq. (3).

A point on the elliptic curve _E comJ, can be expressed as (X, Y, z) ∈F p ^ m × F p ^ m × F p. The Compressed Jacobian coordinate system uses this representation to double / add on the elliptic curve E _comJ .

<L function>
The L-functions (L _{T, T} (P), L _{T, Q} (P)) used in steps 4 and 8 of the mirror algorithm are P = (x _P , y _P ) ∈ G ₁ , T = (x _T). , y _T ) ∈ G ₂ , T'= (x _T' , y _T' ) ∈ G _{2 For} the slope of a line λ ∈ F _{p ^ m} , it can be expressed as in Eq. (4).

To calculate the L-function, the value λ calculated during the calculation of double / addition on the elliptic curve in steps 3 and 7 of the mirror algorithm is used. An efficient method for constructing an L-function using the Affine coordinate system and the Jacobian coordinate system is known, but an efficient method for constructing an L-function using the Compressed Jacobian coordinate system is not known.

<Mirror algorithm according to the present invention>
Algorithm 2 shows a mirror algorithm using double / addition on an elliptic curve using the Compressed Jacobian coordinate system according to the present invention.

The ECDBL executed in step 3 is an algorithm proposed in Non-Patent Document 9 that calculates a double on an elliptic curve using the Compressed Jacobian coordinate system. The algorithm ECDBL takes one point on the elliptic curve E as an input, doubles the point on the elliptic curve E, and the value calculated in the process of calculating the doubling on the elliptic curve E Λ _n ∈ F. Output _{p ^ (k / d)} , λ _d ∈ F _p .

The ECADD executed in step 7 is an algorithm proposed in Non-Patent Document 9 that calculates addition on an elliptic curve using the Compressed Jacobian coordinate system. The algorithm ECADD takes two points on the elliptic curve E as inputs, adds the two points on the elliptic curve E, and the value calculated in the process of calculating the addition on the elliptic curve E Λ _n ∈ F _p. Output _{^ (k / d)} , λ _d ∈ F _p .

The DBL executed in step 4 is the value f, the values Λ _n , λ _d output by ECDBL, the points P (x _P , y _P ), the points (X ₁ , Y ₁ , Z ₁ ), and the points (X ₁ ). _The value Z ₃ which is the Z coordinate of ₃ , Y ₃ , Z ₃ ) is input, and the updated value f is output. The algorithm DBL is shown in Algorithm 3.

The ADD executed in step 8 is the value f, the value Λ _n output by ECADD, the points P (x _P , y _P ), the points (X _Q , Y _Q , 1), and the points (X ₃ , Y _3). , Z ₃ ) takes the value Z ₃ which is the Z coordinate as input, and outputs the updated value f. The algorithm ADD is shown in Algorithm 4.

[Embodiment]
As shown in FIG. 1, the pairing arithmetic unit 10 of the embodiment includes an input unit 1, an initialization unit 2, an ECDBL arithmetic unit 3 (also referred to as an elliptical double arithmetic unit), and a DBL arithmetic unit 4 (also referred to as a double arithmetic unit). It includes an ECADD calculation unit 5 (also called an elliptical addition unit), an ADD calculation unit 6 (also called an addition unit), a final power calculation unit 7, and an output unit 8. The pairing calculation method of the embodiment is realized by the pairing calculation device 10 performing the processing of each step described later.

The pairing arithmetic unit 10 is configured by loading a special program into a known or dedicated computer having, for example, a central processing unit (CPU), a main storage unit (RAM: Random Access Memory), or the like. It is a special device. The pairing arithmetic unit 10 executes each process under the control of the central processing unit, for example. The data input to the pairing arithmetic unit 10 and the data obtained in each process are stored in, for example, the main storage device, and the data stored in the main storage device is read out as necessary for other processes. It will be used. Further, at least a part of each processing unit of the pairing arithmetic unit 10 may be configured by hardware such as an integrated circuit.

The processing procedure of the pairing calculation method of the embodiment will be described with reference to FIG.

In step S1, two points _{P = (x P, y P} ) on the elliptic curve E to the input unit _{1 ∈G 1, Q = (X} Q, Y Q) ∈G 2, and the group G _1, G ₂ of the position The prime number r, which is a number, is input. The order r is input in binary notation as shown in the equation (5).

In step S2, the initialization unit 2 substitutes 1 for the value f and substitutes the point (X _Q , Y _Q , 1) for the point (X ₁ , Y ₁ , Z ₁ ) in the Compressed Jacobian coordinate system. Also, initialize index j to n-2. As shown in the equation (5), n is the number of digits when the order r is expressed in binary.

In step S3, the ECDBL calculation unit 3 calculates the algorithm ECDBL with the points (X ₁ , Y ₁ , Z ₁ ) as inputs, and doubles the points (X ₁ , Y ₁ , Z ₁ ) on the elliptic curve E. Obtain the points (X ₃ , Y ₃ , Z ₃ ) and the values Λ _n and λ _d calculated in the process of calculating the double on the elliptic curve.

In step S4, the DBL arithmetic unit 4 has values f, Λ _n , λ _d , points P (x _P , y _P ), (X ₁ , Y ₁ , Z ₁ ), and points (X ₃ , Y ₃ , Z). _The algorithm DBL is calculated with the value Z ₃ which is the Z coordinate of ₃ ) as an input, and the value f is updated. Further, the DBL calculation unit 4 substitutes a point (X ₃ , Y ₃ , Z ₃ ) into a point (X ₁ , Y ₁ , Z ₁ ).

In step S5, it is determined whether or not r _j is equal to 1. When r _j = 1 (YES), steps S6 and S7 are executed. When r _j ≠ 1 (NO), steps S6 and S7 are not executed, and the process proceeds to step S8.

In step S6, the ECADD calculation unit 5 calculates the algorithm ECADD with the points (X ₁ , Y ₁ , Z ₁ ), (X _Q , Y _Q , 1) as inputs, and the points (X ₁ , Y ₁ , Z _1). ) And the point (X _Q , Y _Q , 1) are added on the elliptic curve E (X ₃ , Y ₃ , Z ₃ ), and the value calculated in the process of calculating the addition on the elliptic curve Λ _{Get n} , λ _d .

In step S7, the ADD calculation unit 6 uses the values f, Λ _n , the point P (x _P , y _P ), (X _Q , Y _Q , 1), and the Z of the point (X ₃ , Y ₃ , Z ₃ ). The algorithm ADD is calculated with the coordinate value Z ₃ as input, and the value f is updated. Further, the ADD calculation unit 6 substitutes a point (X ₃ , Y ₃ , Z ₃ ) for a point (X ₁ , Y ₁ , Z ₁ ).

In step S8, it is determined whether or not the index j exceeds 0. When j> 0 (YES), j ← j-1 is calculated in step S9, that is, the index j is decremented, and the processes of steps S3 to S8 are executed again. When j ≦ 0 (NO), the process proceeds to step S10.

In step S10, the final exponentiation unit 7 calculates the equation (6) and obtains the pairing operation result e (P, Q).

In step S11, the output unit 8 outputs the pairing calculation result e (P, Q).

[Experimental result]
In order to demonstrate the effect of the present invention, the calculation cost when the conventional mirror algorithm (Algorithm 1) is used and the calculation cost when the mirror algorithm (Algorithm 2) according to the present invention is used are compared. In the following, using a computer in which S = M and I = 8M, where M is the calculation time for multiplication, S is the calculation time for double calculation, and I is the calculation time for inverse element calculation, it is described in Reference 2 below. The speed-up rate when the pairing is calculated using the above parameters will be described.

[Reference 2] D. Aranha, K. Karabina, P. Longa, C. Gebotys and J. Lopez, "Faster Explicit Formulas for Computing Pairings over Ordinary Curves," EUROCRYPT 2011, LNCS 6632, pp. 48-68, 2011 ..

The parameters described in Reference 2 are as follows.

At this time, ω = | 6z + 2 |, and the pairing for a certain function g is expressed as follows.

In the above-mentioned mirror algorithm, loops were performed by the number of digits when r was input and r was expressed in binary, but in this experiment, a general technique of reducing the number of loops to ω was used. Since this technique can be applied to both the conventional mirror algorithm and the mirror algorithm of the present invention, it does not affect the experimental results.

When calculating f _{ω, Q} (P) using the conventional mirror algorithm (Algorithm 1) in the Jacobian coordinate system, the calculation time of 7164M was required (M is the calculation time of one multiplication). When f _{ω and Q} (P) were calculated using the mirror algorithm (Algorithm 2) according to the present invention, a calculation time of 6940M was required. Therefore, it was found that the calculation time can be reduced by 3.2% by using the mirror algorithm according to the present invention.

Although the embodiments of the present invention have been described above, the specific configuration is not limited to these embodiments, and even if the design is appropriately changed without departing from the spirit of the present invention, the specific configuration is not limited to these embodiments. Needless to say, it is included in the present invention. The various processes described in the embodiments are not only executed in chronological order according to the order described, but may also be executed in parallel or individually as required by the processing capacity of the device that executes the processes.

[Program, recording medium]
When various processing functions in each device described in the above embodiment are realized by a computer, the processing contents of the functions that each device should have are described by a program. Then, by executing this program on the computer, various processing functions in each of the above devices are realized on the computer.

The program describing the processing content can be recorded on a computer-readable recording medium. The computer-readable recording medium may be, for example, a magnetic recording device, an optical disk, a photomagnetic recording medium, a semiconductor memory, or the like.

In addition, the distribution of this program is carried out, for example, by selling, transferring, renting, or the like, a portable recording medium such as a DVD or CD-ROM on which the program is recorded. Further, the program may be stored in the storage device of the server computer, and the program may be distributed by 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. Then, when the process is executed, the computer reads the program stored in its own recording medium and executes the process according to the read program. Further, as another execution form of this program, a computer may read the program directly from a portable recording medium and execute processing according to the program, and further, the program is transferred from the server computer to this computer. It is also possible to execute the process according to the received program one by one each time. In addition, the above 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 without transferring the program from the server computer to this computer. May be. It should be noted that the program in this embodiment includes information to be used for processing by a computer and equivalent to the program (data that is not a direct command to the computer but has a property of defining the processing of the computer, etc.).

Further, in this embodiment, the present device is configured by executing a predetermined program on the computer, but at least a part of these processing contents may be realized by hardware.

10 Pairing arithmetic unit 1 Input unit 2 Initialization unit 3 ECDBL arithmetic unit 4 DBL arithmetic unit 5 ECADD arithmetic unit 6 ADD arithmetic unit 7 Final exponentiation unit 8 Output unit

Claims (3)

p, and prime r, and order embedded a k, a d a positive integer, the E is an elliptic curve, the F _p a finite field of order _{p, F p ^ (k /} d) the position number p ^{k Let / d be} a finite field, let F _{p ^ k be} a finite field of order p ^k , let G _{1 be a} subgroup of order r on the order curve E (F _p ), and let G _{2 be the} order curve E (F _{p). ^ (k / d)} ) Let the subgroup of the order r on, G _{3 be the} subgroup of the order r on the finite field F _{p ^ k} , and let e be the pairing of G ₁ × G ₂ → G ₃ , N is the number of digits when the order r is expressed in binary, and r ₀ ,…, r _n-1 is the value of each digit when the order r is expressed in binary.
Compressed, where ECDBL is input to a point on the elliptic curve, the point is doubled on the elliptic curve, and the values Λ _n ∈ F _{p ^ (k / d)} and λ _d ∈ F _p are output. An algorithm that calculates double on an elliptic curve using the Jacobian coordinate system.
Compressed, which takes ECADD as input to two points on the elliptic curve, adds the two points on the elliptic curve, and outputs the values Λ _n ∈ F _{p ^ (k / d)} and λ _d ∈ F _p. An algorithm that calculates addition on an elliptic curve using the Jacobian coordinate system.
_{P = (x P, y P} ) points on the elliptic curve E (F _p) and the elliptic curve _{E (F p ^ (k /} d)) on a point _{Q = (X Q, Y Q} ) pairing with e A pairing arithmetic unit that calculates (P, Q).
An initializer that substitutes 1 for the value f and a point (X _Q , Y _Q , 1) for the point (X ₁ , Y ₁ , Z ₁ ),
The above algorithm ECDBL is calculated with the points (X ₁ , Y ₁ , Z ₁ ) as inputs, and the points (X ₁ , Y ₁ , Z ₁ ) are doubled on the elliptic curve E (X ₃ , Y ₃ , Z ₁ ). Z ₃ ) and the elliptic double part that obtains the above values Λ _n , λ _d ,
Using the above values f, Λ _n , λ _d , Z ₃ , points (x _P , y _P ), (X ₁ , Y ₁ , Z ₁ ), L _DBL ← y _P Z ₁ ² Z ₃ + (-x _P Λ _n Z ₁ ² + (Λ _n X ₁ -Y ₁ λ _d )), f ← f ²・ L Calculate _DBL and point points (X ₃ , Y ₃ , Z ₃ ) to points (X ₁ , Y ₁₎ , Z ₁ ) Substituting the double part,
The above algorithm ECADD is calculated with points (X ₁ , Y ₁ , Z ₁ ), (X _Q , Y _Q , 1) as inputs, and points (X ₁ , Y ₁ , Z ₁ ) and points (X _Q , Y _Q) , 1) and the point (X ₃ , Y ₃ , Z ₃ ) added on the elliptic curve E, and the elliptic addition part to obtain the above values Λ _n , λ _d ,
Using the above values f, Λ _n , Z ₃ , points (x _P , y _P ), (X _Q , Y _Q , 1), L _ADD ← y _P Z ₃ + (-x _P Λ _n + (Λ _n) X _Q -Y _Q Z ₃ ))), f ← f ・ L _ADD is calculated and the point (X ₃ , Y ₃ , Z ₃ ) is assigned to the point (X ₁ , Y ₁ , Z ₁ ).
The final exponentiation unit that calculates f ^{(p ^ k-1) / r} ,
Only including,
For each integer j from n-2 to 0 , when r _j = 1, the ellipse doubling part, the doubling part, the ellipse addition part, and the addition part are executed, and in other cases. Executes the elliptical double unit and the double unit,
Pairing arithmetic unit. p, and prime r, and order embedded a k, a d a positive integer, the E is an elliptic curve, the F _p a finite field of order _{p, F p ^ (k /} d) the position number p ^{k Let / d be} a finite field, let F _{p ^ k be} a finite field of order p ^k , let G _{1 be a} subgroup of order r on the order curve E (F _p ), and let G _{2 be the} order curve E (F _{p). ^ (k / d)} ) Let the subgroup of the order r on, G _{3 be the} subgroup of the order r on the finite field F _{p ^ k} , and let e be the pairing of G ₁ × G ₂ → G ₃ , N is the number of digits when the order r is expressed in binary, and r ₀ ,…, r _n-1 is the value of each digit when the order r is expressed in binary.
ECDBL is input to one point on the elliptic curve, the point obtained by doubling the point on the elliptic curve, and the value calculated in the process of calculating the doubling on the elliptic curve Λ _n ∈ F _{p ^ (k) As} an algorithm that calculates double on an elliptic curve using the Compressed Jacobian coordinate system that outputs _{/ d)} , λ _d ∈ F _p .
ECADD is input to two points on the elliptic curve, the points obtained by adding the two points on the elliptic curve, and the value calculated in the process of calculating the addition on the elliptic curve Λ _n ∈ F _{p ^ (k / d) )} , λ _d ∈ F _p, as an algorithm that calculates addition on an elliptic curve using the Compressed Jacobian coordinate system.
The pairing arithmetic unit including the initialization part, the elliptic double calculation part, the double calculation part, the elliptical addition part, the addition part, and the final power calculation part is a point P = (x _P ) on the elliptic curve E (F _p ). , y _P ) and the point Q = (X _Q , Y _Q ) on the elliptic curve E (F _{p ^ (k / d)} ) pairing e (P, Q) is a pairing calculation method. ,
The initialization part substitutes 1 for the value f and the point (X _Q , Y _Q , 1) for the point (X ₁ , Y ₁ , Z ₁ ).
The elliptic double unit calculates the above algorithm ECDBL with the points (X ₁ , Y ₁ , Z ₁ ) as inputs, and doubles the points (X ₁ , Y ₁ , Z ₁ ) on the elliptic curve E. Obtain (X ₃ , Y ₃ , Z ₃ ) and the above values Λ _n , λ _d ,
The double calculation part uses the above values f, Λ _n , λ _d , Z ₃ , points (x _P , y _P ), (X ₁ , Y ₁ , Z ₁ ), and L _DBL ← y _P Z ₁ ² Z ₃ + (-x _P Λ _n Z ₁ ² + (Λ _n X ₁ -Y ₁ λ _d )), f ← f ²・ L Calculate _DBL and point points (X ₃ , Y ₃ , Z ₃ ). Substitute in (X ₁ , Y ₁ , Z ₁ ) and
The elliptic addition part calculates the above algorithm ECADD with points (X ₁ , Y ₁ , Z ₁ ), (X _Q , Y _Q , 1) as inputs, and points (X ₁ , Y ₁ , Z ₁ ) and points ( The point (X ₃ , Y ₃ , Z ₃ ) obtained by adding X _Q , Y _Q , 1) on the elliptic curve E and the above values Λ _n , λ _d are obtained.
The adder uses the above values f, Λ _n , Z ₃ , points (x _P , y _P ), (X _Q , Y _Q , 1) and L _ADD ← y _P Z ₃ + (-x _P Λ _n). + (Λ _n X _Q -Y _Q Z ₃ )), f ← f ・ L _ADD is calculated and the point (X ₃ , Y ₃ , Z ₃ ) is substituted for the point (X ₁ , Y ₁ , Z ₁ ). ,
The final power of calculation unit, calculates the ^{f (p ^ k-1)} / r,
For each integer j from n-2 to 0 , when r _j = 1, the ellipse doubling part, the doubling part, the ellipse addition part, and the addition part are executed, and in other cases. Executes the elliptical double unit and the double unit,
Pairing calculation method. A program for operating a computer as the pairing arithmetic unit according to claim 1.

Images