JP4960894B2 - Elliptic curve point compression device, elliptic curve point expansion device, method and program thereof - Google Patents

Description

The present invention relates to information security technology. In particular, in elliptic curve cryptography, an elliptic curve point compression device, an elliptic curve point expansion device, a method and a program thereof for reducing the data size for specifying a point of an elliptic curve E (F _{q ^ m} ) that is a partial body curve About.

A characteristic curve q is a prime number or a power thereof, an expansion order m is an integer of 2 or more, a, bεF _q , and O is an infinite point, and an elliptic curve E (F _{q ^ m} ) = {(x , Y) ∈ F _{q ^ m} ² | y ² = x ³ + ax + b} ∪O The number of bits of data indicating the point P = (X, Y) ∈F _{q ^ m} ² (referred to as the data size) is 2 × m × log ₂ q. For finite _{F q ^ m} of order (the original number) is ^{q m,} the data size representing one source with finite _{F q ^ m} is the ^{_{log 2 q m = m × log}} 2 q. And since X which is the value of the x coordinate of the point P and Y which is the value of the y coordinate of the point P are elements of the finite field F _{q ^ m} , the data size for specifying the point P is 2 × m Xlog ₂ q.

As a method for reducing the data size for specifying the point P on the elliptic curve E (F _{q ^ m} ), the following method is known (for example, see Non-Patent Document 1). Elliptic curve E _{(F q ^ m)} is the _{X a} as a value of x-coordinate of an arbitrary point on the elliptic curve E _{(F q ^ m),} intersect only at the straight line x = _{X a} and two points. Since the elliptic curve E (F _{q ^ m} ) is line symmetric with respect to the x-axis, among the two intersections where the elliptic curve E (F _{q ^ m} ) and the straight line x = X _a intersect, The value of the y coordinate of one intersection is positive, and the value of the y coordinate of the other intersection is negative. Accordingly, if only the x-coordinate value of the point on the elliptic curve E (F _{q ^ m} ) and the y-coordinate value of the point are known, the point can be specified. For this reason, the data size for specifying the point P on the elliptic curve E (F _{q ^ m} ) can be set to m × log ₂ q + 1 by expressing the positive / negative of the y coordinate with 1 bit.
Ian F. Brake, Gadiel Serrossi, Nigel P. Smart, translated by Jiro Suzuki, "Elliptic Curve Cryptography", first edition, first edition, Pearson Education, December 20, 2001, P79

In the technique described in Non-Patent Document 1, there is a problem that the compressed data size for specifying the point P on the elliptic curve (F _{q ^ m} ) is not sufficiently small.

  It is an object of the present invention to provide an elliptic curve point compression device, an elliptic curve point expansion device, and a method and program thereof that reduce the data size compared to the elliptic curve point compression method described in the background art. .

An elliptic curve E (F _{q ^ m} ) = {(x, y) ∈, where the characteristic q is a prime number or its power, m is an expansion order, a, b∈F _q , and O is an infinite point. In order to compress the point PεF _{q ^ m} ² on F _{q ^ m} ² | y ² = x ³ + ax + b} ∪O and generate the compression information of the point P, first, let φ be a qth power Frobenius map From the point P, the points φP, φ ² P,..., Φ ^{(m − 1)} P∈E (F _{q ^ m} ) are obtained. Point ^{P, φP, φ 2 P,} ..., φ (m - 1) coefficient of each term of the polynomial curve passing through _{P λ 0, λ 2, ...} , determine the λ _m-1 ∈F _q. A point sequence in which the points P, φP, φ ² P,..., Φ ^{(m − 1)} P are arranged in a predetermined order is generated. Position regarding the order of the point P in the point sequence (hereinafter referred to as sequence position.) Information (hereinafter referred to as sequence position information m _P.) Determined. Compression information of the point P, the order position information _{m P} and coefficient lambda _0, lambda _2, ..., and a λ _m-1.

Point ^{P, φP, φ 2 P,} ..., φ (m - 1) coefficient of each term of the polynomial curve passing through _{P λ 0, λ 2, ...} , determine the λ _m-1 ∈F _q. Point ^{P, φP, φ 2 P,} ..., φ (m - 1) coefficient of each term of the polynomial curve passing through _{P λ 0, λ 2, ...} , λ m-1 ∈F q and the order position information _{m P} (For example, the order position information m _P is an integer from 1 to m) and at least the compression information, the data size of the compression information is at least (m−1) × log ₂ q + log ₂ m Can do.

