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

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 i P having the same Z coordinate in Jacobian coordinates using elliptic curve point addition or elliptic curve point doubling according to a Co—Z method for a point P on the elliptic curve and d integers e i (i∈[1, d]);

converting a scalar value k into a scalar value k′ expressed as k′=k 0 ′2 0 +k 1 ′2 1 + . . . +k n−1 ′2 n−1 (k i ′∈{0, ±e 1 , . . . , ±e d }); and

using the pre-computation table T and the scalar value k′ to compute a scalar multiplication k′P using the elliptic curve point addition according to the Co—Z method.

2 . The scalar multiplication system according to claim 1 , wherein

upon computing multi-scalar multiple k 0 P 0 + . . . +k m−1 P m−1 ,

the processor computes a pre-computation table Ti for each point P i (i∈[0, m−1]),

the processor converts each scalar value k i (i∈[0, m−1]) into k i ′=k i0 ′2 0 +k i1 ′2 1 + . . . +k m−1 ′2 n−1 (k ij ′∈{0, ±e 1 , . . . , ±e d }), and

the processor computes multi-scalar multiple k 0 ′P 0 + . . . +k m−1 ′P m−1 using the pre-computation table T i (i∈[0, m−1]) and the scalar value k i ′ (i∈[0, m−1]) after conversion.

3 . The scalar multiplication system according to claim 1 , wherein

the processor computes e i P←e i−1 P+aP or e i P←2e i−1 P 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 i P(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 i P having the same Z coordinate in Jacobian coordinates using elliptic curve point addition or elliptic curve point doubling according to a Co—Z method for a point P on the elliptic curve and d integers e i (i∈[1, d]);

converting a scalar value k into a scalar value k′ expressed as k′=k 0 ′2 0 +k 1 ′2 1 + . . . +k n−1 ′2 n−1 (k i ′∈{0, ±e 1 , . . . , ±e d }); and

using the pre-computation table T and the scalar value k′ to compute a scalar multiplication k′P using the elliptic curve point addition according to the Co—Z 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 i P having the same Z coordinate in Jacobian coordinates using elliptic curve point addition or elliptic curve point doubling according to a Co—Z method for a point P on the elliptic curve and d integers e i (i∈[1, d]);

converting a scalar value k into a scalar value k′ expressed as k′=k 0 ′2 0 +k 1 ′2 1 + . . . +k n−1 ′2 n−1 (k i ′∈{0, ±e 1 , . . . , ±e d }); and

using the pre-computation table T and the scalar value k′ to compute a scalar multiplication k′P using the elliptic curve point addition according to the Co—Z 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 .