JP6228940B2 - SAMPLE DEVICE, SAMPLE METHOD, AND PROGRAM - Google Patents

Description

  The present invention relates to a technique for sampling elements on a specific group of points on an elliptic curve.

In elliptic curve cryptography, there has long been an interest in the problem of how to copy an arbitrary character string such as plain text or hash value to a point on the elliptic curve. One important pairing-friendly elliptic curve is a Barreto-Naehrig curve (BN curve) (see, for example, Non-Patent Document 1). On an algebraic closed field, a BN curve is defined by the following two elliptic curves of the same type.
_{^{E / F p: y 2 =}} x 3 + b
E ′ / F _ρ : y ² = x ³ + b ′
However, E / F _p is an elliptic curve defined on a finite field F _p of order p (where p is a prime number), and E ′ / F _ρ is a finite field F _ρ (F of order ρ = p ² It is an elliptic curve defined on the enlarged body based on _p ). The order of the E / _{F p} is denoted as # E / _{F p,} referred to 'the order of the _{/ F ρ # E' E /} F ρ and. Also, a set of n equally divided points of the E / _{F p} is denoted as E _{/ F} p [n], denoted 'a finite set of n equally divided points of the _{/ F ρ E' E / F} ρ [n] and . These finite sets E / F _p [n] and E ′ / F _ρ [n] each form a county, and are expressed as follows.
G ₁ = E / F _p [n]
G ₂ = E ′ / F _ρ [n]

Non-Patent Document 2 discloses an algorithm F ′ for copying an arbitrary element on a finite field onto a BN curve. If the elliptic curve E / F _p is set so that the entire E / F _p is G ₁ = E / F _p [n], the algorithm F ′ is used to set an arbitrary element on the group G ₁ . You can sample the original.

ただし、｜β｜はβの絶対値を表し、Ｐｒ［γ］は事象γの確率を表し、Ｄ^β，γは識別器Ｄがβ，γを照会して１と判別する事象を表し、Ｃ^ｈおよびＳ^Ｈはｈを照会するＣおよびＨを照会するＳをそれぞれ表し、εは安全変数ｋの関数値を表す。多項式限度のｔ_Ｄ，ｔ_ｓ，ｑ_Ｄに対してεが無視可能関数であるならば、Ｃ^ｈはＨと強識別不可能であるという。 Here, the concept of strong indistinguishability and allowable coding will be described.
<Inability to distinguish strongly>
Up relates Turing machine C to oracle query the cryptographic ideal primitive function h is allowed, there are mimics device S of h running time t _s the oracle query the ideal primitive function H C is allowed, what running time _{t D,} if also satisfies the following for classifier D for the maximum query number _{q D,} ^{C h} is H and _{(t D, t s, q} D, ε) - that is a strong indistinguishable.

Where | β | represents the absolute value of β, Pr [γ] represents the probability of event γ, D ^{β, γ} represents the event that classifier D inquires β, γ and discriminates it as 1, and C ^h and S ^H represent C for inquiring ^h and S for inquiring H, respectively, and ε represents a function value of the safety variable k. _T D polynomial _limit, t s, if ε relative _{q D} is negligible function, ^{C h} is that it is H and strength unidentifiable.

<Allowable encoding>
Let W and U be a finite set. A function F: W → U that satisfies the following three properties is called ε-allowable coding.
[Computability] F can be calculated in a deterministic polynomial time.
[Normality] F (w) for a random variable w uniformly distributed on W cannot be ε-statistically distinguished from a uniform distribution on U.
[Sampleability] An efficient random selection algorithm I exists for every u∈U, and the distribution of I (u) output by the algorithm I for an input u is F ⁻¹ (u) and ε-statistics. Cannot be identified.
Note that “β is γ and ε—statistically indistinguishable” means that the statistical distance between β and γ is less than ε for the negligible function ε. “Β → γ” means that β is mapped to γ.

