JP2016133601A - Multi-scalar multiplication computation device, multi-scalar multiplication computation method and program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a multi-scalar multiplication computation device capable of reducing the number of times of using elliptic addition/elliptic doubling in multi-scalar multiplication calculation.SOLUTION: The multi-scalar multiplication computation device comprises: a prior calculation unit which calculates a point P+ΣePfor all combinations of sets (e, ..., e) of m-1 bits {0,1} and stores the calculated 2points in a prior calculation table; an expression conversion unit which, with a positive integer, an odd number k, and an integer k, ..., kof 0 or bigger as input, performs expression conversion to obtain k', ..., k'in which each digit of k', ..., k'is expressed by {0, ±1} and satisfying conditions that, for all k', j digit is 0, or j digit of k'is {±1} and j digit of k'except k'is 0 or the same value with j digit of k'; and a multi-scalar multiplication calculation unit which calculates a point having the same value with multi-scalar multiplication ΣkPusing the prior calculation table and the expression-converted k', ..., k'.SELECTED DRAWING: Figure 1

Description

  The present invention relates to a key generation, encryption, and decryption device in elliptic curve cryptography and pairing cryptography, and more particularly to a multiscalar multiplication arithmetic device, a multiscalar multiplication arithmetic method, and a program for realizing information security technology.

  The most basic multi-scalar multiplication without pre-calculation and expression conversion is already widely used as a general technique, and is described in Non-Patent Document 1, for example. Non-Patent Document 2 proposes a method for efficiently calculating multiscalar multiplication by pre-calculation and multiscalar multiplication without using expression conversion. Further, Hedabou et al., Non-Patent Document 3 discloses a method that is efficient using a pair of pre-calculation and expression conversion in a manner different from the present invention. Non-Patent Document 3 is described in the context of speeding up fixed-point scalar multiplication, but these can be regarded as multi-scalar multiplication calculations.

D. Hankerson, A. Menezes, and S. Vanstone, “Guide to Elliptic Curve Cryptography,” Springer Professional Computing, Springer-Verlag, pp. 109-113, 2004. C.H. Lim, and P.J. Lee, “More Flexible Exponentiation with Precomputation,” CRYPT0 '94, LNCS 839, pp. 95-107, 1994. M. Hedabou, P. Pinel, and L. Bebeteau, “Countermeasures for Preventing Comb Method Against SCA Attacks,” ISPEC 2005, LNCS 3439, pp. 85-96, 2005.

Elliptic curve cryptography can achieve higher security with a shorter key length than RSA cryptography. In pairing ciphers, an ID-based cipher that can set an arbitrary character string as a public key (Reference Non-Patent Document 1) and a private key / ciphertext as attributes / conditional expressions can be set by using a property called bilinearity. Therefore, it is possible to construct a highly convenient encryption method such as a functional encryption (Reference Non-Patent Document 2) that allows flexible decryption control. Both of these are important encryption technologies from the viewpoint of security and convenience.
(Reference Non-Patent Document 1: D. Boneh, and M. Franklin, “Identity-based Encryption from the Weil Pairing,” SIAM Journal on Computing, vol. 32, no. 3, pp. 586-615, 2003.)
(Reference Non-Patent Document 2: T. Okamoto, and K. Takashima, “Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption,” CRYPTO2010, LNCS 6223, pp.191-208, 2010.)
When these are realized as an actual system, multiscalar multiplication on an elliptic curve is often required. For example, in functional encryption, multiscalar multiplication is the dominant calculation cost in key generation and encryption. Therefore, efficient multiscalar multiplication on an elliptic curve is an important issue. Most of the calculation costs in multi-scalar multiplication are ellipse addition P + Q and ellipse doubling 2P, so it is necessary to reduce the number of times ellipse addition / elliptical doubling is used for efficiency. It becomes.

  Accordingly, an object of the present invention is to provide a multi-scalar multiplication operation apparatus that can reduce the number of times of use of elliptical addition / elliptical doubling in multi-scalar multiplication calculation.

  The multi-scalar multiplication operation device of the present invention includes a pre-calculation unit, an expression conversion unit, and a multi-scalar multiplication calculation unit.

