Biblio

Pairing is carried out by two steps, Miller loop and final exponentiation. In this manuscript, the authors propose an efficient Miller loop for a pairing on the FK12 curve. A Hamming weight and bit-length of loop parameter have a great effect on the computational cost of Miller loop. Optimal-ate pairing is used as the most efficient pairing on the FK12 curve currently. The loop parameter of optimal-ate pairing is 6z+2 where z is the integer to make the FK12 curve parameter. Our method uses z which has a shorter bit-length than the previous optimal-ate pairing as the loop parameter. Usually, z has a low Hamming weight to make final exponentiation efficient. Therefore, the loop parameter in our method has a lower Hamming weight than the loop parameter of the previous one in many cases. The authors evaluate our method by the number of multiplications and execution time. As a result, the proposed algorithm leads to the 3.71% reduction in the number of multiplications and the 3.38% reduction in the execution time.

Pairings on elliptic curves are used for innovative protocols such as ID-based encryption and zk-SNARKs. To make the pairings secure, it is important to consider the STNFS which is the special number field sieve algorithm for discrete logarithms in the finite field. The Fotiadis-Konstantinou curve with embedding degree 12(FK12), is known as one of the STNFS secure curves. To an efficient pairing on the FK12 curve, there are several previous works that focus on final exponentiation. The one is based on lattice-based method to decompose the hard part of final exponentiation and addition chain. However, there is a possibility to construct a more efficient calculation algorithm by using the relations appeared in the decomposition calculation algorithm than that of the previous work. In this manuscript, the authors propose a relation of the decomposition and verify the effectiveness of the proposed method from the execution time.

Pairings on elliptic curves are exploited for pairing-based cryptography, e.g., ID-based encryption and group signature authentication. For secure cryptography, it is important to choose the curves that have resistance to a special variant of the tower number field sieve (TNFS) that is an attack for the finite fields. However, for the pairings on several curves with embedding degree \$k=\10,11,13,14\\$ resistant to the special TNFS, efficient algorithms for computing the final exponentiation constructed by the lattice-based method have not been provided. For these curves, the authors present efficient algorithms with the calculation costs in this manuscript.

Pairings on elliptic curves which are carried out by the Miller loop and final exponentiation are used for innovative protocols such as ID-based encryption and group signature authentication. As the recent progress of attacks for finite fields in which pairings are defined, the importance of the use of the curves with prime embedding degrees \$k\$ has been increased. In this manuscript, the authors provide a method for providing efficient final exponentiation algorithms for a specific cyclotomic family of curves with arbitrary prime \$k\$ of \$k\textbackslashtextbackslashequiv 1(\textbackslashtextbackslashtextmod\textbackslashtextbackslash 6)\$. Applying the proposed method for several curves such as \$k=7\$, 13, and 19, it is found that the proposed method gives rise to the same algorithms as the previous state-of-the-art ones by the lattice-based method.