JP5268066B2 - Conversion operation device, method, program, and recording medium - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a device or the like for converting an optional binary digit string to points on an elliptical curve E(GF(3<SP>m</SP>)): y<SP>2</SP>=x<SP>3</SP>-x+b defined on a finite field of a reference number 3 at a high speed. <P>SOLUTION: A conversion part 105 converts the optional binary digit string ID belong to ä0, 1}<SP>*</SP>to an origin y belong to GF(3<SP>m</SP>) of the finite field GF(3<SP>m</SP>), and a finite field operation part 106 calculates t=y<SP>2</SP>-b belong to GF(3<SP>m</SP>). A 1/3 trace mapping operation part 108 calculates 1/3 trace mapping C(t) making input of t, a finite field operation part 109 calculates x=C(t)<SP>3</SP>-C(t) belong to GF(3<SP>m</SP>), and obtains an x coordinate (x belong to GF(3<SP>m</SP>)) of the elliptical curve E(GF(3<SP>m</SP>)): y<SP>2</SP>=x<SP>3</SP>-x+b. <P>COPYRIGHT: (C)2010,JPO&amp;INPIT

Description

  The present invention relates to a cryptographic technique, and more particularly to a technique for converting an arbitrary bit string into a point on an elliptic curve defined on a finite field of characteristic 3.

Public key cryptography is known as an indispensable technology for information communication technology. However, public key cryptography such as RSA has problems that management of public keys is complicated and management cost is high. In recent years, as a technique for solving such a problem, ID-based encryption using an arbitrary bit string IDε {0,1} ^* as a public key has been proposed (for example, see Non-Patent Document 1).

In ID-based cryptography, an arbitrary bit string ID∈ {0,1} ^* is converted to a point on an elliptic curve, and pairing or elliptic scalar multiplication is performed on this elliptic curve to perform encryption processing or secret Perform key generation processing. In recent years, attention has been focused on a supersingular elliptic curve defined on a finite field GF (3 ^m ) of characteristic 3 as an elliptic curve capable of performing pairing operations at high speed.

An arbitrary bit string ID∈ {0,1} ^* is an elliptic curve E (GF (3 ^m )) defined on the finite field GF (3 ^m ): y ² = x ³ -x + b (b = ± 1) As a conventional method for converting to the upper point, there is a method shown in Non-Patent Document 2. The method shown in Non-Patent Document 2 will be described below.

<Step S1> Using a hash function such as MFG (mask generation function), an arbitrary bit string ID∈ {0,1} ^* is converted into an element on a finite field GF (3 ^m ), and the elliptic curve E (GF (3 ^m )): x coordinate of y ² = x ³ −x + b (x∈GF (3 ^m )).
<Step S2> Substituting x∈GF (3 ^m ) obtained in Step S1 into the right side of the elliptic curve E (GF (3 ^m )): y ² = x ³ −x + b, y ² ∈GF (3 ^m ).
<Step S3> The square root of y ² ∈GF (3 ^m ) obtained in Step S2 is calculated as follows ([Step S3a] to [Step S3d] to obtain y∈GF (3 ^m ), provided that k = (m-1) / 2 = (k _v-1 , ... k ₀ ) ₂ and k _v-1 , ... k ₀ are bits in each digit when k is expressed in binary. Indicates the value {0,1}.
[Step S3a] s = c = x ³ −x + bεGF (3 ^m ).
[Step S3b] For each i from i = ν−2 to 0, the following << Step S3ba >> and << Step S3bb >> are executed.
<< Step S3ba >> It is assumed that t = s.
<< Step S3bb >>
If k _i = 1,

s = c ・ t∈GF (3 ^m )… (2)
The operation of
If k _i = 0,
s = c ・ t∈GF (3 ^m )… (4)
Perform the operation.

[Step S3c]
c = c ・ s ⁶ ∈GF (3 ^m )… (5)
Perform the operation.
[Step S3d] Let c be y∈GF (3 ^m ).
<Step S4> Output (x, y) εE (GF (3 ^m )).

D. Boneh and M. Franklin, "Identify-based encryption from the Weil pairing", CRYTPO 2001. LNCS, vol. 2139, pp. 213-229, Springer, 2001. Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M. "Efficient algorithms for pairing-based cryptosystems", CRYPTO 2002. LNCS, vol.2442, pp.354-368, Springer, Heidelberg (2002).

However, in the method of Non-Patent Document 2, it is necessary to perform multiplication on the finite field GF (3 ^m ) having a high calculation cost a plurality of times in the iterative processing consisting of << Step S3ba >> and << Step S3bb >>. Therefore, high-speed calculation is difficult with the method of Non-Patent Document 2.

  The present invention has been made in view of such a point, and provides a technique capable of converting an arbitrary bit string to a point on an elliptic curve defined on a characteristic 3 finite field at high speed. With the goal.

In the present invention, an arbitrary bit string is converted into an element y∈GF (3 ^m ) of a finite field GF (3 ^m ), and the transformation 3 of the trace mapping is used to obtain a characteristic 3 corresponding to the element y∈GF (3 ^m ). The x coordinate (x∈GF (3 ^m )) of the elliptic curve E (GF (3 ^m )): y ² = x ³ −x + b defined on the finite field GF (3 ^m ) of is obtained. The deformation operation of the trace map can be realized by the Frobenius map on the finite field GF (3 ^m ) and the addition operation, and high-speed calculation is possible.

In the first aspect of the present invention, the conversion unit converts an arbitrary bit string into an element y∈GF (3 ^m ) of a finite field GF (3 ^m ), and the element y obtained by the first finite field operation unit is obtained by the conversion unit. ∈GF (3 ^m ) is used to calculate t = y ² −b∈GF (3 ^m ), and the 1/3 trace mapping operation unit uses t obtained by the first finite field operation unit,

The second finite field computation unit computes x = C (t) ³ -C (t) ∈GF (3 ^m ) using C (t) obtained by the 1/3 trace mapping computation unit The output unit outputs x obtained by the second finite field computation unit and the element y) obtained by the conversion unit. The first mode is applied when m is a positive integer satisfying 2≡m mod 3, and t∈GF (3 ^m ) used in the 1/3 trace mapping operation unit is

And the element y output from the output unit satisfies Tr (y ² −b) = 0.

In the second aspect of the present invention, the conversion unit converts an arbitrary bit string into an element y∈GF (3 ^m ) of a finite field GF (3 ^m ), and the first finite field operation unit is obtained by conversion in the conversion unit. The element y∈GF (3 ^m ) is used, t = y ² −b∈GF (3 ^m ) is calculated, and the 1/2 trace mapping calculation unit uses t obtained by the first finite field calculation unit. ,

The 1/3 trace mapping calculation unit uses H (t) obtained by the 1/2 trace mapping calculation unit,

The second finite field calculation unit uses C (H (t)) obtained by the 1/3 trace mapping calculation unit, and x = C (H (t)) ³ -C (H (t) ) ∈GF (3 ^m ), and the output unit outputs x obtained by the second finite field computation unit and the element y obtained by the conversion unit. The third mode is applied when m is a positive integer satisfying 1≡m mod 3, and t used in the ½ trace mapping operation unit satisfies Expression (7) and is output from the output unit. The element y to be satisfied satisfies Tr (y ² −b) = 0.