Prime number p, positive integer e, q = p ^e , finite field

Let F _q -rational points on the elliptic curve E be E (F _q ).

The pre-calculation unit sets an integer m ≧ 2, and multiscalar multiplication for _m points P ₀ , ..., P _m-1 and integers ₀ 0 or more, k ₀ , ..., k _m-1 Is a function that calculates Σ _{i = 0} ^m-1 k _i P _i and outputs a point on E (F _q ), a set of m-1 bits {0,1} (e ₁ ,... ., e _m-1 ), calculate the point P ₀ + Σ _{i = 1} ^m-1 e _i P _i and save the calculated 2 ^m-1 points in the pre-calculation table To do.

The representation conversion unit takes a positive integer and an odd number k ₀ , and an integer k ₁ , ..., k _m-1 greater than or equal to ₀ , and each digit of k ' ₀ , ..., k' _m-1 is {0 , ± 1}, and the j-th digit of all k ' _i is 0, or the j-th digit of k' ₀ is {± 1} and k ' _i other than k' ₀ is the j-th digit of k ' _i The expression is converted to k ′ ₀ ,..., K ′ _m−1 which satisfies the condition that 0 or the same _{value as} the j-th digit of k ′ ₀ .

The multi-scalar multiplication calculation unit uses k ' ₀ , ..., k' _m-1 converted to the pre-calculation table and multi-scalar multiplication Σ _{i = 0} ^m-1 k _i P _i . Calculate points.

  According to the multiscalar multiplication arithmetic device of the present invention, the number of times of use of elliptical addition / elliptical doubling in multiscalar multiplication calculation can be reduced.

1 is a block diagram illustrating a configuration of a multiscalar multiplication arithmetic device according to Embodiment 1. FIG. 3 is a flowchart showing the operation of the multi-scalar multiplication operation device according to the first embodiment. The figure which illustrates the calculation algorithm of the multi-scalar multiplication using the Binary method. FIG. 3 is a diagram illustrating an algorithm executed by the expression conversion unit according to the first embodiment. FIG. 4 is a diagram illustrating an algorithm executed by the multiscalar multiplication calculation unit according to the first embodiment. FIG. 4 is a diagram for explaining an algorithm used in an algorithm executed by the expression conversion unit according to the first embodiment.

  Hereinafter, embodiments of the present invention will be described in detail. In addition, the same number is attached | subjected to the structure part which has the same function, and duplication description is abbreviate | omitted.

<Preparation>
Prior to the description of the first embodiment, the symbols used in this specification and the conventional method will be described. For prime number p and extended degree e (positive integer), q = p ^e, and finite field

And In addition, for the elliptic curve E, the set of F _q -rational points (rational points) on the elliptic curve
E (F _q ) = {(x, y) ∈E | x, y∈F _q } ∪O
It is defined as At this time, E (F _q ) forms an additive group. In E (F _q ), the ellipse addition R = P + Q (where P ≠ ± Q) and the ellipse doubling R = 2P can be calculated for the input P, Q∈E (F _q ). O is a point where P + O = P with respect to an arbitrary point P∈E (F _q ), and is called a point at infinity. Hereinafter, ellipse addition and its operation amount (calculation cost) are expressed as ECADD, and ellipse doubling and its operation amount (calculation cost) are expressed as ECDBL.

<Multiscalar multiplication>
Scalar multiplication on an elliptic curve is a point P∈E (F _q ) on an elliptic curve and an integer k greater than or equal to 0.

This is a calculation for obtaining. As an extension of scalar multiplication, Σ _{i = 0} ^m-1 when m points P _i (i = 0, ..., m-1) and an integer k _i greater than 0 are input Multi-scalar multiplication calculates k _i P _i = k ₀ P ₀ +... + k _m−1 P _m−1 .

