Author :
Vercauteren, Frederik
Author_Institution :
Flanders Dept. of Electr. Eng., Univ. of Leuven, Leuven-Heverlee, Belgium
Abstract :
In this paper, we introduce the concept of an optimal pairing, which by definition can be computed using only log 2 r/¿(k) basic Miller iterations, with r the order of the groups involved and k the embedding degree. We describe an algorithm to construct optimal ate pairings on all parametrized families of pairing friendly elliptic curves. Finally, we conjecture that any nondegenerate pairing on an elliptic curve without efficiently computable endomorphisms different from powers of Frobenius requires at least log 2 r/¿(k) basic Miller iterations.
Keywords :
iterative methods; public key cryptography; Frobenius power; Miller iterations; ate pairings; elliptic curves; embedding degree; nondegenerate pairing; optimal pairings; parametrized families; Elliptic curve cryptography; Elliptic curves; Embedded computing; Jacobian matrices; Ate pairing; Tate pairing; elliptic curves; pairing-based cryptography;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2009.2034881
