Elliptic curve with Optimal mixed Montgomery-Edwards model for low-end devices

Zhe Liu, Zhi Hu, Wei Wu

Abstract

This paper introduces a special family of twisted Edwards curve named Optimal mixed Montgomery-Edwards (OME) curves. The OME curve is proposed by exploiting the fact that every twisted Edwards curve is birationally equivalent to some elliptic curve in Montgomery form. The OME curves achieve optimal group arithmetic for both of twisted Edwards model and Montgomery model. In particular, the Montgomery model of OME curves only requires 3M + 2S and 1M + 3S + 3C to perform the point addition and point doubling operations, while 7M and 3M + 4S are needed for executing a point addition and point doubling for the twisted Edwards model of them. We also make effort to carefully choose the curve parameters and the underlying implementation field to achieve high performance. An example of OME curve is $$\mathcal{E}/\mathbb{F}_p : - x^2 + y^2 = 1 - 2782^2 \cdot x^2 y^2$$ over p = 2192 − 264 − 1. Our implementation results on the widely used 8-bit micro-controller platforms (i.e., AVR Atmega128) further demonstrate and highlight the practical benefits of proposed OME curve on low-end device. In particular, our implementation, performed in constant-time, reduces the execution time by up to 14% and 18% for fixed point and random point scalar multiplication, respectively, when comparing with the state-of-the-art implementation on the identical platform.
BibTeX
@article{liu2015elliptic,
  author = {Zhe Liu and Zhi Hu and Wei Wu},
  title = {{Elliptic curve with Optimal mixed Montgomery-Edwards model for low-end devices}},
  journal = {Science China Information Sciences},
  year = {2015},
  url = {https://openreview.net/forum?id=qMBoQY0Er2},
}

Loading related content...

Figure