Search

It is said that the lower bound of the number of iterations of Miller's algorithm for pairing calculation is log2 r/φ(k), where φ(·) is the Euler's function, r is the group order, and k is the embedding degree. Ate pairing reduced the number of the loops of Miller's algorithm of Tate pairing from ⌊log2 r⌋ to ⌊ log2(t-1)⌋, where t is the Frobenius trace. Recently, it is known to systematically prepare a pairing-friendly elliptic curve whose parameters are given by a polynomial of integer variable “χ.” For such a curve, this paper gives integer variable χ-based Ate (Xate) pairing that achieves the lower bound. In the case of the well-known Barreto-Naehrig pairing-friendly curve, it reduces the number of loops to ⌊log2χ⌋. Then, this paper optimizes Xate pairing for Barreto-Naehrig curve and shows its efficiency based on some simulation results.

This paper presents implementation techniques of fast Ate pairing of embedding degree 12. In this case, we have no trouble in finding a prime order pairing friendly curve E such as the Barreto-Naehrig curve $y^2=x^3+a, a\\in\\Fp{}$. For the curve, an isomorphic substitution from $\\Gii\\subset \\EFpxii$ into $\\Gii'$ in subfield-twisted elliptic curve $\\EdFpii$ speeds up scalar multiplications over $\\Gii$ and wipes out denominator calculations in Miller's algorithm. This paper mainly provides about 30% improvement of the Miller's algorithm calculation using proper subfield arithmetic operations. Moreover, we also provide the efficient parameter settings of the BN curves. When p is a 254-bit prime, the embedding degree is 12, and the processor is Pentium4 (3.6GHz), it is shown that the proposed algorithm computes Ate pairing in 13.3 milli-seconds including final exponentiation.

This paper proposes an exponentiation method with Frobenius mappings. The main target is an exponentiation in an extension field. This idea can be applied for scalar multiplication of a rational point of an elliptic curve defined over an extension field. The proposed method is closely related to so-called interleaving exponentiation. Unlike interleaving exponentiation methods, it can carry out several exponentiations of the same base at once. This happens in some pairing-based applications. The efficiency of using Frobenius mappings for exponentiation in an extension field was well demonstrated by Avanzi and Mihailescu. Their exponentiation method efficiently decreases the number of multiplications by inversely using many Frobenius mappings. Compared to their method, although the number of multiplications needed for the proposed method increases about 20%, the number of Frobenius mappings becomes small. The proposed method is efficient for cases in which Frobenius mapping cannot be carried out quickly.

A class of zero-correlation zone (ZCZ) sequences constructed by the recursive procedure from a perfect sequence and a unitary matrix was proposed by Torii, Nakamura, and Suehiro [1]. In the reference [1], three parameters, s.t., the sequence length, the family size and the length of the ZCZ, were evaluated for a general estimate of the performance of the ZCZ sequences. In this letter, we give more detailed distributions of that correlation values are zero on their ZCZ sequence sets.

Self-dual normal basis is efficient for the arithmetic operations in extension field and especially trace calculation. However, self-dual normal bases do not exist in [image omitted] when characteristic p is odd and degree m is even. This paper proposes a method to construct an efficient normal basis for trace calculation when extension degree is even. In this paper, we call it pseudo self-dual normal basis.

This paper proposes a method for generating a basis translation matrix between isomorphic extension fields. To generate a basis translation matrix, we need the equality correspondence of a basis between the isomorphic extension fields. Consider an extension field Fp m where p is characteristic As a brute force method, when p m is small, we can check the equality correspondence by using the minimal polynomial of a basis element; however, when p m is large, it becomes too difficult. The proposed methods are based on the fact that Type I and Type II optimal normal bases (ONBs) can be easily identified in each isomorphic extension field. The proposed methods efficiently use Type I and Type II ONBs and can generate a pair of basis translation matrices within 15 ms on Pentium 4 (3.6 GHz) when mlog 2 p = 160.

This paper shows a necessary condition for type– and Gauss period normal bases in Fpm to be the same normal basis by using their traces.