[Point compression device]
What is subject to point compression and point expansion of the present invention is a rational point on an elliptic curve E (F _{q ^ m} ) that is a partial body curve. That is, an elliptic curve E (F _{q ^ m} ) = {(x, y), which is a partial field curve, where the characteristic q is a prime number or its power, m is an expansion order, a, bεF _q , and O is an infinite point. ) ∈F _{q ^ m} ² | y ² = x ³ + ax + b} ∪O, the point P∈F _{q ^ m} ² on the point is the target of point compression and point expansion. Furthermore, as will be described later, among the rational points on the elliptic curve E (F _{q ^ m} ) that is a partial body curve, the points included in the set (φ−1) E (F _{q ^ m} ) are point-compressed. , Subject to point expansion.

It is desirable that the characteristic q and the expansion order m are sufficiently large so that the required safety can be ensured. From the viewpoint of safety, it is desirable to select a and b so as to satisfy the relationship of 4a ³ + 27b ² ≠ 0. Hereinafter, the elliptic curve E (F _{q ^ m} ) that is a partial body curve is also simply referred to as an elliptic curve E (F _{q ^ m} ).

Point compression, that is, compression of a point, means that compression information having a small data size for specifying a point on the elliptic curve E (F _{q ^ m} ) is generated. Point expansion, that is, expansion of a point, means that compression information for specifying a point on the elliptic curve E (F _{q ^ m} ) is returned to the data before compression.

  The point compression apparatus 10 will be described with reference to FIGS. 1 and 2. FIG. 1 is a diagram illustrating a functional configuration of the point compression device 10, and FIG. 2 is a flowchart illustrating a process flow of the point compression device 10.

<Step S1e>
A point PεF _{q ^ m} ² on the elliptic curve E (F _{q ^ m} ) is input to the compression exception determination unit 11. The compression exception determination unit 11 determines whether or not the point Pε (φ−1) E (F _{q ^ m} ), that is, whether or not the point P is included in the set (φ−1) E (F _{q ^ m} ). judge. When it is determined that the point Pε (φ−1) E (F _{q ^ m} ), the point compression apparatus 10 performs the processing after step S2e, and the point Pε (φ−1) E (F _{q ^ m).} ) Is not determined, the process after step S2e is not performed. If the point is not P∈ (φ−1) E (F _{q ^ m} ), point compression is not always possible, and point expansion is possible even if point compression is possible. This is because it is not always possible.

φ is a qth power Frobenius map and is defined as φ: (x, y) → (x ^q , y ^q ). φ is a self-homogeneous mapping of the power of E (F _{q ^ m} ). The set (φ-1) E (F _{q ^ m} ) is a set formed by points obtained by mapping all points on E (F _{q ^ m} ) by mapping (φ-1). That is, it is a set formed by (φ−1) a (= φa−a) with a point on E (F _{q ^ m} ) as a point a.

If E (F _{q ^ m} ) / E (F _q ) is a cyclic group of order L and #E (F _q ) and L are relatively prime, E (F _{q ^ m} ) [L] = ( φ−1) E (F _{q ^ m} ) (see Lemma 1 described later). Therefore, if E (F _{q ^ m} ) / E (F _q ) is a cyclic group of order L and #E (F _q ) and L are relatively prime, the compression exception determination unit 11 determines that the point P∈ (Φ-1) Instead of whether or not E (F _{q ^ m} ), it may be determined whether or not the point PεE (F _{q ^ m} ) [L]. #A represents the order of a, and a [b] represents a set of points that become an infinite point O when multiplied by b among points included in a.

<Step S2e>
The compression intersection generation unit 12 generates points φP, φ ² P,..., Φ ^(m−1) P based on the points P∈F _{q ^ m} ² on the input elliptic curve E (F _{q ^ m} ). For each. The point P and the obtained point are sent to the coefficient generation unit 13 and the compression rearrangement unit 14.

Note that if the point PεF _q ² , φP = P, and taking the even number, if φP = P, it is not the point PεF _q ² . Here, (φ−1) E (F _{q ^ m} ) is a set of points a∈E (F _{q ^ m} ) that does not satisfy φa = a. Therefore, if the point Pε (φ−1) E (F _{q ^ m} ), since it is not φP = P, it is not the point PεF _q ² . Therefore, considering the basic properties of the body, if the point Pε (φ−1) E (F _{q ^ m} ), the points P, φP, φ ² P,..., Φ ^(m−1) P are Everything is different.