The scalar value k _i is an n-bit binary number.
k _i = (k _i ^(n-1) ,…, k _i ⁽⁰⁾ ) = Σ _{j = 0} ^n-1 k _i ^(j) 2 ^j
(Where k _i ^(j) ∈ {0,1}, j = 0, ..., n-1)
It shall be expressed as

  There is a method using the binary method as the most basic multi-scalar multiplication. FIG. 3 shows a calculation algorithm (Algorithm1). This algorithm (Algorithm1)

That is, the point P _i (i = 0,..., M−1) on the m elliptic curves and the scalar value k _i which is an n-bit binary number are input. This algorithm (Algorithm1)

That is, it is an algorithm that outputs a calculation result R of multiscalar multiplication. First, using infinity point O

That is, R is initialized at the infinity point. In the algorithm, the symbol “←” means substitution. next,

That is, the value of j is decremented from j = n−1 to j = 0, and the calculation is repeated from the third line to the ninth line of the algorithm. next,

That is, 2R is substituted for R. next,

That is, the value of i is incremented from i = 0 to i = m−1, and the calculation is repeated from the fifth line to the eighth line of the algorithm.

That is, when k _i ^(j) = 1, using the point P _i on the elliptic curve,

That is, R + P _i is substituted for R. The seventh to ninth lines of the algorithm indicate the end of the repetitive calculation. And the 10th line of the algorithm

That is, the calculation result R of the multiscalar multiplication is output. When the probability of {0, 1} taken by each bit of the scalar value is uniform, Algorithm 1 has a calculation cost of mn / 2ECADD + nECDBL times.

[Lim-Lee method (Non-patent Document 2)]
Details of the Lim-Lee method described in Non-Patent Document 2 will be described below.

<Pre-calculation>
For all combinations of _m bit pairs (e ₀ , ..., e _m-1 ) (e _i ∈ {0,1}), the point Σ _{i = 0} ^m-1 e _i P _i calculate.

<Expression conversion>
In this method, expression conversion is not performed for each k _i .

[HPB05 method (Non-patent Document 3)]
Next, details of the HPB05 system described in Non-Patent Document 3 will be described.

<Pre-calculation>
For all combinations of m-1 bit pairs (e ₁ , ..., e _m-1 ) (e _i ∈ {0,1}), the point P ₀ + Σ _{i = 1} ^m-1 e _i P _i is calculated.