This paper proposes a multiplication algorithm for Fpm, which can be efficiently applied to many pairs of characteristic p and extension degree m except for the case that 8p divides m(p–1). It uses a special class of type-〈k, m〉 Gauss period normal bases. This algorithm has several advantages: it is easily parallelized; Frobenius mapping is easily carried out since its basis is a normal basis; its calculation cost is clearly given; and it is sufficiently practical and useful when parameters k and m are small.

An anonymous credential system allows a user to convince a service provider anonymously that he/she owns certified attributes. Previously, an anonymous credential system was proposed to prove user's attributes to satisfy a monotone formula, i.e., a logic relation with any combination of AND/OR relations. However, this system has a problem of requiring large authentication time which depends on the number of attributes in the proved formula. In this paper, we propose methods to accelerate the authentication time by reducing the exponentiation costs for the calculations of accumulator and the witness which are used in the system. We implemented the accelerated system using a fast pairing library, and measured the authentication times, while changing the size of the proved relation.

This paper addresses a job scheduling problem in Volunteer Computing (VC) systems, where some malicious participant may return incorrect results (sabotaging). Credibility-based job scheduling method, namely ENR-ECJ, is a promising approach to realize high-performance and sabotage-tolerant VC systems based on the credibility of each participant (worker). However, managing the credibility values in the management node may cause considerable performance degradation of whole the system. By implementing ENR-ECJ into a small scale VC system, this paper demonstrates the primacy of ENR-ECJ over existing methods and reveals its condition through the performance evaluation for various number of workers. The results show that ENR-EJC improves the overall performance about 10% when the access frequency of workers is less than 2 per second.

This paper presents the performance evaluations of GMP-based applications on Web-based Volunteer Computing (VC) systems. Web-based VC is expected to gather many volunteer participants (workers) by allowing workers to execute a computation program (job) on Web browsers. On the other hand, the job execution performance on workers degraded because jobs are executed on Web browsers. To reveal the actual performance of Web-based VC, we convert practical applications which use GMP, that is a multi-precision library for scientific computations, and evaluate its performance. The experimental results show that the performance degradation is negligibly small in some cases, e.g. a short bit-length of arguments. This paper also shows a potential for the performance improvement of Web-based VC by substituting GMP functions.

An anonymous credential system allows a user to convince a service provider anonymously that he/she owns certified attributes. Previously, we proposed a paring-based anonymous credential system with constant size of proofs, where the combinations of logical AND and OR relations on user attributes can be proved as CNF formulas. However, this system has a problem of requiring large online computation time during authentication, which depends on the number of AND relations in the proved formula. In this paper, we propose an efficiency improvement of the computational overhead based on online/offline precomputation technique. In our improvement, all exponentiations that can be used for the accumulator and witness computations are executed in advance in the precomputation algorithm. Thus, exponentiations in the online accumulator and witness computations are excluded, and only multiplications are needed. We implemented the system using a fast pairing library, and measured the processing times, while changing the size of the proved CNF formula. The experimental result shows that the computational costs of the proof generation in the case of using lots of AND relations are greatly reduced than the previous system. Hence, it is practical for mobile users.

Recent efficient pairings such as Ate pairing use two efficient subgroups of rational point such that \(\pi (P)=P\) and \(\pi (Q)=[p]Q\), where \(\pi \), \(p\), \(P\), and \(Q\) are the Frobenius map for rational point, the characteristic of definition field, and torsion points for pairing, respectively. This relation accelerates not only pairing but also pairing–related operations such as scalar multiplications. It holds in the case that the embedding degree \(k\) divides \(r-1\), where \(r\) is the order of torsion rational points. Thus, such a case has been well studied. Alternatively, this paper focuses on the case that the degree divides \(r+1\) but not \(r-1\). First, this paper shows a transitive representation for \(r\)–torsion points based on the fact that the characteristic polynomial \(f(\pi )\) becomes irreducible over \(\mathbb {F}_{r}\) for which \(\pi \) also plays a role of variable. In other words, this paper proposes an elliptic curve discrete logarithm on such a torsion group. After that, together with some example parameters, it is shown how to prepare such pairing–friendly elliptic curves.