<Step S3e>
Coefficient generating unit 13, the point ^{P, φP, φ 2 P,} ..., φ (m-1) coefficient lambda ₀ of each term of the polynomial curve passing through P, lambda _2, ..., a λ _m-1 ∈F _q Ask. The obtained coefficients λ ₀ , λ ₂ ,..., Λ _m−1 constitute the compression information of the point P together with the order position information m _P described later.

When the weight of x is 2 and the weight of y is 3, the polynomial f (x, y) = 0 of the weight c (c is an arbitrary natural number) is the intersection of the elliptic curve E (F _{q ^ m} ) and c. It is known to cross. Further, it is known that the weight of the polynomial f (x, y) = 0 that intersects the elliptic curve E (F _{q ^ m} ) at c intersections is c. Here, since the number of points P, φP, φ ² P,..., Φ ^(m−1) P is m, the coefficient generation unit 13 uses the coefficients λ ₀ , λ ₂ ,. What is necessary is just to obtain | require (lambda) _m-1 .

とできる。重みが１の単項式はないため、ｉ＝１の場合の単項式Ｍ_１については考慮する必要はない。このため、重みｍのモニック多項式（重みがｍであり、重みが最大の単項式の係数が１の多項式）の自由度はＦ_ｑ ^ｍ−１である。すなわち、ｍ−１個の係数λ_０，λ_２，…，λ_ｍ−１∈Ｆ_ｑが与えられれば、重みｍのモニック多項式ｆ（ｘ，ｙ）＝Ｍ_ｍ（ｘ，ｙ）＋λ_０Ｍ_０（ｘ，ｙ）＋Σ_ｉ＝２ ^ｍ−１λ_ｉＭ_ｉ（ｘ，ｙ）＝０は、一意に定まる。 A regular monomial other than O with weight i∈N, where M _i is i ≠ 1

And can. Since there is no monomial with a weight of 1, there is no need to consider the monomial M ₁ when i = 1. For this reason, the degree of freedom of the monic polynomial of weight m (the weight is m and the polynomial with the largest monomial coefficient is 1) is F _q ^m−1 . That is, if m−1 coefficients λ ₀ , λ ₂ ,..., Λ _m−1 εF _q are given, the monic polynomial f (x, y) = M _m (x, y) + λ ₀ M with weight m ₀ (x, y) + Σ _{i = 2} ^m−1 λ _i M _i (x, y) = 0 is uniquely determined.

For how to obtain the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 , refer to [First method for obtaining coefficients] and [Second method for obtaining coefficients] described later. For example, the coefficient generation unit 13 calculates the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 by these methods. Of course, the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 may be calculated using other methods.

<Step S4e>
The compression rearrangement unit 14 is a point sequence (P, φP, φ ^{) in} which the points P, φP, φ ² P,..., Φ ^(m−1) P obtained by the compression intersection generation unit 12 are arranged in a predetermined order. ² P, ..., φ ^(m-1) P) ^* is generated. An asterisk * means a point sequence after being rearranged in a predetermined order. The generated point sequence (P, φP, φ ² P,..., Φ ^(m−1) P) ^* is sent to the order position information determination unit 15.

  The predetermined order is an arrangement that can generate a point sequence uniquely according to the order. For example, the order in which the value of the x coordinate of each point is in descending order or ascending order. Of course, the value of the y coordinate may be used instead of the value of the x coordinate.

<Step S5e>
The order position information determination unit 15 determines position information m _P regarding the order of the points P in the point sequence (P, φP, φ ² P,..., Φ ^(m−1) P) ^* . The position related to the order of the points P is abbreviated as the order position of the points P. Further, the information on the order position of the point _P is abbreviated as the order position information m _P of the point P.

For example, when the position of the point P in the point sequence (P, φP, φ ² P,..., Φ ^(m−1) P) ^* is m _left (1 ≦ m _left ≦ m) from the _left , The order position m _left of the point P counted from the left becomes the order position information of the point P. Similarly, the order position m _right of the point P counted from the right in the point sequence (P, φP, φ ² P,..., Φ ^(m−1) P) ^* may be used as the order position information m _P of the point P. . Thus, arbitrary information indicating the order position of the point P in the point sequence (P, φP, φ ² P,..., Φ ^(m−1) P) ^* may be used as the order position information m _P.