In the third aspect of the present invention, the conversion unit converts an arbitrary bit string into an element y∈GF (3 ^m ) of a finite field GF (3 ^m ), and the element y obtained by the first finite field calculation unit is obtained by the conversion unit. Using εGF (3 ^m ), t = y ² −b∈GF (3 ^m ) is calculated, and the 1/3 trace mapping operation unit uses t obtained by the first finite field operation unit, and the expression ( 6), the second finite field calculation unit uses t obtained by the first finite field calculation unit and the corresponding C (t), and x = tC (t) ³ + C (t) ΕGF (3 ^m ) is calculated, and the output unit outputs x obtained by the second finite field computation unit and the element y obtained by the conversion unit. The second mode is applied when m is a positive integer satisfying 1≡m mod 3, and t used in the 1/3 trace mapping operation unit satisfies the expression (7) and is output at the output unit. The element y to be satisfied satisfies Tr (y ² −b) = 0.

  In the present invention, an arbitrary bit string can be converted to a point on an elliptic curve defined on a characteristic 3 finite field at high speed.

It is a block diagram for demonstrating the function structure of the conversion calculating apparatus of 1st Embodiment. It is a flowchart for demonstrating the conversion calculation method of 1st Embodiment. It is a block diagram for demonstrating the function structure of the conversion calculating apparatus of 2nd Embodiment. It is a flowchart for demonstrating the conversion calculation method of 2nd Embodiment. It is a block diagram for demonstrating the function structure of the conversion calculating apparatus of 3rd Embodiment. It is a flowchart for demonstrating the conversion calculation method of 3rd Embodiment. It is a block diagram for demonstrating the function structure of the conversion calculating apparatus of 4th Embodiment. It is a flowchart for demonstrating the conversion calculation method of 4th Embodiment.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.
[Definition of symbols and terms]
First, symbols and terms used in each embodiment are defined.

<Characteristics of finite field GF (q)>
For any element a∈GF (q) of finite field GF (q) (finite field of order q), the smallest positive integer z satisfying 0 = z · a is the characteristic of finite field GF (q) Call it. If the finite field GF (q) is an mth-order extension of the finite field GF (p) (prime field) (GF (q) = GF (p ^m ), p is a prime number), the characteristic of the finite field GF (q) Becomes p. That is, the characteristic number of the finite field GF (3 ^m ) is 3. In the present embodiment, m is a positive integer. In addition, the calculation of the finite field GF (p) that is a prime field can be easily configured by using, for example, a remainder calculation modulo p. For example, an operation on the finite field GF (p) can be realized by setting the addition of the finite field GF (p) as a + b mod p and multiplying the finite field GF (p) as a · b mod p.

<Finite field GF (3 ^m )>
The finite field GF (3 ^m ) is an m-th order expansion based on the finite field GF (3). To represent an element u∈GF (3 ^m ) of a finite field GF (3 ^m ), the original set ω _i ∈GF (3) (i = 0, ..., m- 1) can be used. A typical way to do this is

It is a method to express. Here, [delta] _i is the original δ _i ∈GF finite ^{GF (3 m) (3 m} ), finite GF (3) ^m and the finite GF (3 ^m) is such that one-to-one correspondence Suppose that it is a special combination. Δ _i ∈GF (3 ^m ) having such properties is called a basis. An example of the basis δ _i ∈GF (3 ^m ) is the root x∈GF (3 ^m ) (f (x) = f of the ^m- th irreducible polynomial f (x) whose coefficients are the elements of the finite field GF (3). Δ _i = x ⁱ for x) satisfying 0.

Also,
The addition u ₁ + u ₂ ∈GF (3 ^m ) of the elements u ₁ and u ₂ ∈GF (3 ^m ) of the finite field GF (3 ^m ) defined by can be calculated as follows. Note that (ω _{1, i} , + ω _{2, i} ) is an operation on the finite field GF (3).

Further, based on u _1, u ₂ ∈GF multiplying _{u 1 · u 2 ∈GF (3} m) of (3 ^m) of a finite field GF (3 ^m) can be calculated as follows. Note that the calculations for the coefficients ω _{1, i} , ω _{2, i} are operations on the finite field GF (3).

<Elliptic curve E (GF (3 ^m )) defined on finite field GF (3 ^m )>
The elliptic curve E (GF (q)) defined on the finite field GF (q) is the affine coordinate version of the Weierstrass equation
y ² + a ₁・ x ・ y + a ₃・ y = x ³ + a ₂・ x ² + a ₄・ x + a ₆ (a ₁ , a ₂ , a ₃ , a ₄ , a ₆ ∈GF (q ))… (15)
A special point O called an infinite point is added to a set of points (x, y) (x, y∈GF (q)) that satisfy the above. A binary operation called elliptic addition can be defined for any two points on the elliptic curve E (q) and a unary operation called elliptic inverse can be defined for any one point on the elliptic curve E (q). It is well known that an operation called elliptic scalar multiplication can be defined using elliptic addition. In this form, it was defined on the finite field GF (3 ^m )
y ² = x ³ -x + b (16)
An elliptic curve E (GF (3 ^m )) obtained by adding an infinite point O to a set of points (x, y) (x, y∈GF (3 ^m )) satisfying the above is handled.

<Frobenius map of finite field>
According to the binomial theorem,
Is established. The coefficient of each term on the right side is a constant called a binomial coefficient, and is always a multiple of 3 when i ≠ 0 and i ≠ 3. When δ, θ∈GF (3 ^m ), the value obtained by multiplying δ, θ∈GF (3 ^m ) by a multiple of 3 (multiple of characteristic) is equal to 0.
(δ + θ) ³ = δ ³ + θ ³ (18)
Is established. Furthermore, for c where c∈GF (3), c ³ = c holds.

In general, any GF (3) coefficient advantageous formula f (δ ₁ , δ ₂ , ..., δ _n ) with δ ₁ , δ ₂ , ..., δ _n ∈GF (3 ^m ) as an indefinite element for,
f (δ ₁ , δ ₂ , ..., δ _n ) ³ = f (δ ₁ ³ , δ ₂ ³ , ..., δ _n ³ ) (19)
Is established. Therefore, equation (10) becomes

Can be transformed. Therefore in advance
If the element c _ij ∈GF (3) of the finite field GF (3) that satisfies

Gives a representation of u ³ ∈GF (3 ^m ) using the original basis δ _i . That is, a vector (ω _i ) having m element sets ω _i ∈GF (3) (i = 0, ..., m-1) as elements and an element c _ij ∈GF (3) as elements. A vector expressing u ³ ∈GF (3 ^m ) is obtained simply by multiplying the matrix (c _ij ). If the matrix (c _ij ) ⁿ (n is an integer greater than or equal to 1) is obtained in advance, the vector (ω _i ) is simply multiplied by the matrix (c _ij ) ⁿ and u ^s ∈GF (3 ^m ) ( A vector expressing s = 3 ⁿ ) can be obtained. Furthermore, there are special base such as matrix (c _ij) is simplified, when adopting such a basis, calculating the cost of u ^s ∈GF (3 ^m) is the multiplication over GF (3 ^m) It is known that it is so small that it can be ignored. Thus we call a function to calculate the mapping to u ^s ∈GF (3 ^m) from u∈GF (3 ^m) and 3 ^n-th power Frobenius map.