This paper proposes a compact and efficient \(GF(2^8)\) inversion circuit design based on a combination of non-redundant and redundant Galois Field (GF) arithmetic. The proposed design utilizes redundant GF representations, called Polynomial Ring Representation (PRR) and Redundantly Represented Basis (RRB), to implement \(GF(2^8)\) inversion using a tower field \(GF((2^4)^2)\). In addition to the redundant representations, we introduce a specific normal basis that makes it possible to map the former components for the 16th and 17th powers of input onto logic gates in an efficient manner. The latter components for \(GF(2^4)\) inversion and \(GF(2^4)\) multiplication are then implemented by PRR and RRB, respectively. The flexibility of the redundant representations provides efficient mappings from/to the \(GF(2^8)\). This paper also evaluates the efficacy of the proposed circuit by means of gate counts and logic synthesis with a 65 nm CMOS standard cell library and comparisons with conventional circuits, including those with tower fields \(GF(((2^2)^2)^2)\). Consequently, we show that the proposed circuit achieves approximately 40 % higher efficiency in terms of area-time product than the conventional best \(GF(((2^2)^2)^2)\) circuit excluding isomorphic mappings. We also demonstrate that the proposed circuit achieves the best efficiency (i.e., area-time product) for an AES encryption S-Box circuit including isomorphic mappings.

Optimal Prime Fields (OPFs) are considered to be one of the best choices for lightweight elliptic curve cryptography implementation on resource-constraint embedded processors. In this paper, we revisit efficient implementation of the modular arithmetic over the special prime fields, and present improved implementation of modular multiplication for OPFs, called Optimal Prime Field Coarsely Integrated Operand Caching (OPF-CIOC) method. OPF-CIOC method follows the general idea of (consecutive) operand caching technique, but has been carefully optimized and redesigned for Montgomery multiplication in an integrated fashion. We then evaluate the practical performance of proposed method on representative 8-bit AVR processor. Experimental results show that the proposed OPF-CIOC method outperforms the previous best known results in ACNS’14 by a factor of 5 %. Furthermore, our method is implemented in a regular way which helps to reduce the leakage of side-channel information.