And sequence position information m _P of the point P, the coefficient lambda _0, lambda _2, ..., information including at least a lambda _m-1 becomes the compression information of the point P. The compression information of the point P is sent to the point expansion device 20.

In this example, the data sizes of the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 are (m−1) × log ₂ q in total, and the data size of the order position information m _p is log ₂ m. The data size of the compression information is at least (m−1) × log ₂ q + log ₂ m. Therefore, when m << q (this condition is often satisfied), the data size before compression is 2 × m × log ₂ q or the point compression method described in the background art. The data size for specifying the point P can be made smaller than m × log ₂ q + 1 which is the compressed data size.

[Point deployment device]
The point expansion device 20 will be described with reference to FIGS. 3 and 4. FIG. 3 is a diagram illustrating a functional configuration of the point expansion device 20, and FIG. 4 is a flowchart illustrating a processing flow of the point expansion device 20.

<Step S1d>
Of the compression information, coefficients λ ₀ , λ ₂ ,..., Λ _m−1 are input to the expanded intersection generation unit 21. The developed intersection generation unit 21 obtains intersections between the polynomial f (x, y) having a weight m having coefficients λ ₀ , λ ₂ ,..., Λ _m−1 and the elliptic curve E (f _{q ^ m} ).

If the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 are legitimately generated by the point compression device 10 based on the point P, the intersection calculated by the expanded intersection generation unit 21 is the point P , ΦP, φ ² P,..., Φ ^(m−1) P. The calculated intersection point is sent to the deployment rearrangement unit 22.

<Step S2d>
The expansion rearrangement unit 22 generates a point sequence in which the calculated intersection points are rearranged in a predetermined order. The predetermined order in the expansion rearrangement unit 22 is the same as the predetermined order in the compression rearrangement unit 14 of the point compression device 10. In this example, the same predetermined order is determined for the point compression device 10 and the point expansion device 20. The rearranged point sequence is sent to the point determination unit 23.

When the intersections generated by the expanded intersection generation unit 21 are points P, φP, φ ² P,..., Φ ^(m−1) P, the sequence of points rearranged by the expanded rearrangement unit 22 is (point P , ΦP, φ ² P,..., Φ ^(m−1) P) ^* .

<Step S3d>
The rearranged point sequence (points P, φP, φ ² P,..., Φ ^(m−1) P) ^* and the order position information m _P among the compression information are input to the point determination unit 23. Point determination unit 23 outputs a certain point in order position determined by the order position information m _p. For example, the sequence position information m _p is the case in which an ordinal position of more point P to a number from the left of point sequence is rearranged sequence of points (points P, .phi.P, phi ^{2 P,} ... , Φ ^(m−1) P) ^* Outputs the m _p th point from the left. If the compression information is legitimately compressed by the point compression device 10 based on the point P, this process outputs the point P that is the object of compression.

<Step S4d>
The expansion exception determination unit 24 determines whether or not the point output by the point determination unit 23 is included in the set (φ−1) E (F _{q ^ m} ). When it is determined that it is included in the set (φ−1) E (F _{q ^ m} ), it is determined that the compression information is legitimately compressed by the point compression device 10 based on the point P and correctly expanded. (Step S4dy). If it is determined that it is not included in the set (φ-1) E (F _{q ^ m} ), the compression information has not been properly compressed by the point compression device 10 based on the point P, or has been correctly expanded. It can be determined that there was not (step S4dn). In this case, the point development device 20 does not accept the point output by the point determination unit 23.

In this way, the compression information whose data size is (m−1) × log ₂ q + log ₂ m can be expanded to restore the point P that is the object of compression.

[Lemma 1]
If E (F _{q ^ m} ) / E (F _q ) is a cyclic group of order L, and #E (F _q ) and L are relatively prime,
E (F _{q ^ m} ) [L] = (φ-1) E (F _{q ^ m} )

<< Proof of Lemma 1 >>
phi-1, since a endomorphism on E _{(F q ^ m),} the E _{(F q ^ m)} by homomorphic theorem,
Ker (φ-1) (+) Im (φ-1)
Can be disassembled. Since Ker (φ−1) = E (F _q ),
Im (φ-1) to E (F _{q ^ m} ) / E (F _q )
Since E (F _{q ^ m} ) / E (F _q ) is a cyclic group of order L, and #E (F _q ) and L are relatively prime,
E (F _{q ^ m} ) [L] = (φ-1) E (F _{q ^ m} )
It is.