<Theorem>
The following theorem holds. h: {0,1} ^* → W is a random oracle (cryptographic ideal primitive function), and F: W → U is an ε-allowable encoding. Let t _{I be} the maximum execution time of algorithm I, t _s = 2q _D · t _I, and ε ′ = 4q _D · ε. At this time, F (h (·)): {0, 1} ^* → U is a random oracle (ideal primitive function) H: {0, 1} ^* → U and (t _D , t _s , q _D , ε ′) -Strong identification is impossible.

<Safety of algorithm F '>
However, since the output of the algorithm F ′ described above has a clear distribution bias, even if F ′ (h (•)) is configured using the random oracle h, ε should be a negligible function. I can't. That is, algorithm F ′ does not have normality and sampleability and is not an ε-acceptable encoding. Therefore, the algorithm F ′ has no security based on the above theorem.

In order to solve this problem, Non-Patent Document 2 proposes the following algorithm F ″: {0, 1} ^* → E (F _q ) in which h ₁ and h ₂ are random oracles.
F ″: x → F ′ (h ₁ (x)) + F ′ (h ₂ (x))

Paulo SLM Barreto1 and Michael. Naehrig, “Pairing-Friendly Elliptic Curves of Prime Order,” In B. Preneel and SE Tavares, editors, Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11- 12, 2005, Revised Selected Papers, Volume 3897 of Lecture Notes in Computer Science, pages 319-331, Springer, 2005. P. Fouque and M. Tibouchi, “Indifferentiable hashing to barreto-naehrig curves,” In A. Hevia and G. Neven, editors, Progress in Cryptography, LATINCRYPT 2012-2nd International Conference on Cryptography and Information Security in Latin America, Santiago, Chile, October 7-10, 2012, Proceedings, Volume 7533 of Lecture Notes in Computer Science, pages 1-17, Springer, 2012.

  However, in the above-described algorithm F ″, F ′ needs to be calculated twice, and the amount of calculation is large.

  The subject of this invention is providing the technique which samples the element on the group which consists of an equidistant point on an elliptic curve with safe and small calculation amount.

  The order of the first elliptic curve defined on the finite field is n, the order of the second elliptic curve defined on the extension field of the finite field is m × n> n, and α is m. It is a disjoint integer, and the input element of the extension field is copied to the corresponding point on the second elliptic curve, and the ellipse α × m multiple point of the corresponding point is obtained as the n equally dividing point on the second elliptic curve.

  In the present invention, it is possible to sample elements on a group of equal points on an elliptic curve with a safe and small amount of calculation.

FIG. 1A is a block diagram illustrating a functional configuration of the sample apparatus of the embodiment. FIG. 1B is a block diagram illustrating a functional configuration of the mapping unit. FIG. 2 is a block diagram illustrating the elliptic multiplication unit of the embodiment. FIG. 3A is a flowchart illustrating the sample method according to the embodiment. FIG. 3B is a flowchart illustrating the process of the mapping unit according to the embodiment. FIG. 4 is a block diagram illustrating the processing of the elliptic multiplication unit of the embodiment.

Embodiments of the present invention will be described below.
[Overview]
First, an outline of the embodiment will be described.
The order of the first elliptic curve defined on the finite field is n, the order of the second elliptic curve defined on the extension field of the finite field is m × n> n, and α is mutually equal to m. Suppose that it is a prime integer. n, m, and α are positive integers. In each embodiment, the input element of the enlarged body is copied to a corresponding point on the second elliptic curve, and an ellipse α × m multiple of the corresponding point is obtained as an n-divided point on the second elliptic curve. The n equally divided points on the second elliptic curve thus obtained correspond to m different corresponding points on the second elliptic curve, respectively. That is, in the above-described elliptic α × m multiplication, m different points on the second elliptic curve are copied to the same n equally divided points. Therefore, even if there is a distribution bias in the algorithm for mapping the element of the expansion body to the corresponding point on the second elliptic curve, the bias of the n equally divided points finally obtained is reduced, and the safety is improved. In particular, when following the law of large numbers, normality and sampleability are satisfied, and calculation efficiency is also satisfied by using a well-known efficient method of elliptic multiplication. Therefore, the requirement of ε-acceptable coding is satisfied, and the system of this embodiment cannot be distinguished from a random oracle as a whole (t _D , t _s , q _D , ε ′)-strong. In addition, the calculation for copying the element of the expansion body to the corresponding point on the second elliptic curve may be performed only once, and the amount of calculation is less than the method disclosed in Non-Patent Document 2. From the above, it is possible to sample elements on a group consisting of equal points on an elliptic curve with a safe and small calculation amount.