<Expression conversion>
With positive integers and odd numbers k ₀ and integers k ₁ , ..., k _m-1 greater than or equal to ₀ as input, k ' ₀ is represented by {± 1} and other k' _i (ie i ≠ 0) is, k _'i is the j-th digit k' _i ^(j) is ^{_{{0, k '0 (j}} )} and made such _{k' 0, ..., k '} m-1 output To do. 2 digits significant digit of k _i is adjacent 0, for example, j digit, a j-1 digit k _i ^(j), k _i ^(j-1) is, (k _i ^(j), k _i ^{( j-1)} ) = (0,1) → (1, -1) can be used for the above expression conversion. As a result, for any j-th digit of k ' ₀ , ..., k' _m-1 , i = 1, ..., m-1

(K ' ₀ ^(j) , k' _i ^(j) ) is (1,0), (1,1), (-1,0), (-1,- Take one of the values in 1).

  Hereinafter, the multi-scalar multiplication arithmetic apparatus according to the first embodiment will be described with reference to FIGS. 1 and 2. FIG. 1 is a block diagram illustrating a configuration of a multiscalar multiplication arithmetic apparatus 1 according to the present embodiment. FIG. 2 is a flowchart showing the operation of the multi-scalar multiplication apparatus 1 of this embodiment. As shown in FIG. 1, the multi-scalar multiplication operation apparatus 1 of the present embodiment includes a pre-calculation unit 11, a pre-calculation result storage unit 12, an expression conversion unit 13, and a multi-scalar multiplication calculation unit 14. It is.

<Pre-calculation unit 11, step S11>
Precalculation unit 11, the point P ₀ as a reference, i = 1, ..., with respect to P _i of m-1 (an integer satisfying the m ≧ 2), secondly, pre-calculated, was calculated 2 ^m−1 points are stored in the precalculation table of the precalculation result storage unit 12. At this time, a set of m−1 values (e ₁ ,..., E _m−1 ) taking {0, 1}. The combination of all (e ₁ , ..., em _-1 ) is ^2m-1 . As an example of the mapping method of t for P ₀ ,..., P _m−1 , the following pre-calculation table Tbl [t] is configured. Here, 0 ≦ t <2 ^m−1 .
Tbl [Σ _{j = 1} ^m-1 e _j 2 ^j-1 ] = P ₀ + Σ _{j = 1} ^m-1 e _j P _j
Step S11 is the same as the prior calculation in the HPB05 system.

<Expression Conversion Unit 13, Step S13>
A scalar value conversion method used in this embodiment will be described below. With positive integers and odd numbers k ₀ and integers k ₁ , ..., k _m-1 greater than or equal to ₀ as input, in this embodiment, each digit of k ' ₀ , ..., k' _m-1 is {0 , ± 1} and satisfies either of the following conditions (1) and (2).

(1) For all i = 0, ..., m−1, k ′ _i ^(j) = 0.

(2) The j-th digit of k ′ ₀ is {± 1} and the j-th digit of k ′ _i (ie, i ≠ 0) other than k ′ ₀ is 0 or the same as the j-th digit of k ′ ₀ .

When converting input positive integers and odd numbers k ₀ and integers k ₁ , ..., km _-1 that are greater than or equal to ₀ to an expression that satisfies the above conditions, conversion starts from the 0th digit. , (K ' ₀ , ..., k' _m-1 )

In the conversion after the j + s + 1 digit while creating s zero digits between the jth digit and the j + s + 1 digit for the integer s ≧ 0 It is possible to continue conversion in which digits that do not satisfy the expression of the technique do not appear. If the above-described conversion can be performed at a certain j-th digit, the above-described conversion is repeated by regarding the j + s + 1-th digit as the j-th digit.

  The operation (step S13) of the expression conversion unit 13 will be described in detail with reference to an example algorithm (Algorithm 2) shown in FIG. 4 and an example algorithm (Algorithm 4, 5, 6) shown in FIG. As shown in FIG. 4, the input to the expression conversion unit 13 is

That is, a positive integer and odd number k ₀ described above, an integer of 0 or more k _1, ..., and inputs the k _m-1. The expression conversion unit 13

That is, k ′ ₀ ,..., K ′ _m−1 which are scalar values subjected to representation conversion are output. First, the expression conversion unit 13

That is, the initial value of i is set to 0. Next, the expression conversion unit 13

That is, the third to 28th lines of this algorithm are executed with i <n as a continuation condition. Next, the expression conversion unit 13 uses the i + 1 digit of k ₀ ,

And Next, the expression conversion unit 13 uses the count algorithm (Algorithm 5) shown in FIG.

And As shown in FIG. 6, count (k, i, b) is first set to s ← 0, i <n is a continuation condition, and the i-th digit of k is not b, that is, k ⁽ⁱ⁾ ≠ b. case executes processing for outputting the s, i, if the increments s k ⁽ⁱ⁾ ≠ b is an algorithm to repeat the process of outputting the s. Next, the expression conversion unit 13 uses the check algorithm (Algorithm 6) shown in FIG.

That is, if the result of check (k _j , i, s, b) is true in all of j = 1,..., M−1, execute the 6th to 15th lines of this algorithm, Otherwise, the 17th to 27th lines of this algorithm are executed. As shown in FIG. 6, check (k, i, s, b) outputs false (false) if s = 0, and k ^{(i + j)} ≠ k ⁽ⁱ⁾ b from j = 1 to s. Then, it is an algorithm that repeatedly executes a process of outputting false and outputs true in other cases. When the result of check on the fifth line of Algorithm2 is true, the expression conversion unit 13

In other words, the i-th digit of ^{_{k 0 (-1) b, i}} + t th digit of the i + s + 1 digit to 1, k ₀ of k ₀ (where, t = 1, ..., s ) in Substitute 0. Next, the expression conversion unit 13

  That is, from j = 1 to j = m−1, the algorithm is repeatedly operated from the 9th line to the 14th line while incrementing the value of j. Next, the expression conversion unit 13

In other words, the i-th digit of ^{_{k j (-1) b · k}} j (i), i + t th digit of k _j (where, t = 1, ..., s ) to 0, and substitutes. Next, the expression conversion unit 13

That is, when the i-th row of k _j is −1, the execution result of the carry_add algorithm (Algorithm 4) is substituted for k _j . As shown in FIG. 6, carry_add (k, i) assigns 0 to the i-th row of k, assuming that the i-th row of k is not 0, that is, k ⁽ⁱ⁾ ≠ 0 as a continuation condition (k ⁽ⁱ⁾ This is an algorithm that repeatedly executes the process of incrementing i, substitutes 1 for the other i-th row of k ⁽ k ⁽ⁱ⁾ ← 1), and outputs k. The 13th line of Algorithm2 indicates the end of the branch process starting from the 11th line. The 14th line indicates the end of the repetition process starting from the 8th line. The 15th line indicates that i ← i + s + 1 is set at the end of the process executed when check is true.

The 16th and subsequent lines of Algorithm2 are processes when the result of check (k _j , i, s, b) is not true in any of j = 1,. Specifically, the expression conversion unit 13 determines that the result of check (k _j , i, s, b) is not true at j = 1,.

That is, when k ₀ ^{(i + 1)} = 0, the 18th to 25th lines of the algorithm are executed. The expression conversion unit 13

That is, −1 is assigned to the i digit of k ₀ and 1 is assigned to the i + 1 digit of k ₀ . Next, the expression conversion unit 13

  That is, from j = 1 to j = m−1, the algorithm is repeatedly operated from the 20th line to the 24th line while incrementing the value of j. Next, the expression conversion unit 13

That is, when i-th digit of k _j is not 0, by substituting -1 i-th digit of k _j, k _j to _{carry_add (k j, i + 1} ) is substituted for the execution result. The 23rd line indicates the end of the branch process starting from the 20th line, the 24th line indicates the end of the iterative process starting from the 19th line, and the 25th line indicates the end of the iterative process starting from the 17th line. The 26th line indicates that the expression conversion unit 13 increments i at the end of the process executed when check is not true. Finally, the expression conversion unit 13

That is, the expression conversion result (k ′ ₀ , ..., k ′ _m−1 ) is output (in the above algorithm, the expression conversion result k is overwritten on k ₀ , ..., k _m−1). ' ₀ , ..., k' get _m-1 ).
<Multiscalar multiplication calculation unit 14, step S14>
The multi-scalar multiplication calculation unit 14 uses the expression-converted k ′ ₀ ,..., K ′ _m−1 and the pre-calculation table Tbl [t], and multi-scalar multiplication Σ _{i = 0} ^m− Points having the same value as ¹ k _i P _i are calculated by, for example, Algorithm 3 shown in FIG. The multi-scalar multiplication calculation unit 14

That is, the pre-calculation table Tbl [t] and the expression conversion result (k ′ ₀ ,..., K ′ _m−1 ) are input. The multi-scalar multiplication calculation unit 14

That is, the calculation result R of multiscalar multiplication is output. The multiscalar multiplication calculation unit 14 uses the infinity point O.

And Next, the multi-scalar multiplication calculation unit 14

That is, from i = n + 1 to i = 0, the value of i is decremented and the calculation is repeated from the third line to the tenth line of the algorithm. Next, the multi-scalar multiplication calculation unit 14

And Next, the multi-scalar multiplication calculation unit 14

That is, the i-th digit of k ′ ₀ is substituted for c, and Σ _{d = 1} ^m−1 k ′ _d ⁽ⁱ⁾ 2 ^d−1 is substituted for t. Next, the multi-scalar multiplication calculation unit 14

That is, when c = 1, R + Tbl [t] is substituted for R. Next, the multi-scalar multiplication calculation unit 14

That is, R-Tbl [-t] is substituted for R when c = -1. The ninth line indicates the end of the iterative process starting from the fifth line. The tenth line indicates the end of the branch process starting from the second line. The multi-scalar multiplication calculation unit 14

That is, the calculation result R of multiscalar multiplication is output.

<Modification 1>
In the above-described first embodiment, the multi-scalar multiplication operation device 1 includes the pre-calculation unit 11. However, the present invention is not limited to this, and the pre-calculation unit 11 can be omitted from the multi-scalar multiplication operation device. In this case, it is assumed that a configuration corresponding to the pre-calculation unit 11 exists in an external device or the like. In this case, it is assumed that the external device performs pre-calculation in advance, and the pre-calculation result is stored in advance as a pre-calculation table by the pre-calculation result storage unit 12. In this case, 2 ^m−1 points calculated in advance are fixed points. In the first embodiment, since the pre-calculation unit executes the calculation every time, the calculated point is a variable point.

<Effects of Multiscalar Multiplication Operation Device of Example 1>
According to the multi-scalar multiplication arithmetic device of the present embodiment, a conversion method is realized such that zero digits where the j-th digit is 0 for all k _i appear with the same probability as the Lim-Lee method, The calculation cost is about the same as the Lim-Lee method, and the pre-calculation table size is halved. In addition, as described in the first modification, when the input point P _i is fixed as a system, the calculation cost in the pre-calculation unit 12 is zero, so that an effect can be obtained.

In the fixed point scalar multiplication in the Lim-Lee method, the size of the pre-calculation table is 2 ^m−1 and the calculation cost is n (1-1 / 2 ^m ) ECADD + nECDBL. In HPB05 system, since all the digits are always non-zero at the reference k ' ₀ , ellipse addition cannot be reduced, so the calculation cost is (n + 1) ECADD + (n + 1) ECDBL Become. The size of the pre-calculation table is 2 ^m-1 . In this embodiment, a new method for converting the expression of k _i and a method for creating a pre-calculation table have been proposed. As a result, the pre-calculation table becomes 2 ^m−1 and the calculation cost can be n (1-1 / 2 ^m ) ECADD + (n + 1) ECDBL. In terms of calculation cost, it is almost the same as the Lim-Lee method, and n / 2 ^m ellipse addition was reduced from the HPB05 method. The size of the pre-calculation table is about half that of the Lim-Lee method, which is the same as the HPB05 method. In other words, in this embodiment, the pre-calculation method and the expression conversion method satisfying the good parts of both the Lim-Lee method and the HPB05 method can be realized.

<The main points of Example 1>
In multi-scalar multiplication on elliptic curves, ellipse addition is omitted when there is a high probability that k _i ^(j) = 0 at all i = 0, ..., m-1 to reduce ellipse addition. can do. According to the multi-scalar multiplication operation apparatus of the present embodiment, the zero density can be increased by using a new expression method while making the pre-calculation table the same as HPB05. As a result, the multi-scalar multiplication is reduced. The table size can be calculated faster.

<Supplementary note>
The apparatus of the present invention includes, for example, a single hardware entity as an input unit to which a keyboard or the like can be connected, an output unit to which a liquid crystal display or the like can be connected, and a communication device (for example, a communication cable) capable of communicating outside the hardware entity. Can be connected to a communication unit, a CPU (Central Processing Unit, may include a cache memory or a register), a RAM or ROM that is a memory, an external storage device that is a hard disk, and an input unit, an output unit, or a communication unit thereof , A CPU, a RAM, a ROM, and a bus connected so that data can be exchanged between the external storage devices. If necessary, the hardware entity may be provided with a device (drive) that can read and write a recording medium such as a CD-ROM. A physical entity having such hardware resources includes a general-purpose computer.

  The external storage device of the hardware entity stores a program necessary for realizing the above functions and data necessary for processing the program (not limited to the external storage device, for example, reading a program) It may be stored in a ROM that is a dedicated storage device). Data obtained by the processing of these programs is appropriately stored in a RAM or an external storage device.

  In the hardware entity, each program stored in an external storage device (or ROM or the like) and data necessary for processing each program are read into a memory as necessary, and are interpreted and executed by a CPU as appropriate. . As a result, the CPU realizes a predetermined function (respective component requirements expressed as the above-described unit, unit, etc.).

  The present invention is not limited to the above-described embodiment, and can be appropriately changed without departing from the spirit of the present invention. In addition, the processing described in the above embodiment may be executed not only in time series according to the order of description but also in parallel or individually as required by the processing capability of the apparatus that executes the processing. .

  As described above, when the processing functions in the hardware entity (the apparatus of the present invention) described in the above embodiments are realized by a computer, the processing contents of the functions that the hardware entity should have are described by a program. Then, by executing this program on a computer, the processing functions in the hardware entity are realized on the computer.

  The program describing the processing contents can be recorded on a computer-readable recording medium. As the computer-readable recording medium, for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used. Specifically, for example, as a magnetic recording device, a hard disk device, a flexible disk, a magnetic tape or the like, and as an optical disk, a DVD (Digital Versatile Disc), a DVD-RAM (Random Access Memory), a CD-ROM (Compact Disc Read Only). Memory), CD-R (Recordable) / RW (ReWritable), etc., magneto-optical recording medium, MO (Magneto-Optical disc), etc., semiconductor memory, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory), etc. Can be used.

  The program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

  A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, the computer reads a program stored in its own recording medium and executes a process according to the read program. As another execution form of the program, the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).

  In this embodiment, a hardware entity is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.