In this paper, we particularly deal with no F p -rational two-torsion elliptic curves, where Fp is the prime field of the characteristic p. First we introduce a shift product-based polynomial transform. Then, we show that the parities of (#E - 1)/2 and (#E'- 1)/2 are reciprocal to each other, where #E and #E' are the orders of the two candidate curves obtained at the last step of complex multiplication (CM)-based algorithm. Based on this property, we propose a method to check the parity by using the shift product-based polynomial transform. For a 160 bits prime number as the characteristic, the proposed method carries out the parity check 25 or more times faster than the conventional checking method when 4 divides the characteristic minus 1. Finally, this paper shows that the proposed method can make CM-based algorithm that looks up a table of precomputed class polynomials more than 10 percent faster.

This paper addresses the problem of job scheduling in volunteer computing (VC) systems where each computation job is replicated and distributed to multiple participants (workers) to remove incorrect results. In the job scheduling of VC, the number of assigned workers to complete a job is an important factor for the system performance, however, it cannot be fixed because some of the workers may not return results in real VC. We propose a job scheduling method which considers the expected probability of completion (EPC) for each job based on the worker's history information. The key idea of the proposed method is to assign jobs so that EPC is always greater than a specified value (SPC). By setting SPC as a reasonable value, any job in the proposed method can be completed without excess allocations, which leads to the higher performance of VC systems. Simulation results show that the performance of the proposed method is up to 5 times higher than that of the conventional method, while keeping the error rate lower than a required value.

This paper focuses on developing a square root (SQRT) algorithm in finite fields GF(p2d) (d ≥ 0). Examining the Smart algorithm, a well-known SQRT algorithm, we can see that there is some computation overlap between the Smart algorithm and the quadratic residue (QR) test, which must be implemented before a SQRT computation. It makes the Smart algorithm inefficient. In this paper, we propose a new QR test and a new SQRT algorithm in GF(p2d), in which not only there is no computation overlap, but also most of computations required for the proposed SQRT algorithm in GF(p2d) can be implemented in the corresponding subfields GF(p2d-i) for 1 ≤ i ≤ d, which yields many reductions in the computational time and complexity. The computer simulation also shows that the proposed SQRT algorithm is much faster than the Smart algorithm.

This paper proposes an extension field named TypeII AOPF. This extension field adopts TypeII optimal normal basis, cyclic vector multiplication algorithm, and Itoh-Tsujii inversion algorithm. The calculation costs for a multiplication and inversion in this field is clearly given with the extension degree. For example, the arithmetic operations in TypeII AOPF Fp5 is about 20% faster than those in OEF Fp5. Then, since CVMA is suitable for parallel processing, we show that TypeII AOPF is superior to AOPF as to parallel processing and then show that a multiplication in TypeII AOPF becomes about twice faster by parallelizing the CVMA computation in TypeII AOPF.

In most of the methods of public key cryptography devised in recent years, a finite field of a large order is used as the field of definition. In contrast, there are many studies in which a higher-degree extension field of characteristic 2 is fast implemented for easier hardware realization. There are also many reports of the generation of the required higher-degree irreducible polynomial, and of the construction of a basis suited to fast implementation, such as an optimal normal basis (ONB). For generating higher-degree irreducible polynomials, there is a method in which a 2m-th degree self-reciprocal irreducible polynomial is generated from an m-th degree irreducible polynomial by a simple polynomial transformation (called the self-reciprocal transformation). This paper considers this transformation and shows that when the set of zeros of the m-th degree irreducible polynomial forms a normal basis, the set of zeros of the generated 2m-th order self-reciprocal irreducible polynomial also forms a normal base. Then it is clearly shown that there is a one-to-one correspondence between the transformed irreducible polynomial and the generated self-reciprocal irreducible polynomial. Consequently, the inverse transformation of the self-reciprocal transformation (self-reciprocal inverse transformation) can be applied to a self-reciprocal irreducible polynomial. It is shown that an m-th degree irreducible polynomial can always be generated from a 2m-th degree self-reciprocal irreducible polynomial by the self-reciprocal inverse transformation. We can use this fact for generating 1/2-degree irreducible polynomials. As an application of 1/2-degree irreducible polynomial generation, this paper proposes a method which generates a prime degree irreducible polynomial with a Type II ONB as its zeros. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 88(7): 23–32, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20151

As an accessible and high-performance computing environment, we have studied Web-based Volunteer Computing (VC), in which users can join a VC with just accessing a specified URL on Web browsers. A major problem of Web-based VC has been the difficulty of implementing some advanced functions such as direct communications among users and file sharing, because all processes must be handled onWeb browsers. For this problem, we propose a solution to realize a P2P communication function among Web browsers by using recent Web techniques such as Web Real-Time Communication (WebRTC) API and its library, PeerJS. As an useful application of our method, we demonstrate file sharing on Web browsers. Experimental result indicates that our method achieves almost 50% reduction in the total time of file distribution.

According to some recent implementation reports on Ate---based pairings such as optimal ate pairing with Barreto---Naehrig curve whose embedding degree is 12, sparse multiplication accelerates Miller's loop calculation in a pairing calculation. Especially, 7---sparse multiplication is available when the implementation uses affine coordinates, where 7---sparse means that the multiplicand or multiplier has 7 zeros among 12 coefficients. This paper extends it to pseudo 8---sparse multiplication. Then, some experimental results together with theoretic calculation costs are shown in order to evaluate its efficiency.

This paper shows an approach for reducing the size of the exponent of final exponentiation with multiplying some extra terms. In the case of Tate and Ate pairings with Barreto-Naehrig curve whose embedding degree is 12, the exponent is reduced to (p4 - p2+ 1)/r, where p is the characteristic of the base field and r is the order of pairing.

A lot of improvements and optimizations for the hardware implementation of AES algorithm have been reported. These reports often use, instead of arithmetic operations in the AES original \(\mathbb{F}_{2^8}\), those in its isomorphic tower field \(\mathbb{F}_{((2^{2})^{2})^2}\) and \(\mathbb{F}_{(2^4)^2}\). This paper focuses on \(\mathbb{F}_{(2^4)^2}\) which provides higher–speed arithmetic operations than \(\mathbb{F}_{((2^{2})^{2})^2}\). In the case of adopting \(\mathbb{F}_{(2^4)^2}\), not only high–speed arithmetic operations in \(\mathbb{F}_{(2^4)^2}\) but also high–speed basis conversion matrices from the \(\mathbb{F}_{2^8}\) to \(\mathbb{F}_{(2^4)^2}\) should be used. Thus, this paper improves arithmetic operations in \(\mathbb{F}_{(2^4)^2}\) with Redundantly Represented Basis (RRB), and provides basis conversion matrices with More Miscellaneously Mixed Bases (MMMB).

EMV signature is one of specifications for authenticating credit and debit card data, which is based on ISO/IEC 9796-2 signature scheme. At CRYPTO 2009, Coron, Naccache, Tibouchi, and Weinmann proposed a new forgery attack against the signature ISO/IEC 9796-2. They also briefly discussed the possibility when the attack is applied to the EMV signatures. They showed that the forging cost is $45,000 and concluded that the attack could not forge them for operational reason. However their results are derived from not fully analysis under only one condition. The condition they adopt is typical case. For security evaluation, fully analysis and an estimation in worst case are needed. This paper shows cost-estimation of CNTW attack against EMV signature in detail. We constitute an evaluate model and show cost-estimations under all conditions that Coron et al. do not estimate. As results, it has become clear that EMV signature can be forged with less than $2,000 according to a condition. This fact shows that CNTW attack might be a realistic threat.

Pollard's ρ method is well known as an efficient method for solving elliptic curve discrete logarithm problem (ECDLP). This paper applies it to non-super singular pairing-friendly curves, especially to Barreto-Naehrig curves, together with Frobenius endomorphism. Then, it is shown that the list of rational points can be reduced with norms of their x and y coordinates without loss of theoretic uniqueness.

This paper deals with r-torsion rational points on ordinary pairing-friendly curves such that the embedding degree k divides r + 1, where r is the order of rational points. Especially, its group structure is focused on. In this case, the twisted characteristic polynomial f'(\pi_d) becomes irreducible over Fr, where \pi_d is the skew Frobenius map with twist degree d such as quadratic, cubic, quartic, and sextic. Then, using the irreducible polynomial f'(\pi_d), this paper considers a multiplicative representation of r?torsion rational points.

This paper proposes a method for generating a certain composite order ordinary pairing-friendly elliptic curve of embedding degree 1. In detail, the order has two large prime factors such as the modulus of RSA cryptography. The method is based on a property that the order of the target pairing-friendly curve is given by a cyclotomic polynomial as r(x) of degree 2 with respect to the integer variable x. When the bit size of the prime factors is almost 1000 bits, the proposed method averagely takes about 20 hours on Core 2 Duo (3.0GHz) for generating one.

Recently, pairing-based cryptographies such as ID-based cryptography and group signature have been studied. For their implementations, pairings such as Xate pairing and R-ate pairing are efficient. In order to make pairing calculations faster, it is important to make not only pairing algorithms but also arithmetic operations in the definition field efficient. Thus, in several kinds of ordinary pairing-friendly curves, this paper focuses on Freeman curve that enables fast pairing-based cryptographies. This paper proposes ultimately an customized multiplication algorithm in the extension field for Freeman curve, and then shows some implementation results of Xate pairing and R-ate pairing with Freeman curve.

Many public-key cryptographers have recently focused on cryptographic schemes based on pairing, which is a bilinear map from two elliptic curve groups to a group in an extension field. In order to provide efficient pairings, several kinds of pairing-friendly curves have been proposed. Since most of the pairing-friendly curves are defined over a certain extension field, arithmetic operations in extension field should be carried out efficiently. Especially for final exponentiation included in pairing calculation, squaring is more important than multiplication. This paper proposes an efficient squaring algorithm in 2-nd tower field available for various pairing-friendly curves.

The joint sparse form (JSF) is a representation of a pair of integers, which is famous for accelerating a multi-scalar multiplication in elliptic curve cryptosystems. Solinas’ original paper showed three unsolved problems on the enhancement of JSF. Whereas two of them have been solved, the other still remains to be done. The remaining unsolved problem is as follows: To design a representation of a pair of integers using a larger digit set such as a set involving ±3, while the original JSF utilizes the digit set that consists of 0, ±1 for representing a pair of integers. This paper puts an end to the problem; width-3 JSF. The proposed enhancement satisfies properties that are similar to that of the original. For example, the enhanced representation is defined as a representation that satisfies some rules. Some other properties are the existence, the uniqueness of such a representation, and the optimality of the Hamming weight. The non-zero density of the width-3 JSF is 563/1574(=0.3577) and this is ideal. The conversion algorithm to the enhanced representation takes O(logn) memory and O(n) computational cost, which is very efficient, where n stands for the bit length of the integers.

In the case of Barreto-Naehrig pairing-friendly curves of embedding degree 12 of order r, recent efficient Ate pairings such as R-ate, optimal, and Xate pairings achieve Miller loop lengths of (1/4) ⌊log2r⌋. On the other hand, the twisted Ate pairing requires (3/4) ⌊log2r⌋ loop iterations, and thus is usually slower than the recent efficient Ate pairings. This paper proposes an improved twisted Ate pairing using Frobenius maps and a small scalar multiplication. The proposal splits the Miller's algorithm calculation into several independent parts, for which multi-pairing techniques apply efficiently. The maximum number of loop iterations in Miller's algorithm for the proposed twisted Ate pairing is equal to the (1/4) ⌊log2r⌋ attained by the most efficient Ate pairings.

A lot of improvements and optimizations for the hardware implementation of SubBytes of Rijndael, in detail inversion in F28 have been reported. Instead of the Rijndael original F28, it is known that its isomorphic tower field F((22)2)2 has a more efficient inversion. For the towerings, several kinds of bases such as polynomial and normal bases can be used in mixture. Different from the meaning of this mixture of bases, this paper proposes another mixture that contributes to the reduction of the critical path delay of SubBytes. To the F(22)2-inversion architecture, for example, the proposed mixture inputs and outputs elements represented with normal and polynomial bases, respectively.

Let $q$ and $f(x)$ be an odd characteristic and an irreducible polynomial of degree $m$ over $•F{q}{}$, respectively. Then, suppose that $F(x)=x^mf(x+x^{-1})$ is irreducible over $•F{q}{}$. This paper shows that the conjugate zeros of $F(x)$ with respect to $•F{q}{}$ form a normal basis in $•F{q}{2m}$ if and only if those of $f(x)$ form a normal basis in $•F{q}{m}$ and the partial conjugates given as follows are linearly independent over $•F{q}{}$, •begin{equation} •{•gamma-•gamma^{-1},(•gamma-•gamma^{-1})^q, •cdots ,(•gamma-•gamma^{-1})^{q^{m-1}}•}, •end{equation} where $•gamma$ is a zero of $F(x)$ and thus a proper element in $•F{q}{2m}$. In addition, from the viewpoint of $q$--polynomial, this paper proposes an efficient method for checking whether or not the conjugate zeros of $F(x)$ satisfy the condition.

This paper shows an improvement of Miller's algorithm so as to be efficient for thread programming by using divisor theorem. Then, this paper implements a thread program of the improved Miller's algorithm by which it is shown that the proposed technique is more efficient than ordinary Miller's algorithm.

This paper proposes an efficient implementation of Ate pairing on twisted elliptic curve. Suppose that a pairing-friendly elliptic curve E has a twisted elliptic curve E' of degree d, and let psid be an isomorphic map from E'(Fpc) to the corresponding subgroup of E(Fpk). Then,consider G'1= psid -1(G1) and G'2 = psid -1(G2) for G1,G2 at Ate pairing alpha. Let P isin G1, Q isin ,G2, P' isin G'1 and Q' isin G'2, the authors have shown alpha(Q, P) = ft-1,Q(P) (pK -1)/r = ft-1,Q'(P') (pK -1)/r .This paper shows that this new Ate pairing, namely cross twisted (Xt) Ate pairing, provides an quite efficient implementation.

