FINAL EXPONENTIATION COMPUTATION DEVICE, PAIRING COMPUTATION DEVICE, CRYPTOGRAPHIC PROCESSING DEVICE, FINAL EXPONENTIATION COMPUTATION METHOD, AND COMPUTER READABLE MEDIUM

Abstract

A decomposition unit (211) decomposes an exponent portion of a final exponentiation computation portion of pairing computation in an elliptic curve into an easy part and a hard part, the elliptic curve being expressed by a polynomial r(x), a polynomial p(x), a polynomial t(x), an embedding degree k, and an integer u. A factorization unit (212) factorizes the hard part with using a homogeneous cyclotomic polynomial Ψ.sub.n(x, p). An exponentiation computation unit (22) performs computation of final exponentiation with using the easy part and the factorized hard part.

Claims

1. A final exponentiation computation device comprising processing circuitry to decompose an exponent portion of a final exponentiation computation portion of pairing computation in an elliptic curve into an easy part and a hard part with using a polynomial Φ.sub.k(p(x)), the elliptic curve being expressed by a polynomial r(x), a polynomial p(x), a polynomial t(x), and an embedding degree k, and to factorize the hard part obtained by decomposition, with using a homogeneous cyclotomic polynomial Ψ.sub.n(x, p) indicated by Formula 1, $\begin{array}{cc}{\Psi }_k\left(x,p\right)=\{\begin{array}{cc}{p\left(x\right)}^d{\Phi }_k\left(x/p\left(x\right)\right)& \mathrm{when}k>1\\ 1& \mathrm{when}k=1\end{array}& \left[\mathrm{Formula}1\right]\end{array}$ where
d=degΦ.sub.k(x)

2. The final exponentiation computation device according to claim 1, wherein when the elliptic curve is a family of elliptic curves with the embedding degree k that takes a form of 2.sup.i about an integer i, the processing circuitry factorizes the hard part Φ.sub.k(p(x))/r(x) as indicated by Formula 2, $\begin{array}{cc}\frac{{\Phi }_k\left(p\left(x\right)\right)}{r\left(x\right)}=\left\{h_1\left(x\right)\left(\underset{i|\left(k/2\right)}{.Math.}{\Psi }_i\left(T\left(x\right),p\left(x\right)\right)\right)+h_2\left(x\right)\right\}& \left[\mathrm{Formula}2\right]\end{array}$ where
r(x)=Φ.sub.k(T(x))/h.sub.2(x),
p(x)=h.sub.1(x)r(x)+T(x),
t(x)=T(x)+1

3. The final exponentiation computation device according to claim 1, wherein when the elliptic curve is a family of elliptic curves with the embedding degree k that takes a form of 3.sup.i about an integer i, the processing circuitry factorizes the hard part Φ.sub.k(p(x))/r(x) as indicated by Formula 3, $\begin{array}{cc}\frac{{\Phi }_k\left(p\left(x\right)\right)}{r\left(x\right)}=\left\{h_1\left(x\right)\left(\underset{i|\left(k_1/3\right)}{.Math.}{\Psi }_i\left(T\left(x\right),p\left(x\right)\right)\right)\left({T\left(x\right)}^{k/3}+{p\left(x\right)}^{k/3}+1\right)+h_2\left(x\right)\right\}& \left[\mathrm{Formula}3\right]\end{array}$ where
r(x)=Φ.sub.k(T(x))/h.sub.2(x),
p(x)=h.sub.1(x)r(x)+T(x),
t(x)=T(x)+1

4. The final exponentiation computation device according to claim 1, wherein when the elliptic curve is a family of elliptic curves with the embedding degree k is 2.sup.i3.sup.j about integers i and j, the processing circuitry factorizes the hard part Φ.sub.k(p(x))/r(x) as indicated by Formula 4, $\begin{array}{cc}\frac{{\Phi }_k\left(p\left(x\right)\right)}{r\left(x\right)}=\left\{h_1\left(x\right)\left(\underset{i|\left(k/6\right)}{.Math.}{\Psi }_i\left(T\left(x\right),p\left(x\right)\right)\right)\left({T\left(x\right)}^{k/6}+{p\left(x\right)}^{k/6}-1\right)+h_2\left(x\right)\right\}& \left[\mathrm{Formula}4\right]\end{array}$ where
r(x)=φ.sub.k(T(x))/h.sub.2(x),
p(x)=h.sub.1(x)r(x)+T(x),
t(x)=T(x)+1

5. The final exponentiation computation device according to claim 1, wherein the polynomial t(x) is first-order linear.

6. The final exponentiation computation device according to claim 5, wherein the polynomial t(x)=x+1.

7. The final exponentiation computation device according to claim 1, wherein the polynomial t(x)=x+1, the polynomial r(x)=⅓Φ.sub.9(x)=⅓(x.sup.6+x.sup.3+1), and the polynomial p(x)=(x−1).sup.2r(x)+x.

8. The final exponentiation computation device according to claim 1, wherein the polynomial t(x)=x+1, the polynomial r(x)=Φ.sub.12(x)=x.sup.4−x.sup.2+1, and the polynomial p(x)=⅓(x−1).sup.2r(x)+x.

9. The final exponentiation computation device according to claim 1, wherein the polynomial t(x)=x+1, the polynomial r(x)=Φ.sub.12(x)=x.sup.4−x.sup.2+1, and the polynomial p(x)=¼(x−1).sup.2(x.sup.2+1)r(x)+x.

10. The final exponentiation computation device according to claim 1, wherein the polynomial t(x)=x+1, the polynomial r(x)=Φ.sub.24(x)=x.sup.8−x.sup.4+1, and the polynomial p(x)=⅓(x−1).sup.2r(x)+x.

11. The final exponentiation computation device according to claim 1, wherein the polynomial t(x)=x+1, the polynomial r(x)=⅓Φ.sub.27(x)=⅓(x.sup.18+x.sup.9+1), and the polynomial p(x)=(x−1).sup.2r(x)+x.

12. The final exponentiation computation device according to claim 1, wherein the polynomial t(x)=x+1, the polynomial r(x)=Φ.sub.48(x)=x.sup.16−x.sup.8+1, and the polynomial p(x)=⅓(x−1).sup.2r(x)+x.

13. The final exponentiation computation device according to claim 1, wherein the easy part is a portion expressed by exponentiation of p(x), and the hard part is a portion expressed by exponentiation of x.

14. A pairing computation device comprising the final exponentiation computation device according to claim 1, wherein the processing circuitry computes a Miller function of the paring computation.

15. The pairing computation device according to claim 14, wherein the processing circuitry further performs exponentiation computation of the easy part and exponential computation of the hard part for a function value which is a result of computation of the Miller function, thereby computing a result of the pairing computation.

16. A cryptographic processing device which performs a cryptographic process with using a result of the pairing computation computed by the pairing computation device according to claim 14.

17. A final exponentiation computation method comprising decomposing an exponent portion of a final exponentiation computation portion of pairing computation in an elliptic curve into an easy part and a hard part with using a polynomial Φ.sub.k(p(x)), the elliptic curve being expressed by a polynomial r(x), a polynomial p(x), a polynomial t(x), and an embedding degree k, and factorizing the hard part with using a homogeneous cyclotomic polynomial Ψ.sub.n(x,p) indicated by Formula 5, $\begin{array}{cc}{\Psi }_k\left(x,p\right)=\{\begin{array}{cc}{p\left(x\right)}^d{\Phi }_k\left(x/p\left(x\right)\right)& \mathrm{when}k>1\\ 1& \mathrm{when}k=1\end{array}& \left[\mathrm{Formula}5\right]\end{array}$ where
d=deg Φ.sub.k(x)

18. A non-transitory computer-readable recording medium recorded with a final exponentiation computation program which causes a computer to function as a final exponentiation computation device that performs: a decomposition process of decomposing an exponent portion of a final exponentiation computation portion of pairing computation in an elliptic curve into an easy part and a hard part with using a polynomial Φ.sub.k(p(x)), the elliptic curve being expressed by a polynomial r(x), a polynomial p(x), a polynomial t(x), and an embedding degree k; and a factorization process of factorizing the hard part obtained by the decomposition process, with using a homogeneous cyclotomic polynomial Ψ.sub.n(x, p) indicated by Formula 6, $\begin{array}{cc}{\Psi }_k\left(x,p\right)=\{\begin{array}{cc}{p\left(x\right)}^d{\Phi }_k\left(x/p\left(x\right)\right)& \mathrm{when}k>1\\ 1& \mathrm{when}k=1\end{array}& \left[\mathrm{Formula}6\right]\end{array}$ where
d=degΦ.sub.k(x)

Description

BRIEF DESCRIPTION OF DRAWINGS

[0022] FIG. 1 is a configuration diagram of a final exponentiation computation device 10 according to Embodiment 1.

[0023] FIG. 2 is an explanatory diagram of a process of decomposing an exponent (p(x).sup.k−1)/r(x) according to Embodiment 1 into an easy part and a hard part.

[0024] FIG. 3 is a flowchart illustrating overall operations of the final exponentiation computation device 10 according to Embodiment 1.

[0025] FIG. 4 is an explanatory drawing of factorization which uses a homogeneous cyclotomic polynomial according to Embodiment 1.

[0026] FIG. 5 is a flowchart of an exponentiation simplification process according to Embodiment 1.

[0027] FIG. 6 is a flowchart of an exponentiation computation process according to Embodiment 1.

[0028] FIG. 7 is a flowchart of a computation process of a value M.sub.2 in a case where an embedding degree according to Embodiment 1 is k=2.sup.i.

[0029] FIG. 8 is a flowchart of a computation process of the value M.sub.2 in a case where the embedding degree according to Embodiment 1 is k=3.sup.i.

[0030] FIG. 9 is a flowchart of a computation process of the value M.sub.2 in a case where the embedding degree according to Embodiment 1 is k=2.sup.i3.sup.j.

[0031] FIG. 10 is a configuration diagram of a final exponentiation computation device 10 according to Modification 1.

[0032] FIG. 11 is a configuration diagram of a pairing computation device 30 according to Modification 3.

[0033] FIG. 12 is a configuration diagram of a cryptographic processing device 40 according to Embodiment 2.

[0034] FIG. 13 is a flowchart illustrating operations of the cryptographic processing device 40 according to Embodiment 2.

DESCRIPTION OF EMBODIMENTS

Embodiment 1

[0035] ***Description of Notation***

[0036] In the specification and drawings, sometimes exponentiation is expressed using “{circumflex over ( )}”. In a specific example, a{circumflex over ( )}b expresses a.sup.b.

[0037] ***Description of Configuration***

[0038] A configuration of a final exponentiation computation device 10 according to Embodiment 1 will be described with referring to FIG. 1.

[0039] The final exponentiation computation device 10 is a computer.

[0040] The final exponentiation computation device 10 is provided with hardware devices which are a processor 11, a memory 12, a storage 13, and a communication interface 14. The processor 11 is connected to the other hardware devices via a signal line and controls the other hardware devices.

[0041] The processor 11 is an Integrated Circuit (IC) to perform processing. Specific examples of the processor 11 are a Central Processing Unit (CPU), a Digital Signal Processor (DSP), and a Graphics Processing Unit (GPU).

[0042] The memory 12 is a storage device to store data temporarily. Specific examples of the memory 12 are a Static Random-Access Memory (SRAM) and a Dynamic Random-Access Memory (DRAM).

[0043] The storage 13 is a storage device to keep data. A specific example of the storage 13 is a Hard Disk Drive (HDD). The storage 13 may be a portable recording medium such as a Secure Digital (SD, registered trademark) memory card, a CompactFlash (registered trademark, CF), a NAND flash, a flexible disk, an optical disk, a compact disk, a Blu-ray (registered trademark) Disc, and a Digital Versatile Disk (DVD).

[0044] The e communication interface 14 is an interface to communicate with an external device. Specific examples of the communication interface 14 are an Ethernet (registered trademark) port, a Universal Serial Bus (USB) port, and a High-Definition Multimedia Interface (HDMI) port.

[0045] The final exponentiation computation device 10 is provided with an exponentiation simplification unit 21 and an exponentiation computation unit 22 as feature constituent elements. The exponentiation simplification unit 21 is provided with a decomposition unit 211 and a factorization unit 212. Features of the feature constituent elements of the final exponentiation computation device 10 are implemented by software.

[0046] A program that implements the features of the feature constituent elements of the final exponentiation computation device 10 is stored in the storage 13. This program is read into the memory 12 by the processor 11 and run by the processor 11. The features of the feature constituent elements of the final exponentiation computation device 10 are thus implemented.

[0047] FIG. 1 illustrates a configuration having one processor 11. However, there may be a plurality of processors 11. The plurality of processors 11 may cooperate with each other to run the program that implements the individual features.

[0048] ***Description of Operations***

[0049] Operations of the final exponentiation computation device 10 according to Embodiment 1 will be described with referring to FIGS. 2 to 9.

[0050] An operation procedure of the final exponentiation computation device 10 according to Embodiment 1 corresponds to a final exponentiation computation method according to Embodiment 1. A program that implements the operations of the final exponentiation computation device 10 according to Embodiment 1 corresponds to a final exponentiation computation program according to Embodiment 1.

[0051] Embodiment 1 uses a curve to be parameterized by a family of elliptic curves defined in a literature “[FST10] D. Freeman, M. Scott and E. Teske, “A Taxonomy of Pairing-Friendly Elliptic Curves”, J. Cryptol. (2010) 23:224-280.”

[0052] The curve to be parameterized by the family of elliptic curves defined in the above literature is an elliptic curve determined by a polynomial r(x), a polynomial p(x), a polynomial t(x), an embedding degree k, and an integer u to be assigned to a variable x. This elliptic curve E is an elliptic curve defined over a finite field F.sub.p consisting of elements which are p=p(x) primes. Note that r=r(x) is a maximum prime that divides an order of a subgroup E(F.sub.p) of the elliptic curve E. Also, t=t(x) is a trace of the elliptic curve E. In Embodiment 1, the polynomial t(x) being the trace of the elliptic curve is first-order linear. In a specific example, in Embodiment 1, the polynomial t(x)=x+1 which is the trace of the elliptic curve E.

[0053] Pairing computation on the elliptic curve E is performed by taking as input two certain points P and Q on the elliptic curve E, computing f obtained by evaluation of a rational function called the Miller function with P, and after that raising f to a power of (p(x).sup.k−1)/r(x). First-half f computation is called Miller loop computation. Second-half exponentiation computation is called computation of final exponentiation.

[0054] In the computation of final exponentiation, as illustrated in FIG. 2, an exponent (p(x).sup.k−1)/r(x) is decomposed into an easy part and a hard part with using a polynomial Φ.sub.k(p(x)). Exponentiation computation of the easy part can be efficiently performed using a fast power of p(x).sup.i. On the other hand, in exponentiation computation of the hard part, the power of x (power of u) must be executed a plurality of times, and thus a computation complexity is large. Therefore, an efficient computation method of the hard part is necessary to achieve efficient final exponentiation.

[0055] As indicated by Formula 13, the polynomial p(x), the polynomial r(x), and the polynomial t(x) which are parameters of the curve to be parameterized by the family of elliptic curves can be expressed with using a certain polynomial T(x), a certain polynomial h.sub.1(x), and a certain polynomial h.sub.2(x).

[00004]$$\begin{gathered} \begin{array}{cc}\mathrm{for}T\left(x\right),h_1\left(x\right),h_2\left(x\right)\in Q\left[x\right] \\ r\left(x\right)=\frac{{\Phi }_k\left(T\left(x\right)\right)}{h_2\left(x\right)}, \\ p\left(x\right)=h_1\left(x\right)r\left(x\right)+T\left(x\right), \\ t\left(x\right)=T\left(x\right)+1& \left[\mathrm{Formula}13\right]\end{array} \end{gathered}$$

[0056] Overall operations of the final exponentiation computation device 10 according to Embodiment 1 will be described with referring to FIG. 3.

[0057] (Step S11: Exponentiation Simplification Process)

[0058] The decomposition unit 211 of the exponentiation simplification unit 21 decomposes (p(x).sup.k−1)/r(x), being an exponent portion in the final exponentiation computation portion, into an easy part and a hard part. The easy part is a portion expressed by exponentiation of p(x). The hard part is a portion expressed by p(x) and exponentiation of x (exponentiation of u).

[0059] The factorization unit 212 of the exponentiation simplification unit 21 factorizes the hard part into a format of Formula 14, Formula 15, or Formula 16 with using a homogeneous cyclotomic polynomial as illustrated in FIG. 4. In this case, the factorization unit 212 computes a positive, minimum and non-zero integer a that renders every coefficient of ah.sub.1(x) and ah.sub.2(x) an integer. Since a fraction may appear in at least one coefficient of the polynomial h.sub.1(x) and polynomial h.sub.2(x), multiplication by the integer a is performed here to cancel a denominator of the coefficient from the polynomial h.sub.1(x) and the polynomial h.sub.2(x).

[00005]$\begin{array}{cc}\frac{{\Phi }_k\left(p\left(x\right)\right)}{r\left(x\right)}=\left\{h_1\left(x\right)\left(\underset{i|\left(k/2\right)}{.Math.}{\Psi }_i\left(T\left(x\right),p\left(x\right)\right)\right)+h_2\left(x\right)\right\}& \left[\mathrm{Formula}14\right]\end{array}$$\begin{array}{cc}\frac{{\Phi }_k\left(p\left(x\right)\right)}{r\left(x\right)}=\left\{h_1\left(x\right)\left(\underset{i|\left(k/3\right)}{.Math.}{\Psi }_i\left(T\left(x\right),p\left(x\right)\right)\right)\left({T\left(x\right)}^{k/3}+{p\left(x\right)}^{k/3}+1\right)+h_2\left(x\right)\right\}& \left[\mathrm{Formula}15\right]\end{array}$$\begin{array}{cc}\frac{{\Phi }_k\left(p\left(x\right)\right)}{r\left(x\right)}=\left\{h_1\left(x\right)\left(\underset{i|\left(k/6\right)}{.Math.}{\Psi }_i\left(T\left(x\right),p\left(x\right)\right)\right)\left({T\left(x\right)}^{k/6}+{p\left(x\right)}^{k/6}-1\right)+h_2\left(x\right)\right\}& \left[\mathrm{Formula}16\right]\end{array}$

[0060] (Step S12: Exponentiation Computation Process)

[0061] The exponentiation computation unit 22 performs exponentiation computation of the easy part obtained in step S11 and exponential computation of the hard part factorized in step S11, for the rational function f computed by the Miller loop. Thus, the final exponentiation indicated by Formula 17 is performed.

[00006]$\begin{array}{cc}{f}^{a.Math.\frac{{p\left(x\right)}^k-1}{r\left(x\right)}}& \left[\mathrm{Formula}17\right]\end{array}$

[0062] A result of raising pairing computation to the power of the integer a is computed because the polynomial h.sub.1(x) and the polynomial h.sub.2(x) are multiplied by the integer a.

[0063] The exponentiation simplification process according to Embodiment 1 will be described with referring to FIG. 5.

[0064] In step S21, the exponentiation simplification unit 21 acquires the embedding coefficient k of the elliptic curve E, and the polynomial r(x), the polynomial p(x), and the polynomial t(x) which are parameters about the elliptic curve E.

[0065] In step S22, the decomposition unit 211 computes a factor A.sub.1(x) of (p(x).sup.k−1)/r(x). The factor A.sub.1(x) is an entire portion of the easy part illustrated in FIG. 2. The decomposition unit 211 writes the factor A.sub.1(x) to the memory 12.

[0066] In step S23, the factorization unit 212 generates a second factor A.sub.2(x) of (p.sup.k−1)/r.

[0067] Specifically, when the embedding degree k acquired in step S21 takes a form of k=2.sup.i about the integer i, the factorization unit 212 generates the second factor A.sub.2(x) indicated by Formula 14. When the embedding degree k acquired in step S21 takes a form of k=3.sup.i about the integer i, the factorization unit 212 generates the second factor A.sub.2(x) indicated by Formula 15. When the embedding degree k acquired in step S21 takes a form of k=2.sup.i3.sup.j about integers i and j, the factorization unit 212 generates the second factor A.sub.2(x) indicated by Formula 16. The factorization unit 212 writes the second factor A.sub.2(x) to the memory 12.

[0068] The exponentiation computation process according to Embodiment 1 will be described with referring to FIG. 6.

[0069] In step S31, the exponentiation computation unit 22 reads the embedding degree k of the elliptic curve E, the integer u, the value f computed by the Miller loop, the integer a, and the first factor A.sub.1(x) and the second factor A.sub.2(x) which are generated by the exponentiation simplification process, from the memory 12. Notation that uses the variable x of a polynomial is employed in the description below. In practice, computation is performed by assigning the integer u to the variable x.

[0070] In step S32, the exponentiation computation unit 22 generates a value M.sub.1=f{circumflex over ( )}{A.sub.1(x)} by performing exponentiation where the value f is the base and the first factor A.sub.1(x) is the exponent. In short, the exponentiation computation unit 22 computes the value M.sub.1 by Formula 18.

M.sub.1=f.sup.A.sup.1.sup.(x)  [Formula 18]

[0071] In step S33, the exponentiation computation unit 22 generates a value M.sub.2=M.sub.1{circumflex over ( )}{A.sub.2(x)} by performing exponentiation where the value M.sub.1 is the base and the second factor A.sub.2(x) is the exponent. In short, the exponentiation computation unit 22 computes the value M.sub.2 by Formula 19.

M.sub.2=M.sub.1.sup.A.sup.2.sup.(x)  [Formula 19]

[0072] In step S34, the exponentiation computation unit 22 generates a value M.sub.3=M.sub.2{circumflex over ( )}a by performing exponentiation where the value M.sub.2 is the base and the integer a is the exponent. In short, the exponentiation computation unit 22 computes the value M.sub.3 by Formula 20.

M.sub.3=M.sub.2.sup.a  [Formula 20]

[0073] The value M.sub.3 is a result of pairing computation indicated by Formula 17.

[0074] A computation process of the value M.sub.2 in a case where the embedding degree is k=2.sup.i according to Embodiment 1 will be described with referring to FIG. 7.

[0075] As described above, when the embedding degree is k=2.sup.i, the second factor A.sub.2(x) indicated by Formula 14 is generated.

[0076] In step S41, the exponentiation computation unit 22 acquires the value M.sub.1 generated in step S32 of FIG. 6 and the embedding degree k.

[0077] In step S42, the exponentiation computation unit 22 computes a value B indicated by Formula 21 with using the value M.sub.1.

B=M.sub.1.sup.h.sup.1.sup.(x)  [Formula 21]

[0078] In step S43, the exponentiation computation unit 22 computes a value C indicated by Formula 22 with using the value M.sub.1.

C=M.sub.1.sup.h.sup.2.sup.(x)  [Formula 22]

[0079] In step S44, the exponentiation computation unit 22 assigns a value obtained by dividing the embedding degree k acquired in step S31 of FIG. 6 by 2 to a suffix i. The exponentiation computation unit 22 also assigns the value B computed in step S42 to a value D. Then, the exponentiation computation unit 22 repeats following processes (1) and (2) until the suffix i reaches 1. When the suffix i reaches 1, the exponentiation computation unit 22 ends the process of step S44.

(1) The exponentiation computation unit 22 updates the value D as indicated by Formula 23.

D=D.sup.Ψ.sup.i.sup.(T(x),p(x))  [Formula 23]

(2) The exponentiation computation unit 22 divides the suffix i by 2.

[0080] In step S45, the exponentiation computation unit 22 computes a value E indicated by Formula 24 with using the value C computed in step S43 and the value D computed in step S44.

E=C.Math.D  [Formula 24]

[0081] The value E indicated by Formula 24 is the value M.sub.2.

[0082] A computation process of the value M.sub.2 in a case where the embedding degree is k=3.sup.i according to Embodiment 1 will be described with referring to FIG. 8.

[0083] As described above, when the embedding degree is k=3′, the second factor A.sub.2(x) indicated by Formula 15 is generated.

[0084] In step S51, the exponentiation computation unit 22 acquires the value M.sub.1 generated in step S32 of FIG. 6 and the embedding degree k.

[0085] In step S52, the exponentiation computation unit 22 computes a value B indicated by Formula 25 with using the value M.sub.1.

B=M.sub.1.sup.h.sup.1.sup.(x)  [Formula 25]

[0086] In step S53, the exponentiation computation unit 22 computes a value C indicated by Formula 26 with using the value M.sub.1.

C=M.sub.1.sup.h.sup.2.sup.(x)  [Formula 26]

[0087] In step S54, the exponentiation computation unit 22 assigns a value obtained by dividing the embedding degree k acquired in step S31 of FIG. 6 by 3 to a suffix i. The exponentiation computation unit 22 also assigns the value B computed in step S52 to the value D. Then, the exponentiation computation unit 22 repeats following processes (1) and (2) until the suffix i reaches 1. When the suffix i reaches 1, the exponentiation computation unit 22 ends the process of step S54.

(1) The exponentiation computation unit 22 updates the value D as indicated by Formula 27.

D=D.sup.Ψ.sup.i.sup.(T(x),p(x))  [Formula 27]

(2) The exponentiation computation unit 22 divides the suffix i by 3.

[0088] In step S55, the exponentiation computation unit 22 computes Formula 28 and Formula 29 with using the value D computed in step S54. Then, the exponentiation computation unit 22 computes a value E indicated by Formula 30 with using Formula 28 and Formula 29.

D.sup.T(x).sup.k/3  [Formula 28]

D.sup.p(x).sup.k/3  [Formula 29]

E=D.sup.T(x).sup.k/3.Math.D.sup.p(x).sup.k/3.Math.D  [Formula 30]

[0089] In step S56, the exponentiation computation unit 22 computes a value F indicated by Formula 31 with using the value C computed in step S53 and the value E computed in step S55.

F=C.Math.E  [Formula 31]

[0090] The value F indicated by Formula 31 is the value M.sub.2.

[0091] A computation process of the value M.sub.2 in a case where the embedding degree is k=2.sup.i3.sup.j according to Embodiment 1 will be described with referring to FIG. 9.

[0092] As described above, when the embedding degree is k=2.sup.i3.sup.j, the second factor A.sub.2(x) indicated by Formula 16 is generated.

[0093] In step S61, the exponentiation computation unit 22 acquires the value M.sub.1 generated in step S32 of FIG. 6 and the embedding degree k.

[0094] In step S62, the exponentiation computation unit 22 computes a value B indicated by Formula 32 with using the value M.sub.1.

B=M.sub.1.sup.h.sup.1.sup.(x)  [Formula 32]

[0095] In step S63, the exponentiation computation unit 22 computes a value C indicated by Formula 33 with using the value M.sub.1.

C=M.sub.1.sup.h.sup.2.sup.(x)  [Formula 33]

[0096] In step S64, the exponentiation computation unit 22 assigns a value obtained by dividing the embedding degree k acquired in step S31 of FIG. 6 by 6 to a suffix i. The exponentiation computation unit 22 also assigns the value B computed in step S62 to the value D. Then, the exponentiation computation unit 22 repeats following processes (1) and (2) until the suffix i reaches 1. When the suffix i reaches 1, the exponentiation computation unit 22 ends the process of step S64.

(1) The exponentiation computation unit 22 updates the value D as indicated by Formula 34.

D=D.sup.Ψ.sup.i.sup.(T(x),p(x))  [Formula 34]

(2) The exponentiation computation unit 22 divides the suffix i by 6.

[0097] In step S65, the exponentiation computation unit 22 computes Formula 35, Formula 36, and Formula 37 with using the value D computed in step S64. Then, the exponentiation computation unit 22 computes a value E indicated by Formula 38 with using Formula 35, Formula 36, and Formula 37.

D.sup.T(x).sup.k/6  [Formula 35]

D.sup.p(x).sup.k/6  [Formula 36]

D.sup.−1  [Formula 37]

E=D.sup.T(x).sup.k/6.Math.D.sup.p(x).sup.k/6.Math.D.sup.−1  [Formula 38]

[0098] In step S66, the exponentiation computation unit 22 computes a value F indicated by Formula 39 with using the value C computed in step S63 and the value E computed in step S65.

F=C.Math.E  [Formula 39]

[0099] The value F indicated by Formula 39 is the value M.sub.2.

[0100] Examples of specific curves will be described.

Example 1: BLS-9

[0101] An example in which the curve is a BLS-9 curve will be described.

[0102] In this case, the polynomial t(x)=x+1, the polynomial r(x)=⅓Φ.sub.9(x)=⅓(x.sup.6+x.sup.3+1), and the polynomial p(x)=(x−1).sup.2r(x)+x. Accordingly, the polynomial T(x)=x, the polynomial h.sub.1(x)=(x−1).sup.2, and the polynomial h.sub.2(x)=3.

[0103] Hence, the exponent portion is decomposed as in Formula 40.

[00007]$\begin{array}{cc}\frac{{p\left(x\right)}^9-1}{r\left(x\right)}=\left({p\left(x\right)}^3-1\right).Math.\left({\left(x-1\right)}^2\left(x^2+p\left(x\right)x+{p\left(x\right)}^2\right)\left(x^3+{p\left(x\right)}^3+1\right)+3\right)& \left[\mathrm{Formula}40\right]\end{array}$

Example 2: BLS-12

[0104] An example in which the curve is a BLS-12 curve will be described.

[0105] In this case, the polynomial t(x)=x+1, the polynomial r(x)=Φ.sub.12(x)=x.sup.4−x.sup.2+1, and the polynomial p(x)=⅓(x−1).sup.2r(x)+x. Accordingly, the polynomial T(x)=x, the polynomial h.sub.1(x)=⅓(x−1).sup.2, and the polynomial h.sub.2(x)=1. Hence, the exponent portion is decomposed as in Formula 41.

[00008]$\begin{array}{cc}3.Math.\frac{{p\left(x\right)}^{12}-1}{r\left(x\right)}=\left({p\left(x\right)}^6-1\right)\left({p\left(x\right)}^2+1\right).Math.\left({\left(x-1\right)}^2\left(x+p\left(x\right)\right)\left(x^2+{p\left(x\right)}^2-1\right)+3\right)& \left[\mathrm{Formula}41\right]\end{array}$

Example 3: k=12

[0106] An example of a curve with an embedding degree k=12 (not a BLS curve) will be described.

[0107] In this case, the polynomial t(x)=x+1, the polynomial r(x)=Φ.sub.12(x)=x.sup.4−x.sup.2+1, and the polynomial p(x)=¼(x−1).sup.2(x.sup.2+1)r(x)+x. Accordingly, the polynomial T(x)=x, the polynomial h.sub.1(x)=¼(x−1).sup.2(x.sup.2+1), and the polynomial h.sub.2(x)=1. Hence, the exponent portion is decomposed as in Formula 42.

[00009]$\begin{array}{cc}4.Math.\frac{{p\left(x\right)}^{12}-1}{r\left(x\right)}=\left({p\left(x\right)}^6-1\right)\left({p\left(x\right)}^2+1\right).Math.\left({\left(x-1\right)}^2\left(x^2+1\right)\left(x+p\left(x\right)\right)\left(x^2+{p\left(x\right)}^2-1\right)+4\right)& \left[\mathrm{Formula}42\right]\end{array}$

Example 4: BLS-24

[0108] An example in which the curve is a BLS-24 curve will be described.

[0109] In this case, the polynomial t(x)=x+1, the polynomial r(x)=124(x)=x.sup.8−x.sup.4+1, and the polynomial p(x)=⅓(x−1).sup.2r(x)+x. Accordingly, the polynomial T(x)=x, the polynomial h.sub.1(x)=⅓(x−1).sup.2, and the polynomial h.sub.2(x)=1. Hence, the exponent portion is decomposed as in Formula 43.

[00010]$\begin{array}{cc}3.Math.\frac{{p\left(x\right)}^{24}-1}{r\left(x\right)}=\left({p\left(x\right)}^{12}-1\right)\left({p\left(x\right)}^4+1\right).Math.\left({\left(x-1\right)}^2\left(x+p\left(x\right)\right)\left(x^2+{p\left(x\right)}^2\right)\left(x^4+{p\left(x\right)}^4-1\right)+3\right)& \left[\mathrm{Formula}43\right]\end{array}$

Example 5: BLS-27

[0110] An example in which the curve is a BLS-27 curve will be described.

[0111] In this case, the polynomial t(x)=x+1, the polynomial r(x)=⅓Φ.sub.27(x)=⅓(x.sup.18+x.sup.9+1), and the polynomial p(x)=(x−1).sup.2r(x)+x. Accordingly, the polynomial T(x)=x, the polynomial h.sub.1(x)=(x−1).sup.2, and the polynomial h.sub.2(x)=3. Hence, the exponent portion is decomposed as in Formula 44.

[00011]$\begin{array}{cc}\frac{{p\left(x\right)}^{27}-1}{r\left(x\right)}=\left({p\left(x\right)}^9-1\right).Math.\left({\left(x-1\right)}^2\left(x^2+p\left(x\right)x+{p\left(x\right)}^2\right)\left(x^6+{p\left(x\right)}^3{x}^3+{p\left(x\right)}^6\right)\left(x^9+{p\left(x\right)}^9+1\right)+3\right)& \left[\mathrm{Formula}44\right]\end{array}$

Example 6:BLS-48

[0112] An example in which the curve is a BLS-48 curve will be described.

[0113] In this case, the polynomial t(x)=x+1, the polynomial r(x)=Φ.sub.48(x)=x.sup.16−x.sup.8+1, and the polynomial p(x)=⅓(x−1).sup.2r(x)+x. Accordingly, the polynomial T(x)=x, the polynomial h.sub.1(x)=⅓(x−1).sup.2, and the polynomial h.sub.2(x)=1. Hence, the exponent portion is decomposed as in Formula 45.

[00012]$\begin{array}{cc}3.Math.\frac{{p\left(x\right)}^{48}-1}{r\left(x\right)}=\left({p\left(x\right)}^{16}-1\right)\left({p\left(x\right)}^{16}+{p\left(x\right)}^8+1\right).Math.\left({\left(x-1\right)}^2\left(x+p\left(x\right)\right)\left(x^2+{p\left(x\right)}^2\right)\left(x^4+{p\left(x\right)}^4\right)\left(x^6+{p\left(x\right)}^6-1\right)+3\right)& \left[\mathrm{Formula}45\right]\end{array}$

Effect of Embodiment 1

[0114] As described above, the final exponentiation computation device 10 according to Embodiment 1 decomposes the exponent portion into an easy part and a hard part with using the polynomial Φ.sub.k(p(x)), and transforms the hard part into a linear sum of the polynomial p(x).sup.i. This enables efficient computation of pairing computation.

[0115] Specifically, the final exponentiation computation device 10 according to Embodiment 1 factorizes the hard part with using a homogeneous cyclotomic polynomial. This enables efficient computation of pairing computation concerning many elliptic curves.

[0116] Specifically, as the hard part is decomposed with using the homogeneous cyclotomic polynomial, a number of exponentiation computations of p(x) increases a little, but a number of exponentiation computations of x decreases greatly. It is known that a computation complexity of exponentiation computation of x is very large compared to a computation complexity of exponentiation computation of p(x).

[0117] Therefore, the final exponentiation computation device 10 according to Embodiment 1 can perform pairing computation efficiently by factorizing the hard part by the homogeneous cyclotomic polynomial.

[0118] More specifically, particularly, a computation efficiency of the final exponentiation computation can be improved for a family of typical elliptic curves such as BLS-9, 12, 24, 27, and 48 curves having a trace t(x)=x+1 which have been studied conventionally.

[0119] Final exponentiation computation of the BLS-12 curve (Non-Patent Literature 6) which is a typical elliptic curve, and final exponentiation computation of this time are compared.

[0120] In a literature “D. F. Aranha, L. Fuentes-Castaneda, etc, “Implementing pairings at the 192-bit security level”, Pairing 2012, p. 177˜195.”, x=−2{circumflex over ( )}107+2{circumflex over ( )}105+2{circumflex over ( )}93+2{circumflex over ( )}5 is employed as the parameter of the BLS-12 curve,

[0121] Here again, comparison is performed using the same parameter. At this time, a computation complexity cost of final exponentiation on the BLS12 curve in the above literature is expressed by Formula 46 with using a multiplication cost M over a prime field F.sub.p, a cost S of a power of 2 over the prime field F.sub.p, and an inverse element computation cost I over an expansion field F.sub.p{circumflex over ( )}12.

I+1783M+28998S  [Formula 46]

[0122] In the above literature, computation is performed by employing a final exponentiation computation method of decomposing the hard part as in Formula 47.

[00013]$\begin{array}{cc}\frac{{\Phi }_{12}\left(p\left(x\right)\right)}{r\left(x\right)}=\stackrel{3}{\underset{i=0}{.Math.}}{\lambda }_i\left(x\right){p\left(x\right)}^i& \left[\mathrm{Formula}47\right]\end{array}$

[0123] On the other hand, the final exponentiation computation device 10 according to Embodiment 1 does not quest for a coefficient X. The final exponentiation computation device 10 according to Embodiment 1 factorizes the hard part directly by using a new tool of homogeneous cyclotomic polynomial. Thus, the hard part of final exponentiation of BLS-12 is expressed by Formula 48.

[00014]$\begin{array}{cc}\frac{{\Phi }_{12}\left(p\left(x\right)\right)}{r\left(x\right)}=\frac{1}{3}.Math.{\left(x-1\right)}^2\left(x+p\left(x\right)\right)\left(x^2+{p\left(x\right)}^2-1\right)+1& \left[\mathrm{Formula}48\right]\end{array}$

[0124] A computation complexity cost of final exponentiation of the BLS12 curve with using Formula 48 is expressed by Formula 49.

I+1606M+28944S  [Formula 49]

[0125] ***Other Configurations***

Modification 1

[0126] In Embodiment 1, the feature constituent elements are implemented by software. However, Modification 1 may be possible in which the feature constituent elements are implemented by hardware. A difference of Modification 1 from Embodiment 1 will be described.

[0127] A configuration of a final exponentiation computation device 10 according to Modification 1 will be described with referring to FIG. 10.

[0128] When the feature constituent elements are implemented by hardware, the final exponentiation computation device 10 is provided with an electronic circuit 15 in place of a processor 11, a memory 12, and a storage 13. The electronic circuit 15 is a dedicated circuit that implements the features of the feature constituent elements, a feature of the memory 12, and a feature of the storage 13.

[0129] The electronic circuit 15 is assumed to be a single circuit, a composite circuit, a programmed processor, a parallel-programmed processor, a logic IC, a Gate Array (GA), an Application Specific Integrated Circuit (ASIC), or a Field-Programmable Gate Array (FPGA).

[0130] The feature constituent elements may be implemented by one electronic circuit 15. The feature constituent elements may be decentralized into a plurality of electronic circuits and implemented by the plurality of electronic circuits 15.

Modification 2

[0131] Modification 2 may be possible in which some of the feature constituent elements are implemented by hardware and the remaining feature constituent elements are implemented by software.

[0132] The processor 11, the memory 12, the storage 13, and the electronic circuit 15 are referred to as processing circuitry. That is, the features of the feature constituent elements are implemented by processing circuitry.

Modification 3

[0133] In Embodiment 1, the final exponentiation computation device 10 which computes only the final exponentiation by acquiring the value f computed by the Miller loop is described. A pairing computation device 30 which performs pairing computation may be formed by adding a feature of performing computation of the Miller loop to the final exponentiation computation device 10 described in Embodiment 1.

[0134] A configuration of a pairing computation device 30 according to Modification 3 will be described with referring to FIG. 11.

[0135] The pairing computation device 30 is provided with a Miller function computation unit 31 in addition to the feature constituent elements provided to the final exponentiation computation device 10. The Miller function computation unit 31 is implemented by software or hardware just as the feature constituent elements provided to the final exponentiation computation device 10 are. The Miller function computation unit 31 performs Miller loop computation.

[0136] In this case, in step S31 of FIG. 6, an exponentiation computation unit 22 acquires a value f computed by the Miller function computation unit 31.

Modification 4

[0137] In Embodiment 1, the integer a is computed to cancel the denominator of the coefficient from the polynomial h.sub.1(x) and the polynomial h.sub.2(x). In Embodiment 1, if any coefficient of the polynomial h.sub.1(x) and the polynomial h.sub.2(x) does not include a fraction, 1 will be computed as the integer a. However, if any coefficient of the polynomial h.sub.1(x) and the polynomial h.sub.2(x) does not include a fraction, the integer a need not be computed. In this case, multiplication by the integer a need not be performed in an exponentiation simplification process and an exponentiation computation process.

Embodiment 2

[0138] In Embodiment 1, a computation method of the final exponentiation of the paring computation has been described. In Embodiment 2, a process that uses a result of pairing computation performed in Embodiment 1 will be described. In Embodiment 2, a difference from Embodiment 1 will be described, and a description of the same point as in Embodiment 1 will be omitted.

[0139] ***Description of Configuration***

[0140] A configuration of a cryptographic processing device 40 according to Embodiment 2 will be described with referring to FIG. 12.

[0141] The cryptographic processing device 40 is provided with a cryptographic processing unit 41 in addition to the feature constituent elements provided to the final exponentiation computation device 10 according to Embodiment 1. The cryptographic processing unit 41 is implemented by software or hardware just as the feature constituent elements provided to the final exponentiation computation device 10 are.

[0142] ***Description of Operations***

[0143] Operations of the cryptographic processing device 40 according to Embodiment 2 will be described with reference to FIG. 13.

[0144] An operation procedure of the cryptographic processing device 40 according to Embodiment 2 corresponds to a cryptographic processing method according to Embodiment 2. A program that implements the operations of the cryptographic processing device 40 according to Embodiment 2 corresponds to a cryptographic processing program according to Embodiment 2.

[0145] (Step S71: Pairing Computation Process)

[0146] A result of pairing computation is computed by the feature constituent elements provided to the final exponentiation computation device 10 according to Embodiment 1. The result of pairing computation is written to a memory 12.

[0147] (Step S72: Cryptographic Process)

[0148] The cryptographic processing unit 41 performs a cryptographic process with using the result of pairing computation obtained in step S71. The cryptographic process is a process of cryptographic primitive such as an encryption process, a decryption process, a signature process, and a verification process.

[0149] The encryption process is a process of converting plaintext-state data into a ciphertext so that the data is kept secret from the third party. The decryption process is a process of converting the cyphertext converted by the encryption process into the plaintext-state data. The signature process is a process of generating a signature for at least either one of data manipulation detection and data origin confirmation. The verification process is a process of performing at least either one of data manipulation detection and data origin confirmation by the signature generated by the signature process.

[0150] For example, the cryptographic processing unit 41 may generate a message decrypted from a ciphertext with using a result of pairing computation that takes as input elements of the ciphertext and elements of a decryption key.

Effect of Embodiment 2

[0151] As described above, the cryptographic processing device 40 according to Embodiment 2 implements the cryptographic process with using the feature constituent elements of the final exponentiation computation device 10 according to Embodiment 1. The final exponentiation computation device 10 according to Embodiment 1 can perform pairing computation efficiently. Therefore, the cryptographic processing device 40 according to Embodiment 2 can perform the cryptographic process efficiently.

[0152] ***Other Configurations***

Modification 5

[0153] In Embodiment 2, the cryptographic processing device 40 is provided with the cryptographic processing unit 41 in addition to the feature constituent elements provided to the final exponentiation computation device 10 according to Embodiment 1. However, the cryptographic processing device 40 may be provided with the cryptographic processing unit 41 in addition to the feature constituent elements provided to the pairing computation device 30 described in Modification 3.

[0154] So far, the embodiments and modifications of the present disclosure have been described. Several ones of these embodiments and modifications may be practiced by combination. Also, one or several ones of these embodiments and modifications may be practiced partially. The present disclosure is not limited to the above embodiments and modifications, and various changes can be made to the present disclosure as necessary.

REFERENCE SIGNS LIST

[0155] 10: final exponentiation computation device; 11: processor; 12: memory; 13: storage; 14: communication interface; 15: electronic circuit; 21: exponentiation simplification unit; 211: decomposition unit; 212: factorization unit; 22: exponentiation computation unit; 30: pairing computation device; 31: Miller function computation unit; 40: cryptographic processing device; 41: cryptographic processing unit.