Claims (5)

Prime number p, positive integer e, q = p ^e , finite field

, Where F _q -rational point group on the elliptic curve E is E (F _q ),
Multiscalar multiplication Σ _{i = 0} for _m points P ₀ , ..., P _m-1 and integers k ₀ , ..., k _m-1 greater than or equal to ₀ ^{When m-1} k _i P _i is calculated and a function that outputs a point on E (F _q ) is output, a set of m-1 bits {0,1} (e ₁ , ..., e _{m- 1} ) For all combinations of ₁ ), a point P ₀ + Σ _{i = 1} ^m−1 e _i P _i is calculated, and the calculated 2 ^m−1 points are stored in a pre-calculation table. When,
K ' ₀ , ..., k' _m-1 digits are {0, ± 1} with positive integers and odd numbers k ₀ and integers k ₁ , ..., k _m-1 greater than or equal to ₀ as input Is expressed, and the j-th digit of all k ' _i is 0, or the j-th digit of k' ₀ is {± 1} and the j-th digit of k ' _i other than k' ₀ is 0 or k ' ₀ An expression conversion unit that converts the expression to k ' ₀ , ..., k' _m-1 that satisfies the condition of the same value as the j-th digit of
A multi-scalar multiplication Σ _{i = 0} ^m−1 k _i P _i using the pre-computed table and the expression-converted k ′ ₀ ,..., K ′ _m−1 Multi-scalar multiplication unit including a scalar multiplication unit. Prime number p, positive integer e, q = p ^e , finite field