This paper proposes a method for generating an irreducible polynomial of an arbitrary degree m over an arbitrary prime field Fp such that p > m. The proposed method is closely related to the minimal polynomial determination and therefore it has the following features: its complexity has little dependency on the size of characteristic p, its calculation cost is explicitly given with degree m, and it can generate primitive polynomials when pm - 1 is factorized as the product of prime numbers. The restriction p > m comes from using Newtonpsilas formula.

This paper first introduces cyclic vector multiplication algorithm (CVMA) that is a multiplication algorithm in extension field. Then, it is also introduced that CVMA is useful under the tight restrictions of pairing-based cryptographies. Then, this paper points out a problem about the calculation cost of CVMA. For this problem, this paper proposes an improvement. According to some simulation results, it is shown that the improvement makes CVMA much more efficient.

This paper proposes an improvement of twisted-Ate pairing with Barreto-Naehrig curve so as to efficiently use Frobenius mapping with respect to prime field. Then, this paper shows some simulation results by which it is shown that the improvement accelerates twisted-Ate pairing.

In implementing an efficient pairing calculation, it is saidthat the lower bound of the number of iterations of Miller'salgorithm is log2r/φ(k),where φ(·) is the Euler's function. Ate pairingreduced the number of the loops of Miller's algorithm of Tatepairing from $\lfloor\log_2r\rfloor$ to $\lfloor\log_2(t-1)\rfloor$. Recently, it is known to systematicallyprepare a pairing---friendly elliptic curve whose parameters aregiven by a polynomial of integer variable "Χ". For thecurve, this paper gives integer variable Χ---basedAte pairing that achieves the lower bound byreducing it to $\lfloor\log_2\chi\rfloor$.