<Trace mapping in finite field GF (3 ^m )>
For any t∈GF (3 ^m) tracing mapping in finite GF (3 ^m)
It is defined as As shown in Equation (23), the trace map Tr (t) is obtained by converting the element u∈GF (3 ^m ) of the finite field GF (3 ^m ) into the element u ^s ∈GF (3 ^m ) (s = 3 ⁿ , n Is a 3n power Frobenius map that maps to an integer greater than or ^equal to 1 and addition on the finite field GF (3 ^m ).

<1/2 trace map>
For any t∈GF (3 ^m) 1/2 trace mapping in finite GF (3 ^m)
It is defined as As shown in the equation (24), the 1/2 trace map H (t) is obtained by converting the element u∈GF (3 ^m ) of the finite field GF (3 ^m ) into the element u ^s ∈GF (3 ^m ) (s = 3 ^n, n can be calculated only by addition of the above 3 and ^n-th power Frobenius map that maps to an integer of 1 or more), finite GF (3 ^m).

From equation (24)
It becomes. An arbitrary t∈GF (3 ^m ) is
In order to satisfy Eq. (23) and (26), Eq. (25) is
H (t) + H (t ³ ) = Tr (t) + t… (27)
And can be transformed.

<1/3 trace mapping in finite field GF (3 ^m )>
For any t∈GF (3 ^m) 1/3 trace mapping in finite GF (3 ^m)
It is defined as As shown in Expression (28), the 1/3 trace map C (t) is obtained by converting the element u∈GF (3 ^m ) of the finite field GF (3 ^m ) into the element u ^s ∈GF (3 ^m ) (s = 3 ^n, n can be calculated only by addition of the above 3 and ^n-th power Frobenius map that maps to an integer of 1 or more), finite GF (3 ^m).

Also, when r = m mod 3 = 1, from equation (28),
It becomes. Furthermore, using equations (23) and (26), equation (29) is
C (t) + C (t ³ ) + C (t ⁹ ) = Tr (t) + t + t ³ … (30)
And can be transformed.

Similarly, when r = m mod 3 = 2, from equation (28),
It becomes. Furthermore, using equations (23) and (26), equation (31) is
C (t) + C (t ³ ) + C (t ⁹ ) = Tr (t) + t… (32)
And can be transformed.

〔principle〕
Next, the principle of this embodiment will be described.
In this embodiment, an arbitrary bit string ID∈ {0,1} ^* is assigned to a point (x, x) on an elliptic curve y ² = x ³ −x + b defined on a finite field GF (3 ^m ) of characteristic 3 y) (formula (16)).

For this purpose, first, an arbitrary bit string ID∈ {0,1} ^* is converted into an element y∈GF (3 ^m ) of a finite field GF (3 ^m ), and the obtained element y∈GF (3 ^m ) is used. ,
t = y ² -b ∈GF (3 ^m )… (33)
Perform the operation. In this case, from equation (16),
t = x ³ -x ∈GF (3 ^m )… (34)
It becomes.

Here, when r = m mod 3 = 2 and Tr (t) = 0, from equation (32)
C (t) + C (t ³ ) + C (t ⁹ ) = t ∈GF (3 ^m )… (35)
Considering that this is an operation on the finite field GF (3 ^m ) (see equations (13) and (14)), equation (35) becomes
(C (t) ³ -C (t)) ^3- (C (t) ³ -C (t)) = t ∈GF (3 ^m )… (36)
And can be transformed. From equations (34) and (36),
x = C (t) ³ -C (t) ∈GF (3 ^m )… (37)
It turns out that it is. Therefore, by calculating equation (37) when r = m mod 3 = 2 and Tr (t) = 0, the x coordinate on the curve y ² = x ³ -x + b is obtained, and the ellipse It can be seen that the point (x, y) on the curve y ² = x ³ -x + b is determined.

On the other hand, when r = m mod 3 = 1 and Tr (t) = 0, from equation (30)
C (t) + C (t ³ ) + C (t ⁹ ) = t + t ³ ∈GF (3 ^m )… (38)
And t = H (t),
C (H (t)) + C (H (t) ³ ) + C (H (t) ⁹ ) = H (t) + H (t) ³ ∈GF (3 ^m )… (39)
It is. From Equations (19) and (27), Equation (39) is
C (H (t)) + C (H (t) ³ ) + C (H (t) ⁹ ) = t ∈GF (3 ^m )… (40)
In consideration of the calculation on the finite field GF (3 ^m ) (see equations (13) and (14)), equation (40) becomes
(C (H (t)) ³ -C (H (t))) ^3- (C (H (t)) ³ -C (H (t))) = t∈GF (3 ^m )… (41)
And can be transformed. From equations (34) and (41),
x = C (H (t)) ³ -C (H (t)) ∈GF (3 ^m )… (42)
It turns out that it is. Therefore, by calculating equation (42) when r = m mod 3 = 1 and Tr (t) = 0, the x coordinate on the curve y ² = x ³ -x + b is obtained, and the ellipse It can be seen that the point (x, y) on the curve y ² = x ³ -x + b is determined.

Further, when r = m mod 3 = 1 and Tr (t) = 0, t = C (t) in equation (27) and considering equation (19),
H (C (t)) + H (C (t)) ³ = C (t) ∈GF (3 ^m )… (43)
It can be seen that Also, from formulas (24) and (28),

Meet. Using equation (44), equation (43) is
C (H (t)) + C (H (t)) ³ = C (t) ∈GF (3 ^m )… (45)
And can be transformed
-C (H (t))-C (H (t)) ³ = -C (t) ∈GF (3 ^m )… (46)
And can be transformed. Subtracting C (H (t)) ³ from both sides of equation (45),
-C (H (t))-C (H (t)) ³ -C (H (t)) ³ = -C (t) -C (H (t)) ³ ∈GF (3 ^m )… (47 )
It becomes. For operations on the finite field GF (3 ^m ) (see equations (13) and (14)), -C (H (t)) ³ ∈GF (3 ^m ) is 2 · C (H (t)) ³ ∈GF Since (3 ^m ) is equivalent, equation (47) becomes
4 ・ C (H (t)) ³ -C (H (t)) =-C (H (t)) ³ -C (t) ∈GF (3 ^m )… (48)
4 ・ C (H (t)) ³ ∈GF (3 ^m ) is equivalent to C (H (t)) ³ ∈GF (3 ^m ).
C (H (t)) ³ -C (H (t)) =-C (H (t)) ³ -C (t) ∈GF (3 ^m )… (49)
And can be transformed.

