SCALAR MULTIPLICATION SYSTEM, SCALAR MULTIPLICATION APPARATUS, SCALAR MULTIPLICATION METHOD AND PROGRAM

Abstract

A scalar multiplication system computes a scalar multiplication for a point on an elliptic curve. The scalar multiplication system includes a computer including a memory and a processor configured to execute computing a pre-computation table T including d points e.sub.iP having the same Z coordinate in Jacobian coordinates using elliptic curve point addition or elliptic curve point doubling according to a CoZ method for a point P on the elliptic curve and d integers e.sub.i(i[1, d]); converting a scalar value k into a scalar value k expressed as k=k.sub.02.sup.0+k.sub.12.sup.1+ . . . +k.sub.n12.sup.n1 (k.sub.i{0, e.sub.1, . . . , e.sub.d}); and using the pre-computation table T and the scalar value k to compute a scalar multiplication kP using the elliptic curve point addition according to the CoZ method.

Claims

1. A scalar multiplication system that computes a scalar multiplication for a point on an elliptic curve, and is applied to secure communication, the scalar multiplication system comprising: a computer including a memory and a processor configured to execute computing a pre-computation table T including d points e.sub.iP having the same Z coordinate in Jacobian coordinates using elliptic curve point addition or elliptic curve point doubling according to a CoZ method for a point P on the elliptic curve and d integers e.sub.i (i[1, d]); converting a scalar value k into a scalar value k expressed as k=k.sub.02.sup.0+k.sub.12.sup.1+ . . . +k.sub.n12.sup.n1(k.sub.i{0, e.sub.1, . . . , e.sub.d}); and using the pre-computation table T and the scalar value k to compute a scalar multiplication kP using the elliptic curve point addition according to the CoZ method.

2. The scalar multiplication system according to claim 1, wherein upon computing multi-scalar multiple k.sub.0P.sub.0+ . . . +k.sub.m1P.sub.m1, the processor computes a pre-computation table Ti for each point P.sub.i(i[0, m1]), the processor converts each scalar value k.sub.i(i[0, m1]) into k.sub.i=k.sub.i02.sup.0+k.sub.i12.sup.1+ . . . +k.sub.m12.sup.n1 (k.sub.ij{0, e.sub.1, . . . , e.sub.d}), and the processor computes multi-scalar multiple k.sub.0P.sub.0+ . . . +k.sub.m1P.sub.m1 using the pre-computation table T.sub.i(i[0, m1]) and the scalar value k.sub.i (i[0, m1]) after conversion.

3. The scalar multiplication system according to claim 1, wherein the processor computes e.sub.iPe.sub.i1P+aP or e.sub.iP2e.sub.i1P using elliptic curve point addition or elliptic curve point doubling, respectively, with a being a predetermined natural number, and then converts the Z coordinate of each e.sub.iP(i[1, d]) to compute the pre-computation table T.

4. A scalar multiplication device that computes a scalar multiplication for a point on an elliptic curve, and is applied to secure communication, the scalar multiplication device comprising: a memory; and a processor configured to execute computing a pre-computation table T including d points e.sub.iP having the same Z coordinate in Jacobian coordinates using elliptic curve point addition or elliptic curve point doubling according to a CoZ method for a point P on the elliptic curve and d integers e.sub.i (i[1, d]); converting a scalar value k into a scalar value k expressed as k=k.sub.02.sup.0+k.sub.12.sup.1+ . . . +k.sub.n12.sup.n1(k.sub.i{0, e.sub.1, . . . , e.sub.d}); and using the pre-computation table T and the scalar value k to compute a scalar multiplication kP using the elliptic curve point addition according to the CoZ method.

5. A scalar multiplication method executed by a computer that includes a memory and a processor to compute a scalar multiplication for a point on an elliptic curve, and to be applied to secure communication, the scalar multiplication method comprising: computing a pre-computation table T including d points e.sub.iP having the same Z coordinate in Jacobian coordinates using elliptic curve point addition or elliptic curve point doubling according to a CoZ method for a point P on the elliptic curve and d integers e.sub.i(i[1, d]); converting a scalar value k into a scalar value k expressed as k=k.sub.02.sup.0+k.sub.12.sup.1+ . . . +k.sub.n12.sup.n1 (k.sub.i{0, e.sub.1, . . . , e.sub.d}); and using the pre-computation table T and the scalar value k to compute a scalar multiplication kP using the elliptic curve point addition according to the CoZ method.

