Paper 2010/311

Combining leak--resistant arithmetic for elliptic curves defined over \Fp and RNS representation

J. C. Bajard, S. Duquesne, and M. Ercegovac

Abstract

In this paper we combine the residue number system (RNS) representation and the leak-resistant arithmetic on elliptic curves. These two techniques are relevant for implementation of elliptic curve cryptography on embedded devices.\ % since they have leak-resistance properties. It is well known that the RNS multiplication is very efficient whereas the reduction step is costly. Hence, we optimize formulae for basic operations arising in leak-resistant arithmetic on elliptic curves (unified addition, Montgomery ladder) in order to minimize the number of modular reductions. We also improve the complexity of the RNS modular reduction step. As a result, we show how to obtain a competitive secured implementation. Finally, %we recall the main advantages of the RNS representation, %especially in hardware and for embedded devices, and we show that, contrary to other approaches, ours takes optimally the advantage of a dedicated parallel architecture.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
ellicptic curvesleak resistanceRNSarithmetic
Contact author(s)
sylvain duquesne @ univ-rennes1 fr
History
2010-05-25: received
Short URL
https://ia.cr/2010/311
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/311,
      author = {J. C.  Bajard and S.  Duquesne and M.  Ercegovac},
      title = {Combining leak--resistant arithmetic for elliptic curves defined over $\F_p$ and {RNS} representation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/311},
      year = {2010},
      url = {https://eprint.iacr.org/2010/311}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.