, Where F _q -rational point group on the elliptic curve E is E (F _q ),
Multiscalar multiplication Σ _{i = 0} for _m points P ₀ , ..., P _m-1 and integers k ₀ , ..., k _m-1 greater than or equal to ₀ ^{When m-1} k _i P _i is calculated and a function that outputs a point on E (F _q ) is output, a set of m-1 bits {0,1} (e ₁ , ..., e _m- A pre-computation result storage unit that stores 2 ^m-1 points P ₀ + Σ _{i = 1} ^m-1 e _i P _i calculated in advance for all combinations of ₁ ) as a pre-calculation table;
K ' ₀ , ..., k' _m-1 digits are {0, ± 1} with positive integers and odd numbers k ₀ and integers k ₁ , ..., k _m-1 greater than or equal to ₀ as input Is expressed, and the j-th digit of all k ' _i is 0, or the j-th digit of k' ₀ is {± 1} and the j-th digit of k ' _i other than k' ₀ is 0 or k ' ₀ An expression conversion unit that converts the expression to k ' ₀ , ..., k' _m-1 that satisfies the condition of the same value as the j-th digit of
A multi-scalar multiplication Σ _{i = 0} ^m−1 k _i P _i using the pre-computed table and the expression-converted k ′ ₀ ,..., K ′ _m−1 Multi-scalar multiplication unit including a scalar multiplication unit. Prime number p, positive integer e, q = p ^e , finite field

, Where F _q -rational point group on the elliptic curve E is E (F _q ),
Multiscalar multiplication Σ _{i = 0} for _m points P ₀ , ..., P _m-1 and integers k ₀ , ..., k _m-1 greater than or equal to ₀ ^{When m-1} k _i P _i is calculated and a function that outputs a point on E (F _q ) is output, a set of m-1 bits {0,1} (e ₁ , ..., e _{m- 1} ) For all combinations of ₁ ), a point P ₀ + Σ _{i = 1} ^m−1 e _i P _i is calculated, and the calculated 2 ^m−1 points are stored in a pre-calculation table. When,
K ' ₀ , ..., k' _m-1 digits are {0, ± 1} with positive integers and odd numbers k ₀ and integers k ₁ , ..., k _m-1 greater than or equal to ₀ as input Is expressed, and the j-th digit of all k ' _i is 0, or the j-th digit of k' ₀ is {± 1} and the j-th digit of k ' _i other than k' ₀ is 0 or k ' ₀ An expression conversion step for converting the expression to k ' ₀ , ..., k' _m-1 that satisfies the condition of being equivalent to the j-th digit of
A multi-scalar multiplication Σ _{i = 0} ^m−1 k _i P _i using the pre-computed table and the expression-converted k ′ ₀ ,..., K ′ _m−1 A multi-scalar multiplication method including a scalar multiplication calculation step. Prime number p, positive integer e, q = p ^e , finite field

