Multi-exponentiation algorithm based on binary GCD computation and its application to side-channel countermeasure

• Main Authors: Yen, Sung-Ming, Chen, Chien-Ning, Moon, SangJae
• Other Authors: Temasek Laboratories
• Format: Article
• Language: English
• Published: 2014
• Subjects: DRNTU::Science::Mathematics::Discrete mathematics::Algorithms
• Online Access: https://hdl.handle.net/10356/100160; http://hdl.handle.net/10220/24096
• Institution: Nanyang Technological University

A series of algorithms for evaluation of multi-exponentiation are proposed based on the binary greatest common divisor algorithm. The proposed algorithms are inversion free and have the capability to evaluate double or multi-exponentiation with non-fixed base numbers and exponents. They can also be employed in developing side-channel countermeasures. For n-bit double and triple exponentiation, they achieve the average complexity of 1.53n and 1.75n multiplications (including squarings), respectively. The proposed algorithms can be very useful for the implementation of many public-key cryptosystems on small devices with limited memory space, e.g., smart cards.