Also, considering equation (19), equation (40) is
C (H (t)) ⁹ + C (H (t)) ³ = tC (H (t)) ∈GF (3 ^m )… (50)
And using equation (44), equation (50) becomes
H (C (t)) ⁹ + H (C (t)) ³ = tC (H (t)) ∈GF (3 ^m )… (51)
And can be transformed. From equation (43),
C (t ³ ) = H (C (t ³ )) + H (C (t ³ )) ³ ∈GF (3 ^m )… (52)
When considering equation (19), equation (52) becomes
C (t) ³ = H (C (t)) ³ + H (C (t)) ⁹ ∈GF (3 ^m )… (53)
Furthermore, equation (53) can be transformed into equation (50)
C (t) ³ = C (H (t)) ⁹ + C (H (t)) ³ = tC (H (t)) ∈GF (3 ^m )… (54)
And can be transformed. Here, using equation (54),
C (t) ³ + C (t) -t = tC (H (t)) + C (t) -t = -C (H (t)) + C (t) ∈GF (3 ^m )… (55 )
Using equation (45), equation (55) becomes
C (t) ³ + C (t) -t = -C (H (t)) + C (H (t)) + C (H (t)) ³ = C (H (t)) ³ ∈GF ( 3 ^m )… (56)
And can be transformed. Using this equation (56), equation (49) becomes
C (H (t)) ³ -C (H (t)) =-(C (t) ³ + C (t) -t) -C (t) ∈GF (3 ^m )… (57)
And can be transformed.

Furthermore, in the operation on the finite field GF (3 ^m ) (see equations (13) and (14)), -2 · C (H (t)) ³ ∈GF (3 ^m ) is C (H (t)) ³ Considering that it is equivalent to ∈GF (3 ^m ), Equation (57) becomes
C (H (t)) ³ -C (H (t)) =-(C (t) ³ + C (t) -t) -C (t) = tC (t) ³ + C (t) ∈GF (3 ^m )… (58)
And can be transformed. Therefore, referring to equation (42), calculating r (m) when r = m mod 3 = 1 and Tr (t) = 0, the curve y ² = x ³ −x + b It can be seen that the upper x coordinate is obtained, and the point (x, y) on the elliptic curve y ² = x ³ -x + b is determined.
[First Embodiment]
Next, a first embodiment of the present invention will be described.

In the present embodiment, when m is a positive integer satisfying 2≡m mod 3, an arbitrary bit string ID∈ {0,1} ^* is converted into a finite field GF (3 ^m ) is a form of conversion to a point (x, y) on the elliptic curve y ² = x ³ −x + b defined on the above.

<Configuration>
FIG. 1 is a block diagram for explaining a functional configuration of the conversion operation device 1 according to the first embodiment.
As shown in FIG. 1, the conversion calculation device 1 of this embodiment includes a control unit 101, a temporary memory 102, an input unit 103, a storage unit 104, a conversion unit 105, finite field calculation units 106 and 109 (“first and second finite numbers”). Equivalent to a “body calculation unit”), a calculation control unit 107, a 1/3 trace mapping calculation unit 108, and an output unit 110.

  The conversion operation device 1 is configured such that a predetermined program is read into a known computer having a CPU (central processing unit), a RAM (random-access memory), a ROM (read-only memory), and the like, and the CPU executes the program. Composed. That is, the temporary memory 102 and the storage unit 104 are storage areas configured by, for example, a RAM, a magnetic recording device, a magneto-optical recording medium, or a combination of at least a part thereof. The conversion unit 105, the finite field calculation units 106 and 109, the calculation control unit 107, and the 1/3 trace mapping calculation unit 108 are, for example, processing units configured by reading a predetermined program into the CPU. The input unit 103 is, for example, a user interface such as a keyboard, an input port that receives data input, and a processing unit that performs input processing of data output from other processing units (a predetermined program is read into the CPU). A processing unit configured as described above. The output unit 110 is an output port for outputting data, a processing unit for transferring data to another processing unit (a processing unit configured by reading a predetermined program into the CPU), or the like. Note that the conversion arithmetic device 1 executes each process under the control of the control unit 101. In addition, data generated in each arithmetic process is stored in the temporary memory 102 one by one, and read and used in other arithmetic processes.

<Conversion operation method>
Next, the conversion calculation method of this embodiment will be described.
FIG. 2 is a flowchart for explaining the conversion calculation method of the first embodiment. Hereinafter, the conversion calculation method of this embodiment will be described with reference to FIG. In this embodiment, it is assumed that m is a positive integer that satisfies 2≡m mod 3.

First, an arbitrary bit string IDε {0, 1} ^* is input to the input unit 103 and stored in the storage unit 104 (step S101). Next, the control unit 101 sets w = 0 and stores w in the temporary memory 102 (step S102). Next, the conversion unit 105 reads the bit string IDε {0,1} ^* from the storage unit 104, reads w from the temporary memory 102, and converts the bit string IDε {0,1} ^* read from the storage unit 104 into a finite field. converting the original y = G of ^{GF (3 m) (ID)} + w ∈GF (3 m) ( step S103). In this embodiment, the function G (ID) is a function that converts an arbitrary bit string IDε {0, 1} ^* into an element of a finite field GF (3 ^m ). Such a function G (ID) can be easily configured using a hash function or the like. An example of the function G (ID) is shown below.

[Example of function G (ID)]
(1) Find str = MGF (ID, L) (where L = 2 · floor (log ₂ 3 ^m )) for the input bit string ID∈ {0,1} ^* . MGF (ID, L) is a mask generation function that generates a bit value str having a bit length L from an arbitrary bit string IDε {0,1} ^* by repeatedly performing a hash function operation. (For example, see “RSA Laboratories,“ PKCS # 1 v2.1: RSA Encryption Standard, ”draft 2, January 5, 2001.”). Floor (·) is a floor function. • Outputs the maximum integer below. That is, in this example, L is obtained by doubling the maximum integer of log ₂ 3 ^m or less.

(2) Calculate d = BitStringtoInteger (str). BitStringtoInteger (·) is a function that converts a bit string · to an integer.
(3) ternary expansion of d generates a polynomial d ₃ with coefficients of each term {0,1,2}.
(4) Obtain d ₃ mod f (x) and output the calculated value. Note that f (x) is an m-th irreducible polynomial whose coefficient is the element of the finite field GF (3) (end of description of [example of function G (ID)]).

Next, the element yεGF (3 ^m ) obtained in step S103 is input to the finite field calculation unit 106, and the finite field calculation unit 106 uses the element yεGF (3 ^m ), and t = y ² An operation of -bεGF (3 ^m ) is performed (step S104). Next, tεGF (3 ^m ) generated in step S104 is input to the arithmetic control unit 107, the trace mapping Tr (t) shown in Expression (23) is calculated, and Tr (t) = 0 is satisfied. Whether or not (step S105).

  Here, when it is determined that Tr (t) = 0 is not satisfied, the arithmetic control unit 107 changes the conversion method in step S103 and causes the processes in steps S103 to S105 to be executed again. In the example of this embodiment, the arithmetic control unit 107 obtains w + 1 from w read from the temporary memory 102, stores the obtained w + 1 as new w in the temporary memory 102, and returns the process to step S103 (step S103). S106).

On the other hand, if it is determined in step S105 that Tr (t) = 0 is satisfied, t determined to satisfy Tr (t) = 0 is input to the 1/3 trace mapping operation unit 108. The 1/3 trace map calculation unit 108 uses the t determined to satisfy Tr (t) = 0 in step S105, performs the 1/3 trace map calculation shown in Expression (28), and performs C (t) ΕGF (3 ^m ) is obtained (step S107). The 1/3 trace mapping operation unit 108 converts the element u∈GF (3 ^m ) of the finite field GF (3 ^m ) into the element u ^s ∈GF (3 ^m ) (s = 3 ⁿ , where n is an integer of 1 or more). 3 and ^n-th power Frobenius map to map, only by addition of the above finite GF (3 ^m) can be calculated ^{C (t) ∈GF (3 m} ). Next, C (t) obtained in step S107 is input to the finite field computation unit 109, and the finite field computation unit 109 uses C (t) obtained in step S107, and x = C (t) ³ -C (t) εGF (3 ^m ) is calculated (see step S108 / equation (37)). ^{Incidentally, C (t) 3 ∈GF (} 3 m) is calculated by the third power Frobenius map that maps original u∈GF of a finite field GF (3 ^m) and (3 ^m) to the original u ³ ∈GF ^{(3 m)} it can.