Since α is relatively prime to m, the elliptical α × m multiplication of the corresponding point on the second elliptic curve is performed by multiplying the corresponding point by the ellipse m, and further from the n equally dividing point of the second elliptic curve. Equivalent to multiplying by α over the group Therefore, even if α ≠ 1, the ellipse α × m times the corresponding point is a source of any of the groups of n equally divided points of the second elliptic curve. Therefore, α = 1 may be satisfied, or α ≠ 1 may be satisfied. In normal elliptic multiplication, the amount of calculation is smaller when α = 1 than when α ≠ 1. On the other hand, even when α ≠ 1, the amount of calculation is smaller than the normal elliptic m multiplication on the second elliptic curve by obtaining the elliptic α × m multiplication point using the Frobenius map on the second elliptic curve. Sometimes you can. For example, if the first and second elliptic curves are BN curves, n = 36u ⁴ + 36u ³ + 18u ² + 6u + 1, m = 36u ⁴ + 36u ³ + 30u ² + 6u + 1, and u is an integer parameter, An ellipse α × m times point on the second elliptic curve may be obtained by the calculation 6u−ψ ³ + 3ψ ² −ψ using the Frobenius map ψ on the two elliptic curve. The amount of calculation is less than that obtained by performing the normal elliptic multiplication to obtain an elliptic m-fold point. The Frobenius map ψ satisfies the relationship ψ ⁴ −ψ ² + 1 = 0. Therefore, an ellipse α × m multiple point on the second elliptic curve may be obtained by another calculation that can be changed to 6u−ψ ³ + 3ψ ² −ψ using this relationship. In addition, α = 1 may be used to obtain an ellipse α × m multiple point using the Frobenius map on the second elliptic curve.