6. A non-transitory computer-readable recording medium having computer-readable instructions stored thereon, which, when executed, cause a computer to function as the scalar multiplication system according to claim 1.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0009] FIG. 1 is a diagram illustrating an example of an algorithm of multi-scalar multiplication using a conventional binary method.

[0010] FIG. 2 is a diagram illustrating an example of an algorithm of scalar multiplication with precomputation according to a conventional w-NAF method.

[0011] FIG. 3 is a diagram illustrating an example of an algorithm of pre-computation processing according to the present embodiment.

[0012] FIG. 4 is a diagram illustrating an example of an algorithm of evaluation processing according to the present embodiment.

[0013] FIG. 5 is a diagram illustrating an example of a hardware configuration of a scalar multiplication device according to the present embodiment.

[0014] FIG. 6 is a diagram illustrating an example of a functional configuration of the scalar multiplication device according to the present embodiment.

[0015] FIG. 7 is a diagram illustrating an example of a flowchart of scalar multiplication with precomputation according to the present embodiment.

[0016] FIG. 8 is a diagram illustrating an algorithm of pre-computation processing of scalar multiplication with precomputation according to a w-NAF method in an example.

[0017] FIG. 9 is a diagram illustrating an algorithm of evaluation processing of scalar multiplication with precomputation according to a w-NAF method in an example.

DESCRIPTION OF EMBODIMENTS

[0018] Hereinafter, one embodiment of the present invention will be described. In the present embodiment, a scalar multiplication device 10 capable of efficiently executing scalar multiplication/multi-scalar multiplication with precomputation using the CoZ method will be described. Note that the scalar multiplication device 10 according to the present embodiment can be implemented by various devices such as a general-purpose server, a personal computer (PC), a smartphone, a tablet terminal, an embedded device, and a wearable device, for example.

[0019] <Preparation>

[0020] First, several terms, concepts, and the like will be prepared.

[0021] For a prime number p and a positive integer c, a finite field is F.sub.q where q=p.sup.c. Note that, although F would be written in an outline letter (blackboard bold) to be accurate, it is written as F in the text of the specification.

[0022] For an elliptic curve E defined on the finite field F.sub.q, a set of F.sub.q-rational points on the elliptic curve is defined as follows:

E(F.sub.q)={(x,y)E|x,yF.sub.q}O

where O is an infinite point.

[0023] At this time, it is known that E(F.sub.q) forms an additive group. That is, in E(F.sub.q), the elliptic curve point addition R=P+Q (where PQ) and the elliptic curve point doubling R=2P can be computed for any P, QE(F.sub.q). Furthermore, the infinite point O is the zero element of the additive group, and P+O=P is satisfied for any point PE(F.sub.q). Hereinafter, the elliptic curve point addition and the elliptic curve point doubling are also referred to as point addition and point doubling, respectively.

[0024] <<Coordinates>>

[0025] Affine coordinates are coordinates in which a point PE(F.sub.q) on an elliptic curve is expressed as P=(x, y) (x, yF.sub.q). On the other hand, Jacobian coordinates are coordinates in which a point PE(F.sub.q) on an elliptic curve is expressed as P=(X, Y, Z) (X, Y, ZF.sub.q). The point P=(X, Y, Z) (where Z0) in the Jacobian coordinates can be converted into a point in the affine coordinates by computation of (X/Z.sup.2, Y/Z.sup.3)=(x, y). Hereinafter, the X coordinate, the Y coordinate, and the Z coordinate of an arbitrary point PE(F.sub.q) on the elliptic curve in the Jacobian coordinates are expressed as P.sub.X, P.sub.Y, and P.sub.Z, respectively.

[0026] <<Co-Z Method>>

[0027] Let the expressions of points P, QE(F.sub.Q) on the elliptic curve in the Jacobian coordinates be P=(P.sub.X, P.sub.Y, P.sub.Z), Q=(Q.sub.X, Q.sub.Y, Q.sub.Z). At this time, the CoZ method is a method capable of efficiently computing the elliptic curve point addition P+Q if P.sub.Z=Q.sub.Z.

