Paper 2017/437
Slothful reduction
Michael Scott
Abstract
In the implementation of many public key schemes, there is a need to implement modular arithmetic. Typically this consists of addition, subtraction, multiplication and (occasionally) division with respect to a prime modulus. To resist certain side-channel attacks it helps if implementations are ``constant time''. As the calculations proceed there is potentially a need to reduce the result of an operation to its remainder modulo the prime modulus. However often this reduction can be delayed, a process known as ``lazy reduction''. The idea is that results do not have to be fully reduced at each step, that full reduction takes place only occasionally, hence providing a performance benefit. Here we extend the idea to determine the circumstances under which reduction can be delayed to the very end of a particular public key operation.
Note: New reference
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint. MINOR revision.
- Contact author(s)
- mike scott @ miracl com
- History
- 2018-10-11: last of 8 revisions
- 2017-05-22: received
- See all versions
- Short URL
- https://ia.cr/2017/437
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/437, author = {Michael Scott}, title = {Slothful reduction}, howpublished = {Cryptology ePrint Archive, Paper 2017/437}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/437}}, url = {https://eprint.iacr.org/2017/437} }