Koblitz Curves over Quadratic Fields

In this work, we retake an old idea that Koblitz presented in his landmark paper (Koblitz, in: Proceedings of CRYPTO 1991. LNCS, vol 576, Springer, Berlin, pp 279–287, 1991 ), where he suggested the possibility of defining anomalous elliptic curves over the base field F 4 . We present a careful impl...

Full description

Saved in:
Bibliographic Details
Published in:Journal of cryptology 2019-07, Vol.32 (3), p.867-894
Main Authors: Oliveira, Thomaz, López, Julio, Cervantes-Vázquez, Daniel, Rodríguez-Henríquez, Francisco
Format: Article
Language:English
Subjects:
Coding and Information Theory
Combinatorics
Communications Engineering
Computation
Computational Mathematics and Numerical Analysis
Computer Science
Curves
Fields (mathematics)
Microprocessors
Multiplication
Networks
Number theory
Probability Theory and Stochastic Processes
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this work, we retake an old idea that Koblitz presented in his landmark paper (Koblitz, in: Proceedings of CRYPTO 1991. LNCS, vol 576, Springer, Berlin, pp 279–287, 1991 ), where he suggested the possibility of defining anomalous elliptic curves over the base field F 4 . We present a careful implementation of the base and quadratic field arithmetic required for computing the scalar multiplication operation in such curves. We also introduce two ordinary Koblitz-like elliptic curves defined over F 4 that are equipped with efficient endomorphisms. To the best of our knowledge, these endomorphisms have not been reported before. In order to achieve a fast reduction procedure, we adopted a redundant trinomial strategy that embeds elements of the field F 4 m , with m a prime number, into a ring of higher order defined by an almost irreducible trinomial. We also suggest a number of techniques that allow us to take full advantage of the native vector instructions of high-end microprocessors. Our software library achieves the fastest timings reported for the computation of the timing-protected scalar multiplication on Koblitz curves, and competitive timings with respect to the speed records established recently in the computation of the scalar multiplication over binary and prime fields.
ISSN:0933-2790
1432-1378
DOI:10.1007/s00145-018-9294-z