[First Embodiment]
Next, a first embodiment will be described.
In this embodiment, the case where the first and second elliptic curves are the following BN curves is illustrated.
_{^{E / F p: y 2 =}} x 3 + b
E ′ / F _ρ : y ² = x ³ + b ′
However, E / F _p is an elliptic curve (first elliptic curve) defined on a finite field F p of order _p , and E ′ / F _ρ is a finite field F _ρ (F of order ρ = p ² An elliptic curve (second elliptic curve) defined on the enlarged body based on _p ). x and y are variable (coordinate values), the B∈F _p and B'∈F _[rho constants. The order of the E / _{F p} is denoted as # E / _{F p,} referred to 'the order of the _{/ F ρ # E' E /} F ρ and. and _{n = # E / F p,} m = a _{(# E '/ F ρ)} / (# E / F p), when the u is an integer of parametric, p, n, m satisfy the following relationship.
p = 36u ⁴ + 36u ³ + 24u ² + 6u + 1
n = 36u ⁴ + 36u ³ + 18u ² + 6u + 1
m = 36u ⁴ + 36u ³ + 30u ² + 6u + 1
Such m is called the cofactor of the order, and # E ′ / F _ρ = m × n> n. p is a prime number, and n and m may be a prime number or a positive integer other than a prime number.

<Configuration>
As illustrated in FIG. 1A, the sample device 1 of this embodiment includes an input unit 11, a mapping unit 12, an ellipse multiplication unit 13, an output unit 14, and a memory 15. As illustrated in FIG. 1B, the mapping unit 12 of this embodiment includes a first determination unit 121, a second determination unit 122, a third determination unit 123, and an output unit 124. The sample apparatus 1 is, for example, a general-purpose or dedicated computer including a processor (hardware processor) such as a CPU (central processing unit), a memory such as a random-access memory (RAM), a read-only memory (ROM), or the like. An apparatus configured by executing a predetermined program. The computer may include a single processor and memory, or may include a plurality of processors and memory. This program may be installed in a computer, or may be recorded in a ROM or the like in advance. In addition, some or all of the processing units are configured using an electronic circuit that realizes a processing function without using a program, instead of an electronic circuit (circuitry) that realizes a functional configuration by reading a program like a CPU. May be. In addition, an electronic circuit constituting one device may include a plurality of CPUs. Hereinafter, although explanation is omitted, information inputted to and outputted from each part of the sample device 1 is stored in the memory 15 and read out as necessary.

<Processing>
The processing of this embodiment will be described using FIG. 3A.
First, an arbitrary element tεF _{ρ of} a finite field F _ρ (expanded field) is input to the input unit 11 and sent to the mapping unit 12 (step S11). The mapping unit 12 applies an algorithm f to be described later to the transmitted element t, and uses the element t as a corresponding point f (t) = (t _x , t _y ) ∈E ′ on the elliptic curve E ′ / F _ρ. / F _Copy to _ρ . The corresponding point f (t) obtained is sent to the ellipse multiplication unit 13 (step S12). The elliptic multiplication unit 13 performs the elliptic m multiplication (v _x , v _y ) = [m] f (t) ∈E ′ on the elliptic curve E ′ / F _{ρ with} respect to the sent corresponding point f (t). / F _ρ is performed. Since the order # E ′ / F _ρ of the elliptic curve E ′ / F _ρ is n × m, the elliptic point m times (v _x , v _y ) of the corresponding point f (t) is on # E ′ / F _ρ N equal dividing points. # E '/ F finite set consisting of n equally divided points on _{ρ # E' / F ρ [} n] forms a group (the cyclic group in the present _{embodiment), (v x, v y} ) is the group of the original ( v _x , v _y ) ε # E ′ / F _ρ [n] (step S13). The element (v _x , v _y ) is sent to the output unit 14, and the output unit 14 outputs the element (v _x , v _y ) (step S14).

≪Example of details of algorithm f≫
The details of the algorithm f are illustrated. _Let (x ₀ , y ₀ ) ∈ (E ′ / F _ρ ) \ O be an arbitrary point on the elliptic curve E ′ / F _ρ excluding the infinity point O, where x ₀ y ₀ ≠ 0. Let the root be ξ. In this case, the original T∈F _[rho following _x 1 with respect to _{(t), x 2 (t} ), x 3 (t) of the ∈F _[rho, at least one is an elliptic curve E '/ F _ρ on the x Coordinates.

を楕円曲線Ｅ’／Ｆ_ρ上の対応点ｆ（ｔ）として出力する。ただし、χ：Ｆ_ρ→｛−１，１｝は、任意の元ｔ∈Ｆ_ρに対してχ（−ｔ）＝−χ（ｔ）となり、χ（０）＝１となる関数である（ステップＳ１２６）。 The mapping unit 12 obtains a corresponding point f (t) on the elliptic curve E ′ / _Fρ by applying the following algorithm f to the element t (FIG. 3B). First, first determination unit 121 of the mapping unit 12 (FIG. 1B) based on t is input, the first determination unit 121 determines whether the t = 0∈F ρ _(step S121). If t = 0, the first determination unit 121 sets i: = 1 (step S122), and the process proceeds to step S126. However, “β: = γ” means “being β as γ (substituting γ into β)”. If t ≠ 0, based on t is input to the second judging unit 122, the second determination unit 122 determines whether the 1 ^{+ t} 2 = 0∈F ρ _(step S123). If 1 + t ² = 0, the second determination unit 122 sets i: = 3 (step S124), and the process proceeds to step S126. If 1 + t ² ≠ 0, the element t is input to the third determining unit 123, and the third determining unit 123 performs jε such that g (x _j (t)) ^1/2 is an element of the finite field F _ρ. The smallest j of {1, 2, 3} is set to i, and the process proceeds to step S126. However, g (x) = x ³ + b ′ (step S125). In step S126, the output unit 124

_Is output as a corresponding point f (t) on the elliptic curve E ′ / _Fρ . However, χ: F _ρ → {−1, 1} is a function for which χ (−t) = − χ (t) and χ (0) = 1 for an arbitrary element t∈F _ρ ( Step S126).

<Features of this embodiment>
In the method of the present embodiment, the algorithm f for copying the element t of the finite field F _ρ to the corresponding point f (t) on the elliptic curve E ′ / F _ρ need only be calculated once, and the calculation speed is non-patent document 2. About twice as much as the method disclosed in. In addition, since there is an efficient elliptic multiplication method on the BN curve, the method of this embodiment satisfies the computability. It also satisfies normality and sampleability for the following reasons: Therefore, the system of this embodiment cannot be distinguished from a random oracle by (t _D , t _s , q _D , ε ′)-strong.

≪Normality≫
In the elliptic m multiplication in step S13, m different corresponding points f (t) = (t _x , t _y ) on the elliptic curve E ′ / F _ρ are copied to the same n equally divided points. m is sufficiently large, and a finite set E ′ / F _ρ [n] consisting of n equal points obtained by this calculation follows the law of large numbers. Therefore, even if there is a bias in the distribution of the individual outputs f (t) of the algorithm f, the bias in the distribution of the n equally divided points obtained by this elliptic m multiplication is almost negligible, and the uniform distribution and the ε-statistic Cannot be identified. Therefore, the method of this embodiment satisfies normality.

<< Possibility of specimen >>
An arbitrary element Λ∈E ′ / F _ρ [n] of the finite set E ′ / F _ρ [n] can be copied to the element t∈F _ρ of the corresponding finite field F _ρ by the following algorithm.
Input: Λ∈E ′ / F _ρ [n]
Output: t∈F _ρ
procedure:
1-1) Select an arbitrary element Γ∈E ′ / F _ρ [m] of a finite set E ′ / F _ρ [m] composed of m equally divided points on the elliptic curve E ′ / F _ρ .
1-2) to calculate the Ω = Λ + Γ∈E '/ F ρ.
1-3) A set L = I ′ (Ω) whose elements are elements of the finite field F _ρ is calculated.
1-4) Select an arbitrary element μ∈ {1,..., D} from the set {1,..., D} (d is a positive integer).
1-5) If μ ≦ # L, output an arbitrary element t∈L of the set L and end. However, #L is the order of the set L.
1-6) If μ ≦ # L, return to “1-1”.

