Pairing-friendly elliptic curves of prime order
Michael Naehrig ( Lehrstuhl für Theoretische Informationstechnik - RWTH-Aachen University )
Thursday, January, 12th, 2006, 1415, b-it 1.25 (cosec meeting room)
Contents
A non-supersingular elliptic curve over $\F_p$ is called pairing-friendly if it contains a subgroup of order $r$ whose embedding degree $k$ is not too large, which means that computations in the field $\F_{p^k}$ are feasible. The optimal case occurs when the entire curve has prime order and the desired embedding degree. Pairing-friendly curves of prime or near-prime order are essential in certain pairing-based schemes like short signatures.
Previously known techniques to construct such curves are restricted to embedding degree $k \leq 6$. More general methods produce curves over $\F_p$ where the bit length of $p$ is often twice as large as that of the order $r$ of the subgroup with embedding degree $k$. The best published results achieve $\rho = \log(p)/\log(r) \sim 5/4$. During this talk I will introduce a method to construct elliptic curves of prime order and embedding degree $k = 12$.
The new curves lead to very efficient implementation: non-pairing operations need no more than $\F_{p4}$ arithmetic, and pairing values can be compressed to one third of their length in a way compatible with point reduction techniques. (Talk)