[0028] By using the CoZ method, the following elliptic curve point addition can be efficiently computed in the Jacobian coordinates.

(R,P,t)P+Q

[0029] where the point R is an addition result of P+Q, the point P is a point equivalent to P and satisfying Pz=R.sub.Z (that is, the Z coordinate of P is the same as that of R), and t is an auxiliary output satisfying R.sub.Z=tP.sub.Z.

[0030] Similarly, by using the CoZ method, the following elliptic curve point doubling can be efficiently computed in the Jacobian coordinates.

(R,P,t)2P

[0031] where the point R is a result of 2P, the point P is a point equivalent to P and satisfying P.sub.Z=R.sub.Z, and t is an auxiliary output satisfying R.sub.Z=tP.sub.Z.

[0032] Note that for details of the CoZ method, refer to, for example, Non-Patent Literature 1, Reference Literature 1 N. Meloni, New Point Addition Formulae for ECC Applications, WAIFI 2007, LNCS 4547, pp. 189-201, 2007, and the like.

[0033] <<Scalar Multiplication/Multi-Scalar Multiplication>>

[0034] Scalar multiplication on the elliptic curve is a computation that obtains, for a point PE(F.sub.q) on the elliptic curve and an integer k of 0 or greater, kP expressed as follow:

[00001]$\begin{array}{cc}\mathrm{kP}=\underset{k\mathrm{pieces}}{\underset{}{P+P+.Math.+P}}& \left[\mathrm{Math}.1\right]\end{array}$

[0035] Multi-scalar multiplication is an extension of the scalar multiplication, and is a computation that obtains, for m points P.sub.0, . . . , and P.sub.m1 on the elliptic curve and m integers k.sub.0, . . . , k.sub.m1 of 0 or greater, the following.

[00002]$\begin{array}{cc}\underset{i=0}{\overset{m-1}{.Math.}}{k}_i{P}_i=k_0{P}_0+.Math.+k_{m-1}{P}_{m-1}& \left[\mathrm{Math}.2\right]\end{array}$

[0036] Each scalar value k.sub.i is an n-bit binary number expressed as follow:

[00003]$\begin{array}{cc}{k}_i=\left(k_{i,n-1},.Math.,k_{i,0}\right)=\underset{j=0}{\overset{n-1}{.Math.}}{k}_{i,j}{2}^j\left(k_{i,j}\left\{0,1\right\}\right)& \left[\mathrm{Math}.3\right]\end{array}$

[0037] At this time, a binary method is known as an algorithm of the most basic multi-scalar multiplication. This algorithm is a method that does not use a pre-computation table. FIG. 1 illustrates an example of an algorithm of multi-scalar multiplication using the binary method. As illustrated in FIG. 1, the algorithm of the multi-scalar multiplication using the binary method uses m points P.sub.0, . . . , P.sub.m1E(F.sub.q) and m scalar values k.sub.0, . . . , k.sub.m1 as inputs, and outputs a result R of the multi-scalar multiplication. The algorithm is initialized with RO (line 1), and then repeats the procedures of lines 3 to 8 while decreasing j by 1 from j=n1 to j=0 (line 2), and finally outputs R (line 10). In the procedures of lines 3 to 8, R2R is set at first (line 3), and then the procedures of lines 5 to 7 are repeated while increasing i by 1 from i=0 to i=m1 (line 4). In the procedures of lines 5 to 7, if k.sub.i,j=1 (line 5), then R is updated by R R+P.sub.i (line 6).

[0038] <<Scalar Multiplication/Multi-Scalar Multiplication with Precomputation>>

[0039] Hereinafter, in order to simplify the description, scalar multiplication with precomputation will be described. As described above, since multi-scalar multiplication is an extension of scalar multiplication, the following description can be easily extended to multi-scalar multiplication.

[0040] In the scalar multiplication with precomputation, a result kP of the scalar multiplication is computed by the following three processes for a point PE(F.sub.q) and a scalar value k.