が有限体Ｆ_ρ上に４つの根を持つなら、ｙ＝χ（ｔ）ｇ（ｔ）^１／２を満たす２つの根をｔ_３，ｔ_４とし、有限体Ｆ_ρ上に２つの根を持つなら、ｙ＝χ（ｔ）ｇ（ｔ）^１／２を満たす方の根をｔ_３とする。ｔ_３が存在し、ｇ（ｘ_１（ｔ_３））^１／２∈Ｆ_ρでなく、かつ、ｇ（ｘ_２（ｔ_３））^１／２∈Ｆ_ρでないならば、Ｌ：＝Ｌ∪｛ｔ_３｝とする。ｔ_４が存在し、ｇ（ｘ_１（ｔ_４））^１／２∈Ｆ_ρでなく、かつ、ｇ（ｘ_２（ｔ_４））^１／２∈Ｆ_ρでないならば、Ｌ：＝Ｌ∪｛ｔ_４｝とする。
２−５）Ｌを出力する。 As I ′ (Ω), for example, the following algorithm can be used.
Input: Ω = (x, y) ∈E ′ / F _ρ
Output: L⊂F _ρ
procedure:
2-1) Let L be an empty set.
2-2) If the equation (x−ξ ² x ₀ ) t ² + (x−ξx ₀ ) = 0 for t has a root on the finite field F _ρ , y = χ (t) g (t) ^{1 /} The root satisfying ² is t ₁ and L: = L∪ {t ₁ }.
2-3) If the equation (x−ξx ₀ ) t ² + (x−ξ ² x ₀ ) = 0 for t has a root on the finite field F _ρ , y = χ (t) g (t) ^{1 / If} the root satisfying ² is t ₂ and g (x ₁ (t ₂ )) ^1/2 εF _ρ is not satisfied, L: = L∪ {t ₂ }.
2-4) Equation for t