[Lemma 2]
Pε (φ−1) E (F _{q ^ m} ) ₌ > Σ _{i = 0} ^m−1 φ ⁱ P = O

<< Proof of Lemma 2 >>
From P∈ (φ−1) E (F _{q ^ m} ),
Σ _{i = 0} ^m−1 φ ⁱ P∈ (φ ^m −1) E (F _{q ^ m} ) = {O}
Therefore, Σ _{i = 0} ^m−1 φ ⁱ P = O.

《Supplement for Lemma 2》
If m and #E (F _q ) are relatively prime, the converse is true for Lemma 2. That is,
Σ _{i = 0} ^m−1 φ ⁱ P = O => P∈ (φ−1) E (F _{q ^ m} )
It is. Therefore, when m and #E (F _q ) are relatively prime, the compression exception determination unit 11 (FIG. 1) and / or the deployment exception determination unit 24 (FIG. 3) determines that P∈ (φ−1) E Instead of whether or not (F _{q ^ m} ), it may be determined whether or not Σ _{i = 0} ^m−1 φ ⁱ P = O.

[First method of determining the coefficient]
An example of how to obtain the coefficients λ ₀ , λ ₂ ,..., Λ _{m−1 in} the coefficient generator 13 (FIG. 1) will be described.

f (x, y) = M _m (x, y) + λ ₀ M ₀ (x, y) + Σ _{i = 2} ^m−1 λ _i M _i (x, y) = 0 at points P, φP, φ ² P , ..., substituting φ a ^(m-1) P, respectively, lambda _0, lambda _2, ..., it is the m equations for lambda _m-1. These equations may be solved for λ ₀ , λ ₂ ,..., Λ _m−1 .

That is, the coordinate value of the point P is ( _xφ0 , _yφ0 ), the coordinate value of the point φP is ( _xφ1 , _yφ1 ),..., And the coordinate value of the point φ ^(m−1) P is ( _{xφ (M−1)} , y _{φ (m−1)} ) and substituting these into f (x, y = 0),
M _m (x _φ0 , y _φ0 ) + λ ₀ M ₀ (x _φ0 , y _φ0 ) + Σ _{i = 2} ^m−1 λ _i M _i (x _φ0 , y _φ0 ) = 0
M _m (x _{φ 1} , y _{φ 1} ) + λ ₀ M ₀ (x _{φ 1} , y _{φ 1} ) + Σ _{i = 2} ^m−1 λ _i M _i (x _{φ 1} , y _{φ 1} ) = 0
...
M _m (x _{φ (m−1)} , y _{φ (m−1)} ) + λ ₀ M ₀ (x _{φ (m−1)} , y _{φ (m−1)} ) + Σ _{i = 2} ^m−1 λ _i M _i (x [ _{phi] (m-1)} , y [ _{phi] (m-1)} ) = 0
M _equations for λ ₀ , λ ₂ ,..., Λ _m−1 are obtained. In these formulas, the term M _m of the weight m moved to the right side can be expressed as follows using a matrix.

したがって、係数λ_０，λ_２，…，λ_ｍ−１は、以下のように計算することができる。

Therefore, the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 can be calculated as follows.

[The second way to find the coefficient]
Factor div () of weight m m polynomial f (x, y) = M _m (x, y) + λ ₀ M ₀ (x, y) + Σ _{i = 2} ^m−1 λ _i M _i (x, y) = 0 f)
div (f) = Σ _{i = 0} ^m−1 (φ ⁱ P) −m (O)
It is. Therefore, in the following, in order to obtain the monic polynomial f (x, y) of the weight m, the factor div (f) is div (f) = Σ _{i = 0} ^m−1 (φ ⁱ P) −m (O). Consider creating a polynomial. Here, the factor div (g) for the polynomial g is a formal sum of zeros and poles, the parentheses enclosed in + are the zeros of the polynomial g, and those enclosed in parentheses-are the poles of the polynomial g. Represents.

