JP5379700B2 - Scalar multiplication unit, scalar multiplication method, scalar multiplication program, recording medium - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To realize a simultaneous scalar multiple arithmetic method applicable to an encoded binary system. <P>SOLUTION: The scalar multiple arithmetic unit includes a mean value calculation part, an original calculation part, and a scalar multiple value calculation part. The mean value calculation part calculates a mean value e<SB>d(1)</SB>, ...,<SB>d(M)</SB>(n) for each combination d(1), ..., d(M). The original value calculation part calculates E<SB>d(1)</SB>, ...,<SB>d(M)</SB>G for the all combinations d(1), ..., d(M) calculated by the mean value calculation part. The scalar multiple value calculation part carries out the process of having as a scalar multiple value E<SB>m</SB>G obtained by subtracting the sum of all E<SB>d(1)</SB>, ...,<SB>d(M)</SB>G with the d(m) value of -1 from the sum of all E<SB>d(1)</SB>, ...,<SB>d(M)</SB>G with the d(m) value of 1 for m=1 to M. <P>COPYRIGHT: (C)2011,JPO&amp;INPIT

Description

  The present invention relates to a data encryption device and an authentication device, and particularly relates to a scalar multiplication device, a scalar multiplication operation method, a scalar multiplication operation program, and a recording medium for efficiently realizing information security.

In the operation cost of elliptic curve cryptography and signature, the operation of multiplying the group element G by scalar occupies a large proportion. In this specification, a method for efficiently performing calculation when performing a plurality of scalar multiplications simultaneously will be described. The same argument can be applied to the power of the multiplicative group, but in this specification, the description is unified to a scalar multiple. M integers _E 1 entered on the original G in the group, ..., _E 1 G for _{E M,} ..., that simultaneous scalar multiplication calculation for obtaining the _{E M} G. In order to efficiently execute the simultaneous scalar multiplication, two types of strategies can be considered. One is a method of pre-calculating G in advance and storing it in a storage. This method is highly effective when there is a sufficient amount of storage. The other is a method that does not require prior calculations. In this specification, the latter method is examined.

As a method of performing scalar multiplication without pre-computation, a method of performing binary computation and performing binary computation and addition (binary computation method), the NAF method of Non-Patent Document 1, the Non-Patent Document 2, There is a Booth method. On the other hand, methods (Non-Patent Documents 3, 4, 5, etc.) that improve efficiency by simultaneously performing a plurality of scalar multiplications have been proposed.
FIG. 1 is a diagram showing a processing flow of the binary arithmetic method. In this processing flow, M is an integer of 2 or more, m is an integer of 1 to M, N is a positive integer, n is an integer of 0 to N, G is a group element, E _{1 ,.}

A value E ₁ G,..., E _M G obtained by multiplying the original G by a scalar is obtained. In the binary arithmetic method, when _Em is a random value, the cost of the binary arithmetic method is MN times for the double operation and (1/2) MN times for the addition operation.

  In addition, when performing scalar multiplication with a group that is easy to perform −1 multiplication, such as a point on an elliptic curve, a signed binary method (NAF method: Non-Patent Document 1) is often used. In the binary operation method, one scalar multiplication operation is performed by N times of the double operation and N / 2 times of addition, whereas in the binary method of signing, one operation is performed by N times of the double operation and N / 3 times of the addition operation. Can perform scalar multiplication. Therefore, in M scalar multiplication operations, the doubling operation is MN times and the addition operation is MN / 3 times.

Next, the Tsuruoka method of Non-Patent Document 3 will be described. First, a case where the number of input scalar values is two will be described. N is a positive integer, n is an integer between 0 and N, and E ₁ and E ₂ are

A scalar, G expressed as And
H _1,1 = E ₁ ∧E ₂
H _1,0 = E ₁ -E _1,1
H _0,1 = E ₂ −E _1,1
Intermediate values H _1,1 , H _1,0 , H _0,1 are obtained as follows. However, E ₁ ∧E ₂ indicates that the binary representations E ₁ and E ₂ are logically ANDed for each bit of each digit. The nth bit of E ₁ and E ₂ can be expressed as h ₁ (n) and h ₂ (n) as described above. When the n-th bit of H _1,1 , H _1,0 , H _0,1 is expressed as h _1,1 (n), h _1,0 (n), h _0,1 (n), h ₁ (n ), H ₂ (n) and h _1,1 (n), h _1,0 (n), h _0,1 (n) are as shown in FIG.