_Has four roots on the finite field F _ρ , let t ₃ and t ₄ be the two roots that satisfy y = χ (t) g (t) ^1/2, and two roots on the finite field F _ρ. If so, let t ₃ be the root that satisfies y = χ (t) g (t) ^1/2 . If t ₃ is present and not g (x ₁ (t ₃ )) ^1/2 ∈ F _ρ and not g (x ₂ (t ₃ )) ^1/2 ∈ F _ρ , then L: = L∪ Let {t ₃ }. If t ₄ is present and not g (x ₁ (t ₄ )) ^1/2 ∈ F _ρ and not g (x ₂ (t ₄ )) ^1/2 ∈ F _ρ , then L: = L∪ Let {t ₄ }.
2-5) Output L.

In the algorithm I ′ (Ω) described above, the output L may be an empty set depending on the input value Ω. Therefore, the algorithm I ′ (Ω) itself is not ε-statistically indistinguishable from the random selection algorithm I. However, each Λ∈E ′ / F _ρ is one of m elements E ′ / F _ρ , and m is sufficiently large. Therefore, according to the law of large numbers, the algorithm of 1-1) to 1-6) cannot be discriminated statistically from the random selection algorithm I, and the method of this embodiment satisfies the sampleability.

In step S13 of this embodiment, ellipse m multiplication (v _x , v _y ) = [m] f (t) ∈E ′ / F _ρ is performed. Instead, ellipse α × m multiplication (v _x , v _y ) = [α × m] f (t) ∈E ′ / F _ρ may be performed.

[Second Embodiment]
In the elliptic curve E ′ / F _ρ, there is a linear operation ψ: E ′ / F _ρ → E ′ / F _ρ called a Frobenius map that can perform an operation on the elliptic curve E ′ / F _ρ at high speed. There are f ₁ and f ₂ εF _ρ which are BN curve settings,
ψ: (X, Y) → (f ₁ X *, f ₂ Y *)
Can be calculated. However, (X, Y) is a point on the elliptic curve E ′ / F _ρ , and X * and Y * are conjugates of X and Y on F _ρ , respectively. The relation of ψ ⁴ −ψ ² + 1 = 0 is satisfied. In this embodiment, an ellipse α × m multiple point (v _x , v _y ) on the elliptic curve E ′ / F _ρ is obtained using this Frobenius map ψ. In the following description, differences from the first embodiment will be mainly described, and the same reference numerals will be used for the matters already described, and description thereof will be omitted.

<Configuration>
As illustrated in FIG. 1A, the sample device 2 of this embodiment includes an input unit 11, a mapping unit 12, an ellipse multiplication unit 23, an output unit 14, and a memory 15. The sample apparatus 2 may be an apparatus configured by the above-described computer executing a predetermined program, or may be an apparatus in which a part or all of the processing units are configured using an electronic circuit. .

<Processing>
The processing of this embodiment will be described using FIG. 3A. In this embodiment, the processes of steps S11 and S12 described in the first embodiment are executed, the following process of step S23 is executed instead of step S13, and then the process of step S14 described in the first embodiment is performed. Executed. The process of step S23 will be described.