[0041] Pre-computation processing: For a point PE(F.sub.q) and d integers e.sub.i, . . . , e.sub.d, points e.sub.iP (i[1, d]) are computed, to set a pre-computation table T={e.sub.iP, . . . , e.sub.dP}.

[0042] Scalar value conversion processing: A scalar value k is converted into a scalar value k expressed as k.sub.02.sup.0+k.sub.12.sup.1+ . . . +k.sub.n12.sup.n1. Here, k.sub.i{0, e.sub.1, . . . , e.sub.d}.

[0043] That is, in the scalar value conversion processing, in a case where 2 is a base, a mantissa corresponding to 2.sup.i (where i[0, n1]) is k.sub.i, and k is expressed as (k.sub.n1, . . . , k.sub.0) in a numerical notation, each digit is converted into a value k of 0 or e.sub.i (i[1, d]).

[0044] Evaluation processing: kP is computed by elliptic curve point addition and elliptic curve point doubling using the pre-computation table T and the scalar value k.

[0045] A w-NAF method is known as one of methods for executing scalar multiplication with precomputation at a high speed. FIG. 2 illustrates an example of an algorithm of scalar multiplication with precomputation according to the w-NAF method. As illustrated in FIG. 2, the algorithm of the scalar multiplication with precomputation according to the w-NAF method uses a point PE(F.sub.q), a scalar value kN(where N is a set of all natural numbers), and a window width wN(where w>1) as inputs and outputs a result R=kP of the scalar multiplication. After executing the pre-computation processing (lines 1 to 4), the scalar value conversion processing (line 5), and the evaluation processing (lines 6 to 16), R is finally output (line 17).

[0046] In the pre-computation processing, P[i]P and A2P are initialized for i=1 (line 1), and then P[2i+1]A+P[2i1] is set while increasing i by 1 from i=1 to i=2.sup.w21 (lines 2 to 4). Accordingly, the pre-computation table T={P[1], P[3], . . . , P[2.sup.w11]}={P, 3P, . . . , (2.sup.w11)P} is obtained.

[0047] In the scalar value conversion processing, the scalar value k is converted into k=k.sub.02.sup.0+k.sub.12.sup.1+ . . . +k.sub.n12.sup.n1 (where k.sub.i{0, 1, 3, . . . , (2.sup.w11)}) (line 5).

[0048] In the evaluation processing, after initialization of RO (line 6), the procedures of lines 8 to 15 are repeated while decreasing i by 1 from i=n1 to i=0 (line 7). In the procedures of lines 8 to 15, after setting R2R (line 8), if k.sub.i0 and k.sub.i>0, then R is updated by RR+P[k.sub.i] (line 11), if k.sub.i0 and k.sub.i0, then R is updated by RRP[k.sub.i] (line 13), and in other cases, nothing is performed.

[0049] <Scalar Multiplication/Multi-Scalar Multiplication with Precomputation According to Present Embodiment>

[0050] Next, scalar multiplication/multi-scalar multiplication with precomputation according to the present embodiment will be described. Hereinafter, in order to simplify the description, the scalar multiplication with precomputation according to the present embodiment will be mainly described. As described above, since multi-scalar multiplication is an extension of scalar multiplication, the following description can be easily extended to multi-scalar multiplication.

[0051] In the scalar multiplication according to the present embodiment, the elliptic curve point addition and the elliptic curve point doubling according to the CoZ method are used to create the pre-computation table T in which the Z coordinates of all the points e.sub.1P, . . . , e.sub.dP computed in the pre-computation processing have the same value. This makes it possible to efficiently compute elliptic curve point addition according to the CoZ method even in the evaluation processing. The scalar value conversion processing is similar to the conventional scalar multiplication with precomputation (for example, a conventional w-NAF method, sliding window method, or the like).

[0052] <<Pre-Computation Processing>>

[0053] A point PE(F.sub.q) and d points computed by the pre-computation processing is set as {P(=e.sub.1P), e.sub.2P, . . . , e.sub.dP}. Further, it is assumed that e.sub.iP can be computed as follows with a being a natural number.

e.sub.iPe.sub.i1P+aP or e.sub.iP2.sub.e1P

[0054] Each e.sub.iP may be a negative point as appropriate.