This paper considers a new skew Frobenius endomorphism with pairing---friendly elliptic curve $E(\mathbb{F}{p}{})$ defined over prime field $\mathbb{F}{p}{}$. Then, using the new skew Frobenius map, an efficient scalar multiplication method for pairing---friendly elliptic curve $E(\mathbb{F}{p}{})$ is shown. According to the simulation result, a scalar multiplication by the proposed method with multi---exponentiation technique is about 40% faster than that by plain binary method.

Self-dual normal basis is efficient for the arithmetic operations in extension field and especially trace calculation. However, self-dual normal bases do not exist in Fpm when characteristic p is odd and degree m is even. This paper proposes a method to construct a normal basis of even degree that is efficient for trace calculation.

A square root (SQRT) algorithm in GF(pm) (m = r0r1⋯rn−−1 2d, ri: odd prime, d > 0: integer) is proposed in this paper. First, the Tonelli-Shanks algorithm is modified to compute the inverse SQRT in $GF(p^{2^d})$, where most of the computations are performed in the corresponding subfields $GF{(p^{2^{i}})}$ for 0 ≤i ≤d–1. Then the Frobenius mappings with an addition chain are adopted for the proposed SQRT algorithm, in which a lot of computations in a given extension field GF(pm) are also reduce to those in a proper subfield by the norm computations. Those reductions of the field degree increase efficiency in the SQRT implementation. More specifically the Tonelli-Shanks algorithm and the proposed algorithm in GF(p22), GF(p44) and GF(p88) were implemented on a Pentium4 (2.6 GHz) computer using the C++ programming language. The computer simulations showed that, on average, the proposed algorithm accelerates the SQRT computation by 25 times in GF(p22), by 45 times in GF(p44), and by 70 times in GF(p88), compared to the Tonelli-Shanks algorithm, which is supported by the evaluation of the number of computations.

In this paper, we first introduce a shift product-based polynomial transformation. Then, we show that the parities of (#E – 1)/2 and (#E′ – 1)/2 are reciprocal to each other, where #E and #E′ are the orders of the two candidate curves obtained at the last step of CM method algorithm. Based on this property, we propose a method to check the parity by using the shift product-based polynomial transformation. For a 160-bits prime number as the characteristic, the proposed method carries out the parity check about 20 times faster than the conventional method when 4 divides the characteristic minus 1.