<< Step S23 >>
The ellipse multiplication unit 23 uses the Frobenius map ψ for the sent corresponding point f (t), and an ellipse α × m multiple point [α × m] f (t) ∈ on the elliptic curve E ′ / F _ρ. E '/ _Fρ is obtained and output. α = 1 or α ≠ 1, and there is no limitation on the calculation method of the ellipse α × m multiple point [α × m] f (t) using the Frobenius map ψ. The elliptic curve E ′ / F _ρ of this embodiment forms a cyclic group of order n × m, and is an eigenspace related to the eigenvalue λ of the Frobenius map ψ (common to the elliptic curve forming the cyclic group). In this case, applying the Frobenius map ψ to the point Θ∈E ′ / F _ρ is equal to multiplying the point Θ by the ellipse λ on the elliptic curve E ′ / F _ρ (ψΘ = λΘ). If the function c (λ) relating to the eigenvalue λ satisfies c (λ) ≠ 0 (mod n) and c (λ) = 0 (mod m), the elliptic c (λ) multiplication of the point Θ is a point Θ is multiplied by α × m. Applying an operation expressed by replacing λ of c (λ) with ψ to the corresponding point f (t) is an ellipse α × m multiple [α × m] using the Frobenius map ψ. This is an operation Φ for obtaining f (t). However, the amount of calculation required for the calculation of the ellipse α × m multiple point [α × m] f (t) using the Frobenius map ψ is smaller than the calculation amount of the normal elliptic m multiplication of f (t). Is desirable. For example, the ellipse multiplication unit 23 desirably obtains an ellipse α × m multiple point [α × m] f (t) by the following operation Φ.
Φ: T → (6u−ψ ³ + 3ψ ² −ψ) T (1)
However, a _{T∈E '/ F ρ, T =} f (t) and the elliptical alpha × m times points by [alpha × m] can be calculated f (t).

≪T → (6u−ψ ³ + 3ψ ² −ψ) T calculation example≫
As illustrated in FIG. 2, the elliptic multiplication unit 23 that performs the calculation of Expression (1) includes calculation units 230 to 238 and an output unit 239. In this case, as illustrated in FIG. 4, the calculation unit 230 substitutes the input f (t) for T (T: = f (t) εE ′ / F _ρ ), and outputs the obtained T ( Step S230). The computing unit 231 substitutes the inputted T for R (R: = T), and outputs the obtained R (step S231). The calculating unit 232 receives T and obtains Q: = (6u) T and outputs it (step S232). The computing unit 233 receives R and obtains R: = ψR and outputs it (step S233). The calculation unit 234 receives Q and obtains Q: = QR and outputs it (step S234). The calculation unit 235 receives R and obtains R: = ψR and outputs it (step S235). The calculation unit 236 receives Q and obtains Q: = Q + 3R and outputs it (step S236). The computing unit 237 receives R and obtains R: = ψR and outputs it (step S237). The calculation unit 238 receives Q and obtains Q: = QR and outputs it (step S238). The output unit 239 outputs Q (step S239).

<Features of this embodiment>
In the present embodiment, the ellipse α × m multiple point [α × m] f (t) on the elliptic curve E ′ / F _ρ is calculated using the Frobenius map ψ, so that the speed can be increased as compared with the method of the first embodiment. There is a case. For example, when the method of Formula (1) is used, the speed can be increased by about 4 times compared with the method of the first embodiment.

[Other variations]
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. Moreover, you may comprise the apparatus which has the process parts 31-1 to 31-6 which respectively perform each process of 1-1)-1-6) mentioned above, and obtains the output t from input (LAMBDA). Such an apparatus may be an apparatus configured by the above-described computer executing a predetermined program, or an apparatus in which a part or all of the processing units are configured using an electronic circuit. Good. Needless to say, other modifications are possible without departing from the spirit of the present invention.

  When the above configuration is realized by a computer, the processing contents of the functions that each device should have are described by a program. By executing this program on a computer, the above processing functions are realized on the computer. The program describing the processing contents can be recorded on a computer-readable recording medium. An example of a computer-readable recording medium is a non-transitory recording medium. Examples of such a recording medium are a magnetic recording device, an optical disk, a magneto-optical recording medium, a semiconductor memory, and the like.

  This program is distributed, for example, 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, this computer reads a program stored in its own recording device and executes a process according to the read program. As another execution form of the program, the computer may read the program directly from the portable recording medium and execute processing according to the program, and each time the program is transferred from the server computer to the computer. The processing according to the received program may be executed sequentially. The above-described processing may be executed by a so-called ASP (Application Service Provider) type service that realizes a processing function only by an execution instruction and result acquisition without transferring a program from the server computer to the computer. Good.

  In the above embodiment, the processing functions of the apparatus are realized by executing a predetermined program on a computer. However, at least a part of these processing functions may be realized by hardware.

  The present invention can be used to safely and quickly map an arbitrary value on a finite field to a point on an elliptic curve in an encryption method using an elliptic curve such as an ID-based encryption method or a function encryption method.