If E ₁ and E ₂ are uncorrelated, the Hamming weights of H _1,1 , H _1,0 , H _0,1 are average N / 4, and H _1,1 G, H _1,0 G, H _The amount of calculation for simultaneously _{obtaining 0,1} G using the binary arithmetic method is N times for the doubling operation and an average of (3/4) N times for the addition. Using these, E ₁ G and E ₂ G are obtained as follows.
E ₁ G = H _1,0 G + H _1,1 G
E ₂ G = H _0,1 G + H _1,1 G
If E ₁ G and E ₂ G are obtained by this method (when M = 2), the number of additions is (3/4) N + 2, which is smaller than the number of additions N in the binary arithmetic method. Therefore, the Tsuruoka method is faster than the binary arithmetic method.

FIG. 3 shows a processing flow when performing M simultaneous scalar multiplications by the Tsuruoka method. In the algorithm, in order to simplify the description, the intermediate value H _{d (1),..., D (M) is set} to B _k , and the nth bit h _{d (1 )} of the intermediate value H _{d (1) ,. ),..., D (M)} (n) is expressed as b _k (n) (where 1 ≦ k ≦ 2 ^M −1),

There is a relationship. For example, when M = 2, b ₁ (n) = h _1,0 (n), b ₂ (n) = h _0,1 (n), b ₃ (n) = h _1,1 (n) It is. Since obtaining b _k (n) _where n = 1 to N is obtaining B _k , b _k (n) is also referred to as an intermediate value.

In the case of the Tsuruoka method, the doubling operation is MN times, and the addition operation is (1- (1/2) ^M ) N + α times. If the method of FIG. 3 is performed as it is, α = m · 2 ^M−1 . However, by using the method of Non-Patent Document 5, α = 2 ^{M + 1} −2M−2 times.

A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography. CRC Pres, 1996. Andrew D. Booth, “A Signed Binary Multiplication Technique”, The Quarterly Journal of Mechanics and Applied Mathematics 1951 4 (2), p.236-240, 1951. Tsuruoka Yukio, “Fast Multiplicative Power Calculation Algorithm”, Extended Abstract for JW-ISC'93, IEICE Technical Report. ISEC, Information Security 93 (295), pp.103-111, 1993. David M'Ra: ichi and David Naccache, “Batch Exponentiation: A Fast DLP-based Signature Generation Strategy”, CCS '96, Proceedings of the 3rd ACM Conference on Computer and Communications Security, March 14-16 1996, New Delhi, India , ACM, 1996. Byungchun Chung, Junbeom Hur, Heeyoul Kim, Seong-Min Hong and Hyunsoo Yoon, “Improved batch exponentiation”, Information Processing Letters 109 (2009) 832-837.

  The methods of Non-Patent Documents 3, 4, and 5 are also based on the binary method. When M = 2, there is a drawback that the efficiency is lower than that of the NAF method (Non-Patent Document 1). An object of the present invention is to extend the concept of the Tsuruoka method of Non-Patent Document 3 and realize a simultaneous scalar multiplication method applicable to a signed binary method.

In the scalar multiplication apparatus of the present invention, M is an integer of 2 or more, m is an integer of 1 to M, N is a positive integer, n is an integer of 0 to N, E _{1 ,.}

Scalar, the original group of G which is expressed as the scalar _E 1 to the original G, ..., is a value obtained by multiplying each _{E M} scalar Baichi _E 1 G, ..., determine the _{E M} G. The scalar multiplication unit of the present invention includes an intermediate value calculation unit, an original calculation unit, and a scalar multiplication value calculation unit. The intermediate value calculation unit sets d (m) ε {0, 1, −1} as
E _{d (1)} when the _{d (m) = e m (} n) for all _{m, ..., d (M)} (n) = 1
When d (m) = − e _m (n) for all m, ed ( _{1),..., D (M)} (n) = − 1
In other cases, _{ed (1),..., D (M)} (n) = 0
_{, D (M)} (n) is changed to d (1) = 0,..., D (M) = 0 except for d (1),. combinations) (however, d '(1) = ( - 1) × d (1), ..., d' (M) = (- 1) × e d (1) to d (M) is _{established, ..., d (M)} (n) and _{ed ′ (1),..., D ′ (M)} (n) are only one of them). It is not necessary to obtain the case of d (1) = 0,..., d (M) = 0 because it is not used in subsequent calculations. The proviso of reasons, d '(1) = ( - 1) × d (1), ..., d' (M) = (- 1) × when d (M) is _{established, e d (1) ,..., D (M)} (n) = (− 1) × e _{d ′ (1),..., D ′ (M)} (n) holds, and it is not necessary to obtain both. The original calculation unit calculates all combinations of d (1),..., D (M) obtained by the intermediate value calculation unit.