Next, the output unit 110 was used in step S104 to calculate xεGF (3 ^m ) obtained in step S108 and t determined to satisfy Tr (t) = 0 in step S105. The element yεGF (3 ^m ) is output (step S109).

<Features of this embodiment>
When m is a positive integer satisfying 2≡m mod 3, by performing the processing of this embodiment, an arbitrary bit string ID∈ {0,1} ^* is converted into a finite field GF (3 ^m ) of characteristic 3 It can be converted into a point (x, y) on the elliptic curve y ² = x ³ −x + b defined above, and its calculation cost is lower than the method of Non-Patent Document 2.

Specifically, if the Hamming weight (number of elements other than ₀ ) of k = (m−1) / 2 = (k _ν−1 ,... K ₀ ) ₂ is hw (k), Non-Patent Document 2 The number of multiplications on the finite field GF (3 ^m ) required by the above method is ν + hw (k) times, and the number of 3 multiplications is m−1. On the other hand, the number of multiplications on the finite field GF (3 ^m ) required by the method of this embodiment is 1 and the number of 3 multiplications is m−1. As described above, in the method according to the present embodiment, the number of multiplications with a high calculation cost can be significantly reduced as compared with the method of Non-Patent Document 2. In the method of Non-Patent Document 2, the number of multiplications increases as the value of m increases, but the method of this embodiment is one time regardless of the value of m. Therefore, in the conventional method of Non-Patent Document 2, the value of m (usually, m ≧ 97, specifically, in order to improve the security of the elliptic curve cryptosystem configured on the elliptic curve y ² = x ³ −x + b, In practice, m = 97, 167, 193, 239, 353, 509, etc. are used). As the number of multiplications increases, the method of this embodiment does not increase the number of multiplications.

Further, in this embodiment, the operations of steps S107 and S108 for obtaining the x coordinate on the elliptic curve y ² = x ³ −x + b from y are performed by using the element u∈GF (3 ^m ) of the finite field GF (3 ^m ). original ^{u s ∈GF (3 m) (} s = 3 n, n is an integer of 1 or more) can be achieved only by the addition of over 3 and ^n-th power Frobenius map that maps to, finite GF (3 ^m). By using the 3n- ^th power Frobenius map with a low calculation cost in this way, the overall calculation cost can be greatly reduced. Note that a configuration in which a 3n- ^th power Frobenius map is not used for at least one of the three multiplications of the operations in steps S107 and S108 may be employed.

[Second Embodiment]
Next, a second embodiment of the present invention will be described.
In this embodiment, when m is a positive integer satisfying 1≡m mod 3, an equation (42) is used, and an arbitrary bit string ID∈ {0,1} ^* is converted into a finite field GF (3 ^m ) is a form of conversion to a point (x, y) on the elliptic curve y ² = x ³ −x + b defined on the above. In the following description, differences from the first embodiment will be mainly described, and description of matters common to the first embodiment will be omitted.

<Configuration>
FIG. 3 is a block diagram for explaining a functional configuration of the conversion operation device 2 according to the second embodiment.
As shown in FIG. 3, the conversion calculation device 2 of this embodiment includes a control unit 101, a temporary memory 102, an input unit 103, a storage unit 104, a conversion unit 105, finite field calculation units 106 and 209 (“first and second finite numbers”). Equivalent to a "body calculation unit"), a calculation control unit 107, a 1/3 trace mapping calculation unit 208, a 1/2 trace mapping calculation unit 211, and an output unit 110.

  The conversion operation device 2 is configured by a predetermined program being read into a known computer having a CPU, a RAM, a ROM, and the like, and executed by the CPU. For example, the finite field calculation unit 209, the 1/2 trace mapping calculation unit 211, and the 1/3 trace mapping calculation unit 208 are processing units configured by reading a predetermined program into the CPU. Note that the conversion calculation device 2 executes each process under the control of the control unit 101. In addition, data generated in each arithmetic process is stored in the temporary memory 102 one by one, and read and used in other arithmetic processes.

<Conversion operation method>
Next, the conversion calculation method of this embodiment will be described.
FIG. 4 is a flowchart for explaining the conversion calculation method of the second embodiment. Hereinafter, the conversion calculation method of this embodiment will be described with reference to FIG. In this embodiment, it is assumed that m is a positive integer satisfying 1≡m mod 3.

First, the processing of steps S101 to S106 described in the first embodiment is executed. Here, if it is determined in step S105 that Tr (t) = 0 is satisfied, t determined to satisfy Tr (t) = 0 is input to the ½ trace mapping operation unit 211. The ½ trace mapping calculation unit 211 uses the t determined to satisfy Tr (t) = 0 in step S105, performs the ½ trace mapping calculation shown in Expression (24), and performs H (t) ΕGF (3 ^m ) is obtained (step S206). Next, H (t) obtained in step S206 is input to the 1/3 trace mapping calculation unit 208. The 1/3 trace map calculation unit 208 uses the H (t) obtained in step S206 to perform the 1/3 trace map calculation shown in Expression (28) to obtain C (H (t)) ∈GF ( 3 ^m ) is obtained (step S207). The 1/3 trace mapping operation unit 208 converts the element u∈GF (3 ^m ) of the finite field GF (3 ^m ) into the element u ^s ∈GF (3 ^m ) (s = 3 ⁿ , where n is an integer of 1 or more). 3 and ^n-th power Frobenius map to map, a C (H (t)) ∈GF (3 m) only by the addition of over finite GF (3 ^m) can be calculated.

Next, C (H (t)) obtained in step S207 is input to the finite field computation unit 209, and the finite field computation unit 209 uses C (H (t)) obtained in step S207 to generate x = C (H (t)) ³ −C (H (t)) ∈GF (3 ^m ) is calculated (see step S208 / expression (42)). Incidentally, C (H (t)) 3 ∈GF (3 m) is cube Frobenius mapping to the original u∈GF (3 ^m) of the original u ³ ∈GF ^{(3 m)} of a finite field GF (3 ^m) It can be calculated by mapping.

Next, the output unit 110 was used in step S104 to calculate xεGF (3 ^m ) obtained in step S208 and t determined to satisfy Tr (t) = 0 in step S105. The element yεGF (3 ^m ) is output (step S109).

<Features of this embodiment>
When m is a positive integer satisfying 1≡m mod 3, by performing the processing of this embodiment, an arbitrary bit string ID∈ {0,1} ^* is converted into a finite field GF (3 ^m ) of characteristic 3 It can be converted into a point (x, y) on the elliptic curve y ² = x ³ −x + b defined above, and its calculation cost is lower than the method of Non-Patent Document 2.