The following definitions are made for convenience of calculation. In the following,
Q _n = Σ _{i = 0} ⁿ⁻¹ φ ⁱ P
div (f _n ) = Σ _{i = 0} ⁿ⁻¹ (φ ⁱ P) − (Q _n ) − (n−1) (O)
_{Q n = (x n, y} n), φ n P = (x n ', y n') _and, l _{n, v} n a _{l n = (x n '-x} n) (y-y n) - (Y _n ′ −y _n ) (x−x _n )
v _n = (x−x _{n + 1} )
Then,
div (l _n ) = (Q _n ) + (φ ⁿ P) + (− Q _{n + 1} ) −3 (O)
div (v _n ) = (− Q _{n + 1} ) + (Q _{n + 1} ) −2 (O)
Because
f _{n + 1} = f _n l _n / v _n (1)
It is. Since div (f ₁ ) = (P) − (P) −0 (O),
f ₁ = 1 (2)
And can. (1) and the recurrence formula (2) reducing the second and higher terms y _p by defining equation of an ellipse, by repeating m-1 times while Tsubun the denominator and the numerator,
f _m = Σ _{i = 0} ^m−1 (φ ⁱ P) − (Q _m ) − (m−1) (O)
Can be made. Here, if the point Pε (φ−1) E (F _{q ^ m} ), then Q _m = Σ _{i = 0} ^m−1 φ ⁱ P = O (see Lemma 2 above). Therefore,
f _m = Σ _{i = 0} ^m−1 (φ ⁱ P) −m (O)
It becomes. This f _m becomes the monic polynomial f (x, y) of the weight m passing through the points P, φP, φ ² P,..., Φ ^m−1 P. The amount of calculation in this process is O (m ² ) operations over F _{q ^ m} .

The actual calculation of f (x, y) is not necessarily performed based on the above formula. For example,
div (f _n ) = Σ _{i = 0} ⁿ⁻¹ (φ ⁱ P) − (Q _n ) − (n−1) (O)
Against
div (f _n ^{σ ^ n} ) = Σ _{i = n} ²ⁿ⁻¹ (φ ⁱ P) − (φ _n Q _n ) − (n−1) (O)
Because
div (l _n ′) = (Q _n ) + (φ ⁿ Q _n ) + (− Q _2n ) −3 (O)
div (v _n ′) = (− Q _2n ) + (Q _2n ) −2 (O)
If you use l _n ', v _n '
f _2n = f _n f _n ^{σ ^ n} l _n '/ v _n '
It can be.

[Modification]
The plain text can be stochastically embedded at a point on the elliptic curve E (F _{q ^ m} ) using the point expansion device 20. Plaintext is assigned to the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 ∈F _q and a part of the order position information m _P , and the remaining part is determined at random. For example, the value of each digit when the plaintext is expressed in q-adic number is made to correspond to _one of the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 , and the uncorresponding coefficient and the value of the order position information m _P are Determine at random. Then, based on these coefficients λ ₀ , λ ₂ ,..., Λ _m−1 ∈F _q and the order position information m _P , if the point expansion device 20 tries to expand the points and succeeds in expanding the points, the plain text Is embedded in the expanded point.

The order of the set (φ−1) E (F _{q ^ m} ) is approximately q ^m−1 , whereas the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 ∈F _q and the order position information m _Since the variation of the value that _P can take is mq ^m−1 , the probability of successful embedding in a point on the plaintext elliptic curve E (F _{q ^ m} ) is approximately q ^m−1 / mq ^m−1 = 1 / m. Since the success probability of the conventionally known embedding method is 1 / q, it can be said that this method is efficient when m << q.

When it is known that the point P to be subjected to point compression is included in the set (φ−1) E (F _{q ^ m} ), the compression exception determination unit 11 of the point compression device 10 (FIG. 1). And the process of step S1e (FIG. 3) is not necessarily required. Similarly, when it is known that the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 are legitimately generated by the point compression device 10 based on the point P, the point expansion device 20 is used. The development exception determination unit 24 in FIG. 3 and the processing in step S4d (FIG. 4) are not necessarily required.

  In the point compression device 10 illustrated in FIG. 1 and the point expansion device 20 illustrated in FIG. 3, data is directly transmitted between the respective units, but the data is indirectly transmitted through a storage unit (not illustrated). May be.

Further, the compression rearrangement unit 14 may rearrange the points P, φP,..., Φ ^(m−1) P stored in a storage unit (not shown ⁾ in a predetermined order. That is, the points P, φP,..., Φ ^(m−1) P may not be input to the compression rearrangement unit 14. Similarly, the order position order determination unit 15 determines the position order information of the point P at the points P, φP,..., Φ ^(m−1) P stored in the storage unit, and (points P, φP,. φ ^(m−1) P) ^* may not be input. The same applies to the order position information determination unit 15, the expansion rearrangement unit 22, and the point determination unit 23 of the point expansion device 20.

  When the above configuration is realized by a computer, each unit of the point compression device 10 and the point expansion device 20 is described by a program. By executing this program on a computer, the functions of the above-described units are realized on the computer.

  That is, the CPU sequentially reads and executes each program, whereby the compression exception determination unit 11, the compression intersection generation unit 12, the coefficient generation unit 13, the compression rearrangement unit 14, the order position information determination unit 15, and the expansion intersection generation unit 21. The functions of the deployment rearrangement unit 22, the point determination unit 23, and the deployment exception determination unit 24 are realized. The storage unit such as the storage unit (not shown) described above is realized by a storage unit such as a memory or a hard disk.

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

  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.

  As an execution form different from the above-described embodiment, the computer may read the program directly from the portable recording medium and execute processing according to the program. Each time is transferred, 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 a computer but has a property that is based on computer processing).

  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.

  In addition, the various processes described above are not only executed in time series according to the description, but may be executed in parallel or individually according to the processing capability of the apparatus that executes the processes or as necessary. For example, the process of step S3e (FIG. 2) of the point compression apparatus 10 and the processes of step S4e and step S5e may be performed in parallel. Needless to say, other modifications are possible without departing from the spirit of the present invention.

The figure which illustrates the function structure of a point compression apparatus. The flowchart which illustrates the flow of a process of a point compression apparatus. The figure which illustrates the function structure of a point expansion | deployment apparatus. The flowchart which illustrates the flow of a process of a point expansion | deployment apparatus.

Explanation of symbols

DESCRIPTION OF SYMBOLS 10 point compression apparatus 11 Compression exception determination part 12 Compression intersection generation part 13 Coefficient generation part 14 Compression rearrangement part 15 Order position information determination part 20 Point expansion | deployment apparatus 21 Expansion intersection generation part 22 Expansion rearrangement part 23 Point determination part 24 Expansion exception Judgment part

Claims (10)

An elliptic curve E (F _{q ^ m} ) = {(x, y) ∈, where the characteristic q is a prime number or its power, m is an expansion order, a, b∈F _q , and O is an infinite point. In a point compression apparatus that compresses a point PεF _{q ^ m} ² on F _{q ^ m} ² | y ² = x ³ + ax + b} ∪O to generate compression information of the point P,
compression intersection generation means for determining points φP, φ ² P,..., φ ^{(m − 1)} P∈E (F _{q ^ m} ) from the above point P, where φ is a qth power Frobenius map;
The point ^{P, φP, φ 2 P,} ..., φ (m - 1) coefficient of each term of the polynomial curve passing through _{P λ 0, λ 2, ...} , a coefficient generating means for obtaining the λ _m-1 ∈F _q ,
Compression rearrangement means for generating a point sequence in which the points P, φP, φ ² P,..., Φ ^{(m − 1)} P are arranged in a predetermined order;
Order position information determining means for determining information (hereinafter referred to as order position information m _P ) of the position (hereinafter referred to as order position) relating to the order of the points P in the point sequence;
With
Compression information of the point P, the sequence position information m _P and the coefficient lambda _0, lambda _2, ..., compressor point of the elliptic curve, characterized in that it comprises a λ _m-1. In the elliptic curve point compression device according to claim 1,
A compression exception judging means for judging whether or not the point Pε (φ−1) E (F _{q ^ m} );
The compression intersection generating means, when it is determined that the point _{P∈ (φ-1) E (} F q ^ m), from the point P, the point ^{φP, φ 2 P, ...,} φ (m - 1 ⁾ PεE (F _{q ^ m} ) is a means for obtaining each.
An elliptic curve point compression device characterized by the above. An elliptic curve E (F _{q ^ m} ) = {(x, y) ∈, where the characteristic q is a prime number or its power, m is an expansion order, a, b∈F _q , and O is an infinite point. F _{q ^ m} ² | y ² = x ³ + ax + b} In the point expansion device that generates the point P by expanding the compression information of the point P on O,
The compression information of the point P is information (hereinafter referred to as order position information) of position (hereinafter referred to as order position) regarding the order of the point P when a plurality of points including the point P are arranged in a predetermined order. _P ), and coefficients λ ₀ , λ ₂ ,..., Λ _m−1 ∈F _q ,
Expanded intersection generation means for respectively obtaining a plurality of intersections between a curve represented by a polynomial specified by the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 and the elliptic curve E (F _q ^m );
A deployment rearrangement means for generating a point sequence in which the obtained intersections are rearranged in the predetermined order;
A point determination means for outputting a point in the order position determined by the order position information m _P in the point sequence;
An elliptic curve point expansion device. The elliptic curve point expansion device according to claim 3,
Using φ as the qth power Frobenius map, it is determined whether or not the point output by the point output means is included in (φ−1) E (F _{q ^ m} ), and the output point is (φ−1) A deployment exception determining unit that determines that a point has not been normally expanded when it is determined that the point is not included in E (F _{q ^ m} );
An elliptic curve point expansion device. An elliptic curve E (F _{q ^ m} ) = {(x, y) ∈, where the characteristic q is a prime number or its power, m is an expansion order, a, b∈F _q , and O is an infinite point. In the point compression method for compressing the point PεF _{q ^ m} ² on F _{q ^ m} ² | y ² = x ³ + ax + b} ∪O and generating the compression information of the point P,
The compression intersection generation unit obtains points φP, φ ² P,..., Φ ^{(m − 1)} P∈E (F _{q ^ m} ) from the point P , using φ as the qth power Frobenius map. When,
Coefficient generation unit, the point ^{P, φP, φ 2 P,} ..., φ (m - 1) coefficient of each term of the polynomial curve passing through _{P λ 0, λ 2, ...} , a λ _m-1 ∈F _q A coefficient generation step to be obtained;
Compression shuffle play section, the point ^{P, φP, φ 2 P,} ..., φ - a ^{(m 1)} compression rearrangement step of generating a sequence of points arrayed at a predetermined order ^P,
An order position information determination unit for determining information (hereinafter referred to as order position information m _P ) of a position related to the order of the points P in the point sequence (hereinafter referred to as order position);
Have
Compression information of the point P, the sequence position information m _P and the coefficient lambda _0, lambda _2, ..., point compression method of the elliptic curve, characterized in that it comprises a λ _m-1. In the elliptic curve point compression method according to claim 5,
The compression exception determination unit further includes a compression exception determination step of determining whether or not the point Pε (φ−1) E (F _{q ^ m} );
The compression intersection generation step, when it is determined that the point _{P∈ (φ-1) E (} F q ^ m), from the point P, the point ^{φP, φ 2 P, ...,} φ (m - 1 ⁾ P∈E (F _{q ^ m} ) respectively.
An elliptic curve point compression method characterized by the above. An elliptic curve E (F _{q ^ m} ) = {(x, y) ∈, where the characteristic q is a prime number or its power, m is an expansion order, a, b∈F _q , and O is an infinite point. F _{q ^ m} ² | y ² = x ³ + ax + b} ∪ In the point expansion method for generating the point P by expanding the compression information of the point P on ∪O,
The compression information of the point P is information (hereinafter referred to as order position information) of position (hereinafter referred to as order position) regarding the order of the point P when a plurality of points including the point P are arranged in a predetermined order. _P ), and coefficients λ ₀ , λ ₂ ,..., Λ _m−1 ∈F _q ,
A developed intersection generating unit obtains a plurality of intersections between the curve represented by the polynomial specified by the coefficients λ ₀ , λ ₂ ,..., Λ _m−1 and the elliptic curve E (F _q ^m ). Generation step;
Expand shuffle play unit, the expansion rearrangement step of generating a sequence of points rearranged in the order of the intersections Motoma' above said predetermined,
Point determination unit, of the above point sequence, a decision step that outputs a certain point in order position determined by the sequence position information m _P,
A point expansion method of an elliptic curve having The elliptic curve point expansion method according to claim 7,
The expansion exception determination unit determines whether φ is a qth power Frobenius map and whether or not the point output by the point output step is included in (φ−1) E (F _{q ^ m} ), and the output point Of the elliptic curve, further comprising a development exception judgment step for judging that the point has not been developed normally when it is determined that is not included in (φ−1) E (F _{q ^ m} ) Deployment method.   An elliptic curve point compression program for causing a computer to function as the elliptic curve point compression device according to claim 1.   An elliptic curve point expansion program for causing a computer to function as the elliptic curve point expansion device according to claim 3.

Images