CryptoDB
Koblitz Curves over Quadratic Fields
Authors: | |
---|---|
Download: | |
Abstract: | 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 $${\mathbb {F}}_4$$ 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 $${\mathbb {F}}_4$$ 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 $${\mathbb {F}}_{4^{m}},$$ 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. |
BibTeX
@article{jofc-2019-30137, title={Koblitz Curves over Quadratic Fields}, journal={Journal of Cryptology}, publisher={Springer}, volume={32}, pages={867-894}, doi={10.1007/s00145-018-9294-z}, author={Thomaz Oliveira and Julio López and Daniel Cervantes-Vázquez and Francisco Rodríguez-Henríquez}, year=2019 }