, Where F _q -rational point group on the elliptic curve E is E (F _q ),
Multiscalar multiplication Σ _{i = 0} for _m points P ₀ , ..., P _m-1 and integers k ₀ , ..., k _m-1 greater than or equal to ₀ ^{When m-1} k _i P _i is calculated and a function that outputs a point on E (F _q ) is output, a set of m-1 bits {0,1} (e ₁ , ..., e _m- A pre-calculation result storing step for storing 2 ^m-1 points P ₀ + Σ _{i = 1} ^m-1 e _i P _i calculated in advance for all combinations of ₁ ) as a pre-calculation table;
K ' ₀ , ..., k' _m-1 digits are {0, ± 1} with positive integers and odd numbers k ₀ and integers k ₁ , ..., k _m-1 greater than or equal to ₀ as input Is expressed, and the j-th digit of all k ' _i is 0, or the j-th digit of k' ₀ is {± 1} and the j-th digit of k ' _i other than k' ₀ is 0 or k ' ₀ An expression conversion step for converting the expression to k ' ₀ , ..., k' _m-1 that satisfies the condition of being equivalent to the j-th digit of
A multi-scalar multiplication Σ _{i = 0} ^m−1 k _i P _i using the pre-computed table and the expression-converted k ′ ₀ ,..., K ′ _m−1 A multi-scalar multiplication method including a scalar multiplication calculation step.   A program for causing a computer to function as the multi-scalar multiplication operation device according to claim 1 or 2.

Images