Specifically, the number of multiplications on the finite field GF (3 ^m ) required by the method of Non-Patent Document 2 is ν + hw (k) times, and the number of 3 multiplications is m−1. On the other hand, the number of multiplications on the finite field GF (3 ^m ) required by the method of this embodiment is 1 and the number of multiplications of 3 is 2m−1. As described above, in the method according to the present embodiment, the number of multiplications with a high calculation cost can be significantly reduced as compared with the method of Non-Patent Document 2. As described previously, 3 multiplications can be calculated with a small calculation cost by using 3 ^n-th power Frobenius map. Further, in the method of Non-Patent Document 2, the number of multiplications with a large calculation cost increases as the value of m increases, but the number of multiplications in the method of this embodiment is one regardless of the value of m. Therefore, in the conventional method of Non-Patent Document 2, the number of multiplications increases as the value of m is increased in order to improve the security of the elliptic curve cryptosystem configured on the elliptic curve y ² = x ³ -x + b. On the other hand, the number of multiplications does not increase in the method of this embodiment.

[Third Embodiment]
Next, a third embodiment of the present invention will be described.
In the present embodiment, when m is a positive integer satisfying 1≡m mod 3, using Equation (58), an arbitrary bit string ID∈ {0,1} ^* is converted into a finite field GF (3 ^m ) is a form of conversion to a point (x, y) on the elliptic curve y ² = x ³ −x + b defined on the above. In the following description, differences from the first embodiment will be mainly described, and description of matters common to the first embodiment will be omitted.

<Configuration>
FIG. 5 is a block diagram for explaining a functional configuration of the conversion operation device 3 according to the third embodiment.
As shown in FIG. 5, the conversion calculation device 3 of this embodiment includes a control unit 101, a temporary memory 102, an input unit 103, a storage unit 104, a conversion unit 105, finite field calculation units 106 and 309 (“first and second finite numbers”). Equivalent to a “body calculation unit”), a calculation control unit 107, a 1/3 trace mapping calculation unit 108, and an output unit 110.

  The conversion operation device 3 is configured by a predetermined program being read into a known computer having a CPU, a RAM, a ROM, and the like, and executed by the CPU. For example, the finite field operation unit 309 is a processing unit configured by reading a predetermined program into the CPU. Note that the conversion arithmetic device 3 executes each process under the control of the control unit 101. In addition, data generated in each arithmetic process is stored in the temporary memory 102 one by one, and read and used in other arithmetic processes.

<Conversion operation method>
Next, the conversion calculation method of this embodiment will be described.
FIG. 6 is a flowchart for explaining the conversion calculation method of the third embodiment. Hereinafter, the conversion calculation method of this embodiment will be described with reference to FIG. In this embodiment, it is assumed that m is a positive integer satisfying 1≡m mod 3.

First, the processes of steps S101 to S107 described in the first embodiment are executed. Next, t determined to satisfy Tr (t) = 0 in step S105 and C (t) obtained in step S107 corresponding thereto are input to the finite field calculation unit 309, and the finite field calculation unit In step 309, these are used to calculate x = tC (t) ³ + C (t) εGF (3 ^m ) (see step S308 / formula (58)). ^{Incidentally, C (t) 3 ∈GF (} 3 m) is calculated by the third power Frobenius map that maps original u∈GF of a finite field GF (3 ^m) and (3 ^m) to the original u ³ ∈GF ^{(3 m)} it can.

Next, the output unit 110 was used in step S104 to calculate xεGF (3 ^m ) obtained in step S308 and t determined to satisfy Tr (t) = 0 in step S105. The element yεGF (3 ^m ) is output (step S109).

<Features of this embodiment>
When m is a positive integer satisfying 1≡m mod 3, by performing the processing of this embodiment, an arbitrary bit string ID∈ {0,1} ^* is converted into a finite field GF (3 ^m ) of characteristic 3 It can be converted into a point (x, y) on the elliptic curve y ² = x ³ −x + b defined above, and its calculation cost is lower than the method of Non-Patent Document 2.

Specifically, the number of multiplications on the finite field GF (3 ^m ) required by the method of Non-Patent Document 2 is ν + hw (k) times, and the number of 3 multiplications is m−1. On the other hand, the number of multiplications on the finite field GF (3 ^m ) required by the method of this embodiment is 1, and the number of multiplications is 3 times. As described above, in the method according to the present embodiment, the number of multiplications with a high calculation cost can be significantly reduced as compared with the method of Non-Patent Document 2. As described previously, 3 multiplications can be calculated with a small calculation cost by using 3 ^n-th power Frobenius map. In the method of Non-Patent Document 2, the number of multiplications increases as the value of m increases, but the method of this embodiment is one time regardless of the value of m. Therefore, in the conventional method of Non-Patent Document 2, the number of multiplications increases as the value of m is increased in order to improve the security of the elliptic curve cryptosystem configured on the elliptic curve y ² = x ³ -x + b. On the other hand, the number of multiplications does not increase in the method of this embodiment.

[Fourth Embodiment]
Next, a fourth embodiment of the present invention will be described.
This embodiment is a combination of the first and third embodiments, and when m is a positive integer, using Equation (58) or Equation (37), an arbitrary bit string IDε {0,1} ^* is This is a form of conversion to a point (x, y) on an elliptic curve y ² = x ³ −x + b defined on a finite field GF (3 ^m ) of characteristic 3. In the following description, differences from the first embodiment will be mainly described, and description of matters common to the first embodiment will be omitted.

<Configuration>
FIG. 7 is a block diagram for explaining a functional configuration of the conversion operation device 4 according to the fourth embodiment.
As shown in FIG. 7, the conversion calculation device 4 of this embodiment includes a control unit 101, a temporary memory 102, an input unit 103, a storage unit 104, a conversion unit 105, a finite field calculation unit 106 (“first finite field calculation unit”). ), A control unit 107, a 1/3 trace mapping calculation unit 108, a finite field calculation unit 109, 409 (corresponding to a “second finite field calculation unit”), a conditional branching unit 411, and an output unit 110.

  The conversion operation device 4 is configured by reading a predetermined program into a known computer having a CPU, a RAM, a ROM, and the like, and executing it by the CPU. For example, the finite field operation unit 409 and the conditional branching unit 411 are processing units configured by reading a predetermined program into the CPU. Note that the conversion arithmetic device 4 executes each process under the control of the control unit 101. In addition, data generated in each arithmetic process is stored in the temporary memory 102 one by one, and read and used in other arithmetic processes.

<Conversion operation method>
Next, the conversion calculation method of this embodiment will be described.
FIG. 8 is a flowchart for explaining the conversion calculation method of the fourth embodiment. Hereinafter, the conversion calculation method of this embodiment will be described with reference to FIG. In this embodiment, it is assumed that m is a positive integer.

First, an arbitrary bit string IDε {0,1} ^* and m are input to the input unit 103 and stored in the storage unit 104 (step S401). Next, the control unit 101 sets w = 0 and stores w in the temporary memory 102 (step S102). Next, the conversion unit 105 reads the bit string IDε {0,1} ^* and m from the storage unit 104, reads w from the temporary memory 102, and sets the read bit string IDε {0,1} ^* from the storage unit 104. converting the original y = G of finite ^{GF (3 m) (ID)} + w ∈GF (3 m) ( step S403).

Next, the element yεGF (3 ^m ) and m obtained in step S403 are input to the finite field calculation unit 106, and the finite field calculation unit 106 uses the element yεGF (3 ^m ) and t = Calculation of y ² -bεGF (3 ^m ) is performed (step S404). Next, tεGF (3 ^m ) and m generated in step S404 are input to the arithmetic control unit 107, the trace mapping Tr (t) shown in the equation (23) is calculated, and Tr (t) = It is determined whether or not 0 is satisfied (step S405).

  Here, when it is determined that Tr (t) = 0 is not satisfied, the arithmetic control unit 107 changes the conversion method in step S403 and causes the processes in steps S403 to S405 to be executed again. In the example of this embodiment, the arithmetic control unit 107 obtains w + 1 from w read from the temporary memory 102, stores the obtained w + 1 as new w in the temporary memory 102, and returns the process to step S403 (step S403). S106).

On the other hand, if it is determined in step S405 that Tr (t) = 0 is satisfied, t and m determined to satisfy Tr (t) = 0 are input to the 1/3 trace mapping operation unit 108. The 1/3 trace map calculation unit 108 performs the calculation of the 1/3 trace map shown in Expression (28) using t and m determined to satisfy Tr (t) = 0 in step S405 to obtain C ( t) ∈ GF (3 ^m ) is obtained (step S407). The 1/3 trace mapping operation unit 108 converts the element u∈GF (3 ^m ) of the finite field GF (3 ^m ) into the element u ^s ∈GF (3 ^m ) (s = 3 ⁿ , where n is an integer of 1 or more). 3 and ^n-th power Frobenius map to map, only by addition of the above finite GF (3 ^m) can be calculated ^{C (t) ∈GF (3 m} ). Next, C (t) and m obtained in step S107 are input to the finite field calculation unit 109, and the finite field calculation unit 109 uses them to obtain x = C (t) ³ −C (t) ∈GF. (3 ^m ) is calculated (see step S408 / formula (37)). ^{Incidentally, C (t) 3 ∈GF (} 3 m) is calculated by the third power Frobenius map that maps original u∈GF of a finite field GF (3 ^m) and (3 ^m) to the original u ³ ∈GF ^{(3 m)} it can.

Next, x and m obtained in step S408 are input to the conditional branching unit 411, and it is determined whether or not the conditional branching unit 411 satisfies 1≡m mod 3 (step S409). If it is determined that 1≡m mod 3 is not satisfied, the output unit 110 then sets x∈GF (3 ^m ) obtained in step S408 and Tr (t) = 0 in step S405. The element yεGF (3 ^m ) used in step S404 for calculating t determined to satisfy is output (step S109).

On the other hand, if it is determined that 1≡m mod 3 is satisfied, x and m obtained in step S408 are input to the finite field calculation unit 409, and the finite field calculation unit 409 calculates tx∈GF (3 ^m ). And the operation result is set as a new xεGF (3 ^m ) (step S410). Then, the output unit 110 uses x∈GF (3 ^m ) obtained in step S410 and the element used in step S404 to calculate t determined to satisfy Tr (t) = 0 in step S405. yεGF (3 ^m ) is output (step S109).