Ask for. The scalar multiple calculator calculates from the sum of all E _{d (1),..., D (M)} G where the value of d (m) is 1, all the E's whose value of d (m) is −1. _{d (1),..., d (M)} A process of subtracting the sum of G to obtain a scalar multiple value E _m G is performed from m = 1 to M.

  According to the scalar multiplication unit of the present invention, the concept of simultaneous scalar multiplication can be applied to a signed binary method, so that when a plurality of scalar values are respectively multiplied by a group, the amount of calculation is reduced compared to the conventional technique. Less.

The figure which shows the processing flow of a binary arithmetic method. The figure which shows the nth bit conversion by the Tsuruoka method. The figure which shows the processing flow in the case of performing M simultaneous scalar multiplication by the Tsuruoka method. The figure which shows the function structural example of the scalar multiplication apparatus of this invention. The figure which shows the processing flow of the scalar multiplication apparatus of this invention. Relationship between nth bits e ₁ (n), e ₂ (n) of scalars E ₁ , E ₂ and intermediate values _{ed (1), d (2)} (n) to be obtained when M = 2 FIG. It shows M = scalar _E 1 in the case of 2, n bit _e 1 of _{E 2 (n), e 2} (n), and an intermediate value _{e d (1),} the relationship between _{d (2) (n).} N-th bit _e 1 scalar _{E 1,} E 2, _{E 3} in the case of _{M = 3 (n), e} 2 (n), e 3 (n), and must be determined intermediate value _{e d (1), The} figure which shows the relationship of _{d (2), d (3)} (n). The nth bit e ₁ (n), e ₂ (n), e ₃ (n) of the scalars E ₁ , E ₂ , E ₃ and the intermediate values _{ed (1), d (2)} when M = 3 _{, D (3)} A first diagram showing the relationship (n). The nth bit e ₁ (n), e ₂ (n), e ₃ (n) of the scalars E ₁ , E ₂ , E ₃ and the intermediate values _{ed (1), d (2)} when M = 3 _{, D (3) A} second diagram showing the relationship (n). The figure which shows the example of the detailed process flow of the scalar multiplication apparatus of this invention. It shows a flow for converting the NAF method scalar E _m of binary representation scalar E _m signed binary representation. The figure which shows 0-8 converted into binary representation with a sign by the binary expression 0-8 and NAF method. It shows a flow which converts scalar E _m of binary representation scalar E _m of signed binary representation by Booth Algorithm. The figure which shows the relationship between the 2n-2 digit-2n digit expressed by the binary system, and the 2n-1 digit and the 2n digit converted into the signed binary system expression by Boot method. The figure for comparing the operation amount of each system in the case of multiplying the group element by M N-digit scalars.

  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.

Device Configuration and Processing Flow FIG. 4 shows a functional configuration example of the scalar multiplication unit of the present invention, and FIG. 5 shows a processing flow of the scalar multiplication unit of the present invention. The scalar multiplication apparatus 100 of the present invention is configured such that M is an integer of 2 or more, m is an integer of 1 to M, N is a positive integer, n is an integer of 0 to N, E _{1 ,.}

