WO2010024401A1 - ペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラム - Google Patents

ペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラム Download PDF

Info

Publication number
WO2010024401A1
WO2010024401A1 PCT/JP2009/065099 JP2009065099W WO2010024401A1 WO 2010024401 A1 WO2010024401 A1 WO 2010024401A1 JP 2009065099 W JP2009065099 W JP 2009065099W WO 2010024401 A1 WO2010024401 A1 WO 2010024401A1
Authority
WO
WIPO (PCT)
Prior art keywords
rational
pairing
function
computing
calculation
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2009/065099
Other languages
English (en)
French (fr)
Inventor
保之 野上
正剛 赤根
由美 酒見
良孝 森川
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Okayama University NUC
Original Assignee
Okayama University NUC
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Okayama University NUC filed Critical Okayama University NUC
Priority to EP09810049A priority Critical patent/EP2360659A4/en
Priority to JP2010526795A priority patent/JP5360836B2/ja
Priority to CN200980142428.7A priority patent/CN102308326B/zh
Priority to US13/060,520 priority patent/US8625777B2/en
Publication of WO2010024401A1 publication Critical patent/WO2010024401A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3066—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
    • H04L9/3073—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing

Definitions

  • the present invention relates to a pairing calculation device, a pairing calculation method, and a pairing calculation program that can execute pairing calculation at high speed.
  • an authentication process for confirming that the individual user is a legitimate user may be performed.
  • authentication is generally performed using an ID and a password set in advance for each individual user.
  • an authentication server for executing authentication processing is provided in the network.
  • digital signature data unique to an individual user is added to each data itself.
  • digital signature data it is possible to guarantee that data used by individual users has not been altered by a third party or leaked to a third party, and highly confidential information can be handled safely on the network. It has become possible.
  • the authentication server stores personal information such as what site the individual user has accessed and what service is used. From the viewpoint of protecting personal information, Adequate care is taken to prevent information leakage.
  • the individual user transmits to the authentication server anonymously the signature data certifying that it belongs only to the predetermined group. It is authenticated that the individual user belongs to a predetermined group without specifying. Accordingly, the authentication server prevents unauthorized use by an individual user who does not belong to the group, while authenticating the individual user without accumulating history information for each individual user.
  • the pairing operation is used for anonymous authentication in such a digital group signature.
  • the pairing operation is an operation using a function with two inputs and one output. For example, two rational operations are performed with S as a rational point on the prime field F p and Q as a rational point on the k-th order extension field F p k. in which the original z of the extension field F * p k is output by inputting a point S and Q.
  • the pairing operation has bilinearity that the ab power of z is calculated when a times the rational point S and b times the rational point Q are input. Authentication is performed using this bilinearity.
  • “k” is the embedding degree
  • “F * p k ” is correctly expressed in mathematics as Although, on the display of the restriction, it is displayed as "F * p k".
  • the points on the elliptic curve are used for the rational points S and Q, respectively.
  • Such a pairing operation of rational points on an elliptic curve includes a step of calculating using a mirror algorithm and a step of performing exponentiation on the calculation result.
  • the digital group signature when performing an access right authentication process for an individual user belonging to a group, first, a pairing operation is performed to exclude an individual user whose access right has expired. Next, in the digital group signature, by performing a pairing operation of a predetermined individual user and performing an authentication process, it is possible to flexibly cope with the issuance of the access right for each individual user or the change of the revocation attribute.
  • E an additive group of rational points on a simple elliptic curve
  • E [r] be a set of rational points of prime order r
  • ⁇ p be a Frobenius self-homogeneous map
  • G 1 E [r] ⁇ Ker ( ⁇ p ⁇ [1])
  • G 2 E [r] ⁇ Ker ( ⁇ p ⁇ [p])
  • G 2 G 1 ⁇ F * p k / (F * p k) r
  • a pairing computing device that defines a pairing e as a non-degenerate bilinear map, and calculates a pairing e (Q, S) as S ⁇ G 1 and Q ⁇ G 2 and outputs a computation result.
  • the arithmetic means for calculating the rational function f ⁇ , Q (S) calculates ⁇ Q, stores the operation result in a predetermined register, and uses the operation result of ⁇ Q to perform the predetermined operation. It has the characteristic also in having a calculating means which calculates the rational point.
  • the Frobenius self-homogeneous mapping ⁇ p of the value l of the rational point S (x s , y s ) in the straight line passing through the rational point (Q 1 , Q 2 ) with Q 1 , Q 2 ⁇ G 2 is By using the value of the rational point S (x s , y s ) in the straight line passing through the rational point (pQ 1 , pQ 2 ) Become And the rational function f ′ ⁇ , Q (S) is also calculated.
  • E an additive group of rational points on a ringable elliptic curve
  • E [r] be a set of rational points with prime order r
  • ⁇ p be a Frobenius self-homogeneous map.
  • G 1 E [r] ⁇ Ker ( ⁇ p ⁇ [1])
  • G 2 E [r] ⁇ Ker ( ⁇ p ⁇ [p])
  • pairing e is defined as a non-degenerate bilinear map
  • pairing e (Q, S) is calculated by an electronic computer equipped with a CPU as S ⁇ G 1 and Q ⁇ G 2.
  • the trace of the Frobenius automorphism map ⁇ p is t
  • the pairing e (Q, S) is calculated using the rational function f t ⁇ 1, Q (S) calculated using the Miller algorithm.
  • the CPU of the electronic computer is made to function as a calculation means, ⁇ Q is calculated, and the calculation result of ⁇ Q is obtained. It also has a feature in that it has a step of calculating a predetermined rational point.
  • E an additive group of rational points on a ringable elliptic curve
  • E [r] be a set of rational points with prime order r
  • ⁇ p be a Frobenius self-homogeneous map.
  • G 1 E [r] ⁇ Ker ( ⁇ p ⁇ [1])
  • G 2 E [r] ⁇ Ker ( ⁇ p ⁇ [p])
  • G 2 G 1 ⁇ F * p k / (F * p k) r
  • an arithmetic means for computing the rational function f ⁇ , Q (S), An arithmetic means for calculating a value at a rational point S (x s , y s ) of a straight line passing through the rational point of the line, and an arithmetic operation for calculating a rational function f ′ ⁇ , Q (S) using the calculation result of these arithmetic means And the rational function f ' ⁇ , Q (S) It was made to function as a calculation means for calculating as follows.
  • the pairing calculation program of the present invention is characterized in that the electronic computer functions as a calculation means for calculating ⁇ Q and a calculation means for calculating a predetermined rational point using the calculation result of ⁇ Q.
  • the rational function calculated using the Miller algorithm at the time of the pairing operation is a function of the integer variable ⁇ , so that the rational function can be calculated at high speed, and the pairing operation is performed. Can be speeded up. Therefore, a practical digital group signature service can be provided.
  • FIG. 1 is a schematic diagram of a pairing arithmetic device according to an embodiment of the present invention.
  • FIG. 2 is a flowchart of the pairing calculation program according to the embodiment of the present invention.
  • FIG. 3 is a flowchart for calculating the rational function f ⁇ , Q (S).
  • FIG. 4 is a flowchart of a pairing calculation program according to another embodiment of the present invention.
  • the first step of calculating a rational function using the mirror algorithm in the pairing calculation and the multiplication of the calculation result is performed.
  • the computation is speeded up by computing a rational function using the integer variable ⁇ in the first step.
  • E an additive group of rational points on a simple elliptic curve
  • E [r] be a set of rational points of prime order r
  • ⁇ p be a Frobenius self-homogeneous map
  • G 1 E [r] ⁇ Ker ( ⁇ p ⁇ [1])
  • G 2 E [r] ⁇ Ker ( ⁇ p ⁇ [p])
  • a pairing e is defined as a non-degenerate bilinear map, and a rational function f t calculated by Miller's algorithm, where t is a trace of S ⁇ G 1 , Q ⁇ G 2 and Frobenius automorphism map ⁇ p
  • the pairing e (Q, S) was calculated by using the following equation known as Ate pairing using ⁇ 1, Q (S).
  • pairing that can be calculated at higher speed by using an integer variable ⁇ of an elliptic curve. This pairing is referred to as “Xate pairing”.
  • the elliptic curve used for the pairing calculation is known as a pairing-friendly curve depending on the built-in order.
  • G 1 E [r] ⁇ Ker ( ⁇ p ⁇ [1])
  • G 2 E [r] ⁇ Ker ( ⁇ p ⁇ [p])
  • G 2 G 1 ⁇ F * p 12 / (F * p 12 ) r
  • the pairing e is defined as a non-degenerate bilinear map.
  • Equation 9 From the relational expression p 6 ⁇ -1 (mod r), (Equation 7) can be transformed as follows. 6 ⁇ (1 + p) ⁇ 1 ⁇ (1 + p) 2 + p ⁇ ⁇ 1 + p + p 3 + p 10 (mod r) (Formula 10)
  • G aQ, bQ l aQ, bQ / v aQ + bQ , where l aQ, bQ is the value of a straight line passing through two rational points aQ and bQ, and v aQ + bQ is the vertical line of the rational point aQ + bQ Value. If the built-in order is an even number, the calculation of v aQ + bQ can be omitted.
  • the pairing e (Q, S) is calculated by the following equation.
  • the present inventors refer to this pairing e (Q, S) as Xate pairing.
  • Equation 20 can be transformed as follows.
  • a new value obtained using the rational function f ⁇ , Q (S) and the value of a straight line passing through a predetermined rational point is used. It can be calculated using the rational function f ′ ⁇ , Q (S), and in particular, the rational function f ′ ⁇ , Q (S) can be calculated using ⁇ having a size smaller than t ⁇ 1. Can be speeded up.
  • the pairing calculation device is not limited to the case where the authentication server is configured, and any device can be used as long as it has at least calculation means such as a CPU and can perform pairing calculation. There may be.
  • an electronic computer 10 constituting an authentication server includes a CPU 11 that executes arithmetic processing, various programs such as a pairing arithmetic program, and a hard disk that stores data used in the pairing arithmetic program.
  • a storage device 12 and a memory device 13 composed of a RAM or the like that allows the pairing operation program to be expanded and executed and temporarily store data generated as a result of the execution of the pairing operation program are provided. Yes.
  • 14 is a bus.
  • the electronic computer 10 is connected to a telecommunication line 20 such as the Internet, and can receive the signature data of the digital group signature transmitted from the client device 30 connected to the telecommunication line 20.
  • a telecommunication line 20 such as the Internet
  • reference numeral 15 denotes an input / output control unit of the electronic computer 10.
  • the electronic computer 10 when the signature data of the digital group signature is transmitted from the client device 30, the transmitted signature data is temporarily stored in the memory device 13. Next, in the electronic computer 10, the pairing calculation is performed by executing the pairing calculation program.
  • the electronic computer 10 performs a pairing operation based on the flowchart shown in FIG. 2 to realize a digital group signature.
  • the authentication process in the digital group signature will not be described in detail, but only the pairing operation as a subroutine process in the authentication process will be described in detail.
  • the electronic computer 10 inputs necessary data by causing the CPU 11 to function as an input means as step S1 as shown in FIG. That is, in the electronic computer 10, the data of the integer variable ⁇ and the data of the rational point Q stored in advance in the memory device 13 are input to a predetermined register provided in the CPU 11, and further, the memory device 13 is used as signature data. The data of the rational point S once stored in is input to a predetermined register provided in the CPU 11.
  • the electronic computer 10 causes the CPU 11 to function as the first calculation means in step S2 to calculate the rational function f ⁇ , Q (S) using the Miller algorithm.
  • step S2 The calculation of the rational function f ⁇ , Q (S) is specifically executed as shown in the flowchart of FIG. In particular, in step S2, the calculation of ⁇ Q is performed together with the calculation of the rational function f ⁇ , Q (S), and the calculation result of ⁇ Q is stored in a predetermined register provided in the CPU 11.
  • the electronic computer 10 performs initial setting as step S21.
  • the electronic computer 10 performs processing of f ⁇ 1 and T ⁇ Q, and further sets i ⁇ [log 2 ( ⁇ )], where i is the number of bits when the integer variable ⁇ is represented in binary.
  • the electronic computer 10 performs a predetermined calculation of the rational function f ⁇ , Q (S) portion as step S22.
  • the electronic computer 10 performs a predetermined calculation of the ⁇ Q portion as step S23.
  • the electronic computer 10 determines whether the value u i of the i-th bit of the integer variable ⁇ is “1” or “0” as step S24.
  • step S27 the electronic computer 10 makes an end determination as step S27.
  • step S27 the electronic computer 10 stores the calculation result of the rational function f ⁇ , Q (S) and the calculation result of ⁇ Q in predetermined registers, respectively, and based on the flowchart of FIG. The subroutine is finished.
  • step S3 the electronic calculator 10 causes the CPU 11 to function as the second calculation means to calculate the rational points p 10 ⁇ Q, ⁇ Q + p 10 ⁇ Q, and p ⁇ Q + p 3 ⁇ Q by the pairing calculation program.
  • X p 10 R
  • Y R + p 10 R
  • Z pR + p 3 R
  • the electronic computer 10 performs the following calculation. X ⁇ ⁇ p 10 (T), Y ⁇ T + X, Z ⁇ ⁇ p 3 (Y).
  • step S3 the electronic computer 10 can execute the calculation without performing the multiplication process, so that the calculation can be speeded up.
  • step S4 the computer 10 causes the CPU 11 to function as the third calculation means by the pairing calculation program, and the rational point S (x s , y s in the straight line passing through the rational point ( ⁇ Q, p 10 ⁇ Q). ) Value l 1 and a rational point S (x s , y s ) value l 2 on a straight line passing through the rational point ( ⁇ Q + p 10 ⁇ Q, p ⁇ Q + p 3 ⁇ Q), respectively.
  • l 1 l T
  • X (S) is calculated as follows. ⁇ T, X ⁇ (y X ⁇ y T ) / (x X ⁇ x T ), l T, X (S) ⁇ (x S ⁇ x X ) ⁇ T, X ⁇ (y S ⁇ y X ).
  • l 2 l Y, Z (S) is calculated as follows. ⁇ Y, Z ⁇ (y Z ⁇ y Y ) / (x Z ⁇ x Y ), l Y, Z (S) ⁇ (x S ⁇ x Z ) ⁇ Y, Z ⁇ (y S ⁇ y Z ).
  • step S5 the electronic calculator 10 causes the CPU 11 to function as the fourth calculation means by the pairing calculation program, and the calculation result of the first calculation means, the calculation result of the third calculation means, and the rational point.
  • the rational function f ′ ⁇ , Q (S) is calculated as follows using the value l 3 of the rational point S (x s , y s ) in the straight line passing through (p ⁇ Q, p 3 ⁇ Q).
  • p being the value of the rational point S (x s , y s ) in the straight line passing through the rational point (pQ 1 , pQ 2 )
  • the electronic computer 10 performs the calculation as follows. Here, it indicates that p ⁇ 3 is p 3. 1. C ⁇ f p ⁇ 10 2. C ⁇ C ⁇ f 3. A ⁇ C ⁇ l T, X (S) 4. B ⁇ A p ⁇ 3 5. returnA, B
  • the amount of calculation can be greatly reduced, and the pairing calculation can be speeded up.
  • step S6 the electronic computer 10 causes the CPU 11 to function as the fifth calculation means to perform the last power multiplication in the pairing e (Q, S).
  • the electronic computer 10 performs the calculation as follows. 1. f ' ⁇ f' p ⁇ 6 ⁇ f ' -1 2. f ' ⁇ f' p ⁇ 2 ⁇ f ' 3. a ⁇ (f ' 6 ) ⁇ ⁇ (f' 5 ) p ⁇ 6 4. b ⁇ a p 5. b ⁇ a ⁇ b 6. compute f ' p , f' p ⁇ 2 , andf ' p ⁇ 3 7. c ⁇ b ⁇ (f ' p ) 2 ⁇ f' p ⁇ 2 8. f ' ⁇ f' p ⁇ 3 ⁇ (c 6 ) ⁇ 2 ⁇ c ⁇ b ⁇ (f ' p ⁇ f') 9 ⁇ a ⁇ f ' 4 9. Return f ' ⁇ f' p ⁇ 6 ⁇ f ' -1 2. f ' ⁇ f' p ⁇ 2 ⁇ f ' 3. a ⁇
  • the electronic computer 10 constituting the authentication server performs authentication processing using the pairing calculation result obtained as described above.
  • the authentication server performs the pairing operation based on the flowchart shown in FIG. 4 by executing the pairing operation program.
  • the electronic computer 10 inputs the necessary data by causing the CPU 11 to function as an input means as step T1 as shown in FIG. That is, in the electronic computer 10, the data of the integer variable ⁇ and the data of the rational point Q stored in advance in the memory device 13 are input to a predetermined register provided in the CPU 11, and further, the memory device 13 is used as signature data. The data of the rational point S once stored in is input to a predetermined register provided in the CPU 11.
  • step T2 the electronic calculator 10 causes the CPU 11 to function as the first calculation means to calculate the rational function f ⁇ , Q (S) using the Miller algorithm.
  • step T2 the first expression in step S22 of the flowchart shown in FIG. 3 is as follows. 1. ⁇ T, T ⁇ (3x T 2 + a) / (2y T )
  • the rational function f ⁇ , Q (S) is calculated in the same manner as in the flowchart.
  • step T2 the electronic computer 10 also calculates ⁇ Q together with the rational function f ⁇ , Q (S) and stores the calculation result in a predetermined register.
  • step T3 the electronic calculator 10 causes the CPU 11 to function as the second calculation means to calculate the rational points p ⁇ Q, ⁇ Q + p ⁇ Q, and p 3 ⁇ Q + p 4 ⁇ Q by the pairing calculation program.
  • X pR
  • Y R + pR
  • Z p 3 R + p 4 R
  • the electronic computer 10 performs the following calculation. X ⁇ ⁇ p (T), Y ⁇ T + X, Z ⁇ ⁇ p 3 (Y).
  • step T4 the electronic calculator 10 causes the CPU 11 to function as the third calculation means by the pairing calculation program, and the rational point S (x s , y s ) in the straight line passing through the rational point ( ⁇ Q, p ⁇ Q).
  • the value l 4 and the value l 5 of the rational point S (x s , y s ) in the straight line passing through the rational point ( ⁇ Q + p ⁇ Q, p 3 ⁇ Q + p 4 ⁇ Q) are respectively calculated.
  • l 4 l T
  • X (S) is calculated as follows. ⁇ T, X ⁇ (y X ⁇ y T ) / (x X ⁇ x T ), l T, X (S) ⁇ (x S ⁇ x X ) ⁇ T, X ⁇ (y S ⁇ y X ).
  • l 5 l Y, Z (S) is calculated as follows. ⁇ Y, Z ⁇ (y Z ⁇ y Y ) / (x Z ⁇ x Y ), l Y, Z (S) ⁇ (x S ⁇ x Z ) ⁇ Y, Z ⁇ (y S ⁇ y Z ).
  • the electronic calculator 10 causes the CPU 11 to function as the fourth calculation means in step T5 according to the pairing calculation program, the calculation result in the first calculation means, the calculation result in the third calculation means, and the rational point.
  • the rational function f ′ ⁇ , Q (S) is calculated as follows using the value l 6 of the rational point S (x s , y s ) in the straight line passing through (p 3 ⁇ Q, p 4 ⁇ Q). .
  • p being the value of the rational point S (x s , y s ) in the straight line passing through the rational point (pQ 1 , pQ 2 )
  • the electronic computer 10 performs the calculation as follows. Here, it indicates that p ⁇ 3 is p 3. 1. C ⁇ f p 2. C ⁇ C ⁇ f 3. A ⁇ C ⁇ l T, X (S) 4. B ⁇ A p ⁇ 3 5. returnA, B
  • the electronic calculator 10 1. f ' ⁇ A ⁇ B ⁇ l Y, Z (S) 2. f ' ⁇ f' p ⁇ 4 By calculating as Is calculated.
  • step T6 the electronic calculator 10 causes the CPU 11 to function as the fifth calculation means to perform the last power multiplication in the pairing e (Q, S).
  • the electronic computer 10 constituting the authentication server performs authentication processing using the pairing calculation result obtained as described above.
  • the electronic computer 10 sets the pairing e (Q, S). Can be computed as
  • G 1 E [r] ⁇ Ker ( ⁇ p ⁇ [1])
  • G 2 E [r] ⁇ Ker ( ⁇ p ⁇ [p])
  • G 2 G 1 ⁇ F * p 8 / (F * p 8 ) r
  • the pairing e is defined as a non-degenerate bilinear map.
  • the electronic computer 10 calculates the rational function f ⁇ , Q (S) by the Miller algorithm as described above, and calculates ⁇ Q together with the rational function f ⁇ , Q (S).
  • the operation result is stored in a predetermined register.
  • pairing e (Q, S) is performed.
  • the rational function f ′ ⁇ , Q (S) is calculated by the following equation using the value l 11 of the rational point S (x s , y s ) in the straight line passing through the rational point (pQ, ⁇ Q). You can also.
  • the electronic computer 10 calculates the rational function f ⁇ 2, Q (S) and the rational function f ⁇ , Q (S) by the Miller algorithm as described above, calculates ⁇ Q, and calculates the result. Is stored in a predetermined register.
  • G 1 E [r] ⁇ Ker ( ⁇ p ⁇ [1])
  • G 2 E [r] ⁇ Ker ( ⁇ p ⁇ [p])
  • G 2 G 1 ⁇ F * p 18 / (F * p 18 ) r
  • the pairing e is defined as a non-degenerate bilinear map.
  • the electronic computer 10 calculates the rational function f ⁇ , Q (S) by the Miller algorithm as described above, and calculates ⁇ Q together with the rational function f ⁇ , Q (S).
  • the operation result is stored in a predetermined register.
  • the electronic computer 10 calculates the value l 13 using the rational function f ⁇ , Q (S) and the operation result of ⁇ Q, calculates the rational function f ′ ⁇ , Q (S), and performs pairing.
  • e (Q, S) Can be computed as
  • the pairing operation can be speeded up, and a group signature using the pairing operation can be put into practical use.
  • a high-speed pairing arithmetic device can be provided, and a practical digital group signature service can be provided.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Analysis (AREA)
  • Computing Systems (AREA)
  • Physics & Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • Mathematical Physics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Algebra (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Complex Calculations (AREA)
  • Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
  • Navigation (AREA)
  • Mobile Radio Communication Systems (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

　高速なペアリング演算を可能としたペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムを提供する。 　曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆp kを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数とし、有理関数ｆχ,Q(Ｓ)を演算する演算手段と、所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算する演算手段と、これらの演算手段の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算する演算手段と、有理関数f'χ,Q(Ｓ)を用いて 式（１）としてペアリング演算を行う演算手段と有するものとする。

Description

ペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラム
　本発明は、ペアリング演算を高速に実行可能としたペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムに関する。
　従来、個人ユーザがインターネットなどのネットワーク上において提供されている各種のサービスを利用する場合に、その個人ユーザが正規のユーザであることを確認する認証処理が行われていることがある。このような認証処理では、一般的に、個人ユーザごとにあらかじめ設定されたＩＤ及びパスワード等を用いて認証している。そのために、ネットワークには、認証処理を実行するための認証サーバが設けられている。
　最近では、ディジタル署名技術を用いることにより、個々のデータ自体に個人ユーザに固有のディジタル署名データを付加している。このディジタル署名データによって、個人ユーザが利用するデータが第三者によって改ざんされていないこと、あるいは第三者に漏洩していないことを保証可能として、秘匿性の高い情報もネットワーク上で安全に取り扱い可能となってきている。
　一方、ディジタル署名では、認証サーバでの認証処理にともなって個人ユーザが特定されるため、認証処理のたびに認証サーバに個々の個人ユーザの履歴が情報として逐次蓄積されることとなっている。したがって、認証サーバには、個人ユーザが、どのようなサイトにアクセスしたかとか、どのようなサービスを利用したかなどの個人情報が蓄積されることとなるので、個人情報保護の点からこれらの情報の漏洩が生じないように、十分な注意が払われている。
　このようなディジタル署名を用いることによって生じる個人ユーザの履歴情報の蓄積を解消するために、ディジタル署名を拡張したディジタルグループ署名を用いることが提案されている。
　ディジタルグループ署名を用いた場合には、個人ユーザは、認証サーバに対して匿名で所定のグループに属していることのみを証明する署名データを送信し、認証サーバでは、受信した署名データから個人ユーザを特定することなく個人ユーザが所定のグループに属していることを認証している。したがって、認証サーバでは、グループに属さない個人ユーザによる不正利用を阻止する一方で、個人ユーザごとの履歴情報を蓄積することなく個人ユーザを認証している。
　このようなディジタルグループ署名における匿名認証には、ペアリング演算が用いられている。
　ペアリング演算は、２入力１出力の関数を用いた演算であって、たとえば、Ｓを素体Ｆp上の有理点、Ｑをｋ次拡大体Ｆp k上の有理点として、２つの有理点ＳとＱを入力することにより拡大体Ｆ* p kの元ｚが出力されるものである。しかも、ペアリング演算は、有理点Ｓのａ倍と、有理点Ｑのｂ倍を入力した場合に、ｚのab乗が算出されるという双線形性を有している。この双線形性を利用して認証を行っている。ここで、「ｋ」は埋込み次数であり、「Ｆ* p k」は、数学における表記上、正しくは、
Figure JPOXMLDOC01-appb-M000011
 であるが、表示の制限上、「Ｆ* p k」と表示している。
　一般的に、有理点Ｓ，Ｑにはそれぞれ楕円曲線上の点が用いられている。このような楕円曲線上の有理点のペアリング演算は、ミラーのアルゴリズムを用いて演算するステップと、その演算結果に対してべき乗算を行うステップとで構成されている。
　ディジタルグループ署名では、グループに所属する個人ユーザのアクセス権の認証処理を行う際に、まず、アクセス権が失効している個人ユーザを除外するためのペアリング演算を行っている。次いで、ディジタルグループ署名では、所定の個人ユーザのペアリング演算を行って認証処理を行うことにより、個人ユーザごとのアクセス権の発行または失効の属性変更に柔軟に対応可能としている。
　したがって、たとえば、10,000人の個人ユーザで構成されるグループのディジタルグループ署名の場合に、アクセス権が失効している個人ユーザが100人いれば、100回のペアリング演算が必要となっている。現時点での一般的な電子計算機による１回のペアリング演算には約0.1秒を要していることから、100回のペアリング演算には約10秒を要することとなっている。したがって、現状では、ディジタルグループ署名は実用的な技術とは考えられておらず、広く利用されるものとはなっていなかった。
　現状では、ディジタルグループ署名を実用化するために、ペアリング演算の演算速度を向上させる研究が行われている。たとえば、ペアリング演算の高速化の技術として、楕円曲線上で定義されるＴａｔｅペアリング演算を用い、演算負荷を低減させて高速化を図る技術が提案されている（例えば、特許文献１参照。）。
特開２００５－３１６２６７号公報
　しかしながら、現在提案されているペアリング演算の高速化の技術では未だに十分ではなく、さらなる高速化が求められていた。
　本発明者らは、このような現状に鑑み、ペアリング演算を高速化すべく研究開発を行って、本発明を成すに至ったものである。
　本発明のペアリング演算装置では、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆp kを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
　　Ｇ1＝Ｅ[r]∩Ker(φp－[１]),
　　Ｇ2＝Ｅ[r]∩Ker(φp－[ｐ])
により、
　　ｅ：Ｇ2×Ｇ1→Ｆ* p k/(Ｆ* p k)r
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ1、Ｑ∈Ｇ2としてペアリングｅ(Ｑ,Ｓ)を演算して演算結果を出力するペアリング演算装置であって、フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
Figure JPOXMLDOC01-appb-M000012
 として演算する代わりに、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、有理関数ｆχ,Q(Ｓ)を演算する演算手段と、所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算する演算手段と、これらの演算手段の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算する演算手段と、有理関数f'χ,Q(Ｓ)を用いて
Figure JPOXMLDOC01-appb-M000013
 としてペアリング演算を行う演算手段とによりペアリング演算を行うこととした。
　さらに、本発明のペアリング演算装置では、有理関数ｆχ,Q(Ｓ)を演算する演算手段では、χＱを演算して演算結果を所定のレジスタに記憶し、χＱの演算結果を用いて所定の有理点を演算する演算手段を有することにも特徴を有する。
　しかも、本発明のペアリング演算装置では、埋込み次数ｋ＝12の場合に、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを、整数変数χを用いて
　ｒ(χ)＝３６χ4－３６χ3＋１８χ2－６χ＋１,
　ｔ(χ)＝６χ2＋１
とし、χＱ＝Ｒとして、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、有理点ｐ10χＱ、χＱ＋ｐ10χＱ、ｐχＱ＋ｐ3χＱをそれぞれ演算し、有理点(χＱ,ｐ10χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l1と、有理点(χＱ＋ｐ10χＱ,ｐχＱ＋ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l2をそれぞれ演算し、有理点(ｐχＱ,ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l3を用いて
Figure JPOXMLDOC01-appb-M000014
 として有理関数f'χ,Q(Ｓ)を演算することにも特徴を有する。
　そのうえ、本発明のペアリング演算装置では、有理関数fχ,Q(Ｓ)のフロベニウス自己準同型写像φpがφp(fχ,Q(Ｓ))＝fχ,Q(Ｓ)pであることを用いて
Figure JPOXMLDOC01-appb-M000015
 を演算するとともに、Ｑ1,Ｑ2∈Ｇ2である有理点(Ｑ1,Ｑ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値lのフロベニウス自己準同型写像φpが有理点(pＱ1,pＱ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値であることを用いて
Figure JPOXMLDOC01-appb-M000016
 となる
Figure JPOXMLDOC01-appb-M000017
 を演算して有理関数f'χ,Q(Ｓ)を演算することにも特徴を有する。
　また、本発明のペアリング演算方法では、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆp kを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
　　Ｇ1＝Ｅ[r]∩Ker(φp－[１]),
　　Ｇ2＝Ｅ[r]∩Ker(φp－[ｐ])
により、
　　ｅ：Ｇ2×Ｇ1→Ｆ* p k/(Ｆ* p k)r
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ1、Ｑ∈Ｇ2としてＣＰＵを備えた電子計算機でペアリングｅ(Ｑ,Ｓ)を演算するペアリング演算方法であって、フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
Figure JPOXMLDOC01-appb-M000018
 として演算する代わりに、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、電子計算機のＣＰＵを演算手段として機能させて、有理関数ｆχ,Q(Ｓ)を演算するステップと、電子計算機のＣＰＵを演算手段として機能させて、所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算するステップと、電子計算機のＣＰＵを演算手段として機能させて、前記の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算するステップと、電子計算機のＣＰＵを演算手段として機能させて、有理関数f'χ,Q(Ｓ)を用いて
Figure JPOXMLDOC01-appb-M000019
 として演算するステップとを有するものである。
　さらに、本発明のペアリング演算方法では、有理関数ｆχ,Q(Ｓ)を演算するステップの後、電子計算機のＣＰＵを演算手段として機能させて、χＱを演算し、このχＱの演算結果を用いて所定の有理点を演算するステップを有することにも特徴を有する。
　また、本発明のペアリング演算プログラムでは、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆp kを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
　　Ｇ1＝Ｅ[r]∩Ker(φp－[１]),
　　Ｇ2＝Ｅ[r]∩Ker(φp－[ｐ])
により、
　　ｅ：Ｇ2×Ｇ1→Ｆ* p k/(Ｆ* p k)r
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ1、Ｑ∈Ｇ2としてＣＰＵを備えた電子計算機にペアリングｅ(Ｑ,Ｓ)を演算させるペアリング演算プログラムであって、フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
Figure JPOXMLDOC01-appb-M000020
 として演算させる代わりに、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、電子計算機を、有理関数ｆχ,Q(Ｓ)を演算する演算手段と、所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算する演算手段と、これらの演算手段の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算する演算手段と、この有理関数f'χ,Q(Ｓ)を用いて
Figure JPOXMLDOC01-appb-M000021
 として演算する演算手段として機能させることとした。
　さらに、本発明のペアリング演算プログラムでは、電子計算機を、χＱを演算する演算手段と、このχＱの演算結果を用いて所定の有理点を演算する演算手段として機能させることにも特徴を有する。
　本発明によれば、ペアリング演算の際にミラーのアルゴリズムを用いて計算される有理関数を、整数変数χの関数とすることにより、有理関数の計算を高速に行うことができ、ペアリング演算を高速化することができる。したがって、実用性のあるディジタルグループ署名のサービスを提供できる。
図１は、本発明の実施形態にかかるペアリング演算装置の概略模式図である。 図２は、本発明の実施形態にかかるペアリング演算プログラムのフローチャートである。 図３は、有理関数fχ,Q(Ｓ)を演算するためのフローチャートである。 図４は、本発明の他の実施形態にかかるペアリング演算プログラムのフローチャートである。
　10　電子計算機
　11　ＣＰＵ
　12　記憶装置
　13　メモリ装置
　14　バス
　15　入出力制御部
　20　電気通信回線
　30　クライアント装置
　本発明のペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムでは、ペアリング演算におけるミラーのアルゴリズムを用いて有理関数を演算する第１のステップと、その演算結果に対してべき乗算を行う第２のステップのうち、第１のステップにおいて整数変数χを用いて有理関数を演算することにより、演算を高速化している。
　すなわち、従来のペアリング演算では、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆp kを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
　　Ｇ1＝Ｅ[r]∩Ker(φp－[１]),
　　Ｇ2＝Ｅ[r]∩Ker(φp－[ｐ])
により、
　　ｅ：Ｇ2×Ｇ1→Ｆ* p k/(Ｆ* p k)r
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ1、Ｑ∈Ｇ2、フロベニウス自己準同型写像φpのトレースをｔとして、ミラーのアルゴリズムで計算される有理関数ft-1,Q(Ｓ)を用いて、ペアリングｅ(Ｑ,Ｓ)を、Ａｔｅペアリングとして知られている次式により演算していた。
Figure JPOXMLDOC01-appb-M000022
　これに対して、本発明者らは、楕円曲線の整数変数χを用いることにより、より高速に演算が可能なペアリングを見い出した。このペアリングを、「Ｘａｔｅペアリング」と呼ぶこととする。
　すなわち、本発明のペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムでは、ＡｔｅペアリングではなくＸａｔｅペアリングを用いることにより、高速な演算を可能としているものである。
　特に、ペアリング演算に用いられる楕円曲線は、組み込み次数に応じてそれぞれペアリングフレンドリ曲線として知られており、例えば組み込み次数ｋ＝12の場合には、位数ｒと、フロベニウス自己準同型写像φpのトレースｔが、整数変数χを用いて次のように表せることが知られている。
　ｒ(χ)＝３６χ4－３６χ3＋１８χ2－６χ＋１,
　ｔ(χ)＝６χ2＋１.
　また、組み込み次数ｋ＝10の場合には、次のように表せることが知られている。
　ｒ(χ)＝２５χ4＋２５χ3＋１５χ2＋５χ＋１,
　ｔ(χ)＝１０χ2＋５χ＋３.
　あるいは、次のようにも表せることが知られている。
　ｒ(χ)＝χ8－１,
　ｔ(χ)＝－χ6＋χ4－χ2＋２.
　また、組み込み次数ｋ＝８の場合には、次のように表せることが知られている。
　ｒ(χ)＝９χ4＋１２χ3＋８χ2＋４χ＋１,
　ｔ(χ)＝－９χ3－３χ2－２χ.
　あるいは、次のようにも表せることが知られている。
　ｒ(χ)＝χ4－８χ2＋２５,
　ｔ(χ)＝(２χ3－１１χ＋１５)／１５.
　あるいは、次のようにも表せることが知られている。
　ｒ(χ)＝χ8－χ4＋１,
　ｔ(χ)＝χ5－χ＋１.
　また、組み込み次数ｋ＝18の場合には、次のように表せることが知られている。
　ｒ(χ)＝(χ6＋３７χ3＋３４３)／３４３,
　ｔ(χ)＝(χ4＋１６χ＋７)／７.
　以下において、組み込み次数ｋ＝12の場合を一例としてＸａｔｅペアリングを説明する。
　なお、組み込み次数ｋ＝12の場合には、曲線の式がｙ2＝ｘ3＋ｂ,ｂ∈Ｆpで与えられ、Ｆp 12を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
　　Ｇ1＝Ｅ[r]∩Ker(φp－[１]),
　　Ｇ2＝Ｅ[r]∩Ker(φp－[ｐ])
により、
　　ｅ：Ｇ2×Ｇ1→Ｆ* p 12/(Ｆ* p 12)r
である非退化な双線形写像としてペアリングｅを定義している。
　この場合、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、上述したように整数変数χを用いて次のように表せる。
　ｒ(χ)＝３６χ4－３６χ3＋１８χ2－６χ＋１　・・・（式１）
　ｔ(χ)＝６χ2＋１　・・・（式２）
　（式２）は次のように式変形できる。なお、特に必要でない場合には、便宜上、（χ）の表記を省略する。
　６χ2≡ｔ－１≡ｐ　（mod r）　・・・（式３）
　ここで、標数ｐには次の関係式があることを用いている。
　ｐ＝ｒ＋ｔ－１　・・・（式４）
　したがって、標数ｐは整数変数χを用いて次のように表せる。
　ｐ(χ)＝３６χ4－３６χ3＋２４χ2－６χ＋１・・・（式５）
　（式３）を用いて、（式５）は次のように式変形できる。
　ｐ≡ｐ2－６χ（ｐ＋１）＋４ｐ＋１　（mod r）　・・・（式６）
　この（式６）は、次のように式変形できる。
　６χ(１＋ｐ)≡ｐ2＋３ｐ＋１　（mod r）　・・・（式７）
　ここで、既に知られているｐ4－ｐ2＋１≡０（mod r）の関係式から、次の式が得られる。
　ｐ2(１－ｐ)(１＋ｐ)≡１　（mod r）　・・・（式８）
　この（式８）は、次のように式変形できる。
　(１＋ｐ)-1≡ｐ2(１－ｐ)　（mod r）　・・・（式９）
　（式９）を用いるとともに、ｐ6≡－１（mod r）の関係式から、（式７）は次のように式変形できる。
　６χ≡(１＋ｐ)-1{(１＋ｐ)2＋ｐ}
　　　≡１＋ｐ＋ｐ3＋ｐ10　（mod r）　・・・（式１０）
　次に、Ａｔｅペアリングの有理関数ft-1,Q(・)について考える。特に、（式３）によって有理関数ft-1,Q(・)は次のように表すことができる。ここで、ｔ－１＝Ｔとしている。
Figure JPOXMLDOC01-appb-M000023
　ここで、Ｑ∈Ｇ2であり、∀Ｓ∈Ｇ1に対して、以下の式とする。
Figure JPOXMLDOC01-appb-M000024
　（式１０）を用いることにより次の式が得られる。
Figure JPOXMLDOC01-appb-M000025
　ここで、有理関数は、次の関係式を満たすこととなっている。
Figure JPOXMLDOC01-appb-M000026
Figure JPOXMLDOC01-appb-M000027
Figure JPOXMLDOC01-appb-M000028
　したがって、（式１３）は次のように式変形できる。
Figure JPOXMLDOC01-appb-M000029
　なお、gaQ,bQ＝laQ,bQ／vaQ+bQであって、laQ,bQは２つの有理点ａＱとｂＱを通る直線の値、vaQ+bQは有理点ａＱ＋ｂＱの鉛直線の値である。組み込み次数が偶数の場合には、vaQ+bQの計算は省略できる。
　また、（式１７）中の
Figure JPOXMLDOC01-appb-M000030
 は、双線形性を有していることから、次のように式変形できる。
Figure JPOXMLDOC01-appb-M000031
　したがって、（式３）と（式１３）と（式１９）を用いて（式１７）を式変形することにより、次のようになる。
Figure JPOXMLDOC01-appb-M000032
　ここで、本発明者らは、（式２０）の左辺が双線形性を有していることから、（式２０）の右辺も双線形性を有していることに思い至り、この（式２０）の右辺を新たな有理関数をf'χ,Q(・)とすることとした。
　すなわち、次の式によりペアリングｅ(Ｑ,Ｓ)の演算を行うこととするものである。
Figure JPOXMLDOC01-appb-M000033
 　本発明者らは、このペアリングｅ(Ｑ,Ｓ)をＸａｔｅペアリングと呼んでいる。
　さらに、（式２０）の右辺は、次のように式変形できる。
Figure JPOXMLDOC01-appb-M000034
　すなわち、組み込み次数ｋ＝12の場合には、有理点(χＱ,ｐ10χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l1と、有理点(χＱ＋ｐ10χＱ,ｐχＱ＋ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l2と、有理点(ｐχＱ,ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l3をそれぞれ演算して特定しておくことにより、次の式に基づいてミラーのアルゴリズムを用いた演算を高速化できる。
Figure JPOXMLDOC01-appb-M000035
　しかも、（式２０）の右辺は、次のように式変形できるので、f'χ,Q(Ｓ)の演算をより高速化できる。
Figure JPOXMLDOC01-appb-M000036
　以上のように、Ｘａｔｅペアリングを用いることによって、ペアリング演算を行う場合には、有理関数fχ,Q(Ｓ)と、所定の有理点を通る直線の値を用いて得られた新たな有理関数f'χ,Q(Ｓ)を用いて演算でき、特に、特に有理関数f'χ,Q(Ｓ)が、ｔ－１よりもサイズの小さいχを用いて演算できることによって、ペアリング演算を高速化できる。
　ここまでは、組み込み次数ｋ＝12の場合について説明してきたが、組み込み次数ｋ＝8,10,18の場合にも基本的に同様であるので詳細な説明は省略する。
　以下において、組み込み次数ｋ＝12の場合の実施形態について詳説する。なお、本実施形態では、ディジタルグループ署名を想定しており、所要の電子計算機で構成された認証サーバをペアリング演算装置としている。ただし、ペアリング演算装置は、認証サーバで構成する場合に限定されるものではなく、少なくともＣＰＵなどの演算手段を備えてペアリング演算が実行可能となった装置であれば、どのような装置であってもよい。
　図１に示すように、認証サーバを構成する電子計算機10は、演算処理を実行するＣＰＵ11と、ペアリング演算プログラムなどの各種プログラム、及びペアリング演算プログラムで使用するデータなどを記憶したハードディスクなどの記憶装置12と、ペアリング演算プログラムを展開して実行可能とするとともに、ペアリング演算プログラムの実行にともなって生成されたデータを一時的に記憶するＲＡＭなどで構成されたメモリ装置13を備えている。図４中、14はバスである。
　また、電子計算機10は、インターネットなどの電気通信回線20に接続して、この電気通信回線20に接続されたクライアント装置30から送信されたディジタルグループ署名の署名データを受信可能としている。図１中、15は電子計算機10の入出力制御部である。
　電子計算機10では、クライアント装置30からディジタルグループ署名の署名データが送信されると、送信された署名データをメモリ装置13に一旦記憶する。次いで、電子計算機10では、ペアリング演算プログラムを実行するすることによりペアリング演算を行っている。
　すなわち、電子計算機10では、ペアリング演算プログラムの実行にともなって、図２に示すフローチャートに基づいてペアリング演算を行い、ディジタルグループ署名を実現している。なお、ディジタルグループ署名における認証処理については詳説せず、認証処理におけるサブルーチン処理としてのペアリング演算についてのみ詳説する。
　ペアリング演算プログラムによって、電子計算機10では、図２に示すようにステップＳ１として、ＣＰＵ11を入力手段として機能させて、必要なデータの入力を行っている。すなわち、電子計算機10では、メモリ装置13にあらかじめ記憶している整数変数χのデータと有理点ＱのデータをＣＰＵ11の内部に設けている所定のレジスタに入力し、さらに、署名データとしてメモリ装置13に一旦記憶された有理点ＳのデータをＣＰＵ11の内部に設けている所定のレジスタに入力している。
　次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＳ２として、ＣＰＵ11を第１演算手段として機能させて、ミラーのアルゴリズムによる有理関数fχ,Q(Ｓ)の演算を行っている。
　この有理関数fχ,Q(Ｓ)の演算は、具体的には図３のフローチャートに示すように実行している。特に、ステップＳ２では、有理関数fχ,Q(Ｓ)の演算とともにχＱの演算を行い、χＱの演算結果をＣＰＵ11の内部に設けている所定のレジスタの記憶している。
　すなわち、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２１として、初期設定を行っている。すなわち、電子計算機10では、ｆ←１、Ｔ←Ｑとする処理を行い、さらにｉ←［log2(χ)］として、整数変数χを２進数表示とした場合のビット数をｉとしている
　次いで、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２２として、有理関数fχ,Q(Ｓ)部分の所定の演算を行っている。
　次いで、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２３として、χＱ部分の所定の演算を行っている。
　次いで、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２４として、整数変数χのｉ番目のビットの値ｕiが「１」であるか「０」であるかを判定している。
　ｕi＝１の場合には、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２５として、有理関数fχ,Q(Ｓ)部分の所定の演算を行い、さらに、ステップＳ２６として、χＱ部分の所定の演算を行っている。
　次いで、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２７として、終了判定を行っている。
　ステップＳ２７においてｉ≠１の場合には、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２８として、ｉのデクリメントを行ってステップＳ２２に戻り、ステップＳ２７においてｉ＝１となるまで有理関数fχ,Q(Ｓ)及びχＱの演算を繰り返し行っている。
　ステップＳ２７においてｉ＝１の場合には、電子計算機10は、有理関数fχ,Q(Ｓ)の演算結果、及びχＱの演算結果をそれぞれ所定のレジスタに記憶して、図３のフローチャートに基づくサブルーチンを終了している。
　次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＳ３として、ＣＰＵ11を第２演算手段として機能させて、有理点ｐ10χＱ、χＱ＋ｐ10χＱ、ｐχＱ＋ｐ3χＱをそれぞれ演算している。
　特に、第２演算手段では、ステップＳ２において所定のレジスタに記憶されたχＱ＝Ｒとし、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、各有理点ｐ10χＱ＝ｐ10Ｒ、χＱ＋ｐ10χＱ＝Ｒ＋ｐ10Ｒ、ｐχＱ＋ｐ3χＱ＝ｐＲ＋ｐ3Ｒとして演算を行っている。
　具体的には、Ｔ＝χＱ＝Ｒであって、Ｘ＝ｐ10Ｒ、Ｙ＝Ｒ＋ｐ10Ｒ、Ｚ＝ｐＲ＋ｐ3Ｒとし、電子計算機10では、次のように演算している。
　　Ｘ←φp 10(Ｔ),
　　Ｙ←Ｔ＋Ｘ,
　　Ｚ←φp 3(Ｙ).
　したがって、ステップＳ３において、電子計算機10は、乗算処理をすることなく演算を実行できるので、演算を高速化することができる。
　次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＳ４として、ＣＰＵ11を第３演算手段として機能させて、有理点(χＱ,ｐ10χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l1と、有理点(χＱ＋ｐ10χＱ,ｐχＱ＋ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l2をそれぞれ演算している。
　具体的には、電子計算機10では、l1＝lT,X(Ｓ)を次のように演算している。
　　λT,X←(ｙX－ｙT)/(ｘX－ｘT),
　　lT,X(Ｓ)←(ｘS－ｘX)λT,X－(ｙS－ｙX).
　また、電子計算機10では、l2＝lY,Z(Ｓ)を次のように演算している。
　　λY,Z←(ｙZ－ｙY)/(ｘZ－ｘY),
　　lY,Z(Ｓ)←(ｘS－ｘZ)λY,Z－(ｙS－ｙZ).
　次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＳ５として、ＣＰＵ11を第４演算手段として機能させて、第１演算手段での演算結果と、第３演算手段での演算結果と、有理点(ｐχＱ,ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l3を用いて、次のように有理関数f'χ,Q(Ｓ)を演算している。
Figure JPOXMLDOC01-appb-M000037
　特に、この場合に、電子計算機10では、有理関数fχ,Q(Ｓ)のフロベニウス自己準同型写像φpが、φp(fχ,Q(Ｓ))＝fχ,Q(Ｓ)pであって、φp 10(fχ,Q(Ｓ))＝fχ,Q(Ｓ)p⌒10（ここで、p⌒10はｐ10であることを表している）を用いて
Figure JPOXMLDOC01-appb-M000038
 を演算している。
　さらに、電子計算機10では、Ｑ1,Ｑ2∈Ｇ2である有理点(Ｑ1,Ｑ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値lのフロベニウス自己準同型写像φpが、有理点(pＱ1,pＱ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値であることを用いて
Figure JPOXMLDOC01-appb-M000039
 となる
Figure JPOXMLDOC01-appb-M000040
 を演算して有理関数f'χ,Q(Ｓ)を演算している。
　具体的には、電子計算機10は、次のように演算を行っている。ここで、p⌒3はｐ3であることを表している。
　　1.　Ｃ←ｆp⌒10
　　2.　Ｃ←Ｃ・ｆ
　　3.　Ａ←Ｃ・lT,X(Ｓ)
　　4.　Ｂ←Ａp⌒3
　　5.　returnＡ,Ｂ
　したがって、
Figure JPOXMLDOC01-appb-M000041
 は、
　　f'←Ａ・Ｂ・lY,Z(Ｓ)
として演算できる。
　このように、Ｘａｔｅペアリングを用いることによって演算量を大きく削減することができ、ペアリング演算を高速化できる。
　次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＳ６として、ＣＰＵ11を第５演算手段として機能させて、ペアリングｅ(Ｑ,Ｓ)における最終べきのべき乗算を行っている。
　具体的には、電子計算機10は、次のように演算を行っている。
　　1.　f'←f'p⌒6・f'-1
　　2.　f'←f'p⌒2・f'
　　3.　ａ←(f'6)χ・(f'5)p⌒6
　　4.　ｂ←ａp
　　5.　ｂ←ａ・ｂ
　　6.　compute f'p,f'p⌒2,andf'p⌒3
　　7.　ｃ←ｂ・(f'p)2・f'p⌒2
　　8.　f'←f'p⌒3・(ｃ6)χ⌒2・ｃ・ｂ・(f'p・f')9・ａ・f'4
　　9.　Return f'
　認証サーバを構成する電子計算機10では、上述したようにして得られたペアリングの演算結果を用いて認証処理を行っている。
　本実施形態では、組み込み次数ｋ＝12の場合について説明したが、例えば組み込み次数ｋ＝10の場合でも、同様に演算できる。
　なお、組み込み次数ｋ＝10の場合には、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数が10で、Ｆp 10を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
　　Ｇ1＝Ｅ[r]∩Ker(φp－[１]),
　　Ｇ2＝Ｅ[r]∩Ker(φp－[ｐ])
により、
　　ｅ：Ｇ2×Ｇ1→Ｆ* p 10/(Ｆ* p 10)r
である非退化な双線形写像としてペアリングｅを定義している。
　この場合、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、整数変数χを用いて次のように表せる。
　ｒ(χ)＝２５χ4＋２５χ3＋１５χ2＋５χ＋１,
　ｔ(χ)＝１０χ2＋５χ＋３.
　また、整数変数χの標数ｐによるｐ進数展開は次のように表される。
　５χ＝ｐ4＋ｐ5＋ｐ7＋ｐ8＝ｐ4(１＋ｐ＋ｐ3＋ｐ4)　（mod ｒ(χ)）.
　そして、有理点(χＱ,ｐχＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l4と、有理点(χＱ＋ｐχＱ,ｐ3χＱ＋ｐ4χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l5をそれぞれ演算し、さらに、有理点(ｐ3χＱ,ｐ4χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l6を用いることにより、有理関数f'χ,Q(Ｓ)を次の式により演算している。
Figure JPOXMLDOC01-appb-M000042
　埋め込み次数ｋ＝12の場合と同様に、埋め込み次数ｋ＝10の場合でも、認証サーバでは、ペアリング演算プログラムを実行することにより、図４に示すフローチャートに基づいてペアリング演算を行っている。
　ペアリング演算プログラムによって、電子計算機10では、図４に示すようにステップＴ１として、ＣＰＵ11を入力手段として機能させて、必要なデータの入力を行っている。すなわち、電子計算機10では、メモリ装置13にあらかじめ記憶している整数変数χのデータと有理点ＱのデータをＣＰＵ11の内部に設けている所定のレジスタに入力し、さらに、署名データとしてメモリ装置13に一旦記憶された有理点ＳのデータをＣＰＵ11の内部に設けている所定のレジスタに入力している。
　次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＴ２として、ＣＰＵ11を第１演算手段として機能させて、ミラーのアルゴリズムによる有理関数fχ,Q(Ｓ)の演算を行っている。
　なお、このステップＴ２では、図３に示したフローチャートのステップＳ２２における１番目の式を、次のようにしている。
　　1.　λT,T←(３ｘT 2＋ａ）／（２ｙT）
　ここで、「ａ」は、ｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられた楕円曲線における１次の係数であり、この１番目の式以外は、図３に示したフローチャートと同様に有理関数fχ,Q(Ｓ)の演算を行っている。
　また、電子計算機10は、ステップＴ２でも、有理関数fχ,Q(Ｓ)とともにχＱを演算して、演算結果を所定のレジスタに記憶している。
　次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＴ３として、ＣＰＵ11を第２演算手段として機能させて、有理点ｐχＱ、χＱ＋ｐχＱ、ｐ3χＱ＋ｐ4χＱをそれぞれ演算している。
　特に、第２演算手段では、ステップＴ２において所定のレジスタに記憶されたχＱ＝Ｒとし、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、各有理点ｐχＱ＝ｐＲ、χＱ＋ｐχＱ＝Ｒ＋ｐＲ、ｐ3χＱ＋ｐ4χＱ＝ｐ3Ｒ＋ｐ4Ｒとして演算を行っている。
　具体的には、Ｔ＝χＱ＝Ｒであって、Ｘ＝ｐＲ、Ｙ＝Ｒ＋ｐＲ、Ｚ＝ｐ3Ｒ＋ｐ4Ｒとし、電子計算機10では、次のように演算している。
　　Ｘ←φp(Ｔ),
　　Ｙ←Ｔ＋Ｘ,
　　Ｚ←φp 3(Ｙ).
　次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＴ４として、ＣＰＵ11を第３演算手段として機能させて、有理点(χＱ,ｐχＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l4と、有理点(χＱ＋ｐχＱ,ｐ3χＱ＋ｐ4χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l5をそれぞれ演算している。
　具体的には、電子計算機10では、l4＝lT,X(Ｓ)を次のように演算している。
　　λT,X←(ｙX－ｙT)/(ｘX－ｘT),
　　lT,X(Ｓ)←(ｘS－ｘX)λT,X－(ｙS－ｙX).
　また、電子計算機10では、l5＝lY,Z(Ｓ)を次のように演算している。
　　λY,Z←(ｙZ－ｙY)/(ｘZ－ｘY),
　　lY,Z(Ｓ)←(ｘS－ｘZ)λY,Z－(ｙS－ｙZ).
　次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＴ５として、ＣＰＵ11を第４演算手段として機能させて、第１演算手段での演算結果と、第３演算手段での演算結果と、有理点(ｐ3χＱ,ｐ4χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l6を用いて、次のように有理関数f'χ,Q(Ｓ)を演算している。
Figure JPOXMLDOC01-appb-M000043
　特に、この場合に、電子計算機10では、有理関数fχ,Q(Ｓ)のフロベニウス自己準同型写像φpが、φp(fχ,Q(Ｓ))＝fχ,Q(Ｓ)pであることを用いて
Figure JPOXMLDOC01-appb-M000044
 を演算している。
　さらに、電子計算機10では、Ｑ1,Ｑ2∈Ｇ2である有理点(Ｑ1,Ｑ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値lのフロベニウス自己準同型写像φpが、有理点(pＱ1,pＱ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値であることを用いて
Figure JPOXMLDOC01-appb-M000045
 となる
Figure JPOXMLDOC01-appb-M000046
 を演算して有理関数f'χ,Q(Ｓ)を演算している。
　具体的には、電子計算機10は、次のように演算を行っている。ここで、p⌒3はｐ3であることを表している。
　　1.　Ｃ←ｆp
　　2.　Ｃ←Ｃ・ｆ
　　3.　Ａ←Ｃ・lT,X(Ｓ)
　　4.　Ｂ←Ａp⌒3
　　5.　returnＡ,Ｂ
　さらに、電子計算機10は、
　　1.　f'←Ａ・Ｂ・lY,Z(Ｓ)
　　2.　f'←f'p⌒4
として演算することにより、
Figure JPOXMLDOC01-appb-M000047
 を演算している。
　次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＴ６として、ＣＰＵ11を第５演算手段として機能させて、ペアリングｅ(Ｑ,Ｓ)における最終べきのべき乗算を行っている。
　認証サーバを構成する電子計算機10では、上述したようにして得られたペアリングの演算結果を用いて認証処理を行っている。
　また、組み込み次数ｋ＝10の場合には、ミラーのアルゴリズムを用いて計算される有理関数をfχ⌒2,Q(Ｓ)（χ⌒2はχ2であることを示す）としてペアリングｅ(Ｑ,Ｓ)を演算することもできる。
　この場合、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、整数変数χを用いて次のように表せる。
　ｒ(χ)＝χ8－１,
　ｔ(χ)＝－χ6＋χ4－χ2＋２.
　また、整数変数χの標数ｐによるｐ進数展開は次のように表される。
　ｐχ2＝－ｐ　（mod ｒ(χ)）.
　そして、電子計算機10では、有理関数f'χ,Q(Ｓ)を次の式により演算している。
Figure JPOXMLDOC01-appb-M000048
　したがって、ペアリング演算プログラムによって、電子計算機10では、ペアリングｅ(Ｑ,Ｓ)を
Figure JPOXMLDOC01-appb-M000049
 として演算することができる。
　また、組み込み次数ｋ＝8の場合には、曲線の式がｙ2＝ｘ3＋ａｘ,ａ∈Ｆpで与えられ、Ｆp 8を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
　　Ｇ1＝Ｅ[r]∩Ker(φp－[１]),
　　Ｇ2＝Ｅ[r]∩Ker(φp－[ｐ])
により、
　　ｅ：Ｇ2×Ｇ1→Ｆ* p 8/(Ｆ* p 8)r
である非退化な双線形写像としてペアリングｅを定義している。
　この場合、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、整数変数χを用いて次のように表せる。
　ｒ(χ)＝９χ4＋１２χ3＋８χ2＋４χ＋１,
　ｔ(χ)＝－９χ3－３χ2－２χ.
　また、整数変数χの標数ｐによるｐ進数展開は次のように表される。
　３χ＝－１－ｐ2＋ｐ3　（mod ｒ(χ)）.
　そして、有理点(χＱ,χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l7と、有理点(２χＱ,χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l8と、有理点(ｐ2Ｑ,(３χ＋１)Ｑ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l9と、有理点(３χＱ,Ｑ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l10を用いることにより、電子計算機10では、有理関数f'χ,Q(Ｓ)を次の式により演算している。
Figure JPOXMLDOC01-appb-M000050
　すなわち、ペアリング演算プログラムによって、電子計算機10では、上述したようにミラーのアルゴリズムによる有理関数fχ,Q(Ｓ)の演算を行い、有理関数fχ,Q(Ｓ)とともにχＱを演算して、演算結果を所定のレジスタに記憶している。
　次いで、電子計算機10では、所定のレジスタに記憶されたχＱ＝Ｒとし、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、各有理点２χＱ、ｐ2χ、３χＱ、(３χ＋１)Ｑを演算して、この演算結果を用いて各値l7,l8,l9,l10を演算し、有理関数f'χ,Q(Ｓ)を演算している。
　そして、電子計算機10では、ペアリングｅ(Ｑ,Ｓ)を
Figure JPOXMLDOC01-appb-M000051
 として演算することができる。
　なお、組み込み次数ｋ＝8の場合には、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを、整数変数χを用いて次のように表すこともできる。
　ｒ(χ)＝χ4－８χ2＋２５,
　ｔ(χ)＝(２χ3－１１χ＋１５)／１５.
　この場合、整数変数χの標数ｐによるｐ進数展開は次のように表される。
　χ＝－ｐ＋２ｐ3　（mod ｒ(χ)）.
　この場合には、有理点(ｐＱ,χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l11を用いて有理関数f'χ,Q(Ｓ)を次の式により演算することもできる。
Figure JPOXMLDOC01-appb-M000052
　あるいは、組み込み次数ｋ＝8の場合において、ミラーのアルゴリズムを用いて計算される有理関数をfχ⌒2,Q(Ｓ)（χ⌒2はχ2であることを示す）及びfχ,Q(Ｓ)としてペアリングｅ(Ｑ,Ｓ)を演算することもできる。
　このとき、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、整数変数χを用いて次のように表すことができる。
　ｒ(χ)＝χ8－χ4＋１,
　ｔ(χ)＝χ5－χ＋１.
　この場合、整数変数χの標数ｐによるｐ進数展開は次のように表される。
　ｐχ＋χ2＝－ｐ2　（mod ｒ(χ)）
　この場合には、有理点(χ2Ｑ,ｐχＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l12を用いて有理関数f'χ,Q(Ｓ)を次の式により演算することができる。
Figure JPOXMLDOC01-appb-M000053
　ここで、電子計算機10では、上述したようにミラーのアルゴリズムによる有理関数fχ⌒2,Q(Ｓ)及び有理関数fχ,Q(Ｓ)の演算を行うとともにχＱを演算して、演算結果を所定のレジスタに記憶している。
　そして、電子計算機10では、所定のレジスタに記憶されたχＱ＝Ｒとし、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、有理点ｐχＱを演算して、この演算結果を用いて前記の値l12を演算し、有理関数f'χ,Q(Ｓ)を演算し、ペアリングｅ(Ｑ,Ｓ)を
Figure JPOXMLDOC01-appb-M000054
 として演算することができる。
　また、組み込み次数ｋ＝18の場合には、曲線の式がｙ2＝ｘ3＋ｂ,ｂ∈Ｆpで与えられ、Ｆp 18を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
　　Ｇ1＝Ｅ[r]∩Ker(φp－[１]),
　　Ｇ2＝Ｅ[r]∩Ker(φp－[ｐ])
により、
　　ｅ：Ｇ2×Ｇ1→Ｆ* p 18/(Ｆ* p 18)r
である非退化な双線形写像としてペアリングｅを定義している。
　この場合、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、整数変数χを用いて次のように表せる。
　ｒ(χ)＝(χ6＋３７χ3＋３４３)／３４３,
　ｔ(χ)＝(χ4＋１６χ＋７)／７.
　この場合、整数変数χの標数ｐによるｐ進数展開は次のように表される。
　χ＝－３ｐ＋ｐ4　（mod ｒ(χ)）.
　そして、有理点(３ｐＱ,χＱ)を通る直線の有理点Ｓ(ｘs,ｙs)の値l13、電子計算機10では、有理関数f'χ,Q(Ｓ)を次の式により演算している。
Figure JPOXMLDOC01-appb-M000055
　すなわち、ペアリング演算プログラムによって、電子計算機10では、上述したようにミラーのアルゴリズムによる有理関数fχ,Q(Ｓ)の演算を行い、有理関数fχ,Q(Ｓ)とともにχＱを演算して、演算結果を所定のレジスタに記憶している。
　次いで、電子計算機10では、有理関数fχ,Q(Ｓ)とχＱの演算結果を用いて前記の値l13を演算し、有理関数f'χ,Q(Ｓ)を演算して、ペアリングｅ(Ｑ,Ｓ)を
Figure JPOXMLDOC01-appb-M000056
 として演算することができる。
　以上のように、Ｘａｔｅペアリングによってペアリング演算を行うことにより、ペアリング演算を高速化でき、ペアリング演算を用いたグループ署名を実用化させることができる。
　本発明によれば、高速なペアリング演算装置を提供でき、実用性のあるディジタルグループ署名のサービスを提供できる。

Claims (8)

  1. 　曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆp kを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
    　　Ｇ1＝Ｅ[r]∩Ker(φp－[１]),
    　　Ｇ2＝Ｅ[r]∩Ker(φp－[ｐ])
    により、
    　　ｅ：Ｇ2×Ｇ1→Ｆ* p k/(Ｆ* p k)r
    である非退化な双線形写像としてペアリングｅを定義し、
    　Ｓ∈Ｇ1、Ｑ∈Ｇ2としてペアリングｅ(Ｑ,Ｓ)を演算して演算結果を出力するペアリング演算装置であって、
    　フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
    Figure JPOXMLDOC01-appb-M000001
     として演算する代わりに、
    　位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、
    　有理関数ｆχ,Q(Ｓ)を演算する演算手段と、
    　所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算する演算手段と、
    　これらの演算手段の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算する演算手段と、
    　前記有理関数f'χ,Q(Ｓ)を用いて
    Figure JPOXMLDOC01-appb-M000002
     としてペアリング演算を行う演算手段と
    によりペアリング演算を行うペアリング演算装置。
  2. 　前記有理関数ｆχ,Q(Ｓ)を演算する演算手段では、χＱを演算して演算結果を所定のレジスタに記憶し、
    　前記χＱの演算結果を用いて前記所定の有理点を演算する演算手段を有する請求項１に記載のペアリング演算装置。
  3. 　前記埋込み次数ｋ＝12の場合に、
    　位数ｒと、フロベニウス自己準同型写像φpのトレースｔを、前記整数変数χを用いて
    　ｒ(χ)＝３６χ4－３６χ3＋１８χ2－６χ＋１,
    　ｔ(χ)＝６χ2＋１
    とし、χＱ＝Ｒとして、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、有理点ｐ10χＱ、χＱ＋ｐ10χＱ、ｐχＱ＋ｐ3χＱをそれぞれ演算し、
    　有理点(χＱ,ｐ10χＱ)を通る直線における前記有理点Ｓ(ｘs,ｙs)の値l1と、有理点(χＱ＋ｐ10χＱ,ｐχＱ＋ｐ3χＱ)を通る直線における前記有理点Ｓ(ｘs,ｙs)の値l2をそれぞれ演算し、
    　有理点(ｐχＱ,ｐ3χＱ)を通る直線における前記有理点Ｓ(ｘs,ｙs)の値l3を用いて
    Figure JPOXMLDOC01-appb-M000003
     として前記有理関数f'χ,Q(Ｓ)を演算する請求項２に記載のペアリング演算装置。
  4. 　前記有理関数fχ,Q(Ｓ)のフロベニウス自己準同型写像φpがφp(fχ,Q(Ｓ))＝fχ,Q(Ｓ)pであることを用いて
    Figure JPOXMLDOC01-appb-M000004
     を演算するとともに、
    　Ｑ1,Ｑ2∈Ｇ2である有理点(Ｑ1,Ｑ2)を通る直線における前記有理点Ｓ(ｘs,ｙs)の値lのフロベニウス自己準同型写像φpが有理点(pＱ1,pＱ2)を通る直線における前記有理点Ｓ(ｘs,ｙs)の値であることを用いて
    Figure JPOXMLDOC01-appb-M000005
     となる
    を演算して前記有理関数f'χ,Q(Ｓ)を演算する請求項３に記載のペアリング演算装置。
  5. 　曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆp kを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
    　　Ｇ1＝Ｅ[r]∩Ker(φp－[１]),
    　　Ｇ2＝Ｅ[r]∩Ker(φp－[ｐ])
    により、
    　　ｅ：Ｇ2×Ｇ1→Ｆ* p k/(Ｆ* p k)r
    である非退化な双線形写像としてペアリングｅを定義し、
    　Ｓ∈Ｇ1、Ｑ∈Ｇ2としてＣＰＵを備えた電子計算機でペアリングｅ(Ｑ,Ｓ)を演算するペアリング演算方法であって、
    　フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
    Figure JPOXMLDOC01-appb-M000007
     として演算する代わりに、
    　位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、
    　前記電子計算機のＣＰＵを演算手段として機能させて、有理関数ｆχ,Q(Ｓ)を演算するステップと、
    　前記電子計算機のＣＰＵを演算手段として機能させて、所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算するステップと、
    　前記電子計算機のＣＰＵを演算手段として機能させて、前記の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算するステップと、
    　前記電子計算機のＣＰＵを演算手段として機能させて、前記有理関数f'χ,Q(Ｓ)を用いて
    Figure JPOXMLDOC01-appb-M000008
     として演算するステップと
    を有するペアリング演算方法。
  6. 　前記有理関数ｆχ,Q(Ｓ)を演算するステップの後、
    　前記電子計算機のＣＰＵを演算手段として機能させて、χＱを演算し、このχＱの演算結果を用いて前記所定の有理点を演算するステップを有する請求項５に記載のペアリング演算方法。
  7. 　曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆp kを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
    　　Ｇ1＝Ｅ[r]∩Ker(φp－[１]),
    　　Ｇ2＝Ｅ[r]∩Ker(φp－[ｐ])
    により、
    　　ｅ：Ｇ2×Ｇ1→Ｆ* p k/(Ｆ* p k)r
    である非退化な双線形写像としてペアリングｅを定義し、
    　Ｓ∈Ｇ1、Ｑ∈Ｇ2としてＣＰＵを備えた電子計算機にペアリングｅ(Ｑ,Ｓ)を演算させるペアリング演算プログラムであって、
    　フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
    Figure JPOXMLDOC01-appb-M000009
     として演算させる代わりに、
    　位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、
    　前記電子計算機を、
    　有理関数ｆχ,Q(Ｓ)を演算する演算手段と、
    　所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算する演算手段と、
    　前記の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算する演算手段と、
    　前記有理関数f'χ,Q(Ｓ)を用いて
    Figure JPOXMLDOC01-appb-M000010
     として演算する演算手段
    として機能させるペアリング演算プログラム。
  8. 　前記電子計算機を、
    　χＱを演算する演算手段と、
    　このχＱの演算結果を用いて前記所定の有理点を演算する演算手段
    として機能させる請求項７に記載のペアリング演算プログラム。
PCT/JP2009/065099 2008-08-29 2009-08-28 ペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラム Ceased WO2010024401A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
EP09810049A EP2360659A4 (en) 2008-08-29 2009-08-28 PAIRING CALCULATION DEVICE, PAIRING CALCULATION METHOD AND PAIRING CALCULATION PROGRAM
JP2010526795A JP5360836B2 (ja) 2008-08-29 2009-08-28 ペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラム
CN200980142428.7A CN102308326B (zh) 2008-08-29 2009-08-28 配对运算装置、配对运算方法
US13/060,520 US8625777B2 (en) 2008-08-29 2009-08-28 Pairing computation device, pairing computation method, and pairing computation program

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2008222556 2008-08-29
JP2008-222556 2008-08-29

Publications (1)

Publication Number Publication Date
WO2010024401A1 true WO2010024401A1 (ja) 2010-03-04

Family

ID=41721564

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2009/065099 Ceased WO2010024401A1 (ja) 2008-08-29 2009-08-28 ペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラム

Country Status (5)

Country Link
US (1) US8625777B2 (ja)
EP (1) EP2360659A4 (ja)
JP (1) JP5360836B2 (ja)
CN (1) CN102308326B (ja)
WO (1) WO2010024401A1 (ja)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2012046805A1 (ja) * 2010-10-08 2012-04-12 国立大学法人岡山大学 有理点情報圧縮装置、有理点情報圧縮方法及び有理点情報圧縮プログラム
JP2013527712A (ja) * 2010-05-19 2013-06-27 コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ 属性ベースのデジタル署名システム
JP2014164176A (ja) * 2013-02-26 2014-09-08 Nippon Telegr & Teleph Corp <Ntt> ペアリング演算装置、ペアリング演算方法、およびプログラム
CZ308647B6 (cs) * 2019-06-11 2021-01-27 REGSHARE s.r.o. Mísicí ventil a souprava pro ředění či mísení nebezpečných látek

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8477934B2 (en) * 2009-04-21 2013-07-02 National University Corporation Okayama University Pairing computation device, pairing computation method and recording medium storing pairing computation program
CN102984129A (zh) * 2012-11-02 2013-03-20 王攀 基于三网融合的用户行为可控可管的方法
CN104579661B (zh) * 2013-10-21 2018-05-01 航天信息股份有限公司 基于身份的电子签章的实现方法和装置
JP6610277B2 (ja) * 2016-01-15 2019-11-27 富士通株式会社 共有鍵生成プログラム、共有鍵生成方法および情報処理端末
CN108055134B (zh) * 2017-12-12 2020-08-25 武汉理工大学 椭圆曲线点数乘及配对运算的协同计算方法及系统

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005316267A (ja) 2004-04-30 2005-11-10 Hitachi Ltd 楕円曲線ペアリング演算装置

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020057796A1 (en) * 1998-12-24 2002-05-16 Lambert Robert J. Method for accelerating cryptographic operations on elliptic curves
CN101453332A (zh) * 2002-04-15 2009-06-10 株式会社Ntt都科摩 利用双线性映射的签名方案
US7499544B2 (en) * 2003-11-03 2009-03-03 Microsoft Corporation Use of isogenies for design of cryptosystems
CN101031944A (zh) * 2004-09-30 2007-09-05 索尼株式会社 加密计算方法、加密系统和计算机程序
JP4630117B2 (ja) * 2005-04-25 2011-02-09 日本電信電話株式会社 マルチペアリング演算方法、ペアリング比較方法、それらを用いた装置、およびプログラム
DE102005041102A1 (de) * 2005-08-30 2007-03-15 Siemens Ag Verfahren zur Skalarmultiplikation von Punkten auf einer elliptischen Kurve
KR101405321B1 (ko) * 2007-03-16 2014-06-27 재단법인서울대학교산학협력재단 키 연산 방법 및 이를 이용한 공유 키 생성 방법
KR101273465B1 (ko) * 2007-03-16 2013-06-14 재단법인서울대학교산학협력재단 집합 검증 장치 및 그 방법
CN101809638A (zh) * 2007-08-09 2010-08-18 国立大学法人冈山大学 运算方法和运算装置
CN101911582B (zh) * 2008-01-18 2012-09-05 三菱电机株式会社 密码参数设定装置、密钥生成装置、密码系统、密码参数设定方法和密钥生成方法

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005316267A (ja) 2004-04-30 2005-11-10 Hitachi Ltd 楕円曲線ペアリング演算装置

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
EZEKIEL JUSTIN KACHISA ET AL.: "Constructing Brezing-Weng pairing friendly elliptic curves using elements in the cyclotomic field", CRYPTOLOGY EPRINT ARCHIVE, 2007, pages 1 - 12, XP019103364 *
PAULO S. L. M. BARRETO ET AL.: "Pairing-Friendly Elliptic Curves of Prime Order", PROCEEDINGS OF SAC, vol. 2005, 2005, pages 1 - 13, XP019029550 *
SAKAMI ET AL.: "Hamming Omomi no Chiisai Seisu Hensu o Parameter Settei ni Mochiita Twisted Ate Pairing no Kairyo", 2008 NEN SYMPOSIUM ON CRYPTOGRAPHY AND INFORMATION SECURITY, - January 2008 (2008-01-01), pages 1 - 6, XP008142593 *
See also references of EP2360659A4

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2013527712A (ja) * 2010-05-19 2013-06-27 コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ 属性ベースのデジタル署名システム
WO2012046805A1 (ja) * 2010-10-08 2012-04-12 国立大学法人岡山大学 有理点情報圧縮装置、有理点情報圧縮方法及び有理点情報圧縮プログラム
JP5769263B2 (ja) * 2010-10-08 2015-08-26 国立大学法人 岡山大学 有理点情報圧縮装置、有理点情報圧縮方法及び有理点情報圧縮プログラム
JP2014164176A (ja) * 2013-02-26 2014-09-08 Nippon Telegr & Teleph Corp <Ntt> ペアリング演算装置、ペアリング演算方法、およびプログラム
CZ308647B6 (cs) * 2019-06-11 2021-01-27 REGSHARE s.r.o. Mísicí ventil a souprava pro ředění či mísení nebezpečných látek

Also Published As

Publication number Publication date
EP2360659A4 (en) 2013-03-13
US20110179471A1 (en) 2011-07-21
CN102308326B (zh) 2014-08-13
EP2360659A1 (en) 2011-08-24
CN102308326A (zh) 2012-01-04
JP5360836B2 (ja) 2013-12-04
JPWO2010024401A1 (ja) 2012-01-26
US8625777B2 (en) 2014-01-07

Similar Documents

Publication Publication Date Title
JP5360836B2 (ja) ペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラム
JP4189828B1 (ja) ペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラム
JP5549018B2 (ja) ペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムを記録した記録媒体
Devigne et al. Binary huff curves
Azarderakhsh et al. Hardware deployment of hybrid PQC: SIKE+ ECDH
JP5403630B2 (ja) スカラ倍算器及びスカラ倍算プログラム
US20030156714A1 (en) Elliptic curve scalar multiplication method and device, and storage medium
Dai et al. Don’t forget pairing-friendly curves with odd prime embedding degrees
US10425227B2 (en) Computer-readable recording medium, shared key generation method, and information processing terminal
Silde Comparative study of ECC libraries for embedded devices
Aung et al. Implementation of elliptic curve arithmetic operations for prime field and binary field using java BigInteger class
EP1703373A2 (en) Elliptic curve point octupling using single instruction multiple data processing
CN112436941A (zh) 支持标识密码算法的协处理器、方法、芯片及电子设备
Wang et al. Constructing pairing-friendly elliptic curves under embedding degree 1 for securing critical infrastructures
de Oliveira et al. An efficient software implementation of the hash-based signature scheme MSS and its variants
Zhang et al. An optimal bound for factoring unbalanced RSA moduli by solving Generalized Implicit Factorization Problem: R. Zhang et al.
Realpe-Muñoz et al. High-performance elliptic curve cryptoprocessors over GF (2 m) on Koblitz curves
JP5168649B2 (ja) ペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラム
JPWO2012015047A1 (ja) 埋め込み次数１かつ合成数位数の楕円曲線上の有理点のスカラー倍算およびペアリング演算
EP2222016A1 (en) Method and device for hashing onto points of an elliptic curve
KR20260029361A (ko) 쌍선형 페어링
EP1705560A2 (en) Elliptic curve point octupling for weighted projective coordinates
JP5769263B2 (ja) 有理点情報圧縮装置、有理点情報圧縮方法及び有理点情報圧縮プログラム
CN104731552A (zh) 使用混合仿射雅可比坐标进行ecc点加的硬件架构和方法
Shi et al. A novel fast η-adapt slide window elliptic curve cryptography algorithm

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 200980142428.7

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 09810049

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2010526795

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 13060520

Country of ref document: US

Ref document number: 2009810049

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: DE