1, 2 Specimen device

Claims (8)

The order of the first elliptic curve defined on the finite field is n, the order of the second elliptic curve defined on the extension field of the finite field is m × n> n, and α is m. A disjoint integer,
A mapping unit that maps the input element of the magnified body to a corresponding point on the second elliptic curve;
An elliptic multiplication unit that obtains an ellipse α × m times the corresponding point as an n-divided point on the second elliptic curve;
Specimen device with. The specimen device of claim 1, comprising:
Sample device where α = 1. The specimen device according to claim 1 or 2, wherein
α ≠ 1,
The elliptic multiplication unit obtains an ellipse α × m multiple point on the second elliptic curve using the Frobenius map on the second elliptic curve,
The amount of computation for obtaining an ellipse α × m multiple point on the second elliptic curve using the Frobenius map on the second elliptic curve is smaller than the amount of computation of ellipse m multiplication on the second elliptic curve. , Specimen device. The specimen device according to any one of claims 1 to 3,
The first and second elliptic curves are BN curves;
n = 36u ⁴ + 36u ³ + 18u ² + 6u + 1,
m = 36u ⁴ + 36u ³ + 30u ² + 6u + 1,
A sampling device where u is an integer parameter. The specimen device of claim 4, wherein
The elliptic multiplication unit uses the Frobenius map ψ that can be changed to the calculation 6u−ψ ³ + 3ψ ² −ψ or the calculation 6u−ψ ³ + 3ψ ² −ψ using the Frobenius map ψ on the second elliptic curve. The sample device obtains an ellipse α × m multiple point on the second elliptic curve by the calculation. The specimen device according to claim 4 or 5, wherein
The element of the extension field is t, (x ₀ , y ₀ ) is an arbitrary point where x ₀ y ₀ ≠ 0 on the second elliptic curve excluding the infinity point, and ξ is the primitive cube of 1 Root, g (x) = x ³ + b ′, b ′ is an element of the extension, and satisfies χ (−t) = − χ (t) and χ (0) = 1,

And
The mapping unit is
If t = 0, (x ₁ (t), χ (t) g (x ₁ (t)) ^1/2 ) is the corresponding point,
If 1 + t ² = 0, (x ₃ (t), χ (t) g (x ₃ (t)) ^1/2 ) is the corresponding point,
If t ≠ 0 and _{^{1 + t 2 ≠ 0, g}} (x j (t)) 1/2 of the minimum of j? {1, 2, 3} which is the source of the extension field _(x j _(t) , Χ (t) g (x _j (t)) ^1/2 ) as the corresponding point. The order of the first elliptic curve defined on the finite field is n, the order of the second elliptic curve defined on the extension field of the finite field is m × n, and m × n> n. And α is a relatively prime integer with m,
A mapping step for mapping the input element of the magnified body to a corresponding point on the second elliptic curve;
An ellipse multiplication unit for obtaining an ellipse α × m multiplication point of the corresponding point as an n-divided point on the second elliptic curve;
Specimen method having.   A program for causing a computer to function as the specimen device according to claim 1.

Images