Welcome to the resource topic for 2012/140
Title:
Highly-Parallel Montgomery Multiplication for Multi-core General-Purpose Microprocessors
Authors: Selcuk Baktir, Erkay Savas
Abstract:Popular public key algorithms such as RSA and Diffie-Hellman key exchange, and more advanced cryptographic schemes such as Paillier’s and Damgård-Jurik’s algorithms (with applications in private information retrieval), require efficient modular multiplication with large integers of size at least 1024 bits. Montgomery multiplication algorithm has proven successful for modular multiplication of large integers. While general purpose multi-core processors have become the mainstream on desktop as well as portable computers, utilization of their computing resources have been largely overlooked when it comes to performing computationally intensive cryptographic operations. In this work, we propose a new parallel Montgomery multiplication algorithm which exhibits up to 39% better performance than the known best serial Montgomery multiplication variant for the bit-lengths of 2048 or larger. Furthermore, for bit-lengths of 4096 or larger, the proposed algorithm exhibits better performance utilizing multiple cores available. It achieves speedups of up to 81%, 3.37 times and 4.87 times for the used general-purpose microprocessors with 2, 4 and 6 cores, respectively. To our knowledge, this is the first work that shows with actual implementation results that Montgomery multiplication can be practically parallelized on general-purpose multi-core processors.
ePrint: https://eprint.iacr.org/2012/140
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .