Discrete Logarithms for Torsion Points on Elliptic Curve of Embedding Degree 1

摘要

Recent efficient pairings such as Ate pairing use two efficient subgroups of rational point such that π(P) = P and π(Q) = [p]Q, where π, 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(π) becomes irreducible over F_r for which π 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.