Scalar multiplication over higher degree rational point groups is often regarded as the bottleneck for faster pairing based cryptography. This paper has presented a skew Frobenius mapping technique in the sub-field isomorphic sextic twisted curve of Kachisa-Schaefer-Scott (KSS) pairing friendly curve of embedding degree 18 in the context of Ate based pairing. Utilizing the skew Frobenius map along with multi-scalar multiplication procedure, an efficient scalar multiplication method for KSS curve is proposed in the paper. In addition to the theoretic proposal, this paper has also presented a comparative simulation of the proposed approach with plain binary method, sliding window method and non-adjacent form (NAF) for scalar multiplication. The simulation shows that the proposed method is about 60 times faster than plain implementation of other compared methods.

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) ⌊log2 r⌋. On the other hand, the twisted Ate pairing requires (3/4) ⌊log2 r⌋ 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 proposed idea 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) ⌊log2 r ⌋ attained by the most efficient Ate pairings.

For ID-based cryptography, not only pairing but also scalar multiplication must be efficiently computable. In this paper, we propose a scalar multiplication method on the circumstances that we work at Ate pairing with Barreto-Naehrig (BN) curve. Note that the parameters of BN curve are given by a certain integer, namely mother parameter. Adhering the authors' previous policy that we execute scalar multiplication on subfield-twisted curve (Fp2) instead of doing on the original curve E(Fp12), we at first show sextic twisted subfield Frobenius mapping (ST-SFM) in (Fp2). On BN curves, note is identified with the scalar multiplication by p. However a scalar is always smaller than the order r of BN curve for Ate pairing, so ST-SFM does not directly applicable to the above circumstances. We then exploit the expressions of the curve order r and the characteristic p by the mother parameter to derive some radices such that they are expressed as a polynomial of p. Thus, a scalar multiplication [s] can be written by the series of ST-SFMs . In combination with the binary method or multi-exponentiation technique, this paper shows that the proposed method runs about twice or more faster than plain binary method.

Scalar multiplication methods using the Frobenius maps are known for efficient methods to speed up (hyper)elliptic curve cryptosystems. However, those methods are not efficient for the cryptosystems constructed on fields of small extension degrees due to costs of the field operations. Iijima et al. showed that one can use certain automorphisms on the quadratic twists of elliptic curves for fast scalar multiplications without the drawback of the Frobenius maps. This paper shows an extension of the automorphisms on the Jacobians of hyperelliptic curves of arbitrary genus.

In many cryptographic applications, a large-order finite field is used as a definition field, and accordingly, many researches on a fast implementation of such a large-order extension field are reported. This paper proposes a definition field Fpm with its characteristic p a pseudo Mersenne number, the modular polynomial f(x) an irreducible all-one polynomial (AOP), and using a suitable basis. In this paper, we refer to this extension field as an all-one polynomial field (AOPF) and to its basis as pseudo polynomial basis (PPB). Among basic arithmetic operations in AOPF, a multiplication between non-zero elements and an inversion of a non-zero element are especially time-consuming. As a fast realization of the former, we propose cyclic vector multiplication algorithm (CVMA), which can be used for possible extension degree m and exploit a symmetric structure of multiplicands in order to reduce the number of operations. Accordingly, CVMA attains a 50% reduction of the number of scalar multiplications as compared to the usually adopted vector multiplication procedure. For fast realization of inversion, we use the Itoh-Tsujii algorithm (ITA) accompanied with Frobenius mapping (FM). Since this paper adopts the PPB, FM can be performed without any calculations. In addition to this feature, ITA over AOPF can be composed with self reciprocal vectors, and by using CVMA this fact can also save computation cost for inversion.

A fast method for computing a multiple mP for a point P on elliptic curves is proposed. This new method is based on optimal addition sequences and the Frobenius map. The new method can be effectively applied to elliptic curves E(Fqn), where q is a prime power of medium size (e.g., q 128). When we compute mP over curves E(Fqn) with qn of nearly 160-bits and 11 q 128, the new method requires less elliptic curve additions than previously proposed methods. In this case, the average number of elliptic curve additions ranges from 40 to 50.

A new elliptic curve scalar multiplication algorithm is proposed. The algorithm offers about twice the throughput of some conventional OEF-base algorithms because it combines the Frobenius map with the table reference method based on base-φ expansion. Furthermore, since this algorithm suits conventional computational units such as 16, 32 and 64 bits, its base field Fpm is expected to enhance elliptic curve operation efficiency more than Fq (q is a prime) or F2n.