[0055] At this time, FIG. 3 illustrates an example of an algorithm of the pre-computation processing for creating the pre-computation table T={P, e.sub.2P, . . . , e.sub.dP} in which the Z coordinates of all points are the same. As illustrated in FIG. 3, the pre-computation processing of the scalar multiplication with precomputation according to the present embodiment uses a point PE(F.sub.q) and a natural number a as inputs and outputs a pre-computation table T={P, e.sub.2P, . . . , e.sub.dP}. In FIG. 3, P[e.sub.i] (where i[1, d]) is written as P[i] in order to simplify the notation.

[0056] In the pre-computation processing illustrated in FIG. 3, first, AaP, P[1]P, and t.sub.1 are set to a value satisfying A.sub.Z=t.sub.1P.sub.Z in the procedures of lines 1 to 3. However, in the procedure of line 2, conversion is performed to obtain a point (that is, P[1] is a point whose Z coordinate is the same as the Z coordinate of A) at which A.sub.Z=P[1].sub.Z holds.

[0057] Next, the procedures of lines 5 to 10 are repeated while increasing i by 1 from i=2 to i=d (line 4). In the procedures of lines 5 to 10, if elliptic curve point addition is performed, then, when A.sub.ZP[i1].sub.Z, A is converted into a point whose Z coordinate is the same as P[i1] (line 6), and (P[i], A, t.sub.i)A+P[i1] is set (line 7). On the other hand, if elliptic curve point doubling is performed, then (P[i], B, t.sub.i)2P[i1] is set (line 9). Note that elliptic curve point addition according to the CoZ method is used in line 7, and elliptic curve point doubling according to the CoZ method is used in line 9.

[0058] Subsequently, after setting st.sub.d (line 12), the procedures of lines 14 to 17 are repeated while decreasing i by 1 from i=d1 to i=1 (line 13). In the procedures of lines 14 to 17, P[i].sub.XP[i].sub.X.Math.s.sup.2, P[i].sub.Y, P[i].sub.Y.Math.s.sup.3, P[i].sub.ZP[i].sub.Z.Math.s, and ss.Math.t.sub.i are performed. Accordingly, the Z coordinates of each P[i]=(P[i].sub.X, P[i].sub.Y, P[i].sub.Z) are the same.

[0059] Finally, the pre-computation table T={P[1], P[e.sub.2], . . . , P[e.sub.d])=(P, e.sub.2P, . . . , e.sub.dP} is output (line 19).

[0060] In addition, in the elliptic curve point addition according to the CoZ method, t.sub.i.sup.2 and t.sub.i.sup.3 can be computed without a computational cost instead of t.sub.i. Therefore, the efficiency can be improved by directly computing s.sup.2 and s.sup.3 without sequentially computing s.sup.2 and s.sup.3 in lines 14 and 15 of the pre-computation processing illustrated in FIG. 3.

[0061] In addition, in a case where the pre-computation processing illustrated in FIG. 3 is applied to the multi-scalar multiplication k.sub.0P.sub.0+ . . . +k.sub.m1 P.sub.m1, the procedures of lines 1 to 11 in FIG. 3 are executed for each P.sub.i, and then the procedures of lines 12 to 19 in FIG. 3 are executed for all P.sub.i. At this point, before the procedures of lines 1 to 11 in FIG. 3 are executed on P.sub.i of i1, P.sub.i is converted such that P.sub.iZ=P.sub.i1[e.sub.d].sub.Z (that is, the Z coordinate of P.sub.i is the same as the Z coordinate of P.sub.i1[e.sub.d]) is satisfied with respect to the Z coordinate of P.sub.i1 [e.sub.d].

[0062] <<Scalar Value Conversion Processing>>

[0063] As described above, the scalar value conversion processing of scalar multiplication with precomputation according to the present embodiment is similar to the conventional scalar value conversion processing of scalar multiplication with precomputation. Note that, in the case of application to the multi-scalar multiplication k.sub.0P.sub.0+ . . . +k.sub.m1 P.sub.m1, it is sufficient to perform the scalar value conversion processing on each k.sub.i(i[0, m1]).

[0064] <<Evaluation Processing>>

[0065] Assume that the pre-computation table is T, and the scalar value after scalar value conversion is k=k.sub.02.sup.0+k.sub.12.sup.1+ . . . +k.sub.n12.sup.n1 (where k.sub.i{0, e.sub.1, . . . , e.sub.d}). At this time, FIG. 4 illustrates an algorithm of the evaluation processing of the scalar multiplication with precomputation according to the present embodiment. As illustrated in FIG. 4, the evaluation processing of the scalar multiplication with precomputation according to the present embodiment uses the pre-computation table T and the scalar value k after the scalar value conversion as inputs and outputs a result R=kP of the scalar multiplication.

[0066] In the evaluation processing illustrated in FIG. 4, after initialization of R0 (line 1), the procedures of lines 3 to 12 are repeated while decreasing i by 1 from i=n1 to i=0 (line 2), and R is finally output (line 14). In the procedures of lines 3 to 12, after R2R (line 3), if k.sub.i0 and k.sub.i>0, then AP[k.sub.i] is set (line 6), and if k.sub.i0 and k.sub.i0, then AP[k.sub.i] is set (line 8), A is converted (that is, conversion into a point at which R and Z coordinates are the same) into a point satisfying R.sub.Z=A.sub.Z (line 10), and then R is updated by RR+A (line 11). On the other hand, if k.sub.i=0, nothing is performed. Note that elliptic curve point addition according to the CoZ method is used in line 11, thereby achieving improved efficiency of scalar multiplication.

[0067] Note that the evaluation processing illustrated in FIG. 4 can be directly applied to the multi-scalar multiplication.

[0068] <Hardware Configuration of Scalar Multiplication Device 10>

[0069] Next, a hardware configuration of the scalar multiplication device 10 according to the present embodiment will be described with reference to FIG. 5. FIG. 5 is a diagram illustrating an example of a hardware configuration of the scalar multiplication device 10 according to the present embodiment.

[0070] As illustrated in FIG. 5, the scalar multiplication device 10 according to the present embodiment includes an input device 101, a display device 102, an external interface I/F 103, a communication I/F 104, a processor 105, and a memory device 106. These hardware constituents are communicatively connected to each other via a bus 107.

[0071] The input device 101 is, for example, a keyboard, a mouse, a touch panel, various buttons, or the like. The display device 102 is, for example, a display, a display panel, or the like. Note that the scalar multiplication device 10 may not include at least one of the input device 101 and the display device 102.

[0072] The external I/F 103 is an interface with an external device such as a recording medium 103a. Examples of the recording medium 103a include a compact disc (CD), a digital versatile disk (DVD), a secure digital memory card (SD memory card), a Universal Serial Bus (USB) memory card, and the like.

[0073] The communication I/F 104 is an interface for connecting the scalar multiplication device 10 to a communication network. The processor 105 is any of various arithmetic/logic devices such as a central processing unit (CPU) and a micro processing unit (MPU). The memory device 106 is any of various storage devices such as a hard disk drive (HDD), a solid state drive (SSD), a random access memory (RAM), a read only memory (ROM), and a flash memory.

[0074] Since the scalar multiplication device 10 according to the present embodiment has the hardware configuration illustrated in FIG. 5, it is possible to implement scalar multiplication with precomputation, which will be described later. However, the hardware configuration illustrated in FIG. 5 is an example, and the hardware configuration of the scalar multiplication device 10 is not limited thereto.

[0075] <Functional Configuration of Scalar Multiplication Device 10>

[0076] Next, a functional configuration of the scalar multiplication device 10 according to the present embodiment will be described with reference to FIG. 6. FIG. 6 is a diagram illustrating an example of a functional configuration of the scalar multiplication device 10 according to the present embodiment.

[0077] As illustrated in FIG. 6, the scalar multiplication device 10 according to the present embodiment includes a pre-computation processing unit 201, a scalar value conversion processing unit 202, and an evaluation processing unit 203. Each of these units is implemented by processing that one or more programs installed in the scalar multiplication device 10 cause the processor 105 to execute.

[0078] The pre-computation processing unit 201 executes pre-computation processing by the algorithm illustrated in FIG. 3. Note that the pre-computation table T created by the pre-computation processing is stored in the memory device 106.

[0079] The scalar value conversion processing unit 202 converts the scalar value k into a scalar value k by conventional scalar value conversion processing of scalar multiplication with precomputation.

[0080] The evaluation processing unit 203 executes evaluation processing by the algorithm illustrated in FIG. 4. Accordingly, the result of scalar multiplication (or the result of multi-scalar multiplication when the algorithm illustrated in FIG. 3 is applied to the multi-scalar multiplication) is obtained.

[0081] <Flow of Scalar Multiplication with Precomputation>

[0082] Next, a flow of scalar multiplication with precomputation according to the present embodiment will be described with reference to FIG. 7. FIG. 7 is a diagram illustrating an example of a flowchart of scalar multiplication with precomputation according to the present embodiment.

[0083] First, the pre-computation processing unit 201 executes pre-computation processing by the algorithm illustrated in FIG. 3 (step S101). Next, the scalar value conversion processing unit 202 converts the scalar value k into a scalar value k by conventional scalar value conversion processing of scalar multiplication with precomputation (step S102). Then, the evaluation processing unit 203 executes evaluation processing by the algorithm illustrated in FIG. 4 (step S103). However, steps S101 and S102 are in no particular order, and step S101 may be executed after step S102 is executed.

EXAMPLES

[0084] Next, as an example of scalar multiplication with precomputation according to the present embodiment, a case where the present embodiment is applied to the w-NAF method will be described. FIGS. 8 and 9 illustrate algorithms of the pre-computation processing and the evaluation processing in a case where a point PE(F.sub.q) on the elliptic curve, the scalar value k, and the window width w are given to the scalar multiplication device 10. Note that the pre-computation processing is executed by the pre-computation processing unit 201, and the evaluation processing is executed by the evaluation processing unit 203. In addition, since the scalar value conversion processing is similar to the conventional w-NAF method, description thereof is omitted, but the scalar value conversion processing is executed by the scalar value conversion processing unit 202.

[0085] <<Pre-Computation Processing>>

[0086] In the pre-computation processing illustrated in FIG. 8, first, (A, P[1], t.sub.i)2P is set (line 1), and (P[2i+1], A, t.sub.i+1)A+P[2i1] is set while increasing i by 1 from i=1 to i=2.sup.w21 (line 3). Note that the procedure of line 1 is elliptic curve point doubling according to the CoZ method, and the procedure of line 3 is elliptic curve point addition according to the CoZ method.

[0087] Next, after setting

st.sub.2w2[Math. 4]

[0088] and ZP[2.sup.w11].sub.Z (lines 5 and 6), the procedures of lines 8 to 11 are repeated while decreasing i by 1 from i=2.sup.w21 to i=1 (line 7). In the procedures of lines 8 to 11, P[2i1].sub.XP[2i1].sub.X.Math.s.sup.2, P[2i1].sub.YP[2i1].sub.Y.Math.s.sup.3, and P[2i1].sub.ZZ and ss.Math.t.sub.i are performed.

[0089] Finally, the pre-computation table T={P[1], P[3], . . . , P[2.sup.w11]}={P, 3P, . . . , (2.sup.w11) P} is output (line 13).

[0090] <<Evaluation Processing>>

[0091] In the evaluation processing illustrated in FIG. 9, after initialization of RO and ZP[1].sub.Z (lines 1 and 2), the procedures of lines 4 to 17 are repeated while decreasing i from i=n1 to i=0 by 1 (line 3), and R is output as R(R.sub.x, R.sub.Y, R.sub.Z.Math.Z) (lines 19 and 20). In the procedures of lines 4 to 17, after setting R2R (line 4), if k.sub.i0 and k.sub.i>0, then AP[k.sub.i] is set (line 7), and if k.sub.i0 and k.sub.i0, then AP[k.sub.i] is set (line 9). If k.sub.i0, then R (A.sub.X, A.sub.Y, 1) is set when R=O (line 12), and A(R.sub.Z.sup.2A.sub.X, R.sub.Z.sup.3A.sub.Y, R.sub.Z) and RR+A are set when R0 (lines 14 and 15). On the other hand, if k.sub.i=0, nothing is performed.

[0092] In the evaluation processing illustrated in FIG. 9, in order to use the CoZ method in the elliptic curve point addition in line 15, the Z coordinate is set to 1 at the time of initial value substitution of R in line 12. Accordingly, since the Z coordinate of R becomes a value obtained by multiplying the original value by 1/Z, coordinate conversion can be performed only by multiplication by R.sub.Z in line 14. In addition, in line 19, by multiplying the Z coordinate by Z, correction corresponding to a change in the Z coordinate is performed, and a correct computation result is obtained.

[0093] <Comparison with Conventional Method>

[0094] Here, the scalar multiplication with precomputation using the CoZ method described in Non-Patent Literature 1 is compared with the scalar multiplication with precomputation executed by the scalar multiplication device 10 according to the present embodiment.

[0095] Non-Patent Literature 1 describes a method in which pre-computation processing is performed using a CoZ method, and then two types of evaluation processing are performed using a pre-computation table created by the pre-computation processing. The first method is a method of computing a result of scalar multiplication by using elliptic curve point addition and elliptic curve point doubling of the Jacobian coordinates in the evaluation processing using the pre-computation table as it is. The second method is a method in which the points constituting the pre-computation table are converted from Jacobian coordinates to affine coordinates, and then, in the evaluation processing, a result of the scalar multiplication is computed by the elliptic doubling of the Jacobian coordinates and the elliptic curve point addition in the mixed coordinates using the Jacobian coordinates and the affine coordinates as inputs.

[0096] In the first method described in Non-Patent Literature 1, the CoZ method is used in the pre-computation processing, and thus the speed is high. On the other hand, the elliptic curve point addition in the evaluation processing is the elliptic curve point addition in the normal Jacobian coordinates not using the CoZ method, and thus the speed is low. On the other hand, in the second method, similarly, the pre-computation processing is performed at a high speed, and elliptic curve point addition in the mixed coordinates at a high speed can be used also in the evaluation processing. However, it is necessary to convert the points constituting the pre-computation table to the affine coordinates. The conversion from the Jacobian coordinates into the affine coordinates requires multiplication and inverse calculation on F.sub.q for one point, which is inefficient.

[0097] On the other hand, in the scalar multiplication with precomputation executed by the scalar multiplication device 10 according to the present embodiment, the Z coordinates of the points constituting the pre-computation table are converted into the same value using the properties of the CoZ method, so that coordinate conversion can be performed by performing multiplication on F.sub.q for one point several times. In addition, in the evaluation processing, the coordinate conversion and the elliptic curve point addition according to the CoZ method can be computed at the same computational cost as the computation of the mixed coordinates.

[0098] Therefore, the scalar multiplication with precomputation executed by the scalar multiplication device 10 according to the present embodiment solves the disadvantage of the scalar multiplication with precomputation described in Non-Patent Literature 1, and the scalar multiplication can be computed at a higher speed.

CONCLUSION

[0099] As described above, the scalar multiplication device 10 according to the present embodiment can efficiently compute the scalar multiplication with precomputation as compared with the conventional method. In addition, since the multi-scalar multiplication is an extension of the scalar multiplication, the scalar multiplication device 10 according to the present embodiment can also efficiently compute the multi-scalar multiplication in substantially the same way.

[0100] Note that elliptic curve cryptography is used, for example, when secure communication such as SSL/TLS is performed. In addition, the pairing-based cryptography is used, for example, when constructing advanced functional cryptography such as ID-based encryption or functional encryption. Therefore, the scalar multiplication device 10 according to the present embodiment can be applied to, for example, a device, an apparatus, or a system that performs communication by SSL/TLS or the like, or can be applied to a device, an apparatus, a system, or the like that performs key generation, encryption, decryption, or the like by ID-based encryption, functional encryption, or the like.

[0101] The present invention is not limited to the embodiments specifically disclosed as above, and various modifications and changes, combinations with known technique, and the like can be made without departing from the scope of the claims.

REFERENCE SIGNS LIST

[0102] 10 Scalar multiplication device [0103] 101 Input device [0104] 102 Display device [0105] 103 External I/F [0106] 103a Recording medium [0107] 104 Communication I/F [0108] 105 Processor [0109] 106 Memory device [0110] 107 Bus [0111] 201 Pre-computation processing unit [0112] 202 Scalar value conversion processing unit [0113] 203 Evaluation processing unit