Okayama University

Yasuyuki Nogami

Yoshitaka Morikawa

Yumi Sakemi

Masataka Akane

Hidehiro Kato

Hiroaki Nasu

Kenta Nekado

Provided are a pairing computation device, a pairing computation method, and a pairing computation program all of which enable fast pairing computation. The pairing computation device includes, where:

Pairing computation device, pairing computation method, and pairing computation program

There is provided a pairing computation device provided with a CPU which computes pairing e(S,Q) with S&#x3b5;G, Q&#x3b5;G, &#x3c7; being a given integer variable, and F being a rational function calculated using Miller's algorithm with respect to multi-pairing (MMA). An order r, a trace t of the Frobenius endomorphism &#x3c6;are specified preliminarily using the integer variable &#x3c7; according to an embedding degree k. The CPU performs pairing computation by means of: an input unit which inputs the integer variable &#x3c7;, the rational point S, and the rational point Q into respective predetermined registers; a computation unit which computes F; a computation unit which computes a value at a rational point Q(x, y) of a straight line passing through given rational points; a computation unit which computes f'(Q) using the aforementioned F and the value; and a computation unit which computes the pairing e(S,Q) using aforementioned f&#x2032;(Q) as [F83]. [F83]()=().

Pairing computation device, pairing computation method and recording medium storing pairing computation program

Provided are a scalar multiplier and a scalar multiplication program for performing a scalar multiplication at a high speed. In computing a scalar multiplication [s]P of a rational point P of an additive group E(F) including rational points on an elliptic curve where a characteristic p, an order r, and a trace t of a Frobenius endomorphism at an embedding degree k=12 using an integer variable &#x3c7; are given by: p(&#x3c7;)=36&#x3c7;&#x2212;36&#x3c7;+24&#x3c7;&#x2212;6&#x3c7;+1, r(&#x3c7;)=36&#x3c7;&#x2212;36&#x3c7;+18&#x3c7;&#x2212;6&#x3c7;+1=p(&#x3c7;)+1&#x2212;t(&#x3c7;), t(&#x3c7;)=6&#x3c7;+1, the scalar multiplication [s]P is computed as: [s]P=([A]&#x3c6;'+[B])P, using a Frobenius map &#x3c6;&#x2032;given by: [p]P=&#x3c6;&#x2032;(P) assuming that a twist degree d is 6 and a positive integer e is 2 where k=d&#xd7;e.

Scalar multiplier and scalar multiplication program

In an arithmetic operation method and an arithmetic operation device arithmetic operations such as exponentiation or scalar multiplication can be performed at high speed. In the case where there exists a plurality of different elements Y and each element Y is represented by tuples in which a plurality of different elements X are combined with an operator, an arithmetic operation method for calculating each element Y by using an electronic computer, associates each element Y with the element X by setting each element X, sets temporary data having an index indicating whether or not each element Y has an identical element X for each element X, and represents each element Y by the temporary data combined with the operator. When there is a combination of temporary data which is common in plurality of elements Y in temporary data contained in each element Y, new temporary data is set by combining the common temporary data and each element Y consisting of each tuple is calculated using the new temporary data.

Arithmetic operation method and arithmetic operation device

There is provided a pairing computation device, a pairing computation method and a recording medium recording a pairing computation program all enabling a pairing computation at high speed. In the case where the Ate pairing e(Q,P) is defined as in equation (1) and k is any one of even, a multiple of 3, a multiple of 4, and a multiple of 6, arithmetic operations of a rational function which is required to derive the Miller function f(P) are performed on the proper subfield specified by a twist curve using a quadratic and cubic non-residue v which becomes 1 when an exponentiation of this f(P) to the power of (q&#x2212;1)/r is performed.

Pairing computation device, pairing computation method and recording medium recording pairing computation program

There is provided a computer-readable recording medium recording a program for encryption/decryption, an apparatus for encryption/decryption, an apparatus for multiplication in an extension field, that enable to perform high speed multiplication processing, while allowing the selection of arbitrary key lengths. In multiplying two elements A={a, a, a, . . . , a} and B={b, b, b, . . . , b} in an extension field Fof extension degree m with a prime number p as characteristic, firstly, a positive integer k is determined such that km+1 is a prime number and p is a primitive element in F. Next, two elements A and B are multiplied as two elements in extension field Fof extension degree km with a prime number p as characteristic using the positive integer k. Lastly, using the result of such multiplication, a result of multiplication in an element in the extension field Fof extension degree m which is a subfield of Fis obtained.

Growing community of inventors

Okayama, Japan

Yasuyuki Nogami