Journal of Computer Science

A Review on Heuristics for Addition Chain Problem: Towards Efficient Public Key Cryptosystems

Adamu Muhammad Noma, Abdullah Muhammed, Mohamad Afendee Mohamed and Zuriati Ahmad Zulkarnain

DOI : 10.3844/jcssp.2017.275.289

Journal of Computer Science

Volume 13, Issue 8

Pages 275-289

Abstract

Field exponentiation and scalar multiplication are the pillars of and the most computationally expensive operations in the public key cryptosystems. Optimizing the operation is the key to the efficiency of the systems. Analogous to the optimization is solving addition chain problem. In this study, we survey from the onset of the addition chain problem to the state-of-the-art heuristics for optimizing it, with the view to identifying fundamental issues that when addressed renders the heuristics most optimal mean of minimizing the two operations in various public key cryptosystems. Thus, our emphasis is specifically on the heuristics: Their various constraints and implementations efficiencies. We present possible ways forwards toward the optimal solution for the addition chain problem that can be efficiently applied for optimal implementation of the public key cryptosystems.

Copyright

© 2017 Adamu Muhammad Noma, Abdullah Muhammed, Mohamad Afendee Mohamed and Zuriati Ahmad Zulkarnain. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.