<Features of this embodiment>
When m is a positive integer satisfying 1≡m mod 3 or 2≡m mod 3, by performing the processing of this embodiment, an arbitrary bit string ID∈ {0,1} ^* is converted into a finite characteristic 3 It can be converted to a point (x, y) on an elliptic curve y ² = x ³ −x + b defined on the field GF (3 ^m ), and its calculation cost is lower than the method of Non-Patent Document 2. .

  In this embodiment, the method of the third embodiment (in the case of 1≡m mod 3) or the method of the first embodiment (in the case of 1≡m mod 3) depending on whether 1≡m mod 3 is satisfied by combining the first and third embodiments. 2≡m mod 3). However, depending on whether 1≡m mod 3 is satisfied by combining the first and second embodiments, the method of the second embodiment (in the case of 1≡m mod 3) or the method of the first embodiment (2≡m mod (Case 3) may be taken.

〔simulation result〕
Next, simulation results are shown. Below, the calculation time of the method demonstrated in 4th Embodiment is illustrated.

Table 1 shows each calculation time (μsec) on the finite field GF (3 ^m ) of m = 97,167,193,239,353,509. Here, each operation time corresponding to addition, multiplication, and 3 multiplication indicates an operation time for each of addition, multiplication, and 3 multiplication on the finite field GF (3 ^m ). The three multiplication is a calculation using the 3 ^n-th power Frobenius map. In addition, each computation time corresponding to the conventional method is obtained by calculating a point on an elliptic curve y ² = x ³ −x + b defined on a finite field GF (3 ^m ) by the method of Non-Patent Document 2 ( The calculation time for converting to x, y) is shown. In addition, each computation time corresponding to the proposed method is calculated on an elliptic curve y ² = x ³ -x + b in which an arbitrary bit string is defined on the finite field GF (3 ^m ) by the method described in the fourth embodiment. The calculation time for converting to the point (x, y) is shown. The order m and the irreducible polynomial f (x) = x ^m + x ^τ +2 are (m, τ) = {(97,12), (167,96), (193,12), ( 239, 24), (353, 142), (509, 358)}, and the respective bases (δ _i = x ⁱ ) are determined as described above using their roots x∈GF (3 ^m ). In addition, C language and GCC4.2.2-03 option were used for this implementation, and AMD Opteron processor (2.2 GHz) was operated on Linux / x86_64 to measure the calculation time. Each calculation time in Table 1 is the average of each calculation performed 1,000,000 times or more. Implementation does not use extension instructions such as SSE. As shown in Table 1, it can be seen that the proposed method can perform a conversion operation about 1.5 times faster than the conventional method in any order.

[Other variations, etc.]
The present invention is not limited to the embodiment described above. For example, the various processes described above are not only executed in time series according to the description, but may also be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes. Needless to say, other modifications are possible without departing from the spirit of the present invention.

Further, when the above-described configuration is realized by a computer, processing contents of functions that each device should have are described by a 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.

  As an application field of the present invention, for example, an ID-based encryption field using a pairing operation on an elliptic curve and other elliptic curve fields can be exemplified.

  1-4 conversion operation device

Claims (10)

A conversion arithmetic device that converts an arbitrary bit string to a point (x, y) on an elliptic curve y ² = x ³ -x + b defined on a finite field GF (3 ^m ) of characteristic 3, M is a positive integer satisfying 2≡m mod 3,
A storage unit for storing an arbitrary bit string;
A conversion unit that converts the bit string read from the storage unit into an element y∈GF (3 ^m ) of a finite field GF (3 ^m );
Using the original y∈GF (3 ^m) obtained by the conversion unit, and a first finite field arithmetic unit for performing calculation of ^{t = y 2 -b∈GF (3 m} ),
Using t obtained by the first finite field calculation unit,

A 1/3 trace mapping operation unit that performs the operation of
A second finite field operation unit that performs an operation of x = C (t) ³ −C (t) ∈GF (3 ^m ) using C (t) obtained by the 1/3 trace mapping operation unit;
An output unit that outputs x obtained by the second finite field computation unit and an element y obtained by the conversion unit;
T used in the 1/3 trace mapping operation unit is
The filling,
The element y output at the output unit satisfies Tr (y ² -b) = 0.
A conversion operation device characterized by that. A conversion arithmetic device that converts an arbitrary bit string to a point (x, y) on an elliptic curve y ² = x ³ -x + b defined on a finite field GF (3 ^m ) of characteristic 3, M is a positive integer satisfying 1≡m mod 3;
A storage unit for storing an arbitrary bit string;
A conversion unit that converts the bit string read from the storage unit into an element y∈GF (3 ^m ) of a finite field GF (3 ^m );
A first finite field operation unit that performs an operation of t = y ² −b∈GF (3 ^m ) using the element y obtained by the conversion unit;
Using t obtained by the first finite field calculation unit,
A 1/3 trace mapping operation unit that performs the operation of
A second finite element that calculates x = tC (t) ³ + C (t) ∈GF (3 ^m ) using t obtained by the first finite field arithmetic unit and C (t) corresponding thereto. A field calculator,
An output unit that outputs x obtained by the second finite field computation unit and an element y obtained by the conversion unit;
T used in the 1/3 trace mapping operation unit is
The filling,
The element y output at the output unit satisfies Tr (y ² -b) = 0.
A conversion operation device characterized by that. The conversion arithmetic device according to claim 1 or 2,
At least one of the 1/3 trace mapping operation unit and the second finite field operation unit is:
A 3n- ^th power Frobenius map that maps an element u∈GF (3 ^m ) of a finite field GF (3 ^m ) to an element u ^s ∈GF (3 ^m ) (s = 3 ⁿ , where n is an integer greater than or equal to 1); An arithmetic unit that performs addition on the field GF (3 ^m ),
A conversion operation device characterized by that. A conversion arithmetic device that converts an arbitrary bit string to a point (x, y) on an elliptic curve y ² = x ³ -x + b defined on a finite field GF (3 ^m ) of characteristic 3, M is a positive integer satisfying 1≡m mod 3;
A storage unit for storing an arbitrary bit string;
A conversion unit that converts the bit string read from the storage unit into an element y∈GF (3 ^m ) of a finite field GF (3 ^m );
Using the original y∈GF obtained by conversion by the conversion unit (3 ^m), a first finite field arithmetic unit for performing calculation of ^{t = y 2 -b∈GF (3 m} ),
Using t obtained by the first finite field calculation unit,
A 1/2 trace mapping calculation unit for performing the calculation of
Using H (t) obtained by the 1/2 trace mapping operation unit,
A 1/3 trace mapping operation unit that performs the operation of
Using C (H (t)) obtained by the 1/3 trace mapping operation unit, calculation of x = C (H (t)) ³ -C (H (t)) ∈GF (3 ^m ) is performed. A second finite field arithmetic unit;
An output unit that outputs x obtained by the second finite field computation unit and an element y obtained by the conversion unit;
T used in the 1/2 trace mapping operation unit is:
The filling,
The element y output at the output unit satisfies Tr (y ² -b) = 0.
A conversion operation device characterized by that. The conversion arithmetic device according to claim 4,
At least a part of the 1/2 trace mapping operation unit, the 1/3 trace mapping operation unit, and the second finite field operation unit are:
A 3n- ^th power Frobenius map that maps an element u∈GF (3 ^m ) of a finite field GF (3 ^m ) to an element u ^s ∈GF (3 ^m ) (s = 3 ⁿ , where n is an integer greater than or equal to 1); An arithmetic unit that performs addition on the field GF (3 ^m ),
A conversion operation device characterized by that. A conversion operation method for converting an arbitrary bit string to a point (x, y) on an elliptic curve y ² = x ³ -x + b defined on a finite field GF (3 ^m ) of characteristic 3, M is a positive integer satisfying 2≡m mod 3,
(a) the conversion unit converts the bit string read from the storage unit into an element y∈GF (3 ^m ) of a finite field GF (3 ^m );
(b) first finite field calculation unit, using the original y∈GF obtained in step (a) (3 ^m), and performing the calculation of ^{t = y 2 -b∈GF (3 m} ),
(c) The calculation control unit determines that t obtained in step (b)
Determining whether or not, if not, changing the conversion method in the step (a) to re-execute the steps (a) and (b),
(d) The 1/3 trace mapping operation unit uses t determined to satisfy Tr (t) = 0 in step (c),
A step of performing the operation of
(e) A step in which the second finite field calculation unit calculates x = C (t) ³ −C (t) ∈GF (3 ^m ) using C (t) obtained in step (d). When,
(f) The output unit is used in step (b) to calculate x obtained in step (e) and t determined to satisfy Tr (t) = 0 in step (c). Outputting the generated element y, and
A conversion calculation method. A conversion operation method for converting an arbitrary bit string to a point (x, y) on an elliptic curve y ² = x ³ -x + b defined on a finite field GF (3 ^m ) of characteristic 3, M is a positive integer satisfying 1≡m mod 3;
(a) the conversion unit converts the bit string read from the storage unit into an element y∈GF (3 ^m ) of a finite field GF (3 ^m );
(b) first finite field calculation unit, using the original y∈GF obtained in step (a) (3 ^m), and performing the calculation of ^{t = y 2 -b∈GF (3 m} ),
(c) The calculation control unit determines that t obtained in step (b)
Determining whether or not, if not, changing the conversion method in the step (a) to re-execute the steps (a) and (b),
(d) The 1/3 trace mapping operation unit uses t determined to satisfy Tr (t) = 0 in step (c),
A step of performing the operation of
(e) The second finite field calculation unit calculates t determined to satisfy Tr (t) = 0 in step (c) and C (t) obtained in step (d) corresponding thereto. Using x = tC (t) ³ + C (t) ∈GF (3 ^m ), and
(f) The output unit is used in step (b) to calculate x obtained in step (e) and t determined to satisfy Tr (t) = 0 in step (c). Outputting the generated element y, and
A conversion calculation method. A conversion operation method for converting an arbitrary bit string to a point (x, y) on an elliptic curve y ² = x ³ -x + b defined on a finite field GF (3 ^m ) of characteristic 3, M is a positive integer satisfying 1≡m mod 3;
(a) the conversion unit converts the bit string read from the storage unit into an element y∈GF (3 ^m ) of a finite field GF (3 ^m );
(b) first finite field calculation unit, using the original y∈GF obtained in step (a) (3 ^m), and performing the calculation of ^{t = y 2 -b∈GF (3 m} ),
(c) The calculation control unit determines that t obtained in step (b)
Determining whether or not, if not, changing the conversion method in the step (a) to re-execute the steps (a) and (b),
(d) The 1/2 trace mapping calculation unit uses t determined to satisfy Tr (t) = 0 in the step (c),
A step of performing the operation of
(e) The 1/3 trace map calculation unit uses H (t) obtained in step (d),
A step of performing the operation of
(f) The second finite field arithmetic unit uses C (H (t)) obtained in step (e), and x = C (H (t)) ³ −C (H (t)) ∈GF (3 ^m ) calculation step,
(g) The output unit is used in step (b) to calculate x obtained in step (f) and t determined to satisfy Tr (t) = 0 in step (c). Outputting the generated element y, and
A conversion calculation method.   A program for causing a computer to function as the conversion operation device according to claim 1.   A computer-readable recording medium storing the program according to claim 9.