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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.