Scalar, the original group of G which is expressed as the scalar _E 1 to the original G, ..., is a value obtained by multiplying each _{E M} scalar Baichi _E 1 G, ..., determine the _{E M} G. The scalar multiplication unit 100 includes an intermediate value calculation unit 120, an original calculation unit 130, a scalar multiple calculation unit 140, and a recording unit 190. The intermediate value calculation unit 120 sets d (m) ε {0, 1, −1} as
E _{d (1)} when the _{d (m) = e m (} n) for all _{m, ..., d (M)} (n) = 1
When d (m) = − e _m (n) for all m, ed ( _{1),..., D (M)} (n) = − 1
In other cases, _{ed (1),..., D (M)} (n) = 0
_{, D (M)} (n) is changed to d (1) = 0,..., D (M) = 0 except for d (1),. combinations) (however, d '(1) = ( - 1) × d (1), ..., d' (M) = (- 1) × e d (1) to d (M) is _{established, ..., d (M)} (n) and _{ed ′ (1),..., D ′ (M)} (n) (only one of them) are obtained (S120). It is not necessary to obtain the case of d (1) = 0,..., d (M) = 0 because it is not used in subsequent calculations. The proviso of reasons, d '(1) = ( - 1) × d (1), ..., d' (M) = (- 1) × when d (M) is _{established, e d (1) ,..., D (M)} (n) = (− 1) × e _{d ′ (1),..., D ′ (M)} (n) holds, and it is not necessary to obtain both. Therefore, the number of intermediate values is (3 ^M −1) / 2. In addition, either of the combinations in which d ′ (1) = (− 1) × d (1),..., D ′ (M) = (− 1) × d (M) may be obtained.

  The original calculation unit 130 determines all combinations of d (1),..., D (M) obtained by the intermediate value calculation unit 120.

Is obtained (S130). The scalar multiple calculation unit 140 calculates all the values of d (m) of −1 from the sum of all E _{d (1),..., D (M)} G of d (m) of 1. E _{d (1),..., D (M) The} value obtained by subtracting the sum of G is set to a scalar multiple value E _m G from m = 1 to M (S140). Expressed as an expression

become that way. The recording unit 190 includes an original G, a scalar E _m , an intermediate value ed _{(1),..., D (M)} (n), an E _{d (1), ..., d (M)} G, and a scalar multiple E _m G. Etc. are recorded.
In addition, the scalar multiplication unit 100 may include the expression conversion unit 110 when the scalar input to the scalar multiplication unit 100 is binary representation. The expression conversion unit 110

A scalar E ₁ ,..., E _M (binary representation scalar) expressed as

Are converted into scalars E ₁ ,..., E _M (scalar of signed binary representation) (S110). Specific conversion methods include the NAF method and Boot method.
Description of Principle First, the case of M = 2 will be described. N-th bit _e 1 scalar _E 1, _{E 2} if 6 of M = 2 and _{(n), e 2 (n} ), must be determined intermediate value _{e d (1), d (} 2) (n ). Further, n-th bit _e 1 scalar _E 1, _{E 2} if the FIG. 7 of the _{M = 2 (n), e} 2 (n), and an intermediate value _{e d (1), d (} 2) of the (n) Show the relationship.

When the values of the nth bits e ₁ (n) and e ₂ (n) of the scalars E ₁ and E ₂ are 0, the result is 0 regardless of what multiplication is performed. Therefore, scalar multiplication can be performed if the case where the values of e ₁ (n) and e ₂ (n) are other than 0 is taken into consideration. In the binary system, the only value other than 0 is 1. Therefore, in the Tsuruoka method, h _1,0 (n), h _0,1 (n), and h _1,1 (n) should be considered. On the other hand, in the signed binary system adopted by the present invention, there are 1 and −1 as values other than 0. Therefore, as shown in FIG. 6, an intermediate value is obtained when the values of e ₁ (n) and e ₂ (n) are 1 or −1. Possible combinations as intermediate values are e _1,1 (n), e _1,0 (n), e _{1, -1} (n), e _0,1 (n), e _0,0 (n), e _{0, -1} (n), e- _{1 , 1} (n), e- ₁ , ₀ (n), e- _{1, -1} (n). However, since e _0,0 (n) is e ₁ (n) = 0 and e ₂ (n) = 0, there is no need to consider in multiplication. Also, e _1,1 (n) = − e _{−1, −1} (n), e _1,0 (n) = e _−1,0 (n), e _{1, −1} (n) = e _{−1 , 1} (n), e _0,1 (n) = e _{0, −1} (n), the relationship is established, and if one is obtained, the other need not be obtained. Therefore, it is sufficient to obtain the four intermediate values shown in FIG. In FIG. 6, four of e _1,1 (n), e _1,0 (n), e _{1, -1} (n), and e _0,1 (n) are selected, but d ′ You may select the other where (1) = (− 1) × d (1) and d ′ (2) = (− 1) × d (2).

The relationship between e ₁ (n), e ₂ (n) and intermediate values _{ed (1), d (2)} (n) is as shown in FIG.
When d (1) = e ₁ (n) and d (2) = e ₂ (n), _{ed (1), d (2)} (n) = 1
When d (1) = − e ₁ (n) and d (2) = − e ₂ (n), _{ed (1), d (2)} (n) = − 1
In other cases, _{ed (1), d (2)} (n) = 0
It is.

As can be seen from FIG. 7, 2/3 is other than 0 in the column of e ₁ (n) and e ₂ (n). On the other hand, in the columns of e _1,1 (n), e _1,0 (n), e _{1, -1} (n), e _0,1 (n), only two (only 2/9) are 0. Other than Therefore, there are fewer parts that must actually be multiplied. Therefore, when M = 2, the average number of additions of the NAF method is 2 / 3N, whereas when the present invention is applied to the NAF method, the average number of additions is (5/9) N + 4. , (1/9) N-4 additions can be reduced.

N-th bit _e 1 scalar _{E 1,} E 2, _{E 3} where in Figure 8 of the _{M = 3 (n), e} 2 (n), e 3 (n), and must be determined intermediate value _{e d ( 1), d (2), d (3)} (n) is shown. As described above, since the number of intermediate values _{ed (1), d (2), d (3)} (n) to be obtained is (3 ^M −1) / 2, when M = 3, 13 pieces. N-th bit _e 1 scalar _{E 1,} E 2, _{E 3} in the case of M = 3 in FIG. _{9,10 (n), e 2 (} n), e 3 (n), and an intermediate value _{e d (1) , D (2), d (3)} (n). Also in this example, 2/3 is other than 0 in the column of e ₁ (n), e ₂ (n), and e ₃ (n). On the other hand, in the column of intermediate values _{ed (1), d (2), d (3)} (n), only two (only 2/27) are non-zero. Therefore, the number of calculations can be reduced. Similarly, when M> 3, the number of calculations can be reduced by using the intermediate values _{ed (1),..., D (M)} (n).

Detailed processing flow (specific example of algorithm)
An example of a detailed processing flow of the scalar multiplication unit of the present invention is shown in FIG. Step 1 and Step 2 in FIG. 11 are preprocessing, and each variable is set to an initial value. Step 3 corresponds to S120 of FIG. 5, Step 4 corresponds to S130, and Step 5 corresponds to S140. Step 6 is a process for outputting the result.

In Step 3, Step 4, and Step 5, the intermediate value E _{d (1),..., D (M)} is _represented by B _k and the nth bit of the intermediate value E _{d (1)} ,. e _{d (1),..., d (M)} (n) is expressed as b _k (n) (where 1 ≦ k ≦ 2 ^M −1),

There is a relationship. For example, when M = 2, b ₁ (n) = e _1,0 (n), b ₋₁ (n) = e _−1,0 (n), b ₃ (n) = e _0,1 ( n), b ₋₃ (n) = e _{0, −1} (n), b ₄ (n) = h _1,1 (n), b ₋₂ (n) = h _{1, −1} (n), b ₂ (n) = h− _1,1 (n), b− ₄ (n) = h− _{1, −1} (n). Since obtaining b _k (n) _where n = 1 to N is obtaining B _k , b _k (n) is also called an intermediate value. Since the relationship between k and d (1),..., D (M) is determined in this way, if k is changed from 1 to (3 ^M −1) / 2, d (1) = 0,. , D (M) = 0 all combinations other than d (1),..., D (M) (where d ′ (1) = (− 1) × d (1),..., D ′ (M) _{Ed (1), ..., d (M)} (n) and _{ed '(1), ..., d' (M)} (n) satisfy only = (-1) * d (M) ).

FIG. 12 shows a flow of converting a binary expression scalar E _m to a signed binary expression scalar E _m by the NAF method, and FIG. 13 shows 0 to 8 expressed by the binary expression and 0 converted to a signed binary expression by the NAF method. -8 are shown. FIG. 14 shows a flow of converting a binary expression scalar E _m to a signed binary expression scalar E _m by the Boot method, and FIG. 15 shows a binary expression of 2n−2 to 2n digits and a sign by the Boot method. The relationship between 2n-1 digits and 2n digits converted to binary representation is shown. The NAF method is a method in which the probability of 0 for each digit of a scalar in a signed binary representation is set to 2/3, the probability of 1 or −1 to 1/3. In addition, the Boot method has a probability of 0 for each digit of a scalar in a signed binary representation expressed as 5/8, a probability of 1 or −1 as 3/8 (an odd number has a probability of 0, and an even number has a probability of 0. This is a method of setting the probability of 3/4). The present invention can be combined with any signed binary method other than the NAF method and the Booth method.

Comparison of Computation Amounts FIG. 16 is a diagram for comparing the computation amounts of the respective methods in the case where M N-digit scalars are multiplied by group elements. In any method, since the doubling operation is MN times, only the number of additions is compared in FIG. However, α = 2 ^{M + 1} −2M−2 and β = 3 ^M −2M−1. It should be noted that the NAF method is more efficient than the Boot method when calculating one scalar multiplication by a signed binary method, but the simultaneous scalar multiplication may be reversed. Specifically, when M ≧ 5, the Boot method is more efficient than the NAF method. As in this example, the efficiency may be improved by combining with the present invention regardless of the efficiency of the single device, so that a signed binary method may be selected as appropriate.

  For example, when M = 2, the present invention + NAF method can increase the speed by 11% compared with the conventional NAF method (NAF method alone). As described above, the present invention extends the concept of the Tsuruoka method of Non-Patent Document 3 and realizes a simultaneous scalar multiplication method applicable to a signed binary method. In addition, the number of operations can be reduced including the case of M = 2.

Program, Recording Medium When the above-described configuration is realized by a computer, the processing contents of functions that each device should have are described by the program. The processing functions are realized on the computer by executing the program 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.

  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, the present apparatus is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.

  The present invention can be used for an apparatus for encrypting data or an apparatus for authenticating data that simultaneously performs a plurality of scalar multiplications on a group element.

100 scalar multiplication unit 110 representation conversion unit 120 intermediate value calculation unit 130 original calculation unit 140 scalar double value calculation unit 190 recording unit

Claims (10)

M is an integer of 2 or more, m is an integer of 1 to M, N is a positive integer, n is an integer of 0 to N, E ₁ ,..., E _M

Scalar, the original group of G which is expressed as the scalar E ₁ to the original _G, ..., is a value obtained by multiplying each E _M scalar Baichi E _{1 G,} ..., scalar multiplication calculation for obtaining the E M _G A device,
As d (m) ε {0,1, -1},
E _{d (1)} when the _{d (m) = e m (} n) for all _{m, ..., d (M)} (n) = 1
When d (m) = − e _m (n) for all m, ed ( _{1),..., D (M)} (n) = − 1
In other cases, _{ed (1),..., D (M)} (n) = 0
Intermediate values _{ed (1),..., D (M)} (n) that are
All combinations of d (1),..., d (M) other than d (1) = 0,..., d (M) = 0 (where d ′ (1) = (− 1) × d (1) ,..., D ′ (M) = (− 1) × d (M) ed _{(1),..., D (M)} (n) and _{ed ′ (1),.} (N) is an intermediate value calculation unit obtained for only one),
For all combinations of d (1),..., D (M) obtained by the intermediate value calculator,

An original calculation unit for obtaining
From the sum of all E _{d (1),..., d (M)} G where the value of d (m) is 1, all E _{d (1),. d (M) a} scalar multiplication value calculation unit that performs a process for subtracting the sum of G to make a scalar multiplication value E _m G from m = 1 to M;
A scalar multiplication unit comprising: N is a positive integer, n is an integer between 0 and N, and E ₁ and E ₂ are

A scalar multiplication unit for obtaining scalar double values E ₁ G and E ₂ G, which are values obtained by multiplying the element G by scalars E ₁ and E ₂ , respectively. ,
d (1) ∈ {0,1, −1}, d (2) ∈ {0,1, −1}
When d (1) = e ₁ (n) and d (2) = e ₂ (n), _{ed (1), d (2)} (n) = 1
When d (1) = − e ₁ (n) and d (2) = − e ₂ (n), _{ed (1), d (2)} (n) = − 1
In other cases, _{ed (1), d (2)} (n) = 0
The intermediate values _{ed (1), d (2)} (n) are
Any combination of d (1) and d (2) other than d (1) = 0 and d (2) = 0 (where d ′ (1) = (− 1) × d (1) and d ′ ( 2) = (− 1) × d (2) holds, _{ed (1),..., D (M)} (n) and _{ed ′ (1)} ,. An intermediate value calculator for
For all the combinations of d (1) and d (2) obtained by the intermediate value calculator,

An original calculation unit for obtaining
From the sum of all E _{d (1), d (2)} G with a d (m) value of 1, all E _{d (1), d (2) with} a d (m) value of −1 A scalar multiple calculation unit that performs a process of subtracting the sum of G as a scalar multiple E _m G from m = 1 to M;
A scalar multiplication unit comprising: The scalar multiplication unit according to claim 1,

The scalars E ₁ , ..., E _M expressed as

A scalar multiplication unit comprising an expression conversion unit for converting into scalars E ₁ ,..., E _M expressed as follows. The scalar multiplication unit according to claim 1,

The scalars E ₁ , ..., E _M expressed as

A scalar multiplication unit comprising an expression conversion unit for converting into scalars E ₁ ,..., E _M expressed as follows. M is an integer of 2 or more, m is an integer of 1 to M, N is a positive integer, n is an integer of 0 to N, E ₁ ,..., E _M

Scalar, the original group of G which is expressed as the scalar E ₁ to the original _G, ..., is a value obtained by multiplying each E _M scalar Baichi E _{1 G,} ..., scalar multiplication calculation for obtaining the E M _G A method,
The intermediate value calculation unit sets d (m) ε {0, 1, −1} as
E _{d (1)} when the _{d (m) = e m (} n) for all _{m, ..., d (M)} (n) = 1
When d (m) = − e _m (n) for all m, ed ( _{1),..., D (M)} (n) = − 1
In other cases, _{ed (1),..., D (M)} (n) = 0
Intermediate values _{ed (1),..., D (M)} (n) that are
All combinations of d (1),..., d (M) other than d (1) = 0,..., d (M) = 0 (where d ′ (1) = (− 1) × d (1) ,..., D ′ (M) = (− 1) × d (M) ed _{(1),..., D (M)} (n) and _{ed ′ (1),.} An intermediate value calculating step for (n) is only one);
For all combinations of d (1),..., D (M) obtained by the original calculation unit in the intermediate value calculation step,

An original calculation step for obtaining
The scalar multiple calculator calculates from the sum of all E _{d (1),..., D (M)} G where the value of d (m) is 1, and from the sum of all E d (m) values of −1. _{d (1),..., d (M)} Scalar multiple calculation step for performing the process of subtracting the sum of G from S = 1 to M for the scalar multiple E _m G;
A scalar multiplication method having: N is a positive integer, n is an integer between 0 and N, and E ₁ and E ₂ are

A scalar multiplication method for obtaining scalar double values E ₁ G and E ₂ G, which are values obtained by multiplying the element G by scalars E ₁ and E ₂ , respectively. ,
The intermediate value calculation unit sets d (1) ε {0,1, −1} and d (2) ε {0,1, −1} as
When d (1) = e ₁ (n) and d (2) = e ₂ (n), _{ed (1), d (2)} (n) = 1
When d (1) = − e ₁ (n) and d (2) = − e ₂ (n), _{ed (1), d (2)} (n) = − 1
In other cases, _{ed (1), d (2)} (n) = 0
The intermediate values _{ed (1), d (2)} (n) are
Any combination of d (1) and d (2) other than d (1) = 0 and d (2) = 0 (where d ′ (1) = (− 1) × d (1) and d ′ ( 2) = (− 1) × d (2) holds, _{ed (1),..., D (M)} (n) and _{ed ′ (1)} ,. Intermediate value calculation step for (only one)
For all the combinations of d (1) and d (2) obtained by the original calculation unit in the intermediate value calculation step,

An original calculation unit for obtaining
The scalar multiple calculator calculates from the sum of all E _{d (1) and d (2)} G whose value of d (m) is 1, all E _{d (} whose value of d (m) is −1. _{1), d (2) A} scalar multiple calculation step in which a value obtained by subtracting the sum of G is set to a scalar multiple E _m G for m = 1 to M;
A scalar multiplication method having: The scalar multiplication method according to claim 5, wherein
The expression converter

The scalars E ₁ , ..., E _M expressed as

A scalar multiplication method characterized by having an expression conversion step of converting into scalars E ₁ ,..., E _M expressed as follows. The scalar multiplication method according to claim 5, wherein
The expression converter

The scalars E ₁ , ..., E _M expressed as

A scalar multiplication method characterized by having an expression conversion step of converting into scalars E ₁ ,..., E _M expressed as follows.   A scalar multiplication operation program for operating a computer as the scalar multiplication apparatus according to claim 1.   A computer-readable recording medium on which the scalar multiplication program according to claim 9 is recorded.

Images