Cryptology ePrint Archive: Report 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.

Category / Keywords: implementation /

Date: received 21 May 2017, last revised 14 Jul 2017

Contact author: mike scott at miracl com

Available format(s): PDF | BibTeX Citation

Note: New reference

Version: 20170714:092255 (All versions of this report)

Short URL: ia.cr/2017/437

Discussion forum: Show discussion | Start new discussion