To ensure secure communication between two parties (Alice and Bob), Public Key Agreement (PKA) algorithms play a crucial role. The Diffie-Hellman (D-H) algorithm, introduced by W. Diffie and M. Hellman in 1976, is the most well-known PKA algorithm, based on exponentiation over a finite field. Over time, various PKA algorithms have been developed based on this original idea—these are referred to as D-H realizations or D-H algorithms. A common issue with D-H realizations is their computational inefficiency, particularly in environments with resource-constrained devices. This inefficiency arises from the high computational complexity of generating public and secret shared keys (SSKs), often resulting in communication delays. In this paper, we propose a modified D-H protocol designed to reduce the computational time required by one party, thereby decreasing the total time needed to establish the SSK in asymmetric environments where Alice and Bob have different computational capabilities. The core of this approach leverages the group homomorphism property of the underlying function to enable parallelization and reduce the complexity of Alice’s computations, together with an asymmetric key agreement structure in which both parties may follow distinct computational rules for public key and SSK generation. We demonstrate that the proposed protocol retains the security properties of the original D-H realizations, preserving the hardness of the discrete logarithm (DL), computational Diffie-Hellman (CDH), and decisional Diffie-Hellman (DDH) problems under an asymmetric setting. We also discuss its applicability to other cryptographic protocols. Experimental results show that the modified protocol significantly improves computational efficiency, particularly by reducing Alice's computational burden through parallel processing.
Koki Jimbo (Mon,) studied this question.